索引数据结构之B-Tree与B+Tree（下篇）

扫描下方二维码或者微信搜索公众号菜鸟飞呀飞，即可关注微信公众号，阅读更多Spring源码分析、Java并发编程和Netty源码系列文章。

前言

接上篇博客《索引数据结构之 B-Tree 与 B+Tree（上篇）》，本文将简单介绍 B+Tree 中插入、查找、删除等相关操作，以及对比 B-Tree 与 B+Tree 的区别，最后会重点分析为什么 MySQL 会选择 B+Tree 作为索引的数据结构，而不是 B-Tree。

B+Tree

B+Tree 的大分部性质与 B-Tree 的性质一样，例如：对于一个 m 阶的 B+Tree 而言，根结点的关键字数量为 1 <= k <= m-1，非根结点的关键字数量为 m/2 <= k <= m-1；每一个结点上，所有的关键字都是有序排列的；每个结点最多 m 个子结点。 但 B+Tree 有几个十分重要的性质与 B-Tree 不一样。

1. B+Tree 的所有非叶子结点不存储数据，只存储关键字，即只存储 key，不存储 value;而 B-Tree 的所有结点，不论是叶子结点还是非叶子结点，都存放的是关键字和数据，即存放了 key 和 value；
2. B+Tree 的叶子结点才存储关键字和数据，即存放了 key 和 value；
3. 因为 B+Tree 的非叶子结点只存放关键字，叶子结点才存放数据，因此非叶子结点中关键字对应的数据只能在叶子结点存储，所以在叶子结点中会都会冗余一份非叶子结点的关键字；
4. 因为叶子结点会冗余非叶子结点的关键字，因此 B+Tree 中，每个关键字的右子树的值都是大于等于该关键字，左子树所有的值小于该关键字。
5. 叶子结点中存有一个指针指向兄弟结点，这一点对于 MySQL 中数据的查找是非常方便的。

插入

B+Tree 的插入操作与 B-Tree 的插入操作类似，也存在结点的分裂情况，不同的是，非叶子结点的关键字会在叶子结点中冗余一份。下面以一颗 5 阶的 B+Tree 为例，看看数据的插入流程。 一次向 B+Tree 中插入数据：50、30、40、25，前面的步骤与 B-Tree 完全一样。

当继续向其中插入数据 20 时，此时结点的关键字数量达到 5，超过了 m-1，因此需要将结点从中间分裂，所以从最中间的关键字 30 这儿分裂，将 30 提取到父结点当中，30 左边的所有关键字组成一个新的结点——左孩子，30 右边的所有关键字组成一个新的结点——右孩子，由于 B+Tree 中非叶子结点中的关键字会冗余一份在叶子结点中，所以 30 这个关键字以及这个关键字所对应的数据 value 也会存放进右孩子当中。如下图所示。

查找

B+Tree 中根据关键字查找数据的流程与 B-Tree 也几乎一样，不同的是，B+Tree 的所有数据都存放在叶子结点，因此 B+Tree 最后需要一直查找到叶子结点这一层，查到关键字对应的数据后才返回，而 B-Tree 中非叶子结点也可以存放数据，因此 B-Tree 中查找数据时，可能遍历到非叶子结点时就找到了数据，就可以提前结束寻找过程。 如图所示，从图中的数据中查找关键字 22 的数据。

首先从根结点开始出发，要查找的关键字 22 大于根结点中的第一个关键字 19，因此进入 19 的右子树继续查找，即进入到关键字 22 和 30 所在的这个结点。由于要查找的数据 22 等于当前节点的第一个关键字（此时由于当前节点不是叶子结点，所以不能停止查找），因此继续进入到关键字 22 的右子树查找，即进入到关键字 22、25、26 所在的结点，由于当前结点是叶子结点，并在结点中找到了关键字 22，因此将数据返回。如上图中，红色线条即表示的是本次查找的路径。

删除

由于 B+Tree 的所有数据都存在叶子结点，所以如果要删除的数据存在于 B+Tree 中，那么最终一定是在叶子结点中删除数据，同时如果关键字还存在与非叶子结点中，那么就还需要修改非叶子结点中的指针。在删除过程中也涉及到找兄弟结点借关键字以及合并结点的情况，操作与 B-Tree 类似。 下面以下图中的数据为例。

从 B+Tree 中删除 19。找到 19 所处的叶子结点，然后将 19 删除，然后叶子结点中只剩下关键字 20 了。由于 19 这个关键字还处于非叶子结点中，因此将 19 从非叶子结点中删除，然后用关键字 20 替换。如图。

由于叶子结点中只剩下 20 这一个关键字了，小于 m-1，因此需要向兄弟结点借元素，右边的兄弟结点的元素个数大于 m/2，因此可以将 22 借出，然后修改父节点的指针。所以最终状态如下。

至于删除的其他复杂情形，可以参照上篇文章索引数据结构之 B-Tree 与 B+Tree（上篇）中 B-Tree 的删除示例或者在可视化网站进行动态演示（https://www.cs.usfca.edu/~galles/visualization/Algorithms.html），会更加直观。

MySQL 中索引数据结构

前面关于 B-Tree 和 B+Tree 的知识，介绍了那么多，那么它们究竟有什么用呢？关于 MySQL 中索引的数据结构，网上有很多说法，有的地方说是 B-Tree，有的地方说成 B+Tree，那么究竟是哪一种数据结构呢？答案是 B+Tree。为什么不是 B-Tree 呢？

简单点的答案就是，B-Tree 的非叶子结点会存放数据，而 B+Tree 的非叶子结点不存放数据，只存放关键字，这样同一个结点，B+Tree 的结点能形成的叉数越多，那么存储一定数量的数据，B+Tree 的高度越小，那么插入、查找、删除的性能会越高。（B-Tree 和 B+Tree 的插入、查找、删除的时间复杂度与树的高度成正相关）。

MySQL 中 Innodb 存储引擎存储数据的最小单元是页，一页的大小默认是 16KB，可以通过如下命令查看具体的值，这个值可以被修改。

show variables like 'innodb_page_size';

而对于索引树结构中，一个结点的大小通常是一个数据页的整数倍，即 16KB 的倍数，而一个结点的大小通常也是 16KB。

现在我们假设一个关键字（key）的大小为 2KB，它对应的数据（value）是 2KB，所以一对 key-value 的大小就是 4KB，且假设树的高度都为 3。

对于 B-Tree 而言，所有结点中存的都是 key-value，所以 B-Tree 的第一层，也就是根结点层，最多能存放 16KB/4KB=4 对 key-value，也就是最多分出 5 个叉（5 颗子树）。

因此第二层最多有 5 个结点，每个结点依旧是最多能存储 16KB/4KB=4 对 key-value，每个结点也是分出 5 个叉，所以第二层最多能存储 20 对 key-value。

那么第三层就会有 25 个结点，每个结点最多能存放 16KB/4KB=4 对 key-value，所以第三层最多能存储 25*4 = 100 对 key-value。

因此该 B-Tree 的三层一共能存放 4+20+100 = 124 对 key-value。

再来看下 B+Tree，第一层和第二层都是非叶子结点，只存放 key，第三层是叶子结点，存放 key-value。

第一层最多能存放 16KB/2KB =8 对 key-value，最多能分出 9 个叉；

因为第一层最多能分出 9 个叉，所以第二层最多可以有 9 个结点，每个结点也是最多能存放 16KB/2KB =8 对 key-value，，每个结点能分出 9 个叉，因此第二层最多能存储 72 对 key-value，分出 81 个叉；

因为第二层最多能分出 9 乘以 9 个叉，所以第三层最多有 81 个结点，由于第三层是叶子结点，存放 key 和 value，因此每个结点能存放 16KB/4KB=4 对 key-value。所以第三层一共最多能存放 81*4=324 对 key-value。

B+Tree 的所有数据都存放在叶子结点，即第三层，因此该 B+Tree 一共能存放 324 对 key-value。（远远大于B-Tree的124对key-value）

对比发现，同样高度的树，B+Tree 能存放的数据远远多于 B-Tree（这里举例时，假设的 key 的大小为 2KB，实际的 key 远远比这个小，如果 key 越小，这个差距会越来越大）。前面我们假设的是树的高度不变，那反过来假设我们要存储的数据量是一定的，比如 5GB 的数据，那么最终 B-Tree 的树高肯定是远远高于 B+Tree。

树的高度越高，会有什么影响呢？熟悉树这种数据结构的同学肯定知道，通常树的插入、查找、删除的时间复杂度与树的高度成正相关，树越高，时间复杂度越高，性能越差，这个时间复杂度是理论推导出来的，接下来我们通过 MySQL 的数据读取为例，来解释一下为什么数越高，性能越差。

假设 MySQL 的某张表的大小为 5GB，对于主键索引来说，如果用 B-Tree 来存储，那么它最终的高度可能是 20（这个 20 是假设的一个值），而如果使用 B+Tree 来存储，它最终的高度可能是 4（这个 4 也是假设的一个值）。（这里的高度 4 和 20 都是我们假设的一个值，不是精确值，但反应的是 B+Tree 和 B-Tree 在相同数据量时最终树高相差较大的现象。）

MySQL 中存储数据是以页为单位的，在读数据时，也是以页为单位将数据从磁盘加载进内存当中，每从磁盘中读取一个页，就会发生一次磁盘 IO。也就是说，在查找数据时，每遍历一个结点，就意味着读取一个数据页，也就是发生一次 IO。

对于 B-Tree 而言，如果要查找的数据在树的越底层，就意味着要发生的 IO 次数越多，树越高，查找时可能发生的磁盘 IO 次数越多，磁盘 IO 越多，意味着程序的耗时会越长，性能越差。

而对于 B+Tree 而言，它的树高相对 B-Tree 而言会低很多，而且所有的数据都是存放在叶子结点当中的，所以查询数据时，一定是遍历到叶子结点层，时间复杂度相对稳定，而且发生的磁盘 IO 次数较少，所以整体来讲，B+Tree 性能更优，因此 MySQL 的索引数据结构选择的是 B+Tree，而不是 B-Tree。

通常一颗 B+Tree 的高度为 3 或者 4，这样一次索引的查找通常最多只需要发生 3-4 次磁盘 IO，而 MySQL 中由于 buffer pool 缓冲池的机制，第一层的结点所对应的数据页通常存在于缓存中，第二层的数据页也有很大可能也存于缓存中（MySQL 的预读机制、LRU 缓存淘汰机制等都有可能导致），因此在遍历时，B+Tree 的第一层、第二层极有可能不会发生磁盘 IO，而是基于内存查找，所以一次数据查找，可能就只会发生 1-2 次磁盘 IO，这个查询效率得到了大大提高。

另外，B+Tree 的叶子结点中，存放了相邻叶子结点的指针，因此在进行范围查找时，不需要多次遍历整棵树，只需要找到一个叶子结点后，通过指针，就能找到其他的叶子结点，这是十分高效的一种做法。

总结

本文前半部分主要介绍了 B+Tree 的性质以及通过对比 B-Tree 的插入、查找、删除操作的流程，简单介绍了 B+Tree 的插入、查找、删除操作的流程。最后从 B+Tree 和 B-Tree 数据结构的不同之处出发，详细说明了为什么 MySQL 中索引的数据结构是 B+Tree，而不是 B-Tree。

我们知道了 MySQL 的索引结构为什么没有选择 B-Tree，而是选择了 B+Tree，而那么多高效的数据结构，例如：数组、哈希表、红黑树等，为什么 MySQL 没有选择它们呢？下一篇博客分析。

推荐

• redo log —— MySQL宕机时数据不丢失的原理
• 索引数据结构之B-Tree与B+Tree（上篇）