数据结构：B-树 作者：马育民 • 2022-07-07 11:16 • 阅读：10040 **提示：** `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阶](https://www.malaoshi.top/show_1IX3dKTQtiJh.html "m阶") B树(balanced tree of order m)是一棵平衡的m路搜索树。 它或者是空树，或者是满足下列性质的树： 1. 根结点至少有两个子节点； 2. 每个非根节点所包含的关键字个数 `j` **满足**：`ceil(m/2) - 1 <= j <= m - 1`； 3. 除根结点以外的所有结点（不包括叶子结点）的 [度数](https://www.malaoshi.top/show_1IX3dKTQtiJh.html "度数") 正好是关键字总数加1，所以子树个数 `k` 满足：`ceil(m/2) <= k <= m`； 4. 所有的叶子结点都位于同一层 **解释：** - 关键字：要存储的数据 - `ceil()`：向上取整 ### 例子 [](/upload/0/0/1IX3dLsluBGV.jpg) 上图就是一颗典型的 B-树，其中： - 根结点至少有两个子节点； - 最小度数 `t = 2` - 根结点至少包含一个关键字 - 根结点以外的每个结点至少有 `t - 1 = 1` 个关键字 - 每个结点最多包含 `2t - 1= 3` 个关键字 - 包含 3 个关键字的结点 (C、G、L) 包含有 4 个孩子。 - 同一个结点中的所有关键字升序排列，比如结点 (D、E、F) 的内部结点就是升序排列，且均位于其父结点中的关键字 C 和 G 之间。 - 所有的叶结点均为空。 ### 数据 索引元素所指向的数据记录，比如数据库中的某一行，在B-树中，无论中间节点还是叶子节点都带有数据。 > **数据**：索引元素所指向的数据记录，比如文件系统中的数据 [](/upload/0/0/1IX3dp5Ej3M9.png) # B-树的查找 [](/upload/0/0/1IX3dMEEHzgB.jpg) 以查找关键字 F 为例进行说明 ### 第一步 [](/upload/0/0/1IX3dMExIYtF.jpg) 访问根结点 P ，发现关键字 F 小于 P ，则查找结点 P 的左孩子。 ### 第二步 访问结点 `P` 的左子结点 `[C、G、L]` ，对于一个结点中包含多个关键字时，顺序进行访问： 1. 首先与关键字 `C` 进行比较，发现比 `C` 大； 2. 然后与关键字 `G` 进行比较，发现比 G 小 说明待查找关键字 `F` 位于关键字 `C` 和关键字 `G` 之间的子代中。 ### 第三步 [](/upload/0/0/1IX3dMIDSuyV.jpg) 访问关键字 `C` 和关键字 `G` 之间的子代，该子代结点包含三个关键字 `[D、E、F]` ，进行顺序遍历，比较关键字 `D` 和 `F` ，`F` 比 `D` 大 ### 第四步 [](/upload/0/0/1IX3dMQKew2s.jpg) 顺序访问关键字 `E` ，`F` 比 `E` 大 ### 第五步 [](/upload/0/0/1IX3dMRObSYx.jpg) 顺序访问关键字 `F` ，发现与待查找关键字相同，查找成功。则返回结点 `[D、E、F]` 的指针。 # B树的使用场景 - 多用于做文件系统的索引 #### 参考 https://baike.baidu.com/item/B%E6%A0%91/5411672 https://blog.csdn.net/ff_simon/article/details/101055134 原文出处：http://malaoshi.top/show_1IX3dMSM34jy.html