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

	
	for(j=q->keynum+1;j>i+1;j--)    //結(jié)點(diǎn)中除關(guān)鍵字?jǐn)?shù)目外，其它信息往后移一個(gè)位置
	{
		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;    //插入關(guān)鍵字
	q->recptr[i+1]=r;   //插入記錄
	q->ptr[i+1]=ap;     //插入子樹(shù)
	
	
	
	
	if(ap!=NULL)
	ap->parent=q;     //鏈接雙親
	q->keynum+=1;      //關(guān)鍵字?jǐn)?shù)目加1
}   //Insert



void Split(BTree &q,int l,BTree &ap)
{//將q分裂，生成新結(jié)點(diǎn)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)的新結(jié)點(diǎn)T,原T和ap為子樹(shù)指針
	
	
	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是由查找函數(shù)SearchBTree返回的信息所得
	//在m階B-樹(shù)T上結(jié)點(diǎn)q的key[i]和key[i+1]之間插入關(guān)鍵字k.
	//若引起結(jié)點(diǎn)過(guò)大，則沿雙親鏈進(jìn)行必要的結(jié)點(diǎn)分裂調(diào)整，使T仍是m階B-樹(shù)。
	//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]移入新結(jié)點(diǎn)*ap
			
			q=q->parent;
			if(q)
				i=Search(q,x);
		}//else
	}//while
	if(!finished)   //T是空樹(shù)（參數(shù)q初值為NULL）或者根結(jié)點(diǎn)已分裂為結(jié)點(diǎn)q和ap
		NewRoot(T,q,x,r,ap);
	return OK;
}//InsertBTree