B-树的插入

[c]代码库

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