程序员面试必考题（九）：B树和B+树的基本概念

来自微信公众号：开点工作室（kaidiancs）

1 B 树的基本概念

1970年Bayer等人提出一种多路平衡查找树，称为B树。它的定义如下：

一棵 m 阶B树或者为空，或者为满足下列性质的 m 叉树：

① 树中每个结点至多有m棵子树；

② 根结点至少有两棵子树；

③ 除根结点之外，每个结点至少有棵子树；

④ 所有叶结点都出现在同一层上；

⑤ 所有结点都包含如下形式的数据：

(n,A₀ ,K₁ ,A₁ ,K₂ ,A₂ , … ,K_n,A_n )

其中 n 为关键字的个数， K_i ( i=1, … , n ) 为关键字，且满足 K ₁<K ₂<…<K _n 。 A_i ( i=0,1, … , n ) 为指向子树根结点的指针，且对于 i=1,2, … , n-1， A_i 所指子树上各结点的一切关键字均大于 K_i ，而小于 K_i ₊₁ 。 A ₀ 所指子树上各结点的一切关键字均小于 K ₁ ， A_n 所指子树上各结点的一切关键字均大于 K_n 。对于叶结点，所有指针 A_i 皆为空。对于具有 n 个关键字的非叶结点，将有 n+1棵子树。

图1所示的是一棵5阶（m=5）B树。

当 m =3 时，每个结点中最多包含两个关键字、三个指针，最少时可以只含有一个关键字、两个指针，所以 3 阶 B 树又称为 2-3 树。

2 在m 阶B 树上进行查找

B树的结构保证了它是比较平衡的，每个结点的子树都不能过少，且从根到叶的路径长度都相同，这对于提高查找效率非常有利。

具体的查找方法与在二叉排序树中的查找方法类似。例如，在图1所示的树 T 上查找关键字 n 的过程是：首先从根开始，由于 e<n<p ，则应在位于 e 和 p 中间的指针所指的子树上进行查找；然后，又由于 l<n ，则应在 l 右边的指针所指的子树上进行查找；最后在含有 m 、 n 和 o 三个关键字的叶结点上查找成功。

在m阶B树上进行查找时，其比较次数与两个因素有关； ① 结点中关键字的数目（最多 m-1个，由于它们是有序的，当 m 较大时可以用折半查找方法）； ② 树的深度。现在假设共有 N 个关键字，且 m 已确定。含 N 个关键字的 m 阶B树的最大深度为，即平均查找长度对 N 来说也是对数级的。

3 在m 阶B 树上插入一个关键字

在m阶B树上插入一个关键字，其寻找插入位置的过程与查找失败的过程相同，待到在某个叶结点上找到相应的空指针后，不能像二叉排序树那样向下“伸出”一个新的叶结点，而要将待插入的关键字按次序加到原来的叶结点中。

若插入后该结点的关键字数目没超过 m-1，则插入完成；否则需将这个结点“分裂”为两个叶结点，并让叶结点中间位置的关键字提升到父结点中。如果因此而令父结点中关键字个数超限，则继续这个结点分裂及关键字提升过程。这个过程可能一直延续到根结点，即原来的根结点由于增加一个关键字而导致分裂，并由新提升的关键字构成新的根结点。这是树长高的唯一一种情况。

B树的生成过程就是一个个关键字的插入过程。

例2 一棵5阶B树的生成过程如图2所示。

对于一棵5阶B-树，按照其定义，每个结点中关键字个数最多为4个，最少为2个，相应地指针个数最多为5个，最少为3个。

a是要插入的第一个关键字，所以生成只含有a的根结点，它也是叶结点。接下来g、f、b三个关键字的插入比较简单，它们都插入在a所在的结点中。

再插入k后，由于这个结点已经含有5个关键字了，超出了最大限度，所以结点分裂，中间的关键字是f，提升到父结点中，即新创建一个结点，含有关键字f。其余的四个关键字分裂为两个结点，小于f的两个组成f的第一个孩子，大于f的两个组成f的第二个孩子。

接下来，d、h、m的插入都很简单。

关键字j的插入又将引起结点的分裂，中间关键字j提升至父结点中，与原来的f共同构成含有两个关键字的根结点。同时这个根结点所含的指针个数也增加一个，与原来f两侧的两个指针一起分别指向三个孩子结点。这三个孩子结点最左边的一个（含a、b、d）是原来的孩子结点，右侧的两个是由含g、h、k、m四个关键字的结点分裂而得到的。

e、s、i、r四个关键字的插入过程不再赘述。

x将插入在k、m、r、s组成的叶结点中，这又会导致结点的分裂。中间关键字r提升到父结点中。此时父结点中已含有3个关键字了。

c、l、n、t、u的插入不再赘述。

p将插入到k、l、m、n组成的结点中，导致m提升至根中。而根中已经含有4个关键字了，m的加入又使根必须分裂，中间关键字成为新的根结点。

至此，全部插入完成。

4 在m 阶B 树上删除一个关键字

若关键字位于分支结点上，与二叉排序树类似，选择该关键字的直接前驱或是直接后继来代替它的位置，进而删除其前驱或后继。而这个前驱或后继一定位于叶结点中，故只讨论删除B树叶结点中关键字的过程。

若删除关键字后，叶结点 v 中的关键字个数不少于-1个，则删除完毕；否则，需要调整B树。分以下几种情况讨论：

① 如果至少有一个兄弟结点（设为 u ）中含有的关键字个数多于-1，则可以从 u 结点中“借”过来一个关键字。假设 u 位于 v 的左侧，则将 u 中最大的关键字移至 u 、 v 的父结点 w 中， w 中指向 u 和 v 两个指针之间的关键字下移到 v 中。若 u 位于 v 的右侧，则将 u 中最小的关键字移至父结点 w 中， w 中指向 u 和 v 两个指针之间的关键字下移到 v 中。

② 与 v 相邻的兄弟结点中都没有多余的关键字可以借过来，即 v 的兄弟结点中的关键字个数都仅有-1个，此时需要进行结点的合并。设将与 v 进行合并的兄弟结点为 u ，将 u 、 v 合并为一个结点 x ，同时，父结点 w 中分别指向 u 、 v 的两个指针之间的关键字也下降到 x 中。 w 中关键字个数及指针个数同时减1。如果 w 中关键字个数也少于 -1了，则再递归处理父结点的情况，考察 w 的兄弟，看是否能“借”关键字或是需要与其兄弟结点进行合并。如果每次都需要进行结点的合并，最终将根结点中的唯一一个关键字下降，则树高减1，这是唯一使得树高减1的情况。