2022年7月14日

深入理解 B+ 树

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树

  1. B+ 树的磁盘读写代价更低。B 树在所有节点中都会存放数据,而 B+ 树只在叶子结点中存放数据,使得 B+ 树的内部节点更小,加载速度更快。
  2. B+ 树的查询效率更加稳定。同样是因为,B+ 树的数据都在叶子节点中,查找任意数据,需要经过的深度是一样的。
  3. B+ 树更有利于对数据库的扫描。由于叶子结点中有指针串联,B+ 树可以直接遍历叶子结点,高效进行全表扫描或范围查询。

3.3 PK 哈希

哈希索引是无序的,限制比较多,适应场景较少。


参考资料:

  • http://www.cyc2018.xyz/数据库/MySQL.html#b-tree-原理
  • https://blog.csdn.net/xlgen157387/article/details/90694626
  • 慕课网

You may also like...

发表回复

您的电子邮箱地址不会被公开。


*