B树B+树插入操作的实现

1970年，R.Bayer和E.mccreight提出了一种适用于外查找的树，它是一种平衡的多叉树，称为B树（或B-树、B_树）。

一颗度为n的B树的性质：

1.根节点的关键字的个数最小为1，最大为2*n-1，子节点指针的个数最小2个，最大2*n个

2.非根节点的关键字的个数最小为n-1个，最大为2*n-1，子节点指针的个数最小为n，最大为2*n

3.查找的关键字分布在所有节点中

4.叶节点关键字的高度相同（这是因为，每次节点分裂都会导致所有节点高度+1）

5.每个结点中关键字从小到大排列，并且当该结点的孩子是非叶子结点时，该k-1个关键字正好是k个孩子包含的关键字的值域的分划。

如上图所示，查找关键字x在B树的结构中，9是根节点如果x比9小则查找3，6节点，如果x比9大则查找12，15节点，依次递归，直到找到叶节点也没有x的话，则说明B树结构中没有x的关键字。

B树结构的插入操作：目的是把新关键字m，插入到B树结构的叶子节点上，按照插入原则递归到叶子节点，把节点插入到相应的位置上去。这里需要注意的问题：

如果插入的叶子节点的个数恰好饱和（个数为2*n-1），这样再继续插入节点，则会违反B树结构，这种情况是不希望发生的。所以在插入过程中，需要一种策略来避免这种情况，可以采用这种办法：如果在插入节点的过程中，无论是叶子节点还是非叶子节点，只要碰到节点为满节点，关键字个数为2*n-1个，就分裂该节点。具体的做法就是把index=n-1的关键字分裂到父节点的中间位置，同时把剩余的2n-2个节点，平均分为2个节点，每个节点的关键字的个数为n-1个，同时子节点的个数是n个，这个中间位置的节点，一定可以插入到父节点中，因为在处理当前节点之前，肯定递归到了父节点，保证了父节点肯定不是满节点。

图解节点分裂过程：

节点数据结构：

#define DU 3                       //DU代表B树的度
typedef struct _page{
        int data[DU*2-1];          //节点关键字数组，最多有DU*2-1个关键字
        struct _page *child[DU*2];       //子节点指针数组，最多有DU*2个指针
        struct _page *parent;      //指向父节点
        int isLeaf;                //标志节点是否是叶子节点
}page;

节点初始化函数：

page* pm(){
        page* p=(page *)malloc(sizeof(page));
        int index=0;
        for(;index<sizeof(p->data)/sizeof(int);index++)
                p->data[index]=0;                      //每个关键字置为0
        p->isLeaf=1;                                /                                 //初始化是叶子节点
        return p;
}

取得节点有效关键字个数的函数：

int pageSize(page* p){
        if(p==NULL)
                return 0;
        int result=0;
        int i=0;
        for(;i<DU*2-1;i++){
                if(p->data[i]!=0)
                        result++;
        }
        return result;
}

取得节点关键字数组的最大关键字的数组下标：

int maxIndex(page* p){
        int i=0;
        int result;
        for(;i<2*DU-1;i++){
                if(p->data[i]==0)
                        return i-1;   //如果遇到了0说明前一个下标是最大的下标
        }
        return 2*DU-2;           //如果到了这里说明该节点是满节点，最大关键字下标是2*DU-2
}

左移函数：

void shiftLeft(page* p,int start,int offset){ //start是开始移动的位置，offset 移动的位移
        int tmp=start;
        int max=maxIndex(p);
        if(start+offset>max+1){
                printf("out of bound");
                exit(0);
        }
        if(max==0)
                max=1;
        for(;tmp<max;tmp++){                 //左移关键字
                p->data[tmp]=p->data[tmp+offset];
                p->data[tmp+offset]=0;       //将无用的关键字置为0
        }
        tmp=start;
        for(;tmp<max+1;tmp++){
                p->child[tmp]=p->child[tmp+offset];    //左移子节点指针
                p->child[tmp+offset]=NULL;          //将无用的子节点指针置为NULL
        }
}

节点右移函数：

void shiftRight(page* p,int start,int offset){
        int max=maxIndex(p);
        if(offset+max>2*DU-2){
                printf("out of bound");
                exit(0);
        }
        int index=max;
        for(;index>=start;index--){
                p->data[index+offset]=p->data[index];  //右移关键字数组
                p->data[index]=0;
        }
        index=max+1;
        for(;index>=start;index--){
                p->child[index+offset]=p->child[index];  //右移子节点指针数组
                p->child[index]=NULL;
        }
}

插入节点函数：

void insertData(page* p,int val){           //p表示目的节点，val表示要插入的值
        if(pageSize(p)==DU*2-1){  //如果递归的过程中碰到满节点，就先分裂p节点
                p=splitPage(p,val);                 //分裂的过程后，从新设置p节点
        }
        int index=0;
        for(;index<sizeof(p->data)/sizeof(int);index++){  //寻找子节点的位置，因为分裂节点保证了p节点不是满节点，所以不用考虑满节点的情况（满节点的话index需要加1）
                if(p->data[index]==0||p->data[index]>val){
                                 break;
                }
        }

        if(p->isLeaf==0){                                 //如果不是叶子节点，递归插入到子节点
                insertData(p->child[index],val);
                return;
        }
        if(pageSize(p)>0)                                 //如果节点中有关键字则右移1个位置
shiftRight(p,index,1);
        p->data[index]=val;                              //把新的关键字插入到相应的位置
}

具体节点分裂过程：

1.A节点是B节点的父节点，B节点为满节点，需要分裂B节点，首先创建C节点，然后将B节点关键字数组的从index=n的关键字到最后一个关键字（index=2*n-2）移动到C节点的关键字数组中，同时将B节点的子节点数组index=n到最后一个子节点指针index=2*n-1移动到C节点的子节点数组中。

2.原先的3节点被移动到了父节点A中，这时需要将A节点的关键字数组相应位置右移1个位置为了存放关键字3，A节点的子节点指针数组需要在相应的位置右移1个位置，为了存放指向C节点的指针，同时需要设置C的父节点为A。

节点分裂函数：

page* splitPage(page* p,int val){
 //p节点为满节点，需要分裂，val是用来决定返回递归的新节点，B节点（原来的递归节点），C节点
        int mid=p->data[DU-1];        //取得p中间位置的节点，它被分裂到父节点中
        page* right=pm();             //新建C节点
        int index=DU;
        int i=0;
        for(;index<DU*2-1;index++){   //开始复制B节点的关键字数组和子节点指针数组，
                right->data[i]=p->data[index];
                p->data[index]=0;
                right->child[i]=p->child[index];
                p->child[index]=NULL;
                if(right->child[i]!=NULL)
                        right->child[i]->parent=right;
 //B节点的子节点的父节点原来是B，由于一部分子节点迁移到了C节点上，所以要重新设置子节点的父节点指针
                i++;
        }
        right->child[i]=p->child[2*DU-1];         //子节点指针数组比关键字数组个数多一个
        if(right->child[DU-1]!=NULL)
                right->child[DU-1]->parent=right; //同时设置最后一个子节点指针的父节点
        p->child[2*DU-1]=NULL;
        p->data[DU-1]=0;
        page* result=p;
        right->isLeaf=p->isLeaf;                  //设置C节点是否是叶子节点，
        int isNew=0;
        if(val>mid)                         //如果新节点大于mid，新递归的节点就是C节点
                result=right;
        if(p->parent==NULL){//如果p节点就是根节点了，那么需要新生成Root节点
                root=pm();
                p->parent=root;
                isNew=1;
                root->isLeaf=0;
        }
        page* parent=p->parent;
        int first=0;
        for(;first<2*DU-1;first++){//取得父节点中mid可插入的位置
                if(parent->data[first]>mid||parent->data[first]==0)
                        break;
        }
        index=2*DU-3;
        for(;index>=first;index--){//关键字和子节点指针数组右移1位
                parent->data[index+1]=parent->data[index];
                parent->child[index+2]=parent->child[index+1];
        }
        parent->data[first]=mid;  //插入新的关键字mid，和新的子节点指针right
        parent->child[first+1]=right;
        if(isNew){
                parent->child[0]=p;
        }
        right->parent=parent;
        return result;
}

B+树的性质：

B+树的主要应用就是数据库中的索引，B+树的性质和B树类似，只是B+树的叶子节点多了指向兄弟节点的指针，这样通过查找叶子节点就可以通过兄弟指针实现范围查询了，B树是不可以的，它只能遍历单个叶子节点。同时，关键字全部在叶子节点，也就是所非叶子节点中的关键字只是起着索引作用，所以每个非叶子节点可以容纳更多的关键字，所以从db的角度来说，取得了一个数据页，B树结构除了关键字的信息还包括了它的关键字代表的全部信息，反之B+树一个数据页存储的只是关键字的信息和子节点的数据页指针，它能存储更多的子节点指针信息，B+树只要得到比B树更少的数据页就可以查找到关键字代表的信息，所以B+树更适合作为索引的数据结构。

数据页的数据结构：

typedef struct _page{
    int data[DU*2-1];
    struct _page *child[2*DU];
    struct _page *parent;
    int isLeaf;
    struct _page *sibling; //多了一个指向兄弟节点的指针
}page;

其他操作和B树操作相同，只是节点分裂操作和B树不太一样

1.可以先把A节点分裂成为两个节点，因为中间节点会上升到父节点，同时还会滞留在原来的A节点中，这里可以根据情况随意分配节点，可以A节点留下3个，新节点分配2个，也可以A2个，新节点3个，子节点指针数组可以A节点留下3个指针，新节点B复制剩余3个指针，注意A节点原本可能已经有了兄弟节点指针sbling，这样分裂后的节点A的sibling应该指向新节点B，然后B指向原来A的兄弟节点sibling

2.节点分裂中间的关键字会滞留在A节点中，同时中间关键字也会上升到父节点，同时父节点相应位置，关键字和子节点指针数组右移一位。

B+树节点分裂过程：

page* splitPage(page* p,int val){
   int mid=p->data[DU-1];            //mid中间节点
   page* right=pm();                 //新建right节点
   int index=DU;
   int i=0;
   for(;index<DU*2-1;index++){       //把p节点的关键字和子节点指针移动到right节点上
     right->data[i]=p->data[index];
     p->data[index]=0;               //把当前位置置为无效
     right->child[i]=p->child[index];
     p->child[index]=NULL;           //把当前位置置为无效
     if(right->child[i]!=NULL)
       right->child[i]->parent=right;//重新设置p节点子节点的父节点
       i++;
   }
   right->child[DU-1]=p->child[2*DU-1];
   if(right->child[DU-1]!=NULL)
      right->child[DU-1]->parent=right;
   p->child[2*DU-1]=NULL;
   if(p->isLeaf)                    //如果是叶子节点设置p节点的兄弟节点就是right节点
      p->sibling=right;
   page* result=p;
   right->isLeaf=p->isLeaf;
   if(val>mid)
     result=right;
   int isNew=0;
   if(p->parent==NULL){             //如果p节点就是根节点，新建root节点
     root=pm();
     p->parent=root;
     isNew=1;
     root->isLeaf=0;
   }
   page* parent=p->parent;
   int first=0;
   int a=0;
   for(;first<2*DU-1;first++){     //寻找p节点父节点插入mid的合适位置
     if(parent->data[first]>mid||parent->data[first]==0)
         break;
   }
   index=2*DU-3;
   for(;index>=first;index--){     //p节点右移操作
     parent->data[index+1]=parent->data[index];
     parent->child[index+2]=parent->child[index+1];
   }
   parent->data[first]=mid;
   parent->child[first+1]=right;
   if(isNew){
     parent->child[0]=p;
   }else if(first+2<=2*DU-1&&parent->child[first+2]!=NULL){
      right->sibling=parent->child[first+2];  //把right节点的兄弟节点设置为原节点的兄弟节点
   }
   right->parent=parent;
   return result;
}

B+树测试代码：

int main(){
  root=pm();
  int i=0;
  int data[]={12,5,32,56,2,7,23,676,97,54,234,79,1,3,15,22,13,16,888,21,25,24,26,100,101,102,103,104,105,106};
  for(;i<30;i++)
     insertData(root,data[i]);
  page *temp=root;
  while(temp->isLeaf==0){
    temp=temp->child[0];
  }
  do{
     int index=0;
    for(;index<5;index++){
      if(temp->data[index]==0)
        break;
      printf("%d\n",temp->data[index]);
    }
    temp=temp->sibling;
  }while(temp!=NULL);
}

结果：

参考资料：

1.算法导论第二版，机械工业出版社