首页 > 代码库 > 数据结构之B-树，你每天都在用的，源码发布！

数据结构之B-树，你每天都在用的，源码发布！

2024-07-02 21:39:37   228人阅读

     [QQ群: 189191838，对算法和C++感兴趣可以进来]

     五一前就筹划着写下这篇文章，但是迫于自己从来没有实现过B-树(如果大家感兴趣，我可以考虑写一篇B+树的文章)，手中没有源代码，另外自己以前对B-树也是一知半解状态中，担心误人子弟，在4月30日终于把代码写完，今天调完之前的bug之后，那种感觉就像在鸟无人烟的大荒漠中走了好久，看到一间有水的屋子，长舒一口气！好的废话不多说，下面直接切入正题！

     链表，树，图是最基本的数据结构了，链表有单链表、双链表，有环和无环等等；树有二叉树、多叉树，平衡树、不平衡树等等；图有有向、无向图等等。如果把算法建模看成是建筑师建造一座大厦，那么数据结构就是地基，地基的好坏直接关系到房子能建多高。

     今天我们要讲到的是树的一种，即B-树。要说B-树，就必然要说平衡二叉树，否则这是不科学的，没有平衡二叉树哪来B-树。它的定义是这样的：

     平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

     

 

图一

     这个是一颗典型的平衡二叉树，对根节点50而言，左右子树的高度都是3，高度差绝对值不超过1；对左子树而言，根节点是17，但是他的左右两子树高度都是2，差的绝对值也不超过1.我们递归的观察，显然它符合平衡二叉树的基本条件。

    如果我们把右子树剪掉，他就不是平衡二叉树了。左边高度为3，右边高度为0；3-0=3>1.

图二

 OK，说到这里，我想我们可以讲讲B-树了。B-树其实可以理解为多叉平衡树！它的定义是这样的：(其中T一般大于3)

 1)不仅高度平衡，而且所有的叶子节点都在同一层。

 2)除根节点外其他每个节点最少保存(T-1)个关键字，至多保存(2T-1)个关键字；至少保存(T)个孩子结点，至多(2T)个孩子结点。

 3)对于关键字K而言，左孩子结点的所有关键字都小于K，右孩子结点的所有关键字都大于K。在同一个结点上，关键字是从小到大依次排列。结点中除叶子节点关键字外，均有左右孩子。

随便提一下，现在有很多B-树的变形，有些要求每个节点至少保存2/3(2T-1)个关键字等等，也是可以的。

 如下图就是一颗典型的B-树：

图三

      OK，对于B-树，想必大家有了一个直观的认识。那么B-树有什么用呢？当今社会太浮躁了，没用的东西留着干嘛？果断弃之。显然B-树是非常有用的。大家用数据库进行开发吗？如果你用，那么其实你每天都在用B-树有没有，因为大部分数据库的底层实现都是用B-树。

      B-树对大数据特别有用，特别是查询情况多的时候（比如数据库）；因为一旦数据量特别大之后，内存肯定不能把所有数据都装到内存中，我们唯有通过硬盘存储，存储在硬盘中之后，怎样才能高效的进行查询呢？我们仔细观察B-绝对是一个很好的选择，因为它最糟糕的时候效率都是logT(N);硬盘的速度相对内存来说是比较慢的，较少一次硬盘读取对用户体验是一个莫大的支持！

   老规矩：如果需要全部源代码请点赞后留下email地址。

    其实基于B-的数据库，数据操作基本可以归纳为四个部分：

   读取硬盘数据：根据给定页面Id读取硬盘数据到内存，然后返回内存相应位置；

   硬盘写操作：给定内存需写入数据地址信息，写入到给定页面id硬盘中。

   申请硬盘页面：如果页面中id不存在，开拓硬盘页面，然后返回内存地址。

   释放页面：给定一个硬盘页面id,释放该资源。

   OK，我们了解到了B-树的重要性之后，也就知道了学习B-树的现实意义了。那我们现在可以继续开扒了。

   B-树应该怎么设计呢？看了B-树的定义之后，B-树数据结构应该包括：1)关键字个数，2)指向父节点的指针,3)关键字集合,4)孩子结点集合。

   根据以上论述，我们把B-树的数据结构代码化之后如下：

 1 struct BTreeNode{
 2     int keyNum;//关键字个数。
 3     BTreeNode* parentNode;//父结点指针
 4     vector<NodeValueType> nodeValues;
 5     vector<BTreeNode*> childs;
 6     BTreeNode(){
 7         keyNum=0;
 8         parentNode=NULL;
 9     }
10 };

    对于B-树而言最常用的就是增删改查了。改可以认为是删，然后增。所以可以理解成主要操作有增、删、查！下面分三部分详解他们。

B-树的查询操作：

     B-树的查询可以从根节点开始查找，根节点没有查到，再查找某一个孩子结点。

     因为B-树结点都有很多孩子节点，查找哪个孩子结点就显得特别重要了，总不能乱查吧。它应该是查找第一个比关键字大的左结点，如果没有一个比该关键字大的关键字，则查找最右孩子。如此递归。直到查到叶子结点，如果叶子结点也没有找到，那么B-树中不存在该关键字。

    比如对于图三，查找关键字G。首先在根节点中查找，根节点只有M一个关键字，显然不符合条件。查找到第一个大于G的关键字，这里M比G大，所有积蓄查找M的左子树，左子树的根节点关键字有：D、H。同样第一个比G大的是H。H的左孩子结点关键字是F、G。这样，G被找到了。返回。

    

图四

 算法具体描述为：

 1 bool SearchBTreeByValue(BTreeNode* q,NodeValueType k){
 2     int i=0;
 3     while(i<q->keyNum&&q->nodeValues[i]<=k){
 4         if (q->nodeValues[i]==k){
 5             return true;//相等则返回q
 6         }
 7         i++;
 8     }
 9     if (!q->childs.size()){
10         return false;//没有找到直接返回NULL
11     }
12     return SearchBTreeByValue(q->childs[i],k);
13 }

 B-树的增加(插入)操作

    【插入操作要寻找到叶子节点插入】因为B-树中最多只能保存2T-1个关键字，如果当前的关键字个数已经达到2T-1，还需插入一个的话就需要分裂成两个结点。如下图，T=2.如果还需插入一个18.由于结点X已经有3个关键字了。已经full了。如果还需要插入18，就不符合条件了，就需要分裂成两个结点，同时增加一层。再进行插入。也可以插入完成后，再分裂。最终还是要分裂。

    如果B-树没有满的话，直接插入就好。

     

图五

 

 

图六 

 1 BTreeNode* InsertNodeToBTreeByValue(BTreeNode* p,NodeValueType theValue){
 2     if (SearchBTreeByValue(p,theValue)){
 3         cout<<theValue<<"已经存在了，骚年！"<<endl;
 4         return p;
 5     }
 6     while(p->childs.size()!=0){//一直找到叶子结点
 7         int i=0;
 8         while(i<p->keyNum&&p->nodeValues[i]<theValue){
 9             i++;
10         }
11         p=p->childs[i];
12     }
13     p->nodeValues=InsertKeyToNodeByValue(p->nodeValues,theValue);//插入到当前叶子结点
14     p->keyNum++;
15     return adjustBTree(p);//使得最大不超过maxKey
16 }

 

B-树的删除操作

    说实话，删除操作比增加操作复杂多了，这也是我的程序一直出现bug的地方。假设要在结点x中删除关键字k。

    因为删除操作需要考虑删除后结点会少于T-1和树不平衡的情况。

    删除操作主要考虑三种情况：

    1)x是叶子结点，包含k

    2)x是内部结点，包含k

    3)x是内部结点，不包含k.

    对于1)，直接删除，同时更新keynum;

    对于2)，考虑k的左右孩子，

                若有一个孩子的关键字个数大于T-1,若左孩子y，用最右边的关键字和k交换，同时递归删除delete(y,k);

                若右孩子(z)数大于T-1，则递归删除delete(z,k);

                若左右孩子都等于T-1，则需要合并左孩子，k，右孩子，同时删除右孩子。

   对于3)，y=x.child[k];若y的关键字个数大于T-1,则递归删除delete(y,k)

                                   若y的关键字个数等于T-1,则寻找他的兄弟节点，兄弟节点若有大于T-1个数的，补一个过来。

                                                                      若没有的话，就进行和其中兄弟节点合并，再递归delete.

  1 BTreeNode* DeleteBTreeNode(BTreeNode* p,NodeValueType theValue){
  2     int theValueOrderInNode=GetOrderInNodeByValue(p,theValue);//返回当前序号，theValueOrderInNode
  3     //BTreeNode* w=p->parentNode;
  4     if (theValueOrderInNode!=-1&&p->childs.size()==0){
  5         p->nodeValues.erase(p->nodeValues.begin()+theValueOrderInNode,p->nodeValues.begin()+theValueOrderInNode+1);
  6         p->keyNum--;
  7         return GetBTreeRoot(p);
  8     }else if (theValueOrderInNode==-1){//该结点中不存在theValue
  9         int i=0;
 10         while(i<p->keyNum&&p->nodeValues[i]<theValue){
 11             i++;//得到第I个孩子。
 12         }
 13         BTreeNode* y=p->childs[i];//找到i+1个孩子结点
 14         if (y->keyNum>atLeastKeyNum){
 15             return DeleteBTreeNode(y,theValue);
 16         }else if(y->keyNum==atLeastKeyNum){
 17             BTreeNode* leftSlibing=new BTreeNode(),*rightSlibing=new BTreeNode();//左右结点出现啦！
 18             leftSlibing=NULL,rightSlibing=NULL;
 19             if (i!=0){//有左兄弟
 20                 leftSlibing=p->childs[i-1];
 21             }
 22             if (i!=p->keyNum){//有右兄弟
 23                 rightSlibing=p->childs[i+1];
 24             }
 25             if (leftSlibing!=NULL&&leftSlibing->keyNum>atLeastKeyNum){//左兄弟移动一个到y中
 26                 y->nodeValues.insert(y->nodeValues.begin(),p->nodeValues[i-1]);
 27                 y->keyNum++;
 28                 p->nodeValues[i-1]=leftSlibing->nodeValues[leftSlibing->keyNum-1];
 29                 if (y->childs.size()!=0){
 30                     y->childs.insert(y->childs.begin(),*(leftSlibing->childs.end()-1));
 31                     leftSlibing->childs.erase(leftSlibing->childs.end()-1,leftSlibing->childs.end());
 32                 }
 33                 leftSlibing->nodeValues.erase(leftSlibing->nodeValues.end()-1,leftSlibing->nodeValues.end());
 34                 leftSlibing->keyNum--;
 35                 return DeleteBTreeNode(y,theValue);
 36             }else if(rightSlibing!=NULL&&rightSlibing->keyNum>atLeastKeyNum){//右兄弟移动一个到y中
 37                 y->nodeValues.insert(y->nodeValues.end(),p->nodeValues[i]);
 38                 y->keyNum++;
 39                 if (y->childs.size()!=0){
 40                     y->childs.insert(y->childs.end(),*(rightSlibing->childs.begin()));
 41                     rightSlibing->childs.erase(rightSlibing->childs.begin(),rightSlibing->childs.begin()+1);
 42                 }
 43                 p->nodeValues[i]=rightSlibing->nodeValues[0];
 44                 rightSlibing->nodeValues.erase(rightSlibing->nodeValues.begin(),rightSlibing->nodeValues.begin()+1);
 45                 rightSlibing->keyNum--;
 46                 return DeleteBTreeNode(y,theValue);
 47             }else{//合并成一个
 48                 if (leftSlibing!=NULL){//同左合并
 49                     leftSlibing->nodeValues.insert(leftSlibing->nodeValues.end(),p->nodeValues[i-1]);
 50                     leftSlibing->keyNum++;
 51                     p->nodeValues.erase(p->nodeValues.begin()+i-1,p->nodeValues.begin()+i);
 52                     MoveBTreeNode(leftSlibing,y);
 53                     p->childs.erase(p->childs.begin()+i-1,p->childs.begin()+i);
 54                     p->keyNum--;
 55                     if (p->keyNum==0){
 56                         leftSlibing->parentNode=NULL;
 57                     }
 58                     return DeleteBTreeNode(leftSlibing,theValue);
 59                 }else{//同右合并
 60                     y->nodeValues.insert(y->nodeValues.end(),p->nodeValues[i]);
 61                     y->keyNum++;
 62                     p->nodeValues.erase(p->nodeValues.begin()+i,p->nodeValues.begin()+i+1);
 63                     MoveBTreeNode(y,rightSlibing);
 64                     p->childs.erase(p->childs.begin()+i+1,p->childs.begin()+i+2);
 65                     p->keyNum--;
 66                     if (p->keyNum==0){
 67                         y->parentNode=NULL;
 68                     }
 69                     return DeleteBTreeNode(y,theValue);
 70                 }
 71             }
 72         }
 73     }else if (theValueOrderInNode!=-1){//在该结点中找到了。
 74         BTreeNode* leftChild=GetPreChildByNodeValue(p,theValue);
 75         BTreeNode* rightChild=GetSuccessByNodeValue(p,theValue);
 76         if (leftChild!=NULL&&leftChild->keyNum>atLeastKeyNum){//左
 77             p->nodeValues[theValueOrderInNode]=leftChild->nodeValues[leftChild->keyNum-1];
 78             leftChild->nodeValues[leftChild->keyNum-1]=theValue;
 79             //leftChild->parentNode=p;
 80             return DeleteBTreeNode(leftChild,theValue);
 81         }
 82         else if (rightChild!=NULL&&rightChild->keyNum>atLeastKeyNum){//右
 83             p->nodeValues[theValueOrderInNode]=rightChild->nodeValues[0];
 84             rightChild->nodeValues[0]=theValue;
 85             //rightChild->parentNode=p;
 86             return DeleteBTreeNode(rightChild,theValue);
 87         } 
 88         else if (leftChild!=NULL){//需要合并了
 89             leftChild->nodeValues.insert(leftChild->nodeValues.end(),p->nodeValues[theValueOrderInNode]);
 90             leftChild->keyNum++;
 91             MoveBTreeNode(leftChild,rightChild);//从左移到右
 92             p->nodeValues.erase(p->nodeValues.begin()+theValueOrderInNode,p->nodeValues.begin()+theValueOrderInNode+1);
 93             p->childs.erase(p->childs.begin()+theValueOrderInNode+1,p->childs.begin()+theValueOrderInNode+2);
 94             p->keyNum--;
 95             if (p->keyNum==0){
 96                 leftChild->parentNode=NULL;
 97             }
 98             return DeleteBTreeNode(leftChild,theValue);
 99         }
100     }
101     return NULL;
102 }

 

操作数据：用106,103,109,130,145,165,42,60,136,107,108对B-树进行初始化。然后再进行查找删除操作。

                        图七

 参考文献：http://zgking.com:8080/home/donghui/publications/books/dshandbook_BTree.pdf

                http://webdocs.cs.ualberta.ca/~holte/T26/del-b-tree.html

                http://www.cs.nott.ac.uk/~nza/G52ADS/btrees2.pdf

 

      版权所有，欢迎转载，但是转载请注明出处：潇一

 

 


联系
我们