7.5 B 树与 B+ 树

m 阶 B 树的定义与高度范围，插入时的分裂、删除时的借位与合并，以及 B+ 树与 B 树的区别。

B 树的定义

B 树，又称多路平衡查找树，B 树中所有结点的孩子个数的最大值称为 B 树的阶，通常用 $m$ 表示。一棵 $m$ 阶 B 树或为空树，或为满足如下特性的 $m$ 叉树：

B 树的高度

由下面的分析可知，B 树中的一个结点访问一次磁盘，因此查找的磁盘存取次数与 B 树的高度成正比。一般所说的 B 树高度不包括最后的不带任何信息的叶结点所处的那一层。若 $n \ge 1$，则对任意一棵包含 $n$ 个关键字、高度为 $h$、阶数为 $m$ 的 B 树：

例如，假设一棵 3 阶 B 树共有 8 个关键字，则其高度范围为 $2 \le h \le 3.17$，取整数即 $2 \le h \le 3$。

B 树的查找

在 B 树上进行查找与二叉查找树很相似，只是每个结点都是多个关键字的有序表，在每个结点上所做的不是两路分支决定，而是根据该结点的子树所做的多路分支决定。

B 树的查找包含两个基本操作：① 在 B 树中找结点（在磁盘上进行）；② 在结点内找关键字（在内存中进行，可采用顺序查找法或折半查找法）。

B 树的插入

与二叉查找树的插入操作相比，B 树的插入操作要复杂得多。将关键字 key 插入 B 树的过程如下：

分裂的方法：取一个新结点，在插入 key 后的原结点，从中间位置 $\lceil m/2 \rceil$ 将其中的关键字分为两部分，左部分包含的关键字放在原结点中，右部分包含的关键字放到新结点中，中间位置 $\lceil m/2 \rceil$ 的结点插入原结点的父结点。若此时导致其父结点的关键字个数也超过了上限，则继续进行这种分裂操作，直至这个过程传到根结点为止，进而导致 B 树高度增 1。

在”再删除”输入框中填入关键字（例如 80 49），即可在插入完成后继续观察删除过程。

B 树的删除

B 树中的删除操作与插入操作类似，但要更复杂一些，即要使得删除后的结点中的关键字个数 $\ge \lceil m/2 \rceil - 1$，因此将涉及结点的”合并”问题。

当被删关键字 k 不在终端结点（最低层非叶结点）中时，可以用 k 的前驱（或后继）k′ 来替代 k，然后在相应的结点中删除 k′，关键字 k′ 必定落在某个终端结点中，则转换成了被删关键字在终端结点中的情形。

当被删关键字在终端结点中时，有下列三种情况：

1. 直接删除关键字：若被删除关键字所在结点删除前的关键字个数 $\ge \lceil m/2 \rceil$，表明删除该关键字后仍满足 B 树的定义，则直接删去该关键字；
2. 兄弟够借：若被删除关键字所在结点删除前的关键字个数 $= \lceil m/2 \rceil - 1$，且与此结点相邻的右（或左）兄弟结点的关键字个数 $\ge \lceil m/2 \rceil$，则需要调整该结点、右（或左）兄弟结点及其双亲结点（父子换位法），以达到新的平衡；
3. 兄弟不够借：若被删除关键字所在结点删除前的关键字个数 $= \lceil m/2 \rceil - 1$，且此时与该结点相邻的左、右兄弟结点的关键字个数都 $= \lceil m/2 \rceil - 1$，则将关键字删除后与左（或右）兄弟结点及双亲结点中的关键字进行合并。

在合并过程中，双亲结点中的关键字个数会减 1。若其双亲结点是根结点且关键字个数减少至 0（根结点关键字个数为 1 时，有 2 棵子树），则直接将根结点删除，合并后的新结点成为根；若双亲结点不是根结点，且关键字个数减少到 $\lceil m/2 \rceil - 2$，则又要与它自己的兄弟结点进行调整或合并操作，并重复上述步骤，直至符合 B 树的要求为止。

B+ 树

B+ 树是应数据库所需而出现的一种 B 树的变形树。一棵 $m$ 阶 B+ 树需满足下列条件：

1. 每个分支结点最多有 $m$ 棵子树（孩子结点）；
2. 非叶根结点至少有两棵子树，其他每个分支结点至少有 $\lceil m/2 \rceil$ 棵子树；
3. 结点的子树个数与关键字个数相等；
4. 所有叶结点包含全部关键字及指向相应记录的指针，叶结点中将关键字按大小顺序排列，并且相邻叶结点按大小顺序相互链接起来（支持顺序查找）；
5. 所有分支结点（可视为索引的索引）中仅包含它的各个子结点（即下一级的索引块）中关键字的最大值及指向其子结点的指针。

B 树与 B+ 树的区别

即时练习