数据结构:B-树 作者:马育民 • 2022-07-07 11:16 • 阅读:10044 **提示:** `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)](/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)](/upload/0/0/1IX3dp5Ej3M9.png) # B-树的查找 [![](/upload/0/0/1IX3dMEEHzgB.jpg)](/upload/0/0/1IX3dMEEHzgB.jpg) 以查找关键字 F 为例进行说明 ### 第一步 [![](/upload/0/0/1IX3dMExIYtF.jpg)](/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)](/upload/0/0/1IX3dMIDSuyV.jpg) 访问关键字 `C` 和关键字 `G` 之间的子代,该子代结点包含三个关键字 `[D、E、F]` ,进行顺序遍历,比较关键字 `D` 和 `F` ,`F` 比 `D` 大 ### 第四步 [![](/upload/0/0/1IX3dMQKew2s.jpg)](/upload/0/0/1IX3dMQKew2s.jpg) 顺序访问关键字 `E` ,`F` 比 `E` 大 ### 第五步 [![](/upload/0/0/1IX3dMRObSYx.jpg)](/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 原文出处:https://malaoshi.top/show_1IX3dMSM34jy.html