btree insert( key, t )
typekey key;
btree t;

{
typekey ins;
extern btree NewTree;
typekey InternalInsert();
    ins = InternalInsert( key, t );
    /*** check for growth at the root ***/
    if ( ins != NoKey ) return( NewNode( ins, t, NewTree) );
    return( t );
};

   typekey InternalInsert( key, t )
   typekey key;
   btree t;
   {int i, j;
   typekey ins;
   btree tempr;
   extern btree NewTree;
   if ( t == NULL ) {   /*** the bottom of the tree has been reached:
                             indicate insertion to be done ***/
        NewTree = NULL;
        return( key );
        }
   else {
       for ( i=0; i<t->d && key>t->k[i]; i++ );
       if ( i<t->d && key == t->k[i] )
           Error; /*** Key already in table ***/
       else {
        ins = InternalInsert( key, t->p[i] );
        if ( ins != NoKey )
        /*** the key in "ins" has to be inserted in present node ***/
            if (t->d < 2*M) InsInNode( t, ins, NewTree );
            else    /*** present node has to be split ***/
               {/*** create new node ***/
               if ( i<=M ) {
                  tempr = NewNode( t->k[2*M-1], NULL, t->p[2*M] );
                  t->d--;
                  InsInNode( t, ins, NewTree );
                  }
               else tempr = NewNode( ins, NULL, NewTree );
               /*** move keys and pointers ***/
               for ( j=M+2; j<=2*M; j++ )
                   InsInNode( tempr, t->k[j-1], t->p[j] );
               t->d = M;
               tempr->p[0] = t->p[M+1];
               NewTree = tempr;
               return( t->k[M] );
               }
        }
    return( NoKey );
    }
   };