B树-一一网

B树的简介

B树是一种平衡的多路搜索树，多用于文件系统、数据库的实现。

B树，B-tree，B-树都是等价的。

对于B树，m阶B树中的 m阶的值是整个 B树中取节点的最大的度。

观察上面几个B树，可以发现一些共同的特点：

1 个节点可以存储超过 2 个元素、可以拥有超过 2 个子节点；
拥有二叉搜索树的一些性质；
平衡：每个节点的所有子树高度一致；
比较矮。

m 阶 B树的性质（m≥2）

假设一个节点存储的元素个数为 x：

节点是根节点：1 ≤ x ≤ m − 1
节点是非根节点：┌ m/2 ┐ − 1 ≤ x ≤ m − 1

┌ ┐ 表示向上取整，即 ceiling 的意思

如果该节点有子节点，子节点个数 y = x + 1
根节点：2 ≤ y ≤ m
非根节点：┌ m/2 ┐ ≤ y ≤ m

比如 m = 3，2 ≤ y ≤ 3，因此可以称为（2, 3）树、2-3树
比如 m = 4，2 ≤ y ≤ 4，因此可以称为（2, 4）树、2-3-4树

特殊的情况，当 m = 2时，即二叉搜索树。

数据库中是用 B树，m取值一般是 200 ~ 300。

B树和二叉搜索树的对比

B树和二叉搜索树，在逻辑上是等价的。
多代节点合并，可以获得一个超级节点。
2代合并的超级节点，最多拥有 4 个子节点（至少是 4阶B树）；
3代合并的超级节点，最多拥有 8 个子节点（至少是 8阶B树）；
n代合并的超级节点，最多拥有 2n个子节点（至少是 2n阶B树）；

m阶B树，最多需要 log2m 代合并。

B树的常见操作

B树的查找

跟二叉搜索树的搜索类似，B树的查找思路如下：

先在节点内部从小到大开始搜索元素；
如果命中，搜索结束；
如果未命中，再去对应的子节点中搜索元素，重复步骤 1。

如下图 4阶B树，查找元素 51：
1）先在根节点内部查找元素，比较大小 51 > 39，进入 39 的右子树进行查找；
2）在节点（59，79，94）内部查找，51 < 59，进入该节点的左子树进行查找；
3）在节点（49，51，54）内部查找，51 > 49，查找节点内部的下一个值，在该节点内部找到 51 == 51，找到元素，查找结束。

B树的添加

新添加的元素必定是添加到叶子节点。

在插入的叶子节点位置，根据当前叶子节点元素个数分为两种情况：
对于m阶B树：
1）该结点中元素个数小于 m-1 ，则直接插入即可。
2）若该结点中元素个数个数等于 m-1，则将引起结点的分裂。需要做额外的操作，具体操作稍后分类分析。

下面就上面两种情况进行相应分析：

节点中元素个数小于 m-1 ，则直接插入即可。
如下图所示：

节点中元素个数个数等于 m-1，上溢。

上溢是指，在插入元素是，元素插入某个节点后，导致该节点内的元素个数超出了B树限制的节点内元素最大个数。

如下图的 3阶B树，插入元素 90，插入到节点Z 之后，节点Z 的元素个数此时为 3，超过了 3阶B树限制的节点内元素个数上限 2（即：3 – 1）。此时上溢。

添加导致的上溢的解决方案
上溢节点的中间元素向上合并，并将中间元素的左右两部分分裂为上移合并元素的左右节点
具体拆分步骤如下：
首先：上溢节点的元素个数必然等于 m，m 为 B树的阶数值；
假设上溢节点最中间元素的位置为 k；
将 k 位置的元素向上与父节点合并；
将 k 位置的元素分裂成 2 个子节点；并让这两个子节点成为上移元素的元素的子节点。

这 2 个子节点的元素个数，必然都不会低于最低限制（┌ m/2 ┐ − 1）

一次分裂完毕后，有可能导致父节点上溢，最极端的情况，有可能一直分裂到根节点。

每一个上溢节点都按照上面的步骤进行处理，最终完成恢复。

同样以上面的 3阶B树插入元素 90 的流程：

查询 90 应该插入的节点位置，在节点Z（85, 95）之间；
判断插入元素的节点的元素个数，节点Z 本来已经有两个元素（对于3阶B树：2 = 3 – 1），插入之后已经超过了其限制元素的个数（3 – 1 = 2），此时出现了上溢；
上溢节点（节点Z），中间元素 90 向上与父节点合并，同时将向上合并之前的 90 的子节点 85、95 分类为上移合并之后的 90 的子节点；
90 上移合并之后的节点 Y此时元素个数 3（3 > 3 – 1），同样超过了了其限制元素的个数，导致了上溢。对节点Y的中间元素 75 向上与父节点（图中根节点35）合并，即重复步骤三的操作；
最终分裂到根节点，完成添加上溢的问题，恢复成一个 3阶B树。

整个流程如下图所示：

B树的删除

B树元素的删除，可以分类两大类，删除元素所在节点为叶子节点和非叶子结点。

删除元素在叶子节点上

若原叶子节点元素个数大于 ceil(m/2) - 1（即删除一个之后仍 >= ceil(m/2) - 1）则直接删除元素;
若原叶子节点元素个数小于等于 ceil(m/2) - 1（即删除一个之后 < ceil(m/2) - 1）:
2.1 兄弟节点元素个数大于 ceil(m/2) - 1，则：父节点中一个元素下移，同时该兄弟节点中一个元素上移到父节点，删除完成
2.2 兄弟节点元素个数小于等于 ceil(m/2) - 1，则：父节点中一个元素下移，并将下移的元素和当前节点以及当前节点的兄弟节点的元素进行合并，形成一个新节点，原父结点中的元素的两个孩子指针就变成了一个孩子指针，指向这个新结点。此时原父节点的元素下移后，原父节点同样可能出现下溢，需要继续上面操作，直至恢复位置。

删除元素在非叶子节点上

使用后继元素替换掉要删除的元素的值，然后删除后继元素所在的节点中删除后继元素（类似于二叉搜索树删除结点），这个时候就转化成了上面删除元素在叶子节点上的情况。

下面通过示例分别展示上面几种情况的删除处理过程：

删除元素在叶子节点，且原叶子节点元素个数 > ceil(m/2) - 1：
如下图上面部分 4阶B树，删除元素 11（叶子节点，且节点元素个数 3 > ceil(4/2) - 1），所以直接删除元素 11 即可（如下图下面面部分）。

删除元素在叶子节点上，且原叶子节点元素个数 <= ceil(m/2) - 1，同时兄弟节点元素个数 > ceil(m/2) - 1。

如下图 4阶B树
下图左上部分，删除元素 5，删除之后该节点元素个数为 0，小于下限 1（ceil(4/2) - 1），此时其右边兄弟节点个数 3（大于ceil(4/2) – 1），父节点中元素 7 下移到当前节点，同时其右边兄弟节点中元素 9 上移到父节点，如下图中的左下部分。
最终展示结果如下图右半部分。