int InserBTree ( NodeType **t,KeyType kx,NodeType *q,int i )
{ /* 在m 阶B 树*t 上结点*q 的
key[i],key[i+1]之间插入关键码kx*/ /*若引起结点过大，则沿双亲链进行必要的结点分裂调整，使*t
仍为m 阶B 树*/
x=kx;
ap=NULL;
finished=FALSE;
while ( q&&!finished )
{
Insert ( q,i,x,ap ); /*将x 和ap 分别插入到q->key[i+1]和q->ptr[i+1]*/
if ( q->keynum<m ) finished=TRUE; /*插入完成*/
else
{ /*分裂结点*p*/
s=m/2;
split ( q,ap );
x=q->key[s];
/*将q->key[s+1…m],q->ptr[s…m]和q->recptr[s+1…m]移入新结点*ap*/
q=q->parent;
if ( q ) i=Search ( q,kx ); /*在双亲结点*q 中查找kx 的插入位置*/
}/*else*/
}/*while*/
if ( !finished ) /*(*t)是空树或根结点已分裂为*q*和ap*/
NewRoot ( t,q,x,ap ); /*生成含信息(t,x,ap)的新的根结点*t,原*t 和ap 为子树指针*/
}