机遇屋-B+树为什么快

B+树为什么快

作者：ych

#### B树的构建规则
![](https://img.jiyuwu.com/upload/article/2022/11/85D7CC8B77BA3BDFE0FE0EB3694C746E.png)

（1）排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；

（2）子节点数：非叶节点（根节点和枝节点）的子节点数 >1、且子节点数量<=M 、且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；

（3）关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数 如ceil(1.1)结果为2);

（4）所有叶子节点均在同一层、叶子节点除了包含了关键字 和 关键字记录的指针外，也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

#### B+树构建规则
![](https://img.jiyuwu.com/upload/article/2022/11/7A6B5625EC3BE62668AEBF0E2451838C.png)

（1）B+树的非叶子节点不保存具体的数据，而只保存关键字的索引，而所有的数据最终都会保存到叶子节点。因为所有数据必须要到叶子节点才能获取到，所以每次数据查询的次数都一样，这样一来B+树的查询速度也就会比较稳定，而B树的查找过程中，不同的关键字查找的次数很有可能都是不同的（有的数据可能在根节点，有的数据可能在最下层的叶节点），所以在数据库的应用层面，B+树就显得更合适。

（2）B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。因为叶子节点都是有序排列的，所以B+树对于数据的排序有着更好的支持。

（3）非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料 这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

#### B+树和B树由什么区别？
1.B+树的的非叶子节点只存储索引,叶子节点存储数据（所以B+树能存储更多的索引，并且查询次数也是一样的）
2.B+树每个叶子节点都包含了根节点的键值数据，每个叶子节点的关键字从小到大链
>在B树的基础上每个节点存储的关键字数更多，树的层级更少所以查询数据更快，所有关键字指针都存在叶⼦节 点，所以每次查找的次数都相同所以查询速度更稳定。 除此之外，B+树的叶⼦节点是跟后序节点相连接的，这对范围查找是⾮常有⽤的。 看到没B+树的⾮叶⼦节点是主键，主键占⽤的空间越⼩，每个节点能放的主键就能更多，这就是为什么我们的主键 ⼀般不设置太⼤的原因。主键占⽤的空间⼩，能降低树⾼，减少IO次数

#### B+树为什么快?

B+树是B-Tree的改进版本，同时也是数据库索引索引所采用的存储结构。数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都指向相邻的叶子节点的地址。相比B-Tree来说，进行范围查找时只需要查找两个节点，进行遍历即可。而B-Tree需要获取所有节点，相比之下B+Tree效率更高。

#### 总结
1、相同思想和策略
从平衡二叉树、B树、B+树、B*树总体来看它们的贯彻的思想是相同的，都是采用二分法和数据平衡策略来提升查找数据的速度；

2、不同的方式对树的不断优化

>1、首先，为了保证树的节点均匀分布，所以在二叉树的基础上加上了平衡算法，就有了平衡二叉树。
2、为了减少树的高度，所以B树一个节点下面可以添加N个子节点，然后每个节点的大小限制在磁盘块容量大小，让节点只需要通过一次IO就能读取到所有数据，通过增加节点存储的数据减少了树的高度，而节点的数据变多并没有让IO次数变多。
3、B+树在B树的基础上，在查询的稳定性 和排序方面进行了优化，因为B+树所有的数据都会保存到叶子节点，然后所有叶子节点本身是有序的。
4、B*树为了减少 树在构建过程中节点的拆分、合并次数，所以在每个节点上都保存了旁边节点的指针，在节点需要进行拆分、合并时，优先从旁边节点挪数据，从而减少构建过程中节点拆分、合并的次数，提升了树的构建性能。

#### 扩展知识 
为什么官方建议使用自增长主键作为索引？

结合B+Tree的特点，自增主键是连续的，在插入过程中尽量减少页分裂，即使要进行页分裂，也只会分裂很少一部分。并且能减少数据的移动，每次插入都是插入到最后。总之就是减少分裂和移动的频率。

评论区

先去登录

B+树为什么快

相关推荐

评论区