47 多路查找树：B树在数据库中的应用

你好，我是王健伟。

这节课我们来谈一谈多路查找树。传统的、用来搜索的二叉查找树有很多，比如平衡二叉树、红黑树等。

虽然通常情况下它们的查询性能很不错，但当数据量非常大的时候，它们却无能为力。因为当数据量非常大时，内存是很有限的，不可能把所有数据全部加载到内存中，大部分数据只能存放到磁盘上，只有需要的数据才会被加载到内存中。

通常来讲，计算机访问内存的速度要远远快于访问磁盘的速度，那么程序大部分的时间就会阻塞在磁盘IO上。所以尽量减少对磁盘的访问次数就是提高程序性能的关键。

那么，如何组织数据才能达到尽量减少对磁盘的访问次数的效果呢？一起来看一看B树。

B树的基本概念、定义及基础实现代码

B树也被称为多路平衡查找树，也称为B-树，这里的-并不是减号而是一个连字符。这里的多路可以理解为相对于二叉树而言，二叉树是二路查找树，因为最多只有两个子节点，所以查找时最多只有两条路。而B树有多条路（至少3条路），也就是说，B树的节点可以有多个子节点。

B树是一种组织和维护外存（磁盘上的文件）系统非常有效的数据结构，常用在数据库里，引入B树的主要目的就是减少磁盘的I/O操作。

因为平衡二叉树、红黑树等最小高度保持在$log_{2}^{{n}$附近，这意味着大部分针对平衡二叉树、红黑树的操作（查找、插入、删除等）的时间复杂度为O($log_{2}}}$)，如果树中的节点数据很多都是保存在磁盘上的，那么这里就可以将O($log_{2^{{n}$)理解成对磁盘的访问次数。显然，减少对磁盘的访问次数这件事就变得极其重要。对比来看，B树的高度不是$log_{2}}$，这意味着使用B树可以极大地减少对磁盘的访问次数。}$，而是一个可以控制的高度，一般这个高度会远小于$log_{2}^{n

换一种理解方式来说，平衡二叉树、红黑树每个节点只存储一个数据元素，或者说存储的数据量非常少，从而造成了这些树的高度显得非常高，也造成了对节点操作时间开销上的增加（比如查找某个节点之类的操作）。而B树每个节点可以存储多个数据元素，并且是一种多叉树，B树的节点可以有许多孩子，从几个到数千个。

B树的性质

通常描述一棵B树的时候，需要指定它的阶数（分叉数），我们把树中节点最大的孩子数目称为B树的阶，一棵m阶的B树或为一棵空树，或者是满足下面这些性质的m叉树。我来给你梳理一下。

关于节点个数

每个节点至多有m个子节点（m个分支/m叉）。比如对于3阶B树，每个节点至多有3个子节点，对于5阶B树，每个节点至多有5个子节点。
除根节点外，所有非叶节点至少有⌈m/2⌉（向上取整）个子节点。比如对于3或4阶B树，非根非叶节点至少要有2个子节点，对于5或6阶B树，非根非叶节点至少有3个子节点。

关于数据

每个节点至多有m-1个数据，每个数据也可以称呼为一个关键字。比如对于3阶B树，每个节点至多有2个数据，对于5阶B树，每个节点至多有4个数据。
根节点至少可以只有1个数据，其他节点至少有⌈m/2⌉-1个数据（键）。比如对于3阶或4阶B树，非根节点至少要有1个数据，而对于5阶或6阶B树，非根节点至少要有2个数据。

关于叶子节点

如果一个节点有子节点，则其子节点的数目一定比该节点的数据数目多1。
节点中数据左侧挨着的指针所指向的子节点中的数据都比该数据小，数据右侧挨着的指针所指向的子节点中的数据都比该数据大，这种数据排列类似于二叉查找树（参考下图1）。
所有叶子节点出现在同一层次上。换句话说，对于任何一个节点，其所有子树的高度都是相同的。

图1是一棵3阶B树：

在图1中，62左侧指针所指向的节点值为45，小于62，而值62和71之间夹着的指针所指向的节点值为69，正好位于值62和71之间，值71右侧指针所指向的节点值为78、411，都大于71。B树的各个子节点也遵循这样的数据大小规律。

我们看一个问题：一棵m阶B树所有节点共包含n个数据。看一看这棵B树的最小高度和最大高度分别是多少？

最小高度：若让该B树高度尽可能小，需要每个节点包含的数据数量尽可能多。

根据B树性质“每个节点至多有m-1个数据（有m个子节点）”我们来分析一下。

第1层为根节点（1个节点），第2层有m个节点，第3层有m*m，也就是$m^{{2}$个节点，以此类推，设该B树共有h层，则第h层有$m}$个节点。

因为每个节点有m-1个数据，所以这h层的B树一共有 (m-1)(1+m+$m^{2}$+$m$+…+$m^{{h-1}$)个数据。而1+m+$m}$+$m^{3}$+…+$m$)/(1-m)，将该公式代入 (m-1)(1+m+$m}$是个等比数列求和公式（有兴趣可以通过搜索引擎了解），该求和公式的结果为(1-$m^{h^{2}$+$m$+…+$m^{{h-1}$)，得到$m}$-1个数据。}$-1，意味着高度为h的B树最多有$m^{h

因为该m阶B树包含n个数据，这意味着n≤$m^{{h}$-1，则h≥$log_{m}}$。}$。即这棵B树的高度h最小也不会小于$log_{m}^{(n+1)

最大高度：也就是让这棵B树尽量高。这就需要让各节点包含的子节点数目或者说数据数目尽可能少。

这里需要用到B树的2个性质。一个是，除根节点外，所有非叶节点至少有⌈m/2⌉（向上取整）个子节点；另一个是，根节点至少可以只有1个数据，其他节点至少有⌈m/2⌉-1个数据。

为描述方便，我们设⌈m/2⌉=k，然后尝试分析。

第1层为根节点（1个节点），最少包含1个数据。第2层最少包含2个节点，即最少包含2(k-1)个数据。第3层最少包含2k个节点，即最少包含2k(k-1)个数据。第4层最少包含2$k^{{2}$个节点，即最少包含2$k}$(k-1)个数据。以此类推，设该B树共有h层，则第h层最少包含2$k^{{h-2}$个节点，即最少包含2$k}$ (k-1)个数据。

所以这h层的B树最少包含这么多个数据：1+2(k-1)+2k(k-1)+2$k^{{2}$(k-1)+…+2$k}$(k-1)= 1+2(k-1)(1+k+$k^{2}$+…+$k$)，这里1+k+$k^{2}$+…+$k$又是等比数列求和公式，将该公式代入1+2(k-1)(1+k+$k^{2}$+…+$k$)，得到1+2(k-1)( (1-$k^{{h-1}$)/(1-k))=1+2($k}$-1。}$-1)= 2$k^{h-1

因为该m阶B树包含n个数据，这意味着n≥2$k^{{h-1}$-1，则h≤($log_{k}}$)+1。}$)+1，即h≤($log_{⌈m/2⌉}^{((n+1)/2)}$)+1。也就是说这棵B树的高度h最大也不会大于 ($log_{k}^{((n+1)/2)

B树的实现代码

访问“可视化数据结构算法演示网站”页面并单击其中的“B Trees”链接，在其中就可以对B树中节点的插入、删除等操作进行演示，很直观，对你理解B树的常规操作非常有帮助。

基础实现代码如下：

//B树每个节点的定义
template <typename T, int M>//T代表数据元素的类型，M代表B树的阶
struct BTreeNode
{
    T   data[M]; //数据/关键字
    BTreeNode<T, M>* childs[M + 1]; //子节点指针数组
    BTreeNode<T, M>* parent;        //父节点指针
    int size;    //节点中实际数据的个数

    BTreeNode() //构造函数
    {
        size = 0;

        for (int i = 0; i < M; ++i)
        {
            data[i] = -1; //随便给个比较特殊的值-1，这样跟踪调试时也好观察和辨认。
        }
        for (int i = 0; i < (M + 1); ++i)
        {
            childs[i] = nullptr;
        }
        parent = nullptr;
    }
};
//B树的定义
template<typename T,int M>
class BTree
{
public:
    BTree()  //构造函数
    {
        root = nullptr;
    }
    ~BTree() //析构函数
    {
        ReleaseNode(root);
    }
private:
    void ReleaseNode(BTreeNode<T,M>* pnode)
    {
        if (pnode != nullptr)
        {
            for (int i = 0; i < (pnode->size + 1); ++i)
            {
                if (pnode->childs[i] != nullptr)
                {
                    ReleaseNode(pnode->childs[i]);
                }
            }
        }
        delete pnode;
    }
private:
    BTreeNode<T,M>* root; //树根指针    
    };

B树的插入操作及实现代码

在这里看一个B树节点插入的步骤（其实就是B树的创建步骤）。假如要按顺序给这些数据创建一棵4阶B树：11，12，6，5，13，7，3，4，2，1，9，8，10。

有两点值得说明：

根据前面描述的B树性质，4阶B树每个节点最少有1个数据，最多有3个数据。
新插入的数据总是会落在最底层的叶子节点上。

那么创建的步骤就会是下面这样。

因为当前并不存在B树，所以以11为根创建一棵B树。
插入12，因为12大于11，所以12位于11的右侧，与11共用一个节点。
插入6，因为6小于11，所以6位于11的左侧，与11、12共用一个节点。
插入5，因为5小于6，所以5位于6的左侧，此时注意，5、6、11、12共用一个节点。但因为4阶B树最多有3个数据，因此这个节点必须要进行拆分（分裂），拆分的原则是取这几个数据中间（⌈m/2⌉）的那个数据并作为根节点，剩余的数据分别做这个节点的左孩子和右孩子节点。对于5、6、11、12，一共是4个数据，⌈4/2⌉=2，因此取第2个数据6作为根节点（当然取第3个数据11也可以。因为当一个节点中包含偶数个数据比如4个数据时，中间的数据可以是第2个也可以是第3个），将数据5所代表的节点作为6的左孩子，将11、12这两个数据所代表的节点作为6的右孩子，如图2所示：

插入13，从根节点6开始，因为13大于6，因此沿着6的右指针向下找，找到11、12这个节点，因为13大于12，因此按照排列顺序，11、12、13三个数据被放到一起作为一个节点。
插入7，从根节点6开始，通过比较大小，将7、11、12、13这4个数据放到一起作为一个节点，因为4阶B树最多有3个数据，因此这个节点必须要进行拆分，将11作为根节点，将数据7所代表的节点作为11的左孩子，将12、13这两个数据所代表的节点作为11的右孩子。再将11这个节点并到数字6所代表的根节点中（因为根节点还不超过3个数据），注意因为11大于6，因此11排在6后面，如图3所示：

插入3，从根节点6、11开始，通过比较大小，将3放到5所在的节点中。
插入4，从根节点6、11开始，通过比较大小，将4放到3、5所在的节点中，注意顺序，现在3、4、5在一个节点中。
插入2，从根节点6、11开始，通过比较大小，将2放到3、4、5所在的节点中，该节点超过3个数据，所以进行拆分，将3作为根节点，将数据2所代表的节点作为3的左孩子，将4、5这两个数据所代表的节点作为3的右孩子。再将3这个节点并到6、11所代表的根节点中（因为根节点还不超过3个数据），注意因为3小于6也小于11，因此3排在6和11的前面，如图4所示：

插入1，从根节点3、6、11开始，通过比较大小，将1放到2所在的节点中，注意1排在2的前面。
插入9，从根节点3、6、11开始，通过比较大小，将9放到7所在的节点中，注意9排在7的后面。
插入8，从根节点3、6、11开始，通过比较大小，将8放到7、9所在的节点中，注意排列顺序是7、8、9，如图5所示：

插入10，从根节点3、6、11开始，通过比较大小，将10放到7、8、9所在的节点中，排列顺序是7、8、9、10，如图6所示：

7、8、9、10所在的节点超过3个数据，所以进行拆分，将8作为根节点，将数据7所代表的节点作为8的左孩子，将9、10这两个数据所代表的节点作为8的右孩子，如图7所示：

再将8这个节点并到3、6、11所代表的根节点中，此时根节点中数据的排列顺序是3、6、8、11，如图8所示：

因为4阶B树最多有3个数据，因此图8的根节点必须要进行拆分，将6作为根节点，将数据3所代表的节点作为6的左孩子，将8、11这两个数据所代表的节点作为6的右孩子，如图9所示：

通过前述的“可视化数据结构算法演示网站”继续插入数据14、15、16构造一棵4阶B树如下图10所示：

此时，向这个B树中插入数据17会怎样？

因为新插入的数据总是会落在最底层的叶子节点上，通过比较大小，数据17会被插入到14、15、16所在的节点并且放在数据16之后。如图11所示：

4阶B树最多有3个数据，因此14、15、16、17这个节点必须要进行拆分，将15作为根节点，将数据14所代表的节点作为15的左孩子，将16、17这两个数据所代表的节点作为15的右孩子。那么15这个数据摆在何处呢？要摆在15的父节点8、11、13中，并且根据大小关系是摆在这三个数据的后面。如图12所示：

节点8、11、13、15超过了3个数据，要继续拆分，将11作为根节点，将数据8所代表的节点作为11的左孩子，将13、15这两个数据所代表的节点作为11的右孩子，11这个节点摆在其父节点6中。如图13所示：

可以看到B树的创建或者说生长方向是从下到上的。在了解了B树的数据插入步骤后，就可以开始书写代码了。在BTree类模板的定义中，增加成员函数InsertElem、InsertDataIntoNode，参考课件。

为了能够将一个B树比较直观地显示出来以检测插入数据元素的代码是否书写正确，这里增加前面显示红黑树时用过的层序遍历接口levelOrder并稍加改造，完整的实现代码参考课件里的levelOrder成员函数。

在main主函数中加入代码：

BTree<int, 4> mybtree;
mybtree.InsertElem(11);
mybtree.InsertElem(12);
mybtree.InsertElem(6);
mybtree.InsertElem(5);
mybtree.InsertElem(13);
mybtree.InsertElem(7);
mybtree.InsertElem(3);
mybtree.InsertElem(4);

mybtree.InsertElem(2);
mybtree.InsertElem(1);
mybtree.InsertElem(9);
mybtree.InsertElem(8);
mybtree.InsertElem(10);

mybtree.levelOrder();

执行结果如下：

将上述结果与图9作比较，可以证明结果是正确的。

B树的删除操作及实现代码

B树的删除操作比B树的插入操作稍微复杂一些。我们首先明确一下B树每个节点有多少个数据。根据B树的性质，以一棵5阶B树为例：

一棵5阶B树，每个节点最多有4个数据。
根节点可以只有1个数据，非根节点至少有2个数据。

因为B树的删除操作实际和插入操作是相反的，所以先来回忆一下B树的插入操作，对于一棵5阶B树：

如果插入数据到某个节点而该节点原来的数据不够4个，则可以将数据直接插入到该节点。
如果插入数据到某个节点而该节点原来的数据已经达到了4个（上限），比如原来的数据为“50、60、70、80”，而要插入的数据是75，那么插入数据后这个节点的数据就变成“50、60、70、75、80”，这超过了5阶B树每个节点最多包含4个数据的上限，必须对这个节点进行拆分。⌈5/2⌉=3，因此取第3个数据70作为根节点，将50、60所代表的节点作为70的左孩子，将75、80所代表的节点作为70的右孩子，如图14所示：

好，现在我们再看一看B树的删除操作。插入数据时考虑的是B树中每个节点数据数量的上限，删除数据时考虑的是B树中每个节点数据数量的下限。具体看一看删除数据的两种情况：

所删除的数据位于终端节点（没有子节点的节点即叶子节点）之中。
所删除的数据位于非终端节点（有子节点的节点）之中。

如果所删除的数据位于非终端节点，则要转换成对终端节点中数据的删除，以图14中删除数据70为例：

找到70的前趋数据60。找法是找数据70所在节点的左子树最右侧的值，最终找到的60一定是终端节点。当然也可以找70的后继数据75（数据70所在节点的右子树最左侧的值）。
将60和70数据互换，此时70就位于终端节点中。
删除位于终端节点中的70。当然，删除后还要继续判断该节点中的数据数量，如果数据数量低于下限，还要继续进行节点合并处理。

所以，不管删除的数据是否位于终端节点，最终一定会转变成对终端节点中数据的删除。那么对终端节点中数据的删除，又分为两种情况。

以一棵5阶B树为例：

只要删除数据后节点中的数据数量不低于下限，就可以直接在该节点中将数据删除。比如一棵5阶B树非根节点要求至少有2个数据，如果被删除数据的节点不是根节点并且该节点在删除数据后剩余的数据数量不少于2个，则直接将数据删除即可。
如果将数据删除后节点的数据数量低于2，就会导致节点的合并，合并也是B树删除操作最繁琐之处。

关于兄弟节点数据的个数是否超过数量2，我们还是来分类讨论一下。

兄弟节点数据的个数超过2

如果兄弟节点数据的个数超过数量2，就可以从兄弟中借一个数据过来。借的方法采用“父子换位法”，如图15是一棵5阶B树。

现在要删除数据50，删除50后所在节点只剩余数据60，低于2个数据，此时观察兄弟节点（优先考察紧挨着的左侧兄弟节点，若不行再考察紧挨着的右侧兄弟节点），兄弟节点（12、15、23）数据个数超过2，可以从该兄弟节点采用“父子换位法”借一个数据，具体步骤是把父节点中的数据45放到数据50所在的节点，把左侧兄弟中最大值23拿出来放到父节点中，最终得到的B树如图16所示：

再看一看图17这棵5阶B树：

现在要删除图17中的数据50，删除50后所在节点只剩余数据60，低于2个数据，此时观察紧挨着的左侧兄弟节点，该节点只有2个数据，无法借数据，再观察紧挨着的右侧兄弟节点（80、90、100），数据个数超过2，可以从该兄弟节点采用“父子换位法”借一个数据，具体步骤是把父节点中的数据70放到数据50所在的节点，把右侧兄弟中最小值80 拿出来放到父节点中，最终得到的B树如图18所示：

兄弟节点数据的个数没超过2

如果兄弟节点数据的个数没超过数量2，就无法从兄弟中借数据。此时，被删除了数据的节点就会和兄弟节点、父节点进行合并（这其实就是插入数据的逆向操作）。如图19这棵B树：

如果删除数据55，则该节点只剩余数据56，这就不满足5阶B树非根节点至少有2个数据的要求。于是，兄弟节点21、23，节点56，以及父节点中的数据43合并成了一个新的节点，最终得到的B树如图20所示：

再看一看图21这棵5阶B树：

现在要删除图21中的数据56，于是，兄弟节点88、99，节点43，以及父节点中的数据65合并成了一个新的节点，最终得到的B树如图22所示：

不难发现，这种合并必然会导致父亲节点的数据数量减少1个：

如果父亲节点是根节点并且根节点的数据数量减少至0个，那么就需要删除原来的根节点，将合并后的新节点作为根节点。
如果父节点不是根节点，那么如果该父节点的数据数量减少1个导致低于2个数据，那么就继续以该父节点为中心，采用“从兄弟节点借数据”或者“和兄弟节点、父节点进行合并”的方式来处理该节点。如此反复。

重点提醒，因为实现代码有一定复杂性，所以在阅读实现代码或者自己书写和调试实现代码时，我强烈建议利用前面介绍过的算法网站，然后删除其中的某个节点，观察删除步骤，利用这种方法，更容易读懂现有代码或书写出正确的代码。例如，可以用下面的代码构造一棵5阶B树。

BTree<int, 5> mybtree;
for(int i = 1; i <= 35; ++i)
    mybtree.InsertElem(i);

同时，我们将这棵5阶B树创建在上述的算法网站中，如图23所示：

现在，删除数据19，看一看删除步骤：

删除19后，该节点只剩余了1个数据20，这违反了B树规则（5阶B树非根节点必须至少包含2个数据）。但是兄弟节点也只有两个数据所以无法从兄弟节点借数据，只能与兄弟节点、父节点进行合并。也就是说，删除数据19后，数据20所在节点、数据22、23所在节点以及数据21、24代表的父节点会进行合并，如图24所示：

合并后的情形如图25所示，此时数据20、21、22、23组成了一个新节点，尤其要注意的是数据21也被并入到该新节点中。

现在的问题是，原来由于数据21、24组成的节点因为数据21被合并导致只剩余了数据24，该节点只剩余了1个数据，违反了B树规则。因为无法从兄弟节点借数据，于是与兄弟节点（数据12、15所在节点）、父节点（数据9、18、27所在节点）进行合并，合并后的情形如图26所示。

图26中，数据12、15、18、24组成了一个新节点，尤其要注意的是数据18也被并入到该新节点中而且数据18右侧的指针指向的孩子节点是图25中数据24左侧指针指向的孩子节点，这种指针指向的调整在代码中都要细心实现，否则写出的代码就会产生错误。
在了解了B树的数据删除步骤后，就可以开始书写代码了。在BTree类模板的定义中，增加DeleteElem成员函数，参考课件。

在main主函数中，注释掉以往代码，增加如下代码测试数据删除操作：

BTree<int, 6> mybtree;
for(int i = 1; i <= 30; ++i)
    mybtree.InsertElem(i);
mybtree.levelOrder();
mybtree.DeleteElem(20);
cout << endl;
mybtree.levelOrder();

执行结果如下：

希望你多进行测试，测试的数据越多，越可能找到程序编写中的错误，从而使编写的代码尽量正确。我在编写代码中向B树中连续增加了近70个数据时才发现了代码中存在的一些不容易被觉察的错误。

小结

本节我带你详细学习了多路查找树中的B树。考虑到内存的有限性，要处理的数据不可能全部保存在内存中，绝大部分还是要保存在磁盘上，但磁盘的访问速度相对内存来讲又慢得多。那么，如何组织数据来尽量减少对磁盘的访问次数从而提高对数据的访问效率，就变得非常重要。这也是引入B树这种数据结构来组织数据的初衷。

B树是一种组织和维护外存（磁盘上的文件）系统非常有效的数据结构，常用在数据库中，引入B树的主要目的是减少磁盘的I/O操作。B树是一种多叉树，其节点可以有许多孩子，从几个到数千个。

由此，我们引出了B树的性质，理解即可。我为你详细地描述了B树的插入和删除操作并提供了相关的实现代码。B树的插入操作主要是要处理好节点的拆分问题，删除操作是插入操作的逆向操作，主要是要处理好节点的合并操作。注意好这几点，就已经事半功倍了。

思考题

请尝试分析一下B树与红黑树之间有哪些异同，并阐述各自的适用场合。
请绘制一棵高度为3的5阶B树，树的节点数据可以自行决定。

欢迎你在留言区和我交流，如果觉得有所收获，也也可以把课程分享给更多的朋友一起学习。我们下节课见！

精选留言（1）

Tiger 👍（1） 💬（0）
老师您好，按照B树的定义，M阶的B树每个节点至多有M个子节点，每个节点至多有M-1个关键字，所以在节点的定义中，childs数组的大小应该是M，data数组的大小应该是M-1
2023-10-10