算法小讲堂之B树和B+树（浅谈）|考研笔记

一、前言

前面学习了平衡二叉树（ A V L AVL AVL 树），我们知道了平衡的概念就是让树尽量的 “胖” ，让它的高度不会线性增长，那么这篇笔记主要是分享 B B B 树和 B + B+ B+ 树的原理、应用（不涉及代码实现，也许有一天会补上，谁知道呢）

二、定义

B B B 树（又称 B − B- B− 树）和 B + B+ B+ 树其实差别不是很大，所以我会着重介绍 B B B 树，然后最后指出 B + B+ B+ 树的不同点

那么什么是 B B B 树呢？

B B B 树，又称 多路平衡查找树 ， B B B 树中所有结点的孩子个数的最大值称为 B B B 树的 阶 ，通常用 m m m 表示。

这里的多路其实就是指这一颗树可能不只是最多有两颗子树，具体多少颗是由 B B B 树的阶决定的，作为一颗 B B B 树应该满足一下要求：

• ①若根节点不是 叶结点 ，则至少有两个子树（即一个关键字）
• ②除了根结点外，其他每个结点至少有 m 2 \frac{m}{2} 2m​ 个子树，最多有 m m m 个子树，对应的每一个结点至少有 ⌈ m 2 − 1 ⌉ \left \lceil \frac{m}{2} -1 \right \rceil ⌈2m​−1⌉ 个关键字
• ③每一个结点的关键字从左到右升序排列
• ④ B B B 树是一个严格的多路平衡查找树，它的左右子树的高度室相等的，且叶结点处于同一层（即所有结点的平衡因子都为 0 0 0 ）

上面提到的关键字就是对于每一个结点可能会存在多个值的情况，这些值按照升（降）序排列，用于划分子树区间，之前的二叉平衡树我们对于每一个结点只有一个关键字，我们就有两个分支，显然若是有 m m m 个关键字则会有 m + 1 m+1 m+1 个分支，其实这就是一个简单的区间划分（相邻关键字划分一个区间、前后俩结点单独一个分区）

PS：这里需要注意一下，在王道的书上是将叶结点（P285页）定义成了不存在的一层，但是在严蔚敏的书上定义的就是最后一层有关键字的结点，比如下图中，王道将第四层定义为叶子节点，严蔚敏的书上认为叶子结点（终端节点）是第三层，而笔者也认为第三层才是叶子节点或者称为终端节点

三、原理 3.1 树的高度

假设一颗二叉树包含 n ( n > = 1 ) n(n>=1) n(n>=1) 个关键字、高度为 h h h ，阶数为 m m m 的 B B B 树

• 至少高度： 既然是至少高度，那么我们应该尽量希望每个结点的关键字都是满即 m − 1 m-1 m−1 的，于是我们得到了如下不等式：

∵ n < = ( m − 1 ) ( 1 + m + m 2 + … … + m h − 1 ) n < = m h − 1 ∴ h > = l o g m ( n + 1 ) ∵ n =2(\left \lceil \frac{m}{2} \right \rceil)^{h-1} \\ \\ ∴ h =2(⌈2m​⌉)h−1∴h