7.11.B树

一.前言：

回顾二叉排序树（英文缩写BST，又名二叉查找树），详情见"7.5.二叉排序树(英文缩写为BST，又名二叉查找树)"。

以上述图片为例，

在二叉排序树中查找目标关键字，

如果要查找的目标关键字比当前结点的值更小，那么会往左子树这边查找，

如果要查找的目标关键字比当前结点的值更大，那么会往右子树这边查找，

所以二叉排序树就是用一个关键字把一个有可能存在目标关键字的数域分割成了两份，

比如初始的搜索范围是(-∞,+∞)，上述图片中二叉排序树的根结点为29，第一次查找把(-∞,+∞)分成了(-∞,29)和(29,+∞)，

现在的问题是能否把二叉排序树变成m叉排序树(又名m叉查找树)，

显然可以。

二.5叉排序树：

1.特点：

如上图，

给出的是一个5叉排序树(又名5叉查找树)，虽然拓展到5叉排序树，但是原理和二叉排序树类似，

5叉排序树中1个结点最少包含1个关键字、2个分叉，因为1个关键字会把1个查找区间分割为两个部分，所以会有两个分叉；

5叉排序树中1个结点最多包含4个关键字、5个分叉，4个关键字可以把查找区间分割为五个部分。

注：1个结点内的关键字必须是有序的，要么递增、要么递减。

2.实例：

比如第一个根结点中有一个元素22，

如果当前要查找的元素的值比22小，就应该到当前结点的左子树中继续查找；

如果当前要查找的元素的值比22大，就应该到当前结点的右子树中继续查找，

假设现在要查找的元素的值比22大，那么接下来要到22的右子树中查找，在22的右子树中可以找到的数值是在(22,+∞)，

22的右孩子中出现了关键字36、45，相当于把(22,+∞)拆分了，拆分为(22,36)、(36,45)、(45,+∞)。

36结点的右孩子和45结点的左孩子组成的孩子结点范围为(36,45)。

3.失败结点：

上述图片中的紫色结点就是失败结点，

比如结点15右孩子上的失败结点的范围是(15,22)，如果要查找的关键字落在了(15,22)，那最终就会落入失败结点(15,22)，意味着查找失败，

再看结点40的左孩子上的失败结点的范围是(36,40)，如果要查找的关键字落在了(36,40)，那最终就会落入失败结点(36,40)，意味着查找失败。

三.5叉排序树的查找：

1.查找成功：

以上述图片为例，

现在查找目标关键字9，从根结点出发，根结点中保存的关键字只有22，显然9比22小，所以如果9存在的话，那么只能到22的左子树中查找，因此会到包含关键字5、11的结点中，

如下图：

如上图，

接下来会顺序扫描包含关键字5、11的结点，

第一个关键字5比9更小，所以会检查下一个关键字11，

第二个关键字11比9更大，所以如果目标关键字9存在的话只可能在11的左孩子中，

因此会到包含关键字6、8、9的结点中进行查找，

如下图：

如上图，

接下来会顺序扫描包含关键字6、8、9的结点，

第一个关键字6比9更小，所以会检查下一个关键字8，

第二个关键字8比9更小，所以会检查下一个关键字9，

第三个关键字9等于要查找的目标关键字9，意味着查找成功，

如下图：

如上图，

查找一个结点中的每一个关键字，可以用顺序查找，也可以用折半查找，

这是因为一个结点中的关键字是有序排列的，如果一个结点中包含的关键字比较多，那么就可以用折半查找的方法进行优化。

2.查找失败：

以上述图片为例，

现在查找目标关键字41，从根结点出发，根结点中保存的关键字只有22，显然41比22大，所以接下来会让指针右移指向下一个关键字，此时指针指向NULL，所以如果41存在的话，那么只能到22的右子树中查找，因此会到包含关键字36、45的结点中，

如下图：

如上图，

接下来会顺序扫描包含关键字36、45的结点，

第一个关键字36比41更小，所以会检查下一个关键字45，

第二个关键字45比41更大，所以如果目标关键字41存在的话只可能在45的左孩子中，

因此会到包含关键字40、42的结点中进行查找，

如下图：

如上图，

接下来会顺序扫描包含关键字40、42的结点，

第一个关键字40比41更小，所以会检查下一个关键字42，

第二个关键字42比41更大，所以如果目标关键字41存在的话只可能在42的左孩子中，

如下图：

如上图，

此时达到了紫色的失败结点，意味着查找失败。

这里虽然标出了紫色的失败结点，实际上指向紫色的失败结点的指针为NULL。

四.如何保证查找效率：尽可能地让m叉查找树矮、胖

1.规定一：变矮

如上图，

如果每个结点中只保存一个关键字，也就是1个结点只有2个分叉，此时就是二叉查找树，

这种情况下由于每个结点中关键字太少，所以如果关键字总数相同的话，此时的树会变高，查找树越高，意味着要查找更多层结点，导致效率低，

所以对于5叉查找树，该怎么保证查找效率？

• 规定一(策略)：m叉查找树中，规定除了根结点外，任何结点至少有⌈m/2⌉个分叉，即至少含有⌈m/2⌉-1个关键字

所以可以规定在5叉查找树中，除了根结点外，其他任何一个结点至少有⌈5/2⌉=3(向上取整)个分叉，即至少含有2个关键字，这样的规定可以保证5叉查找树每一个结点中的关键字个数不会太少，也就可以保证这棵树不会很高即层数不会太多，相应的查找效率也会提高。

疑问：为什么规定"除了根结点外"？根结点也保证至少有⌈5/2⌉=3(向上取整)个分叉，即至少含有2个关键字不好吗？

如下图：

如上图，

实际上不是不好，而是做不到，

比如5叉查找树中刚开始只有1个关键字22，这种情况下5叉查找树只有1个根结点，

而且这个根结点中只有1个关键字，所以这种情况下根结点只有2个分叉，没办法保证根结点会有3个以及3个以上的分叉，所以根结点是例外。

2.规定二：变胖

如上图，

上述图片的5叉查找树是否优秀？

虽然满足了5叉查找树中，除了根结点外，其他任何一个结点至少有⌈5/2⌉=3(向上取整)个分叉，即至少含有2个关键字，

但并不优秀，结合二叉查找树的知识，不难想到这棵5叉查找树最大的问题是不平衡。

如何理解m叉查找树不平衡？就是一个结点的各个子树高度相差很大，这种不平衡的特性显然也会导致5叉查找树变得很高，相应的会导致查找过程中要查很多层结点，从而使得查找效率降低。

所以这个问题该怎么解决呢？回想二叉查找树是如何解决的，在二叉查找树中规定每一个结点的左、右子树的高度之差不超过1，这样就保证了二叉查找树的平衡，

现在把这样的策略迁移到m叉查找树中，可以规定对于任何1个结点来说，它的所有子树的高度之差都不超过1，

这个逻辑在二叉树中用起来比较方便，但在多叉树中会复杂一些，就是要确定每一个棵树的高度之差不超过1，相互之间需要两两进行对比，这样的话时间复杂度会比较高，所以可以修改策略，如下：

• 规定二(策略)：m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同即没有高度差->做到这一点的话，就可以保证m叉查找树是平衡的，也就可以保证m叉查找树不会有太多层，从而保证了查找效率；所有的子树高度都相同，最终会导致的结果就是叶子结点即紫色的失败结点一定出现在最下面的同一层

所以在m叉查找树中如果可以保证每一个结点中分叉数量不是特别少，同时还要保证这棵树是平衡的即满足"规定一"和"规定二"，那么这就是一棵B树，

如下图：

如上图，

给出的5叉查找树就是一个5阶的B树，

规定一：5叉查找树中，规定除了根结点外，任何结点至少有⌈5/2⌉=3个分叉，即至少含有⌈5/2⌉-1=2个关键字；

规定二：5叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同即没有高度差，

该5叉查找树满足了"规定一"和"规定二"，那么这就是一棵B树。

五.B树：

1.定义：

• B树中通常把失败结点称为叶子结点，叶子结点为NULL

• B树中最下面一层含有实际数据的结点称为终端结点

• B树又称多路平衡查找树，为什么叫多路？因为每一个结点可能有多个分叉出现，可能会从多条路往下查找；为什么叫平衡？因为对于每一个结点来说，它的任何一个子树的高度都一定是相同的，所以可以说任何一个结点都是平衡的，而且是绝对平衡，并不像平衡二叉树那样还可以允许左、右子树有1的高度差

• B树的阶就是B树中最多有几个分叉，最多几个分叉，就是几阶，比如上述图片的B树就是5阶，因此所谓的5阶B树就是5叉查找树，最多会有5个分叉，只不过会在普通的5叉查找树的基础上再对它进行一系列的要求以保证查找效率

• m叉树的特性1里m棵子树就是m个分叉；特性2是因为B树是绝对平衡的，因为要保证B树中任何一个结点要绝对平衡，所以对于一个根结点来说，如果这个根结点不是终端结点的话，是否有可能只有1棵子树呢？显然不能，如果能的话就无法保证根结点的绝对平衡，所以根结点至少有两棵子树(注：根结点至少有1个关键字)

• B树中包括根结点在内的所有结点都必须是绝对平衡的即m叉查找树中，规定对于任何一个结点，其所有子树的高度都要相同即没有高度差

• B树中叶子结点指的是不带信息的结点即失败结点，为什么不带信息呢？因为叶子结点本质上是一个空指针，为什么出现在同一层上呢？是因为要求所有的结点都绝对平衡，因此所有的叶子结点一定都是同时出现在最下面一层

• B树中1个结点如果有n个关键字，那么就有n+1个指针；B树中1个结点中的关键字可以是递增排序，也可以是递减排序(默认递增)

• 叶子结点为NULL，不存在分叉

2.核心特性：

• m指的是m叉树的m棵子树即m个分叉

3.B树的高度：

问题：含n个关键字的m阶B树，最小高度、最大高度是多少？

注：这里计算B树的高度不包括叶子结点的高度。

Ⅰ.最小高度：

如上图，

如果要让B树的高度最小，在关键字总数不变的情况下，应该让每个结点包含的关键字尽可能的满即让B树宽一些，结点中关键字越多，意味着各层的分叉越多，就能使得B树变宽，

对于m阶B树来说，每一个结点最多有m-1个关键字、m个分叉，

所以在分叉最多的情况下

->第一层最多有1个结点即最多存储1个根结点，根据"m阶B树中每1个结点最多有m个分叉"可知1个结点中最多有m个分叉即第一层最多有m棵子树，因此第二层最多有m个结点（当B树为空时第一层存储0个结点，此时B树为空树）

->第二层最多有m个结点，根据"m阶B树中每1个结点最多有m个分叉"可知m个结点中最多有m * m=m²个分叉即第二层最多有m²棵子树，因此第三层最多有m²个结点

->第三层最多有m²个结点，根据"m阶B树中每1个结点最多有m个分叉"可知m²个结点中最多有m² * m=m³个分叉即第三层最多有m³棵子树，因此第四层最多有m³个结点

->以此类推，如果有h层的话，第h层最多会有个结点->所以h层的m阶B树最多有 1+m+m²+...+个结点

又因为m阶B树中每1个结点最多有m-1个关键字，所以最多有(m-1) * (1+m+m²+...+)个关键字，

现在包含n个关键字的m阶B树要让其高度为h，显然n≤(m-1) * (1+m+m²+...+)=-1，取对数可得h≥，

注：m指的是m叉树的m棵子树即m个分叉，分叉最少为0，但此时根据题目的要求分叉不可能为0（因为分叉为0即B树为空树），根据B树的特性可知此时m至少为2，所以m≥2，所以以m为底数的对数是递增函数，取其对数时无需变号，

所以含n个关键字的m阶B树中，最小高度为。

Ⅱ.最大高度：

如上图，

如果要让B树的高度最高，在关键字总数不变的情况下，应该让每个结点包含的关键字尽可能的少即让B树高一些，结点中关键字越少，意味着各层的分叉越少，就能使得B树变高，

对于m阶B树来说，在树不为空的情况下根结点最少有2个分叉，其他结点最少有⌈m/2⌉个分叉，

所以在分叉最少的情况下

->第一层只有1个根结点，根结点最少有2个分叉即第一层最少有2棵子树，因此第二层至少有2个结点

->第二层有2个结点，根据"m阶B树中每1个结点除根结点外的所有非叶子结点至少有⌈m/2⌉棵子树可知第二层最少有2⌈m/2⌉棵子树，因此第三层至少有2⌈m/2⌉个结点

->第三层至少有2⌈m/2⌉个结点，根据"m阶B树中每1个结点除根结点外的所有非叶子结点至少有⌈m/2⌉棵子树可知第三层最少有2⌈m/2⌉ * ⌈m/2⌉=2⌈m/2⌉²棵子树，因此第四层至少有2⌈m/2⌉²个结点

->以此类推，如果有h层的话，第h层至少有个结点，第h+1层即叶子结点这一层至少有个结点，

所以这里推出高度为h的m阶B树它的叶子结点至少有个，

又因为在含有n个关键字的B树中必有n+1个叶子结点（原理类似求二叉排序树中失败结点的个数，B树中的n个关键字相当于在整个查找区间(-∞,+∞)内插入n个关键字，这n个关键字会把整个查找区间(-∞,+∞)切分为n+1个部分，这n+1个部分就对应了n+1种失败的情况，所有的失败情况都会体现在叶子结点即失败结点中，所以失败结点即叶子结点有n+1个），

那么n+1≥，取对数可得h≤，

注：m指的是m叉树的m棵子树即m个分叉，分叉最少为0，但此时根据题目的要求分叉不可能为0（因为分叉为0即B树为空树，分叉也不可能为1，为1不符合B树要求），根据B树的特性可知此时m至少为2，所以m≥2即⌈m/2⌉≥1，所以以⌈m/2⌉为底数的对数是递增函数，取其对数时无需变号，

所以含n个关键字的m阶B树中，最大高度为。

推算含n个关键字的m阶B树的最大高度的另一种思路：从关键字入手

注：m阶B树中除根结点、叶子结点外的1个结点中至少有⌈m/2⌉个分叉(子树)，意味着1个结点至少有⌈m/2⌉-1个关键字；根结点允许只有1个关键字

Ⅲ.总结：

六.总结：

• 可以把B树的B理解为Balance即平衡，一个平衡的m叉查找树

• 对于B树的查找可以类比二叉排序树的查找，详情见"7.5.二叉排序树(英文缩写为BST，又名二叉查找树)"