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 为子树指针*/ |
} |