btree.cpp

一个简单的b tree 实现代码

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <math.h>
#include <time.h>
#include "btree.hpp"
#include <string>
 
  using namespace std;
/*btree search(typekey, btree,int*); 
btree insert(typekey,btree); 
btree delete_n(typekey,btree); 
int height(btree); 
int count(btree); 
double payload(btree); 
btree deltree(btree); 

static void InternalInsert(typekey, btree); 
static void InsInNode(btree, int); 
static void SplitNode(btree, int); 
static btree NewRoot(btree); 

static void InternalDelete(typekey, btree); 
static void JoinNode(btree, int); 
static void MoveLeftNode(btree t, int); 
static void MoveRightNode(btree t, int); 
static void DelFromNode(btree t, int); 
int print_tree(btree t, int); 
static btree FreeRoot(btree); 

static btree delall(btree); 
static void Error(int,typekey); 
*/

//int btree_disp; /* 查找时找到的键在节点中的位置 */ 
//char * InsValue = NULL; /* 与要插的键相对应的值 */ 
//static int flag; /* 节点增减标志 */
//static int btree_level = 0; /* 多路树的高度 */
//static int btree_count = 0; /* 多路树的键总数 */
//static int node_sum = 0;  /* 多路树的节点总数 */
//static int level; /* 当前访问的节点所处的高度 */
//static btree NewTree; /* 在节点分割的时候指向新建的节点 */
//static typekey InsKey; /* 要插入的键 */

#ifdef key_string
  string null_string="";
#endif
tree::tree()
	{
		 btree_level = 0;
		 btree_count = 0;
		 node_sum = 0;  
		 root=(btree)malloc(sizeof(node));
			memset(root,0x0,sizeof(node));
		}
tree::~tree()
	{


		}

btree tree::search(typekey key, btree t,int *pos)
{
	int i,j,m;
	int l;
	l=btree_level;
	while (l >= 0){

	  /*	for(i=0, j=t->d-1; i<=j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m))
		{i=i;
		}    */
		if(l==0)
	  i=0;else i=1;
		for(;i<t->d ;i++)
		{
			if   (key <= t->k[i])break;
		}

		if (key == t->k [ i ])
		{
		   if(l>0)
		   {
			// i++;
		   }
			else
			{btree_disp = i;
			*pos=i;
			return t;}
		}
		else
	
		 if(l>0 && ( key != t->k [ i ]))
		 i--;
		t = t->p[ i ];
		l--;
	}
	return NULL;
}

btree tree::insert(typekey key, btree t,char* p_str)
{ 		btree temp=NULL,t1;
			t1=t;
	level=btree_level;

		temp=InternalInsert(key, t1,p_str,level);
	if (temp != NULL)  /* 根节点满之后，它被分割成两个半满节点 */
		t1=NewRoot(t,temp);    /* 树的高度增加 */
	  root=t1;
	return t1;
}

btree tree::InternalInsert(typekey key, btree t,char* p_str,int l)
{
	 btree temp=NULL,nt;
	  int i,j,m=0;

	   //检查 key  在 node 的位置
	  if(l==0)
	  i=0;else i=1;
		for(;i<t->d ;i++)
		{
			if   (key <t->k[i])break;

			if (key == t->k[ i]  ) {
				Error(1,key); /* 键已经在树中 */
				flag = 0;
				return NULL;
			}
		}

   if(l==0) //到达底部 是否存在子节点 存在则继续下一层
	{

			if (key == t->k[ i]  ) {
				Error(1,key); /* 键已经在树中 */
				flag = 0;
				return NULL;
			}

		  if(t->d<2*M)
				{
					//如果有空间存放新key,则insert 进node
					InsInLeafNode(key,p_str,t, i);

				}
		  else
			  {
			   //如果无空间则分裂节点,返回新节点指针
			   //返回的新节点temp 的K0 需要insert 到 父节点中
				temp=SplitLeafNode(key,p_str, NULL,t, i);
			  }

		}
	else
		{

				  if(l>0) i--;


				 temp=InternalInsert(key, t->p[i],  p_str,l-1);
				 if(t->k[i]!=t->p[i]->k[0] )//&& temp==NULL
				 t->k[i]=t->p[i]->k[0];
				 nt=temp;
					 if(temp!=NULL)
					 {
						//新增索引节点 若父节点有空间则insert 否则,分裂父节点
								if(t->d<=2*M)
								{
									InsInIndexNode( temp,t, i+1);
									temp=NULL;
								}
							 else
								{
									temp=SplitNode(temp->k[0],p_str,temp, t, i);

									   /*	 if (	nt->p[0]!=NULL)
										 { for(i=0;i<nt->d;i++)
											 {
												nt->k[i]=nt->k[i+1];
												nt->v[i]=nt->v[i+1];
													nt->p[i]=nt->p[i+1];
												}
											 nt->d--;
											 }
											*/
								}

						}
			}
	return temp;
}



/*
* 把一个键和对应的右子树插入一个节点中
*/
void tree::InsInLeafNode(typekey key,char *p_str ,btree t, int d)
{

	 int i;
	/* 把所有大于要插入的键值的键和对应的右子树右移 */
	for(i = t->d; i > d; i--){
		t->k[ i ] = t->k[i-1];
		t->v[ i ] = t->v[i-1];
		t->p[i+1] = t->p[ i ]=NULL;
	}
	/* 插入键和右子树 */

	t->k[ i ] = key;
		t->v[ i ]=p_str;
   //	t->v[ i ] =(char*)malloc(20);
   //	sprintf(t->v[ i ],"%s" ,p_str);

	t->p[ i ] = NULL;
	t->d++;
	t->min=t->k[0];
	}

void tree::InsInIndexNode(btree nt,btree t ,int d)
{
	int i;
	/* 把所有大于要插入的键值的键和对应的右子树右移 */
	for(i = t->d; i > d; i--)
	{
		t->k[ i ] = t->k[i-1];
		t->v[ i ] = t->v[i-1];
		t->p[i] = t->p[ i-1 ];
	}
	/* 插入键和右子树 */
	t->k[ d ] = nt->k[0];
	t->p[d] = nt;
	t->v[ d ] = NULL;
	t->d++;

	/* if (	nt->p[0]!=NULL)
	 { for(i=0;i<nt->d;i++)
	  {
		nt->k[i]=nt->k[i+1];
		nt->v[i]=nt->v[i+1];
		nt->p[i]=nt->p[i+1];

	  }
		  nt->d--;}
	  */

}


void tree::InsInNode(btree t, int d)
{
	int i;
	/* 把所有大于要插入的键值的键和对应的右子树右移 */
	for(i = t->d; i > d; i--){
		t->k[ i ] = t->k[i-1];
		t->v[ i ] = t->v[i-1];
		t->p[i+1] = t->p[ i ];
	}
	/* 插入键和右子树 */
	t->k[ i ] = InsKey;
	t->p[i+1] = NewTree;
	t->v[ i ] = InsValue;
	t->d++;
}

btree tree::SplitNode(typekey key, char *v,btree nt, btree t, int d )
{
	int i,j,k=0;
	btree temp;
	typekey temp_k;
	char *temp_v;
	/* 建立新节点 */
	temp = (btree)malloc(sizeof(node));
	memset( temp,0x0,    sizeof(node));
  /*
	 *   +---+--------+-----+-----+--------+-----+
	 *   | 0 | ...... |  M  | M+1 | ...... |2*M-1|
	 *   +---+--------+-----+-----+--------+-----+
	 *   |<-      M+1     ->|<-        M-1     ->|
	 */
	if (d > M) { /* 要插入当前节点的右半部分 */
		/* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,
		 * 并且为要插入的键值+子树空出位置 */


		 for(i=M+1,j=0;i<t->d;i++,j++)
		  {


		  if(t->k[i]>key && k==0)
			{k=1;
				temp->k[j]=key;
				//temp->v[j] =(char*)malloc(20);
				temp->p[j] = nt;
			   //	sprintf(temp->v[j],"%s" ,v);//,strlen(p_str));
				//free(v);
			}else if(i+1==t->d)
				{
				  temp->k[j+1]=key;
				 // temp->v[j+1] =(char*)malloc(20);
				 // sprintf(temp->v[j+1],"%s" ,v);//,strlen(p_str));
				  temp->p[j+1] = nt;
				  //free(v);
				}
				temp->k[j+k]=t->k[ i ];
			   //	temp->v[j+k] = t->v[ i ];
				temp->p[j+k] = t->p[i];
			   #ifdef key_string
			   string s(NULL);
				t->k[ i ]=s;
			   #else
				t->k[ i ]=0;
			   #endif
				t->p[i]=NULL;


		  }



	

	}
	else { /* d <= M */
		/* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */
		for(i=M,j=0;i<t->d;i++,j++)
		{
			temp->k[j]=t->k[ i ];
		   //	temp->v[j] = t->v[ i ];
			temp->p[j] = t->p[i];
		  #ifdef key_string

				t->k[ i ]=null_string;
			   #else
				t->k[ i ]=0;
			   #endif
			t->p[i]=NULL;
		}
		//在原来的节点的d位置插入新节点
		for(i=M;i>=d;i--)
		{
			t->k[i+1]=t->k[i];
			t->p[i+1]=t->p[i];
		   //	t->v[i+1]=t->v[i];
		}

		t->k[d]=key;
	   //	t->v[ d ] =(char*)malloc(20);
		t->p[ d ] =nt;
	   //	sprintf(t->v[ d],"%s" ,v);//,strlen(p_str));
	   //	free(v);

	}
	t->d =M+1;
	temp->d = M+1;
	NewTree = temp;
	node_sum++;


	InsKey=  temp->k[0] ;
	// InsValue=  temp->v[0] ;
	// NewTree= temp->p[0] ;
	  pop_key=  temp->k[0];
	  temp->min= pop_key;

   /*	  for(i=0;i<temp->d;i++)
	  {
		temp->k[i]=temp->k[i+1];
		temp->v[i]=temp->v[i+1];
		temp->p[i]=temp->p[i+1];

	  }
	  temp->d--;
	  */


	return temp;
}


btree tree::SplitLeafNode(typekey key, char *v,btree nt, btree t, int d )
{
	int i,j,k=0;
	btree temp=NULL;
	typekey temp_k;
	char *temp_v;
	/* 建立新节点 */
	temp = (btree)malloc(sizeof(node));
	memset( temp,0x0,    sizeof(node));
  /*                     1     2              3
	 *   +---+--------+-----+-----+--------+-----+
	 *   | 0 | ...... |  M  | M+1 | ...... |2*M-1|
	 *   +---+--------+-----+-----+--------+-----+
	 *   |<-      M+1     ->|<-        M-1     ->|
	 */
	if (d > M) { /* 要插入当前节点的右半部分 */
		/* 把从 2*M-1 到 M+1 的 M-1 个键值+子树对转移到新节点中,
		 * 并且为要插入的键值+子树空出位置 */


		 for(i=M+1,j=0;i<t->d;i++,j++)
		  {


		  if(t->k[i]>key && k==0)
			{k=1;
				temp->k[j]=key;

			   //	temp->v[j] =(char*)malloc(20);
			   //	sprintf(temp->v[j],"%s" ,v);
			   temp->v[j]=v;
			}else if(i+1==t->d)
				{
				  temp->k[j+1]=key;
				  temp->v[j+1]=v;
				 // temp->v[j+1] =(char*)malloc(20);
				 // sprintf(temp->v[j+1],"%s" ,v);
				}
				temp->k[j+k]=t->k[ i ];
				temp->v[j+k] = t->v[ i ];
				temp->p[j+k] = t->p[i];
				#ifdef key_string
					t->k[ i ]=null_string;
				#else
				t->k[ i ]=0;
				#endif
				t->p[i]=NULL;


		  }







	}
	else { /* d <= M */
		/* 把从 2*M-1 到 M 的 M 个键值+子树对转移到新节点中 */

		//先将>=m的节点转移到新节点
		for(i=M,j=0;i<t->d;i++,j++)
		{
			temp->k[j]=t->k[ i ];
			temp->v[j] = t->v[ i ];
			temp->p[j] = t->p[i];
			#ifdef key_string
					t->k[ i ]=null_string;
				#else
				t->k[ i ]=0;
				#endif
			t->p[i]=NULL;
		}
		//在原来的节点的d位置插入新节点
		for(i=M;i>=d;i--)
		{
			t->k[i+1]=t->k[i];
			t->p[i+1]=t->p[i];
			t->v[i+1]=t->v[i];
		}

		t->k[d]=key;
		t->v[ d ]=v;
		//t->v[ d ] =(char*)malloc(20);
		t->p[ d ] =NULL;
	   //	sprintf(t->v[ d],"%s" ,v);

		}



	t->d =M+1;
	temp->d = M;
	t->min=t->k[0];
	temp->min=temp->k[0];
	NewTree = temp;
	node_sum++;
	pop_key=temp->k[0];
	return temp;
}



btree tree::delete_n(typekey key, btree t)
{
	level=btree_level;
	btree t1=NULL;
	InternalDelete1(key, t,level);
	if (t->d <= 1)
	/* 根节点的子节点合并导致根节点键的数目随之减少，
	 * 当根节点中没有键的时候，只有它的最左子树可能非空 */
		t=FreeRoot(t);
	   //	root=t;
	return t;
}

void tree::InternalDelete1(typekey key, btree t,int l)
 {  int i,j,m,l1;
	btree nr,nm,nl,t1=NULL;
	int lvl;


	if (l < 0)
	{
		Error(0,key); /* 在整个树中未找到要删除的键 */
		flag = 0;
		return;
	}

	 if(l==0)
	  i=0;else i=1;
		for(;i<t->d ;i++)
		{
			if   (key <t->k[i])break;
		}

		if(l>0)
		{	i--;
			InternalDelete1(key, t->p[ i ] ,l-1);


			 if(t->p[i]->d>0)
			 {
				 if(t->k[i]!=t->p[i]->k[0])
				  t->k[i]=t->p[i]->k[0] ;


					//判断是否需要合并叶子节点    l==1 &&
				if( t->p[i]->d<=M)
				{
					nm =t->p[i];
					if(i==0 && t->d>1)
					{
						nr=t->p[i+1];
						if (nm->d+nr->d<=2*M )
						{
						t1=MergeLeafNode(nm,nr,0,l);
						DelFromNode(t,i+1);
						free(nr);
						t->d--;
						}
						else if(l>1 &&nr->d==2*M+1 &&nm->d<M)
						{
						 t1=MergeLeafNode(nm,nr,2,l);
						 if(t->k[i+1]!=t->p[i+1]->k[0])
								t->k[i+1]=t->p[i+1]->k[0] ;
						}

					}else if (i==t->d-1 && t->d>1)
					{
						nl=t->p[i-1];
						//if (nm->d+nl->d<=2*M )
					   if ((nm->d+nl->d<=2*M ) || ((nm->d+nl->d<=2*M+1 )&&l>1))
						{
							t1=MergeLeafNode(nl,nm,0,l);
							DelFromNode(t,i);
							free(nm);
							t->d--;

						}else if(l>1 && nl->d==2*M+1 &&nm->d<M)
						{
						  t1=MergeLeafNodeBack(nl,nm,M,l);
							if(t->k[i]!=t->p[i]->k[0])
								t->k[i]=t->p[i]->k[0] ;

						}
					}
					else if(  t->d>2)
					{
						nl=t->p[i-1];
						nr=t->p[i+1];
						if ((nm->d+nl->d+nr->d<=4*M)||(nm->d+nl->d+nr->d<=4*M+2 &&l>1))
						{
							if (nl->d<2*M+1)
							{
							  if((nr->d+nm->d<=2*M+1 &&l>0)||(nr->d+nm->d<=2*M))
							  {
								t1=MergeLeafNode(nm,nr,0,l);
								free(nr);
								DelFromNode(t,i+1);
								t->d--;
								if(t->k[i]!=t->p[i]->k[0])
									t->k[i]=t->p[i]->k[0] ;
							  }
							  else
							  {
								t1=MergeLeafNode(nl,nm,2*M-nl->d,l);
								if(nm->d>0)
								{
									t1=MergeLeafNode(nm,nr,0,l);
									free(nr);
									DelFromNode(t,i+1);
									if(t->k[i]!=t->p[i]->k[0])
										t->k[i]=t->p[i]->k[0] ;

								}
								else
								{
									free(nm);
									DelFromNode(t,i);
								}
								t->d--;
							  }
							}
							else
							{
							   t1=MergeLeafNode(nm,nr,0,l);
							   if(nr->d==0)
							   {
									free(nr);
									DelFromNode(t,i+1);
									t->d--;
							   }
							}

						}
						else if(l>0 && nl->d==2*M+1 && nr->d==2*M+1 &&nm->d<M)
						{
							t1=MergeLeafNode(nm,nr,M,l);

						}
					}
					if (l==btree_level&&t->d<=1)
							{root=t1;btree_level--;}

				}
				else if(t->p[i]->d<M)
				{//合并索引节点

				}
			 }
			 else  //节点已被删除
			 {
				DelFromNode(t,i);
				t->d--;
			 }

		 }
		 else if(l==0)
		 {
               i--;
			 if (key == t->k [ i ])
			{
				 if(t->v[ i ]!= NULL)
				   {
						#ifdef key_string
							t->k[ i ]=null_string;
						#else
							t->k[ i ]=0;
						#endif
						free(t->v[i]);
				   }
					DelFromNode(t,i);     //维护父节点索引
					btree_count--;
					t->d--;
					if (t->k[ 0 ]!=t->min)
					t->min=t->k[ 0 ];
				 }
				 else{
				 printf("key not found\n");
				 }
		  }

 }


void tree::InternalDelete(typekey key, btree t,int le)
{
	int i,j,m,l1;
	btree nr,nm,nl,t1=NULL;
	int lvl;


	if (le < 0)
	{
		Error(0,key); /* 在整个树中未找到要删除的键 */
		flag = 0;
		return;
	}
//	for(i=0, j=t->d-1; i<j; m=(j+i)/2, (key > t->k[m])?(i=m+1):(j=m));

	for(i=0;i<t->d ;i++)
		{
			if   (key <= t->k[i])break;
		}
			l1=i;

			if(le>0)               //判断为索引
			 {
				if (key == t->k [ i ] )
				  i++;
				InternalDelete(key, t->p[ i ] ,le-1);

					l1=i;
					if(t->p[ i ]->d<M)
					{
					   if(i>0 && i<t->d)//节点中间 12
					   {
					   // 判断 前节点加后节点的空闲空间 是否足够合并
							if( 4*M-(t->p[ i-1 ]->d +t->p[ i+1 ]->d)<t->p[ i ]->d  )
							{ //无空间 无需合并
							   i=i;
							}
							else
							{
								 nl=t->p[ i-1 ] ;
								 nr=t->p[ i+1];
								 nm=t->p[ i];
								  l1=i;
								if( 2*M-nl->d>nm->d  )
								   {
									t1=MergeNode(nl,nm,0);
									/*for(j=i-1;j<t->d;j++)
									{
										t->k[j]=t->k[j+1];
										t->v[j]=t->v[j+1];
										t->p[j+1]=t->p[j+2];
									}
									 t->p[j]=t->p[j+1];  */
									  t->d--;
								   }
								 else if ( 2*M-nr->d  > nm->d )
								  {
								  t1=MergeNode(nm,nr,0);
								   t->d--;
								   nm=nr;
								   l1=i+1;
								   }
								 else if  ((( 4*M-nl->d -nr->d > nm->d  )  && nl->p[0]==NULL) )
								 {
									MergeNode(nl,nm,0);
									 l1=i;
									if(nl->p[0]!=NULL)
									{t1=MergeNode(nm,nr,0);
									nm=nr;
									l1=i+1;
									}
									 t->d--;
								 }

							  }

					   }
					   else if(i==0)
					   {
							nl=t->p[i] ;
							nm=t->p[i+1];
						  if( ( nl->d+nm->d<2*M) ||((nl->d+nm->d<=2*M)&&(nl->p[0]==NULL)))
						   {
								t1=MergeNode(nl,nm,0);
								 l1=i+1;
								t->d--;
								//后面的节点索引需要前移
									for(j=i;j<t->d;j++)
									{
										t->k[j]=t->k[j+1];
										t->v[j]=t->v[j+1];
										t->p[j+1]=t->p[j+2];
									}
									 t->p[j+1]=t->p[j+2];
									     
								}
					   }
					   else if (i==t->d)
					   {
					   //如左侧有空间 向左合并
					   nl=t->p[ i-1 ] ;
					   nm=t->p[ i];
						 if (( nl->d<2*M - nm->d ) || ((nl->p[0]==NULL)&&( nl->d<=2*M - nm->d ) )   )
						   {