经典搜索算法之B树与B+树

女爷i 2022-05-16 07:20 186阅读 0赞

## 1.B树     ##

在笔者[上篇文章][Link 1]中，我们说到二叉查找树的时间复杂度最好情况为![O(log\{n\})][O_log_n]，最差情况为![O(n)][O_n]。最差情况是所有的数据全部在一端时，那怎样避免出现这种情况，让二叉查找树所有查找的时间复杂度均为![O(log\{n\})][O_log_n]呢，为了达到这一目标，我们需要让二叉查找树保持平衡，不能将结点全部聚集在某一端。为了保证查找树的平衡，我们需要一些灵活性，因此在这里我们允许树中的一个结点可以保存多个数值。比如：

![70][]

如上图中，22左边的孩子都比22小，而其左边孩子13，17按顺序排放，中间的孩子在22和35之间，右边的孩子比35大。

如上图所示的树称为B树(或B-树、B\_树)，它是一种m阶平衡多叉树。当m取2时，便是二叉搜索树，其中m指的是一个结点最多有多少个孩子结点。

对于m阶B树，其具有如下性质：

1.  根结点至少有两个子女；
2.  每个结点的值的个数为 1 <= n < m；
3.  所有的叶子结点都位于同一层；
4.  除根结点以外的所有结点（不包括叶子结点）的孩子正好是值个数的加1；
5.  每个结点中的值都按照从小到大的顺序排列，每个值的左子树中的所有的值都小于它，而右子树中的所有的值都大于它。

下面来看一个更加清晰的B树：

![70 1][]

上图为3阶B树，在实际应用中的B树的阶数m都非常大（通常大于100），所以即使存储大量的数据，B树的高度仍然比较小，这有利于树的插入删除。在数据库中我们将B树（和B+树）作为索引结构，可以加快查询速速。

**      B树的插入**

如果插入的结点只有一个数值，直接在该结点插入即可。例如，在上图中插入9，则直接在10结点前面插入9即可。但如果插入44，此时便需要通过结点的向上分裂来完成插入。

插入44：

![70 2][]

发现此结点有3个值，不满足3阶B树，因此要进行分裂，将中间的40向上结点移动：

![70 3][]

分裂后此B树变成了4阶B树，不满足3阶B树条件，原因是40移动到上结点所致，因此继续向上结点移动，将50移动到上节点：

![70 4][]

此时发现又出现3个值的结点，继续进行分裂：

![70 5][]

此时便满足条件，完成。

B树的删除按照插入的方法反过来操作即可，即父结点(如果不符合父结点大于左结点小于右结点的条件，则与上层父节点位置调换，直到符合条件为止)不断下移合并，知道符合条件为止。

## 2、B+树 ##

B+树是B树的一种变体，有着比B树更高的查询性能，B+树和B树除了有一些共同特点外，还有一些新的特点：

1.  有k个子树的**中间结点**包含有k个元素（B树中是k-1个元素），每个元素不保存数据，只用来索引，所有数据都保存在叶子节点。
2.  所有的叶子结点中包含了全部元素的信息，及指向含这些元素记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。
3.  所有的中间结点元素都同时存在于子节点，在子节点元素中是最大（或最小）元素。

下面我们使用数值来表示一棵B+树：

![70 6][]

由上图可以看到，B+树的每个结点的最大或最小元素都出现在下一个结点的首或尾。在B+树中，只有叶子节点存储数据，其它中间结点全部是索引。在数据库的聚集索引中，叶子节点直接包含数据库中某一行数据。在非聚集索引中，叶子节点带有指向数据库行的指针。

**B+树的查找**

B+树的查找有两种方式：从最小值进行顺序查找；从根结点开始，进行随机查找。在查找时，若非终端结点上的关键值等于给定值，并不终止，而是继续向下直到叶子结点（因为叶子结点才存数据）。因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。其余同B-树的查找类似。

由于B+树的数据都存储在叶子结点中，分支结点均为索引，方便扫库，只需要扫一遍叶子结点即可，但是B树因为其分支结点同样存储着数据，我们要找到具体的数据，需要进行一次中序遍历按序来扫，所以B+树更加适合在区间查询的情况，所以通常B+树用于数据库索引，而B树则常用于文件索引。

**B+树的插入**

![70 7][]

**假设我们要向上图插入0，发现没有破坏B+树结构，直接在1，2结点处插入即可。**

**如果在结点的中间插入并破坏了B+树的结构：**

但是如果我们要插入12，则发现破坏了B+树的结构，则：

![70 8][]

分裂破坏了结构的结点，并将12移到上结点：

![70 9][]

插入完毕。

**如果在端点处插入并破坏了B+树的结构：**

假如插入16：

![70 10][]

分裂后，父结点要配合子结点的端点值：

![70 11][]

删除操作，只需将插入操作进行反向操作即可。读者可以想想如何删除16。

**B+数的优势：**

1.  单一节点存储更多的元素，使得查询的IO次数更少。（应用于文件系统、数据库系统）
2.  所有查询都要查找到叶子节点，查询性能稳定。
3.  所有叶子节点形成有序链表，便于范围查询。

[Link 1]: https://blog.csdn.net/m0_38075425/article/details/81745544
[O_log_n]: https://private.codecogs.com/gif.latex?O%28log%7Bn%7D%29
[O_n]: https://private.codecogs.com/gif.latex?O%28n%29
[70]: /images/20220516/7259de21fc4f419495a0aed36f74077f.png
[70 1]: /images/20220516/eae2920602984d399e07928d0ebc1b60.png
[70 2]: /images/20220516/0ab5606908384a429226dfa070a482af.png
[70 3]: /images/20220516/c9c041054c7c48d4ac7db6bfd2bd73ec.png
[70 4]: /images/20220516/36c862525c7d40ad8ae1a7a7ee4a78f7.png
[70 5]: /images/20220516/0bb342bc5090431792e4ddc748565a4b.png
[70 6]: /images/20220516/4ddce148f9264d7fb00c78d966307997.png
[70 7]: /images/20220516/70c4990b25ab40a0a1c80697ffef35f4.png
[70 8]: /images/20220516/a2f8b80f78dc4ed495247e904cf8fe8e.png
[70 9]: /images/20220516/df878b1e923e4c10819bb620046019f9.png
[70 10]: /images/20220516/c18d16ceefb644c394deb5a91aab342a.png
[70 11]: /images/20220516/7be4126cce2640e4943b0274459e6899.png