深入理解 B+ 树

导航

1 什么是 B+ 树？有什么用？

B+ 树是一种数据结构，是大多数 MySQL 存储引擎的默认索引类型，用于提高查询效率。

B Tree 指的是 Balance Tree，也就是平衡树。平衡树是一颗查找树，并且所有叶子节点位于同一层。

B+ Tree 是基于 B Tree 和叶子节点顺序访问指针进行实现，它具有 B Tree 的平衡性，并且通过顺序访问指针来提高区间查询的性能。

在 B+ Tree 中，一个节点中的 key 从左到右非递减排列，如果某个指针的左右相邻 key 分别是 key_i 和 key_i+1，且不为 null，则该指针指向节点的所有 key 大于等于 key_i 且小于等于 key_i+1。

所有的数据都存储在叶子节点中，非叶子节点仅存储 key 和指针。

进行查找操作时，首先在根节点进行二分查找，找到一个 key 所在的指针，然后递归地在指针所指向的节点进行查找。直到查找到叶子节点，然后在叶子节点上进行二分查找，找出 key 所对应的 data。

插入删除操作会破坏平衡树的平衡性，因此在进行插入删除操作之后，需要对树进行分裂、合并、旋转等操作来维护平衡性。

答：约 2kw。

这是怎么得出来的呢？

在计算机中磁盘存储数据最小单元是扇区，一个扇区的大小是 512 字节，而文件系统（例如XFS/EXT4）的最小单元是块，一个块的大小是 4k。

有图为证：

而对于我们的 InnoDB 存储引擎也有自己的最小存储单元——页（Page），一个页的大小默认是16K（可以通过参数进行设置）。

于是，我们能得到这张图：

列出以下已知条件：

假设一行数据的大小为 1k，那么一个页就可以存放 16 行数据。
B+ 树中，每一个节点占用的空间都是一页。
对于单个叶子节点：存放的都是数据，记录数=16。
对于非叶子节点：假设主键 ID 为 bigint 类型，长度为 8 字节，而指针大小在 InnoDB 源码中设置为 6 字节，这样一共 14 字节。那么，一个非叶子节点存储的指针数量为 16384 / 14 = 1170。
B+ 树的高度一般为 1-3 层，这里要求最大值，我们以 3 层来计算。

由以上条件可以算出，一棵 3 层 B+ 树，能存放的数据行数为：1170 * 1170 * 16 = 21902400。

这就是一开始给出的答案，约 2kw。

B+ 数高度更低。

红黑树的出度为 2，B+ 树的出度可以非常大（按照之前的估算，可以达到 1170 左右）。这样一来，相比红黑树，B+ 树就有了更低的高度。

树的高度越低，磁盘寻道的次数越少，速度就越快。

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

参考资料：