深入理解 B+ 树
- MySQL
- 2022-07-14
- 15热度
- 0评论
1 什么是 B+ 树？有什么用？
1.1 数据结构
B+ 树是一种数据结构，是大多数 MySQL 存储引擎的默认索引类型，用于提高查询效率。
B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。
B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。
在 B+ Tree 中，一个节点中的 key 从左到右非递减排列，如果某个指针的左右相邻 key 分别是 keyi 和 keyi+1，且不为 null，则该指针指向节点的所有 key 大于等于 keyi 且小于等于 keyi+1。
所有的数据都存储在叶子节点中，非叶子节点仅存储 key 和指针。
1.2 查找操作
进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。
插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，需要对树进行分裂、合并、旋转等操作来维护平衡性。
2 InnoDB 中一颗 B+ 树大约能存储多少行数据？
答：约 2kw。
这是怎么得出来的呢？
2.1 最小存储单元
在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如XFS/EXT4）的最小单元是块，一个块的大小是 4k。
有图为证：
而对于我们的 InnoDB 存储引擎也有自己的最小存储单元——页（Page），一个页的大小默认是16K（可以通过参数进行设置）。
于是，我们能得到这张图：
2.2 开始计算
列出以下已知条件：
- 假设一行数据的大小为 1k，那么一个页就可以存放 16 行数据。
- B+ 树中，每一个节点占用的空间都是一页。
- 对于单个叶子节点：存放的都是数据，记录数=16。
- 对于非叶子节点：假设主键 ID 为 bigint 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。那么，一个非叶子节点存储的指针数量为 16384 / 14 = 1170。
- B+ 树的高度一般为 1-3 层，这里要求最大值，我们以 3 层来计算。
由以上条件可以算出，一棵 3 层 B+ 树，能存放的数据行数为：1170 * 1170 * 16 = 21902400。
这就是一开始给出的答案，约 2kw。
3 相比于其他结构，B+ 树的优势是什么？
3.1 PK 红黑树
B+ 数高度更低。
红黑树的出度为 2，B+ 树的出度可以非常大（按照之前的估算，可以达到 1170 左右）。这样一来，相比红黑树，B+ 树就有了更低的高度。
树的高度越低，磁盘寻道的次数越少，速度就越快。
3.2 PK B树
- B+ 树的磁盘读写代价更低。B 树在所有节点中都会存放数据，而 B+ 树只在叶子结点中存放数据，使得 B+ 树的内部节点更小，加载速度更快。
- B+ 树的查询效率更加稳定。同样是因为，B+ 树的数据都在叶子节点中，查找任意数据，需要经过的深度是一样的。
- B+ 树更有利于对数据库的扫描。由于叶子结点中有指针串联，B+ 树可以直接遍历叶子结点，高效进行全表扫描或范围查询。
3.3 PK 哈希
哈希索引是无序的，限制比较多，适应场景较少。
参考资料：
- http://www.cyc2018.xyz/数据库/MySQL.html#b-tree-原理
- https://blog.csdn.net/xlgen157387/article/details/90694626
- 慕课网
