B-树的详解

布满荆棘的人生 2022-06-18 00:29 120阅读 0赞

*前言*

博客编写人：Willam
    博客编写时间：2017/3/27
    博主邮箱：2930526477@qq.com（有志同道合之人，可以加qq交流交流编程心得）

## 1、背景知识 ##

下面这段摘抄自博客：（[从B 树、B+ 树、B\* 树谈到R 树][B _B_ _B_ _R]）  
动态查找树主要有：[二叉查找树（Binary Search Tree）][Binary Search Tree]，[平衡二叉查找树（Balanced Binary Search Tree）][Balanced Binary Search Tree]，红黑树(Red-Black Tree )，B-tree/B+-tree/ B\*-tree (B~Tree)。前三者是典型的二叉查找树结构，其查找的时间复杂度O(log2N)与树的深度相关，那么降低树的深度自然会提高查找效率。

但是咱们有面对这样一个实际问题：就是大规模数据存储中，实现索引查询这样一个实际背景下，树节点存储的元素数量是有限的（如果元素数量非常多的话，查找就退化成节点内部的线性查找了），这样导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下（为什么会出现这种情况，待会在外部存储器-磁盘中有所解释），那么如何减少树的深度（当然是不能减少查询的数据量），一个基本的想法就是：采用多叉树结构（由于树节点元素数量是有限的，自然该节点的子树数量也就是有限的）。

也就是说，因为磁盘的操作费时费资源，如果过于频繁的多次查找势必效率低下。那么如何提高效率，即如何避免磁盘过于频繁的多次查找呢？根据磁盘查找存取的次数往往由树的高度所决定，所以，只要我们通过某种较好的树结构减少树的结构尽量减少树的高度，那么是不是便能有效减少磁盘查找存取的次数呢？那这种有效的树结构是一种怎样的树呢？

这样我们就提出了一个新的查找树结构——多路查找树。根据平衡二叉树的启发，自然就想到平衡多路查找树结构，也就是这篇文章所要阐述的第一个主题B~tree，即B树结构(后面，我们将看到，B树的各种操作能使B树保持较低的高度，从而达到有效避免磁盘过于频繁的查找存取操作，从而有效提高查找效率)。

## 2、B-树的介绍 ##

B-树其实就是我们平时所说的B树，除了B-树外，还有另外一种叫B+树，我们这里先介绍什么是B-树：  
B-树是一种**平衡的多路查找树**，它在文件系统中很有用（原因之前已经介绍了）。B-树的结构有如下的特点：  
\*\*一棵度为m的B-树称为m阶B-树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分  
为k个子集。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求  
m≥3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：\*\*

*  树中的每个结点至多有m颗子树。
 *  若根结点不是叶子结点，则至少有两颗子树。
 *  除根结点外，所有非终端结点至少有\[ m/2 \] ( 向上取整 )颗子树。
 *  所有的非终端结点中包括如下信息的数据

（n,A0,K1,A1,K2,A2,….,Kn,An）  
其中：Ki（i=1,2,…,n）为关键码，且Ki < K(i+1)，

Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn.  
![这里写图片描述][SouthEast]  
n 为关键码的个数。

*  所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。

## 3、B-树的基本操作–查找介绍 ##

我们先给出如下的一个4阶的B-树结构。  
![这里写图片描述][SouthEast 1]

如上图所示，这是我们的一个4阶的B-树，现在假设我们需要查找45这个数是否在B-树中。

1.  从根节点出发，发现根节点a有1个关键字为35，其中45>35，往右子树走，进入节点c
2.  发现结点c有2个关键字，其中其中43<45<78,所以进入结点g。
3.  发现结点g有3个关键字，其中3<45<47,所以继续往下走，发现进入了结束符结点：F，所以45不在B-树中

OK，我们从上述的查找的过程可以得出，在B-树的查找过程为：

1.  在B- 树中查找结点
2.  在结点中查找关键字。

由于B- 树通常存储在磁盘上， 则前一查找操作是在磁盘上进行的， 而后一查找操作是在内存中进行的， 即  
在磁盘上找到指针p 所指结点后， 先将结点中的信息读入内存， 然后再利用顺序查找或折半查找查询等于K  
的关键字。显然， 在磁盘上进行一次查找比在内存中进行一次查找的时间消耗多得多.  
因此， 在磁盘上进行查找的次数、即待查找关键字所在结点在B- 树上的层次树， 是决定B树查找效率的首要  
因素，对于有n个关键字的m阶B-树，从根结点到关键字所在结点的路径上路过的结点数不超过：  
![这里写图片描述][SouthEast 2]

## 4、B-树的插入 ##

其实B-树的插入是很简单的，它主要是分为如下的两个步骤：

1. 使用之前介绍的查找算法查找出关键字的插入位置，如果我们在B-树中查找到了关键字，则直接返回。否则它一定会失败在某个最底层的终端结点上。
     2.然后，我就需要判断那个终端结点上的关键字数量是否满足：n<=m-1,如果满足的话，就直接在该终端结点上添加一个关键字，否则我们就需要产生结点的“分裂”。
         分裂的方法是：生成一新结点。把原结点上的关键字和k（需要插入的值）按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。

下面我们来举例说明，首先假设这个B-树的阶为：3。树的初始化时如下：  
![这里写图片描述][SouthEast 3]

首先，我需要插入一个关键字：30，可以得到如下的结果：  
![这里写图片描述][SouthEast 4]

再插入26，得到如下的结果：

![这里写图片描述][SouthEast 5]

OK，此时如图所示，在插入的那个终端结点中，它的关键字数已经超过了m-1=2，所以我们需要对结点进分裂，所以我们先对关键字排序，得到：26 30 37 ，所以它的左部分为（不包括中间值）：26，中间值为：30，右部为：37，左部放在原来的结点，右部放入新的结点，而中间值则插入到父结点，并且父结点会产生一个新的指针，指向新的结点的位置，如下图所示：  
![这里写图片描述][SouthEast 6]

OK，然后我们继续插入新的关键字：85，得到如下图结果：  
![这里写图片描述][SouthEast 7]

正如图所示，我需要对刚才插入的那个结点进行“分裂”操作，操作方式和之前的一样，得到的结果如下：  
![这里写图片描述][SouthEast 8]

哦，当我们分裂完后，突然发现之前的那个结点的父亲结点的度为4了，说明它的关键字数超过了m-1，所以需要对其父结点进行“分裂”操作，得到如下的结果：  
![这里写图片描述][SouthEast 9]

好，我们继续插入一个新的关键字：7，得到如下结果：  
![这里写图片描述][SouthEast 10]

同样，需要对新的结点进行分裂操作，得到如下的结果：  
![这里写图片描述][SouthEast 11]  
到了这里，我就需要继续对我们的父亲结点进行分裂操作，因为它的关键字数超过了：m-1.  
![这里写图片描述][SouthEast 12]

哦，终于遇到这种情况了，我们的根结点出现了关键子数量超过m-1的情况了，这个时候我们需要对父亲结点进行分列操作，但是根结点没父亲啊，所以我们需要重新创建根结点了。  
![这里写图片描述][SouthEast 13]

好了，到了这里我们也知道怎么进行B-树的插入操作。

## 5、B-树的删除操作 ##

B-树的删除操作同样是分为两个步骤：

1.  利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k（需要删除的关键字）所在结点是否为叶子结点有不同的处理方法。如果没有找到，则直接返回。
2.  若该结点为非叶结点，且被删关键字为该结点中第i个关键字key\[i\]，则可从指针son\[i\]所指的子树中找出最小关键字Y，代替key\[i\]的位置，然后在叶结点中删去Y。

如果是叶子结点的话，需要分为下面三种情况进行删除。

*  如果被删关键字所在结点的原关键字个数n>=\[m/2\] ( 上取整），说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需删除对应的关键字：k和指针：A 即可。
 *  如果被删关键字所在结点的关键字个数n等于( 上取整）\[ m/2 \]-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。

**调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）\[m/2\]-1。则可将右兄弟(或左兄弟)结点中最小关键字(或最大的关键字)上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。**

*  被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）\[m/2\]-1。假设该结点有右兄弟，且其右兄弟结点地址由双亲结点中的指针Ai所指，则在删去关键字之后，它所在结点中剩余的关键字和指针，加上双亲结点中的关键字Ki一起，合并到 Ai所指兄弟结点中(若没有右兄弟，则合并至左兄弟结点中)。

下面，我们给出删除叶子结点的三种情况：  
第一种：关键字的数不小于（上取整）\[m/2\]，如下图删除关键字：12  
![这里写图片描述][SouthEast 3]  
删除12后的结果如下，只是简单的删除关键字12和其对应的指针。  
![这里写图片描述][SouthEast 14]

第二种：关键字个数n等于( 上取整）\[ m/2 \]-1，而且该结点相邻的右兄弟(或左兄弟)结点中的关键字数目大于( 上取整）\[m/2\]-1。  
![这里写图片描述][SouthEast 15]

如上图，所示，我们需要删除50这个关键字，所以我们需要把50的右兄弟中最小的关键字：61上移到其父结点，然后替换小于61的关键字53的位置，53则放至50的结点中。然后，我们可以得到如下的结果：  
![这里写图片描述][SouthEast 16]

第三种：关键字个数n等于( 上取整）\[ m/2 \]-1，而且被删关键字所在结点和其相邻的兄弟结点中的关键字数目均等于（上取整）\[m/2\]-1

![这里写图片描述][SouthEast 17]

如上图所示，我们需要删除53，那么我们就要把53所在的结点其他关键字（这里没有其他关键字了）和父亲结点的61这个关键字一起合并到70这个关键字所占的结点。得到如下所示的结果：  
![这里写图片描述][SouthEast 18]

Ok，我已经分别对上述的四种删除的情况都做了举例，大家如果还有什么不清楚的，可以看看代码，估计就可以明白了

## 6、B-树的基本操作的代码实现 ##

*  BTree.h文件的代码

/************************************************************/
    /*                程序作者：Willam                          */
    /*                程序完成时间：2017/3/28                   */
    /*                有任何问题请联系：2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    #ifndef BMT_H_
    #define BMT_H_
    
    
    #include<iostream>
    #include<cstdlib>
    using namespace std;
    #define m 3
    
    
    typedef int KeyType;
    
    typedef struct BMTNode {
        int keynum;
        BMTNode * parent;
    
        KeyType   key[m + 1];
        BMTNode * ptr[m + 1];
    
        BMTNode() : keynum(0), parent(NULL) {
            for (int i = 0; i <= m; ++i) {
                key[i] = 0;
                ptr[i] = NULL;
            }//endfor
        }//endctor
    }*BMT;
    typedef struct Node {
        int keynum;  //关键字的数量
        Node * parent;  //父亲结点
        KeyType key[m + 1]; //记录关键字，但是0号单元不用
        Node *  ptr[m + 1]; //记录孩子结点的指针
        Node() :keynum(0), parent(NULL) {
            for (int i = 0; i <= m; i++)
            {
                key[i] = 0;
                ptr[i] = NULL;
            }//endfor
        }//endcontruct
    };
    
    class BTree {
    private:
        Node * head;
        int search(Node *& T, KeyType K); //查找关键字
        void insert(Node * & T, int i, KeyType K, Node * rhs); //插入关键字的位置
        bool split(Node *& T, int s, Node * & rhs, KeyType & midK); //结点分裂
        bool newroot(Node * & T, Node * & lhs, KeyType midK, Node * & rhs);
        void RotateLeft(Node * parent, int idx, Node * cur, Node * rsilb);
        void RotateRight(Node * parent, int idx, Node * cur, Node * lsilb);
        void Merge(Node * parent, int idx, Node * lsilb, Node * cur);
        void DeleteBalance(Node * curNode);
        void Delete(Node * curNode, int curIdx);
    public:
        BTree();
        Node * gethead();
        bool searchKey_BTree(KeyType K, Node * & recNode, int & recIdx);
        bool insert_BTree(KeyType k);
        bool Delete_BTree(KeyType K);
        void Destroy(Node * & T);
        void WalkThrough(Node * & T);
    
    };
    
    
    #endif /* BMT_H_ */

*  BTree.cpp文件的代码

#include"BTree.h"
    BTree::BTree() {
        this->head = NULL;
    }
    //结点中，查找关键字序列，是否存在k，私有方法
    int BTree::search(Node * & t,KeyType k) {
        int i = 0;
        for (int j = 1; j <= t->keynum; ++j) {
            if (t->key[j] <= k) {
                i = j;
            }
        }
        return i;
    }
    
    //遍历整个树，查找对应的关键字，公有方法，
    bool BTree::searchKey_BTree(KeyType k, Node * & recNode, int & recIdx) {
        if (!head) {
            //cerr << "树为空" << endl;
            return false;
        }
        Node * p = head;
        Node * q = NULL;
        bool found = false;
        int i=0;
        while (p && !found) {
            i = this->search(p, k); //记住i返回两种情况：第一种是找到对应的关键字
            //第二次是找到了最后一个小于k的关键字下标（主要作用与插入时）
            if (i > 0 && p->key[i] == k) {
                //找到了记录结点和结点中关键字的下标
                recIdx = i;
                recNode = p;
                return true;
            }//endif
            else {
                recNode = p;         // 记录p的值，方便返回
                recIdx = i;
                p = p->ptr[recIdx]; // 查找下一个结点，
            }//endelse
    
        }//endw
        return false;
    }
    //这是在结点的关键字序列中，插入一个而关键字，私有方法
    void BTree::insert(Node * & t, int i, KeyType k, Node * rhs) {
        //我们需要把关键字序列往后移动，然后插入新的关键字
        for (int j = t->keynum; j >= i + 1; --j) {
            t->key[j + 1] = t->key[j];
            t->ptr[j + 1] = t->ptr[j];
        }
        //插入新的关键字
        t->key[i + 1] = k;
        t->ptr[i + 1] = rhs;
        ++t->keynum;
    }
    
    //对对应的结点进行分裂处理,对t结点进行分裂处理，私有方法
    bool BTree::split(Node * & t, int s, Node * & rhs, KeyType & midk) {
        rhs = new Node;
        //rhs为新建的结点，用于保存右半部分的。
        if (!rhs) {
            overflow_error;
            return false;
        }
        //我们们把t分裂的，所以rhs是t的兄弟结点，有相同的父母
        rhs->parent = t->parent;
    
        //其中关键字序列的中间值为
        midk = t->key[s];
        t->key[s] = 0;
        //这个通过画图，就可以知道rhs的0号孩子的指针，就是t的s号结点指针
        rhs->ptr[0] = t->ptr[s];
    
        //如果原来的t的s号孩子指针，现在的rhs的0号孩子指针不为空，则需要改变孩子的的父亲结点
        if (rhs->ptr[0]) {
            rhs->ptr[0]->parent = rhs;
        }//endif
        t->ptr[s] = NULL;
        for (int i = 1; i <= m - s; ++i) {
            //现在是把右半部分全部复制到到rhs中
            rhs->key[i] = t->key[s + i]; t->key[s + i] = 0;
            rhs->ptr[i] = t->ptr[s + i]; t->ptr[s + i] = NULL;
            //理由和刚才的理由一样
            if (rhs->ptr[i]) {
                rhs->ptr[i]->parent = rhs;
            }//endif
        }//endfor
        rhs->keynum = m - s;
        t->keynum = s - 1;
        return true;
    }
    //新建一个新的结点，私有方法
    bool BTree::newroot(Node * & t, Node * & lhs, KeyType midk, Node * & rhs) {
        Node * temp = new Node;
        if (!temp) {
            overflow_error;
            return false;
        }
        temp->keynum = 1;
        temp->key[1] = midk;
    
        temp->ptr[0] = lhs;
        //左孩子不为空
        if (temp->ptr[0]) {
            temp->ptr[0]->parent = temp;
        }
        temp->ptr[1] = rhs;
        //右孩子不为空
        if (temp->ptr[1]) {
            temp->ptr[1]->parent = temp;
        }
        t = temp;
        return true;
    
    }
    //插入一个k（public方法）
    bool BTree::insert_BTree(KeyType k) {
        Node * curNode = NULL;
        int preIdx = 0;
        if (this->searchKey_BTree(k, curNode, preIdx)) {
            cout << "关键已经存在" << endl;
            return false;
        }
        else {
            //没有找到关键字
            KeyType curk = k;
            Node * rhs = NULL;
            bool finished = false;
            while (!finished && curNode) {
                //不管是否合法，直接先插入刚才找到的那个关键字序列中
                this->insert(curNode, preIdx, curk, rhs);
                if (curNode->keynum < m) {
        //满足条件，直接退出
                    finished = true;
                }
                else {
                    int s = (m + 1) / 2;  //s为中间值的下标
                    if (!this->split(curNode, s, rhs, curk)) {
                        //分裂失败，直接返回
                        return false;
                    }
                    if (curNode->parent == NULL) {
                        //如果curNode已经是根节点了，则可以直接退出了
                        break;
                    }
                    else {
                        //如果有那个父亲结点的话，此时curk指向的是原来这个结点中间值
                        //所以需要和父亲结点融合
                        curNode = curNode->parent;
                        preIdx = this->search(curNode, curk);
                    }
                }
            }
            //如果head为空树，或者根结点已经分裂为结点curNode和rhs了，此时是肯定到了
            //根结点了
            if (!finished && !this->newroot(head, curNode, curk, rhs)) {
                cerr << "failed to create new root" << endl;
                exit(EXIT_FAILURE);
            }
        }
    }
    
    //删除结点k，找到合适的结点（public方法）
    bool BTree::Delete_BTree(KeyType k) {
        Node * curNode = NULL;
        int curIdx = 0;
        if (this->searchKey_BTree(k, curNode, curIdx)) {
            this->Delete(curNode, curIdx);
            return true;
        }
        else {
            return false;
        }
    }
    
    //删除对应的进入结点，去删除关键字
    void BTree::Delete(Node * curNode, int curIdx) {
        //curIdx不合法法时，直接返回
        if (curIdx<0 || curIdx>curNode->keynum) {
            return;
        }
        while (true) {
        //这里的步骤不是很清楚，等下来讨论
            //此时说明我们是处于非叶子结点
            if (curNode->ptr[curIdx - 1] && curNode->ptr[curIdx]) {
    
                //使用右子树中最小的关键字替换对应当前的关键的，然后删除那个最小的关键字
                Node * p1 = curNode->ptr[curIdx];
                while (p1->ptr[0]) {
                    p1 = p1->ptr[0];
                }
                int res = p1->key[1];
                this->Delete_BTree(p1->key[1]);
    
                curNode->key[curIdx] = res;
    
                break;
            }
            else if (!curNode->ptr[curIdx - 1] && !curNode->ptr[curIdx])
            {   // is leaf
                for (int i = curIdx; i <= curNode->keynum; ++i) {
                    curNode->key[i] = curNode->key[i + 1];
                    // all ptr are NULL , no need to move.
                }//end for.
                --curNode->keynum;
                this->DeleteBalance(curNode);
                break;
            }
            else { //debug
                cerr << "Error" << endl;
            }
        }//endw
    }
    //删除对应关键字后，我们需要对删除后的树进行调整
    void BTree::DeleteBalance(Node * curNode) {
        int lb = (int)m / 2;  
        Node * parent = curNode->parent;
        while (parent && curNode->keynum < lb) {
        //说明删除了关键字后，原来的那个结点已经不
            //符合B-树的最小结点要求，这个不懂可以回去看看条件
            int idx = 0;
            //找到curNode在其父亲节点中的位置
            for (int i = 0; i <= parent->keynum; ++i) {
                if (parent->ptr[i] == curNode) {
                    idx = i;
                    break;
                }
            }
            Node * lsilb = NULL; Node * rsilb = NULL;
            if (idx - 1 >= 0) {
        //如果当前结点有左兄弟
                lsilb = parent->ptr[idx - 1];
            }
            if (idx + 1 <= parent->keynum) {
        //说明当前结点有右兄弟
                rsilb = parent->ptr[idx + 1];
            }
            //只要右兄弟存在，而且满足rsilb->keynum > lb，即是删除的调整的情况2
            if (rsilb && rsilb->keynum > lb) {
                this->RotateLeft(parent, idx, curNode, rsilb);
                break;
            }//如果右兄弟不满足，而左兄弟满足，同样可以
            else if (lsilb && lsilb->keynum > lb) {
                this->RotateRight(parent, idx, curNode, lsilb);
                break;
            }//如果左右兄弟都不满足，那就是情况3了，
            else {
                //合并到左兄弟，
                if (lsilb)
                    this->Merge(parent, idx, lsilb, curNode);
                else//没有左兄弟，合并到右兄弟
                    this->Merge(parent, idx + 1, curNode, rsilb);
                // potentially causing deficiency of parent.
                curNode = parent;
                parent = curNode->parent;
            }
        }
        if (curNode->keynum == 0) {
            // root is empty,此时树为空
            head = curNode->ptr[0];
            delete curNode;
        }//endif
    }
    void BTree::RotateLeft(Node * parent, int idx, Node * cur, Node * rsilb) {
        //这个是在右兄弟存在的情况下，而且满足rsilb->keynum > lb，则我们需要从把
        //右兄弟结点中的最小关键字移动到父亲结点，而父亲结点中小于该右兄弟的关键字的关键字
        //就要下移到刚刚删除的那个结点中。
    
        //父亲结点中某个结点下移
        cur->key[cur->keynum + 1] = parent->key[idx + 1]; 
        cur->ptr[cur->keynum + 1] = rsilb->ptr[0];  //
        if (cur->ptr[cur->keynum + 1]) {
            cur->ptr[cur->keynum + 1]->parent = cur;    
        }
        rsilb->ptr[0] = NULL;
    
        ++cur->keynum;
    
        parent->key[idx + 1] = rsilb->key[1];
        rsilb->key[idx] = 0;
        //右兄弟上移一个结点到父亲结点，
        for (int i = 0; i <= rsilb->keynum; ++i) {
        //删除最靠右的那个结点
            rsilb->key[i] = rsilb->key[i + 1];
            rsilb->ptr[i] = rsilb->ptr[i + 1];
        }
        rsilb->key[0] = 0;
        --rsilb->keynum;
    }
    void BTree::RotateRight(Node * parent, int idx, Node * cur, Node * lsilb) {
    
        //这个是在左兄弟存在的情况下，而且满足lsilb->keynum > lb，则我们需要从把
        //左兄弟结点中的最大关键字移动到父亲结点，而父亲结点中大于该左兄弟的关键字的关键字
        //就要下移到刚刚删除的那个结点中。
    
        //因为是在左边插入
        for (int i = cur->keynum; i >= 0; --i) {
        //因为左边的都比右边小，所以要插入第一个位置
            cur->key[i + 1] = cur->key[i];
            cur->ptr[i + 1] = cur->ptr[i];
        }
        //在第一个位置插入父亲结点下移下来的结点
        cur->key[1] = parent->key[idx];
        cur->ptr[0] = lsilb->ptr[lsilb->keynum];
    
        if (cur->ptr[0])
            cur->ptr[0]->parent = cur;
        lsilb->ptr[lsilb->keynum] = NULL;
        ++cur->keynum;
    
        // from lsilb to parent.
        parent->key[idx] = lsilb->key[lsilb->keynum];
        lsilb->key[lsilb->keynum] = 0;
        --lsilb->keynum;
    
    }
    void BTree::Merge(Node * parent, int idx, Node * lsilb, Node * cur) {
    
        //函数实现都是往lsilb上合并，首先是先把cur中的剩余部分，全部合到左兄弟中个，
        for (int i = 0; i <= cur->keynum; ++i) {
            lsilb->key[lsilb->keynum + 1 + i] = cur->key[i];
            lsilb->ptr[lsilb->keynum + 1 + i] = cur->ptr[i];
            if (lsilb->ptr[lsilb->keynum + 1 + i])
                lsilb->ptr[lsilb->keynum + 1 + i] = lsilb;
       }
        //然后再把父亲结点中的idx对应的内容添加到左兄弟
        lsilb->key[lsilb->keynum + 1] = parent->key[idx];
        lsilb->keynum = lsilb->keynum + cur->keynum + 1;
        delete cur;
        //然后更新我们的父亲结点内容
        for (int i = idx; i <= parent->keynum; ++i) {
            parent->key[i] = parent->key[i + 1];
            parent->ptr[i] = parent->ptr[i + 1];
        }//end for.
        --parent->keynum;
    }
    void BTree::Destroy(Node * & T) { //是否空间
        if (!T) { return; }
        for (int i = 0; i <= T->keynum; ++i)
            Destroy(T->ptr[i]);
        delete T;
        T = NULL;
        return;
    }
    void BTree::WalkThrough(Node * &T) {
        if (!T) return;
        static int depth = 0;
        ++depth;
        int index = 0;
    
        bool running = true;
    
        while (running) {
            int ans = 0;
            if (index == 0) {
                ans = 2;
            }
            else {
                cout << "Cur depth: " << depth << endl;
                cout << "Cur Pos: " << (void*)T << ";  "
                    << "Keynum: " << T->keynum << "; " << endl;
                cout << "Index: " << index << ";  Key: " << T->key[index] << endl;
    
                do {
                    cout << "1.Prev Key; 2.Next Key; 3.Deepen Left; 4.Deepen Right; 5.Backup  << endl;
                    cin >> ans;
                    if (1 <= ans && ans <= 5)
                        break;
                } while (true);
            }
    
    
            switch (ans) {
            case 1:
                if (index == 1)
                    cout << "Failed." << endl;
                else
                    --index;
                break;
            case 2:
                if (index == T->keynum)
                    cout << "Failed" << endl;
                else
                    ++index;
                break;
            case 4:
                if (index > 0 && T->ptr[index])
                    WalkThrough(T->ptr[index]);
                else
                    cout << "Failed" << endl;
                break;
            case 3:
                if (index > 0 && T->ptr[index - 1])
                    WalkThrough(T->ptr[index - 1]);
                else
                    cout << "Failed" << endl;
                break;
            case 5:
                running = false;
                break;
            }//endsw
        }//endw
    
        --depth;
    }
    Node * BTree::gethead() {
        return this->head;
    }

main.cpp文件的代码

#include"BTree.h"
    
    #define BMT_TEST
    #ifdef BMT_TEST
    //BMT: 10 45 24 53 90 3 37 50 61 70 100
    int main(void)
    {
        BTree t;
    
        int n;
        cout << "输入数的个数：" << endl;
        cin >> n;
        cout << "输入各个数的值：" << endl;
        for (int i = 0; i < n; i++) {
            int temp;
            cin >> temp;
            t.insert_BTree(temp);
        }
        Node * head = t.gethead();
        t.WalkThrough(head);
    
        int key;
        cout << "输入需要删除的值：" << endl;
        cin >> key;
        t.Delete_BTree(key);
        head = t.gethead();
        t.WalkThrough(head);
    
        return 0;
    }
    #endif

输入：

11
    10 45 24 53 90 3 37 50 61 70 100

输出：  
![这里写图片描述][SouthEast 19]

## 7、总结 ##

终于把B-树的代码写完了，写的我号辛苦啊，还是参考别人的代码才写出来的，参考链接如：  
[http://www.voidcn.com/blog/qq\_21555605/article/p-4869078.html][http_www.voidcn.com_blog_qq_21555605_article_p-4869078.html]  
只是，它的代码注释也太少了，而且有一些错误。

[B _B_ _B_ _R]: http://blog.csdn.net/v_JULY_v/article/details/6530142
[Binary Search Tree]: http://blog.csdn.net/qq_35644234/article/details/64516551
[Balanced Binary Search Tree]: http://blog.csdn.net/qq_35644234/article/details/66476853
[SouthEast]: /images/20220618/25fd9de176c6402990ddbeb84c95c1e9.png
[SouthEast 1]: /images/20220618/49729a32da1743b78ba6b15c6cce228d.png
[SouthEast 2]: /images/20220618/2a9db428dc4c46acbb44a42ada27e21b.png
[SouthEast 3]: /images/20220618/8fb02903cfe948f8b9e34caba1fca253.png
[SouthEast 4]: /images/20220618/fd1288d397444a27934740c85f841988.png
[SouthEast 5]: /images/20220618/20f67d8eb68a41fdb69b98686dcbf175.png
[SouthEast 6]: /images/20220618/042d4ca66ddd4cd6887ddae0a1e33ee8.png
[SouthEast 7]: /images/20220618/5a46c0bea1c947a8b3c4839ba33cf8f9.png
[SouthEast 8]: /images/20220618/45ac8c3e11194668a5823af130138574.png
[SouthEast 9]: /images/20220618/b590d50720dd429ab0ffa0fd40855793.png
[SouthEast 10]: /images/20220618/ecf844938355494786371ad65acdcfe5.png
[SouthEast 11]: /images/20220618/4e57867d85e8481db11fb941c572373c.png
[SouthEast 12]: /images/20220618/af9a769e73a14ec0a7e0e322d03e4aa8.png
[SouthEast 13]: /images/20220618/2e184ff280904a2abaaeb7887c0b306b.png
[SouthEast 14]: /images/20220618/7c66e92a858b498bbce811fe77f15fa8.png
[SouthEast 15]: /images/20220618/7397bb44adc041509b8716c6fac9050b.png
[SouthEast 16]: /images/20220618/e46da114b182469c8fac058f33ddc49c.png
[SouthEast 17]: /images/20220618/6231921f859a42199d90332d9384fcb8.png
[SouthEast 18]: /images/20220618/baca153c2e6a49369532d35103d40803.png
[SouthEast 19]: /images/20220618/e589868cf97842c8b7e0b5c88e3ae43e.png
[http_www.voidcn.com_blog_qq_21555605_article_p-4869078.html]: http://www.voidcn.com/blog/qq_21555605/article/p-4869078.html