提示： B树 就是 B-树 ，- 是个连字符号，不是减号

为什么提出B-树

平衡树的缺点

在大多数的平衡查找树（Self-balancing search trees)，比如 AVL 树 和红黑树，都是将所有的数据放在 内存 中。

当数据量达到了亿级别，需要存储到磁盘，从磁盘读写数据，比内存更加耗时

查询时，查找的时间复杂度，与树的高度相同。所以树高多少，就需要读取硬盘多少次

大多数平衡查找树高度是 log2(n)（ n 是树中的结点个数），都太高了，导致性能变差

B-树

B-树的 高度可控，一般远小于 log2(n)，所以查询时，与 AVL 树和红黑树相比，B-树的磁盘访问次数极大地降低，查询性能更强

对比例子

假设我们现在有 838,8608 个节点：

• 对于红黑树而言，树的高度 log2(8388608) = 23 ，需要读取磁盘 23 次

• 对于 B-树，假设每一个结点可以包含 8 个键（当然真实情况下没有这么平均，有的结点包含的键可能比8多一些，有些比 8 少一些），那么整颗树的高度将最多 8 （log8(8388608) = 7.8 ) 层，只需要读取磁盘 8 次

B树的定义

一棵 m阶 B树(balanced tree of order m)是一棵平衡的m路搜索树。

它或者是空树，或者是满足下列性质的树：

1. 根结点至少有两个子节点；
2. 每个非根节点所包含的关键字个数 j 满足：ceil(m/2) - 1 <= j <= m - 1；
3. 除根结点以外的所有结点（不包括叶子结点）的 度数 正好是关键字总数加1，所以子树个数 k 满足：ceil(m/2) <= k <= m；
4. 所有的叶子结点都位于同一层

解释：

• 关键字：要存储的数据
• ceil()：向上取整

例子

上图就是一颗典型的 B-树，其中：

• 根结点至少有两个子节点；
• 最小度数 t = 2
• 根结点至少包含一个关键字
• 根结点以外的每个结点至少有 t - 1 = 1 个关键字
• 每个结点最多包含 2t - 1= 3 个关键字
• 包含 3 个关键字的结点 (C、G、L) 包含有 4 个孩子。
• 同一个结点中的所有关键字升序排列，比如结点 (D、E、F) 的内部结点就是升序排列，且均位于其父结点中的关键字 C 和 G 之间。
• 所有的叶结点均为空。

数据

索引元素所指向的数据记录，比如数据库中的某一行，在B-树中，无论中间节点还是叶子节点都带有数据。

数据：索引元素所指向的数据记录，比如文件系统中的数据

B-树的查找

以查找关键字 F 为例进行说明

第一步

访问根结点 P ，发现关键字 F 小于 P ，则查找结点 P 的左孩子。

第二步

访问结点 P 的左子结点 [C、G、L] ，对于一个结点中包含多个关键字时，顺序进行访问：

1. 首先与关键字 C 进行比较，发现比 C 大；
2. 然后与关键字 G 进行比较，发现比 G 小

说明待查找关键字 F 位于关键字 C 和关键字 G 之间的子代中。

第三步

访问关键字 C 和关键字 G 之间的子代，该子代结点包含三个关键字 [D、E、F] ，进行顺序遍历，比较关键字 D 和 F ，F 比 D 大

第四步

顺序访问关键字 E ，F 比 E 大

第五步

顺序访问关键字 F ，发现与待查找关键字相同，查找成功。则返回结点 [D、E、F] 的指针。

B树的使用场景

• 多用于做文件系统的索引

参考

https://baike.baidu.com/item/B%E6%A0%91/5411672
https://blog.csdn.net/ff_simon/article/details/101055134