insert.h

一个B-树实现与编辑

void Insert(BTree &q,int i,int x,Record *r,BTree &ap)//将x插入地点q的第i+1位置
{
	int j;

	
	for(j=q->keynum+1;j>i+1;j--)    //结点中除关键字数目外，其它信息往后移一个位置
	{
		q->key[j]=q->key[j-1];
		q->recptr[j]=q->recptr[j-1];
		q->ptr[j]=q->ptr[j-1];
	}
	q->key[i+1]=x;    //插入关键字
	q->recptr[i+1]=r;   //插入记录
	q->ptr[i+1]=ap;     //插入子树
	
	
	
	
	if(ap!=NULL)
	ap->parent=q;     //链接双亲
	q->keynum+=1;      //关键字数目加1
}   //Insert



void Split(BTree &q,int l,BTree &ap)
{//将q分裂，生成新结点ap
	ap=new BTNode;
	for(int j=0;j<=m;j++)
	{
		
		ap->ptr[j]=NULL;
	}
	for(int j=1;j<m;j++)
		ap->recptr[j]=NULL;

	for(int j=m;j>=l;j--)
	{
		ap->ptr[j-l]=q->ptr[j];
		
		if(q->ptr[j]!=NULL)q->ptr[j]->parent=ap;q->ptr[j]=NULL;
	}
	for(int j=m;j>=l+1;j--)
	{
		ap->key[j-l]=q->key[j];
		q->key[j]=0;
		ap->recptr[j-l]=q->recptr[j];
		q->recptr[j]=NULL;
	}
	q->key[l]=0;
	q->recptr[l]=NULL;
	ap->keynum=m-l;
	q->keynum=l-1;
	
}//Split

void NewRoot(BTree &T,BTree q,int x,Record *r,BTree &ap)
{
	//生成含信息(T,x,ap)的新结点T,原T和ap为子树指针
	
	
	q=new BTNode;
	q->parent=NULL;
	q->keynum=1;
	q->ptr[0]=T;
	q->ptr[1]=ap;
	q->key[1]=x;
	q->recptr[1]=r;
	for(int j=2;j<=m;j++)
	{
		q->recptr[j]=NULL;
		q->ptr[j]=NULL;
	}
	
	
	
	if(ap!=NULL&&T!=NULL)
	{
		ap->parent=q;
		T->parent=q;
	}
	T=q;
	
}

Status InsertBTree(BTree &T,int x,Record *r,BTree q,int i)
{//q和i是由查找函数SearchBTree返回的信息所得
	//在m阶B-树T上结点q的key[i]和key[i+1]之间插入关键字k.
	//若引起结点过大，则沿双亲链进行必要的结点分裂调整，使T仍是m阶B-树。
	//Record *x=r;
	BTree ap=NULL;
	bool finished=FALSE;
	while(q&&!finished)
	{
		Insert(q,i,x,r,ap);//将x和ap分别插入到q->key[i+1]和q->ptr[i+1]
		if(q->keynum<m)finished=TRUE;//插入完成
		else
		{
			x=q->key[s];
			r=q->recptr[s];
			ap=NULL;
			Split(q,s,ap);  //将q->key[s...m],q->recptr[s...m],q->ptr[s...j]移入新结点*ap
			
			q=q->parent;
			if(q)
				i=Search(q,x);
		}//else
	}//while
	if(!finished)   //T是空树（参数q初值为NULL）或者根结点已分裂为结点q和ap
		NewRoot(T,q,x,r,ap);
	return OK;
}//InsertBTree