这篇文章的灵感源自于前几天有个想要转行做数据分析的小伙伴来问我，关于 B+树 的问题。于是我整理了我们两个之间的聊天记录，给不那么“技术”但又想了解 B+树 的小伙伴讲讲 MySQL 索引究竟为什么使用 B+树。这篇文章的主要目的旨在思想，如果有一些存在歧义的地方，欢迎大家批评指正～
讨论 “MySQL 索引“ 时，我们到底在讨论什么
首先，我们先来说说这里的 “MySQL 索引” 到底指的是什么。我不想再重复一遍关于“索引”这个名词的定义，这种官方（拗口难懂）的定义显然不太适合不那么“技术”的小伙伴。
“MySQL 索引“ 很明显有两部分，“MySQL” + “索引”。MySQL 就不过多解释了，为了方便理解，只提一下 MySQL 是由两部分组成的，Server 层 和 存储引擎层。负责数据的存储、提取的就是存储引擎层，它的架构是插件式的，也就是说在 MySQL 存储引擎层可以使用不同的存储引擎，其中最常见的就是 InnoDB。所以当没有特殊说明时，“MySQL 索引” 指的是在 InnoDB 引擎中的索引。
索引对应的场景是什么
要想知道 MySQL 为什么选用 B+树 作为存储索引的数据结构，就要先想想，索引究竟要解决什么样的问题，或者说索引对应的场景是什么。我们都知道索引的目的是为了加快查询数据的速度，那么需要在什么场景下来实现这个目的呢？
我们以最简单的查询场景分类，可以大致分为以下两个场景。
数值相等的查询，对应的 SQL 语句中的 “=”
数值范围内的查询，对应的 SQL 语句中的 “>“、”<“
数值相等的查询
数值相等的查询，可以说是最基础也最常见的查询了。假设存储一组静态数据，并且这些数据只包含数字。当需要在一组数据中查找一个元素时，我们可以提前把这些数据按照从小到大的顺序排列后放入数组中，得到一个有序数组。有查找需要的时候，可以在有序数组里每次都找到中间位置的元素，根据中间位置的元素和给定值的大小关系，将查找的数据范围减半。比如给出 7 个数字 [7, 3, 2, 1, 5, 4, 6]，需要查找的数字是 5。我们先把这十个数字按照从小到大的顺序排列为 [1, 2, 3, 4, 5, 6, 7]，第一次查找，中间位置的元素是 4，5 比 4 大，继续在 4 右边的数字内查找，即 [5, 6, 7]。第二次查找，中间位置的元素是 6，5 比 6 小，继续在 6 左边的数字内查找，即[5]。第三次查找，成功找到 5。以这样的方式，在有序数组内的每一次查找，都会将查找的范围减半，这样的方式就是二分查找。
二分查找非常适合在有序数组内查找数值，但如果是像数据库这种经常会写入、删除、更新，动态更新的数据，一直要保证数组的有序性，这样的开销会很大。
有没有一种方式，即能支持二分查找，又能在动态更新数据的时候，减少保证数据有序性的开销呢？
这种数据结构叫二叉查找树，它是在树的基础上，令每个结点的左子树中的所有结点小于本结点，右子树中的所有结点大于本结点，从而保证了数据的有序性。
二叉树能够支持二分查找，满足快速查找数值相等的情况，又能在数据动态更新的时候，减少一些因为数据移动带来的开销。但是在实际情况中，有可能会出现一种非常极端的情况，就是这棵树非常的 “倾斜“，在这样的二叉树中查找数据就会退化成依次比较，完全体现不出“二分查找”的高效，反而沦为了“暴力”查找，每个元素都要遍历一次才能查找到想要的数据。
为了避免这种情况的出现，我们就要将一颗二叉树，尽可能地左右两边“平衡”一点，对称一点。这种两边相差不大，数据尽可能地在树中均匀分布的二叉查找树，叫做平衡二叉查找树。可以说平衡二叉查找树是 B+树 最基本的雏型。
到现在为止，我们已经可以做到在数据中利用 “二分查找” 的思想，动态地构建平衡二叉查找树，快速查询数值相等的数据了。但不能满足第二个常见的查询场景，那就是在区间内查找数据。
数值区间范围的查询
如何能够在平衡二叉查找树的基础上进行一些 “改造”，得到一个可以快速查询区间数据的数据结构呢？
我们可以对平衡二叉查找树做一点调整，让结点中不存储真正的数据，而是存储索引。在最下层的结点（叶子结点）中存放着原始的数据，并且将这些真实数据 “串” 起来（使用双向链表），支持向前向后的访问下一个数据。这样可以保证最下层结点（叶子结点）是全部的数据，且是有序的。
这样在查找的时候，不是最下层结点（非叶子结点）可以使用 “二分查找” 的思想，快速查找到区间的边界值，然后在最下层结点（叶子结点）部分，顺序查找直到另一个边界值，就可以满足快速查找区间范围内的数据。这其实就是 B+树的思想。
通过改造后的数据结构，虽然多增加存储了索引，但现在我们即可以满足快速查询数值相等的数据，又可以满足快速查询区间范围内的数据。
如果是在数据量很少，直接在内存中存储索引、操作数据的情况下，其实到这里就可以满足需求，快乐地结束了。但是在 MySQL 中，存储的数据量可能是千万级别、亿级别，那这个时候直接在内存中存储索引、操作数据，显然是不太可能的。我们只能用 “时间换空间”，将索引存储在磁盘上。这又会带来一个新的问题，将索引存储在磁盘上，在查询数据读取索引时，会比直接读取存储在内存中的索引，数据查询效率低得多得多。读取同样大小的数据，从磁盘中读取花费的时间，可能是从内存中读取所花费时间的上万倍，甚至几十万倍。
在大数据量的情况下，我们为了不占用过多的内存，把这棵索引树存储在了硬盘中。在查询时需要读取索引的结点时，每个结点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。所以我们为了提高查询的速度，就要将树的高度降低，减少磁盘 IO 的操作次数。如何能降低一棵树的高度？
我们可以将树的“分叉”增多，也就是增加每个结点的子结点个数，原来我们都是使用的二叉树，也就是每个结点的子结点个数是 2，现在我们增加到 5。
不难推断出，对于相同个数的数据构建 n 叉树索引，n 叉树中的 n 越大，树的高度就越小。这个 n 叉树就是 B+树。那么在实际运用中 B+树 到底应该使用几叉树呢？
这个数值其实是根据操作系统 “页” 的大小来提前计算得到的，操作系统在读取数据的时候，每次只会读取一“页”大小的数据，当数据的大小超过一 “页” 时，会触发多次 IO。所以我们要尽可能让每个结点的大小等于 “页” 的大小。
因为是和不那么“技术”的小伙伴一起讨论，所以在这里就点到为止。后面再整理一下关于索引的命中、页分裂等的内容～
总结
现在让我们来总结一下，首先我们先大致了解了，一直在谈论的 “ MySQL 索引是 B+树 ”这句话到底是什么意思。通过分析索引的目的（加快查询速度），对日常生活中常见的查询场景分为数值相等的查询和数值区间范围的查询。在数值相等的查询里，我们先了解了二分查找的思想，发现它在动态更新的数据集中，在维护数据有序性的开销上有些大。发现使用二叉查找树，在动态更新的数据集中，相对于简单的二分查找，可以降低维护数据有序性上的开销。再考虑到极端情况，会出现非常 “倾斜” 的二叉查找树，所以对二叉查找树做了一些限制，不允许出现这种非常 “倾斜” 的情况，我们就得到了平衡二叉查找树。至此我们已经可以满足在数值相等的场景下对数据的快速查询。为了能够支持在数值区间范围的快速查询，对平衡二叉查找树做了一些“改造”。在树中的非叶子结点不存储数据，只存储索引，在叶子结点中存储具体数据，且在叶子结点中将数据 “串” 起来，能够支持向前向后的访问下一个数据，得到了最终的 B+树。
不难看出，B+树 这种数据结构的出现，最大的意义就在于能够对数据进行数值区间范围内的快速查找。
