MySQL 为什么使用 B+ 树索引
Why use mysql B-Tree index
1 前言
为什么 MySQL 采用 B+ 树作为索引？
如果纯粹的猜测 MySQL 数据库索引为什么使用 B+ 树？那么围绕这个问题的回答通常一定是围绕 B+ 树本身是什么，有什么优势这两点去解释这个问题。
这不是我开始这么去想的，看了很多文章都是从这一维度问答，这些回答让我失望。直到那天问了坐在我旁边那个整天摸鱼的 5 年程序员；他慵懒的回答：你想为什么是使用的是树结构呢？咦，听到这回答，一下打开了我的思绪，有点意思！
先抛开 B+ 树是什么，有什么优势，这些先入为主的答案。我想要的是为什么❓
为什么 MySQL 的索引有那么多的数据结构可选，偏偏选树结构？为什么那么多的树结构？为什么又偏偏采用 B+ 树作为索引?
这才是我要想明白的！我想要的是不只是答案，还要答案背后的脉络！我想要的不仅是要知其然，更想要知其所以然。
2 那么多数据结构，为什么选树结构？
众多的数据结构在逻辑层面可分为：线性结构和非线性结构。
线性结构有：数组、链表，基于它们衍生出的有哈希表（哈希表也称散列表）、栈、队列等。
非线性结构有：树、图。
还有其他数据结构如：跳表、位图 也都由基础数据结构演化而来，不同的数据结构存在即都是为了解决某些场景问题。
如果要知道索引适合什么数据结构，那我们得先来回答索引需要来解决什么样的问题（痛点）？和发挥着什么样的作用？其次再才是选择什么样的数据结构。后者只是果，前者才是因。
我们都知道 MySQL 存储的数据是在磁盘里，因为即使设备断电，放在磁盘的数据是不会有影响的，保障了数据不丢失，这意味着 MySQL 在磁盘上的数据是持久化的。
但数据存储在磁盘得到保障的同时也是有代价的，这代价就是磁盘的处理速度是毫秒级别的，相比内存纳秒级别的速度，简直是小巫见大巫。
你可能对时间单位没什么概念，可以看 1 毫秒能慢上纳秒几万倍。
索引虽然存储在磁盘上，但使用索引查找数据时，可以从磁盘先读取索引放到内存中，再通过索引从磁盘找到数据；再然后将磁盘读取到的数据也放到内存里。索引就让磁盘和内存强强联手，趁机搭上了内存的车，感受了一把纳秒级别速度的推背感。
但是不管查询的过程中怎么优化，只要根还在磁盘，就避免不了会发生多次磁盘 I/O ，而磁盘 I/O 次数越多，消耗的时间也越多。聪明的你这会儿可以看出这其实就是个需要考虑解决的痛点了。
- 要尽少在磁盘做 I/O 操作
但还有那么多的数据结构可选呢。其实索引需要发挥的目的已经决定了有哪些数据结构可选，那么就可以缩小选择其他数据结构的范围。从为什么要建索引本身的首要目的出发。
- 要能尽快的按照区间高效地范围查找
当然索引首要目的能支持高效范围查询，还要有插入更新等操作的动态数据结构。
所以有满足以这两条主要条件的除了树结构你还会想到其他什么数据结构？还有就是哈希表、跳表
2.1 哈希表
哈希表的物理存储是一个数组⚠️，而数组在内存中是连续地址的空间。
数据以 Key、Value 的方式存储。哈希表拥有精确的查询，所以时间复杂度是 O(1)。
而哈希表之所以能这么快是通过 Key 计算数组下标来快速找到 Value。
最简单的计算的方式是 余数法，通过先计算key的 HashCode，再通过哈希表的数组长度对 HashCode 求余，求余得出的余数就是数组下标，最后由下标访问到哈希表中存的Key、Value。
但是 Key 计算出的下标可能会有相同的情况，例如 HashCode 1010 对 6 取余是 2，但是 HashCode 1112 对 6 取余也是 2。
哈希算法随机计算出 HashCode 取余数组长度可能出现数组下标相同的情况，就是所谓的 哈希冲突。
而 哈希冲突 常用 链表 的方法解决。当发生 哈希冲突，相同下标的数据元素会替换成存储指针，而不同 Key 的数据元素添加到链表中。查找时通过指针遍历这个链表，再匹配出正确的 Key 就可以。
如上图所示，Key 是 “一颗剽悍的种子” 的字符串 ，Value 是 “不要忘了关注、点赞、评论”。我们通过计算key为 HashCode（1010） 的整数型值int。然后用 HashCode（1010） 对长度为 6 的哈希表数组长度做取余得出 2，这 2 的值元素就是 ( Key = “一颗剽悍的种子”,Value = “不要忘了关注、点赞、评论”) 。
虽然哈希表虽然可以高效的等值查询。例如SQL：
select * from weixin where username = "一颗剽悍的种子"但是不支持区间查询。例如SQL：
select * from weixin where age < 18那么如果哈希表用来做成索引，当进行范围查询时意味着要全部扫描。类似 Redis 存储形式是 KV 的 NoSQL 数据库，会适合等值查询的场景。
2.2 跳表
跳表似乎对于我们来说是一个比较陌生的数据结构，但是在 Redis 中却是比较常用的数据结构之一。跳表底层实质就是可以进行二分查找的有序链表，他在链表基础加上索引层，即能支持插入、删除等动态操作，也支持按区间高效查询。而且不管是查找、插入、删除对应的时间复杂度都是 O(logn)。
要理解跳表，先来看链表，假设链表存储是有序的数据，我们要想查询某一个数据，在最差的情况下要从头全遍历整个链表，时间复杂度是 O(n)。
如下图所示，跳表是在链表基础上加了索引层。可以起到支持区间查询的作用。
从上图所示，我们如果要查询一个 26 的节点，跳表就可以先从索引层遍历，当遍历到在索引层的 21 节点，会发现下一个索引层的节点是 36 节点时，很明显要找的 26
的节点就在这区间。此时我们只要再通过索引层指向原始链表的指针往下移到原始链这一层遍历，只要遍历 2 个节点即可找到 26 了。如果用原来的链表需要遍历 。如果用原来的链表需要遍历 10 个节点，现在只要遍历 8 个节点8 个节点，现在也只要遍历 8 个节点（5->10->16->21->36->21->21->26
），但是对于大量数据来说，是可以节省查询时间的。（原文应该是有误，这是按照我的理解写的，具体可以参看原文）。
如下图中，一图胜千言。当数据量大时，一个包含多个结点的链表，在建立了五级索引后可以突显的看到索引层的优势。同时注意道这样一个规律 “加一层索引，查询所需要遍历的节点个数减少，查询效率也就提高了。”
从用户的角度就是，跳表这家伙其实就是在告诉链表从什么地方开始找比较快。
看到这，跳表似乎也很适合用来作为索引的数据结构。但是不要忘了还有首个条件没满足，就是 “要尽少在磁盘做 I/O 操作。” 而跳表显然没能满足这一条件，跳表在随数据量增多的情况，索引层也会随着增高，相应的就会增加读取I/O的次数，从而影响性能。
那么回到 “那么多数据结构，为什么选树结构的问题？”，我们发现哈希表和跳表并不能很好的满足解决磁盘痛点和索引目的的这两个主要条件。那么我们来看为什么要来选树结构。
2.3 树结构
我们先来看现实中一颗树都有哪些部分组成，首先要有根、树枝、还有树叶。那抽象成树结构也是一样的，树结构的顶端是 根节点（root），左侧的节点称为 左子树，右子树对应的在右侧的节点，树的末端没有节点的称为 叶子节点。
从树的层级关系可以分为上下级和同级节点，如下图，D、E是B节点的子节点，那么B 节点就是它们的父节点，跟B节点在同一层级的C节点是B节点的兄弟节点。
同时树的最大层级数，称为树的高度（深度），图下的树高度是3。
从树结构的层级角度看，其实树结构是不是跟前面的跳表还有点相似。而跳表之所以这么快是因为有能按区间高效查询的索引层。
而树结构其特性决定了遍历数据方式本身就纯天然的支持按区间查询。再加上树是非线性结构的优势相比于线性结构的数组，不必像数组的数据是连续存放的。那么当树结构在插入新数据时就不用像数组插入数据前时，需要将数据所在往后的所有数据节点都得往后挪动的开销。所以树结构更适合插入更新等动态操作的数据结构。
树结构在满足了索引目的和其他条件的情况下，至于减少磁盘查询操作的痛点其实我们就可以在基于树结构的数据结构中去选择。
3 那么多的树结构？为什么偏偏采用 B+ 树作为索引?
那么多的树结构中，除了B+树，你还会想到哪些树结构？二叉树查找树、自平衡二叉树、B树。
3.1 二叉树
在了解二叉查找树或者自平衡二叉树前需要先简单知道什么是二叉树，什么是二分查找树。因为你看二叉查找树不就是这两棵树的合并吗。
我们先来看看二叉树，二叉树的树结构中定义的是每个节点的可以是0个子节或1个子节点，但是最多不超2个子节点。
而二叉树还有两个形式：满二叉树、完全二叉树
满二叉树
满二叉树的定义是一棵二叉树的所有非叶子节点都存在左右子节点，并且所有子节点在同一层级。
完全二叉树
完全二叉树是指从左至右填充节点，直到最后一层，且最后一层的节点都靠左对齐。因此，满二叉树的所有层都可能被填充满，而完全二叉树虽然最后一层不一定满，但是尽可能填充到最左侧。如下图。
3.2 二叉查找树
此二叉查找树的 “二” 非彼二，因为此 “二” 既可以说是表示二叉的树，也可以表示二分查找，因为二叉查找树既是二叉也融合了二分查找。
先简单的看看二分查找，二分查找可以避免有序的数组从头依次的遍历查询，因为我们知道这种情况如果要查找一个数最差的情况时间复杂就是O(n)
，整体查询效率不高。而如果数组是有序的，就可以通过二分查找将每次的查询范围减半，时间复杂度自然就是O(logn)。如下图所示。
所以说，二叉查找树不同于普通二叉查找树，是将小于根节点的元素放在左子树，而右子树正好相反是放大于根节点的元素。说白了就是根节点是左子树和右子树的中位数，左边放小于中位数的，右边放大于中位数，这不就是二分查找算法的奥义。
如上动图所示，二分查找树在查找数据时，只需要将需要查找的元素与树节点元素进行比较，当元素大于根节点则往右子树中查找，元素小于根节点则往左子树中查找，元素如果正好是中位数那么就是正好是根节点，所以二叉查找树具备高效查询。
但是二叉树也有明显弊端，在极端情况下，如果每次插入的数据都是最小或者都是最大的元素，那么树结构会退化成一条链表。查询数据是的时间复杂度就会是O(n)，如下图所示。
当二分查找树退化成链表时，我们知道链表不仅不能高效查询而且也增加了磁盘 IO 操作，所以我们得划向下一个树型数据结构。
3.3 自平衡二叉树/AVL树
自平衡二叉树就是来解决二叉查找树极端下退化成链表的问题，自平衡二叉树也称平衡二叉查找树（AVL树）。
可以看到从简单的二叉树，一步步演化到二分查找树再到现在的自平衡二叉树。一个简单的东西慢慢的逐渐走向复杂。如果只知道答案，我们是不会知道来龙去脉的。
平衡二叉查找树其实主要就是在二叉查找树的基础上加上约束：让每个节点的左右子树高度差不能超过 1。那么这样让可以让左右子树都保持平衡，让查询数据操作的时间复杂度在 O(logn)。
如下图所示，平衡二叉查找树将每次插入的元素数据都会维持自平衡。
如下图所示，普通非平衡二叉树和平衡二叉树的对比。
还有在 Java 中集合类常见的红黑树，也是自平衡二叉树中的一种。
但是不管自平衡树是平衡二叉查找树还是红黑树，都会随着插入的元素增多，而导致树的高度变高，这同样意味着磁盘 I/O 操作次数多，影响到整体查询的效率。
3.4 B树
我们平时看到B+树还有B-树，不免就会将B-树读成B减树 ，但B-树其-横线只是连接符，所以B-树就是称为B树。
自平衡二叉树虽然查找的时间复杂度在O(logn)，前面也说过它本身是一个二叉树，每个节点只能有2个子节点，那么随着数据量增大的时候，节点个数越多，树高度也会增高（也就是树的深度越深），增加磁盘 I/O 次数，影响查询效率。
那么你如果从树形结构的二叉树这一路的进阶过程中可以看到，二叉树每一次为了解决一个新的问题都会创造出新的bug或者创造一个又个的痛点。看到这就不难猜到，B树的出现可以解决树高度的问题。
之所以是 B 树，而并不是名称中 “xxx二叉树”，就是它不再限制一个父节点中只能有两个子节点，而是允许 M 个子节点（M > 2）。不仅如此，B树的一个节点可以存储多个元素，相比较于前面的那些二叉树数据结构又将整体的树高度降低了。
B 树的节点可以包含有多个子节点，所以B树是一棵多叉树，它的每一个节点包含的最多子节点数量的称为B树的阶。如下图是一颗 3 阶的 B 树。
上图中每一个节点称为页，在 mysql 中数据读取的基本单位是页，而页就是我们上面所说的磁盘块。磁盘块中的 p 节点是指向子节点的指针。
指针在树结构中都有，在前面的二叉树中也都是有的。
那我们来看一下上图所示，当一颗 3 阶的B树查找 90 这个的元素时的流程是怎么样的？
先从根节点出发，也就是 磁盘块1，判断 90 在17 ~ 35之间，通过磁盘块1中的指针 p3 找到磁盘块4。还是按照原来的步骤，在磁盘块4中的65 ~ 87之间相比较，最后磁盘4的指针p3找到磁盘块11。也就找到有匹配90的键值。
可以发现一颗 3 阶的 B 树在查找叶子节点时，由于树高度只有 3，所以查找过程最多只需要3次的磁盘 I/O 操作。
数据量不大时可能不太真切。但当数据量大时，节点也会随着增多；此时如果还是前面的自平衡二叉树的场景下，由于二叉树只能最多2个叶子节点的约束，也只能纵向去的去扩展子节点，树的高度会很高，意味着需要更多的操作磁盘 I/O 次数。而 B 树则可以通过横向扩展节点从而降低树的高度，所以效率自然要比二叉树效率更高。直白说就是变矮胖了。
看到这，相信你也知道如果 B 树这么适合，也就没有接下来 B+ 树的什么事了。
接着，那为什么不用 B 树，而用 了B+ 树呢？
其实，B 树其实已经满足了我们最前面所要满足的条件，减少磁盘 I/O 操作，同时支持按区间查找。但注意，虽然 B 树支持按区间查找，但并不高效。
例如上面的例子中，B树能高效的通过等值查询 90这个值，但不方便查询出一个区间内比如，3 ~ 10 区间内所有数的结果。因为当B树做范围查询时需要使用中序遍历，那么父节点和子节点也就需要不断的来回切换涉及了多个节点会给磁盘 I/O 带来很多负担。
3.5 B+树
B+ 树从+的符号可以看出是 B 树的升级版，MySQL 中 innoDB 引擎中的索引底层数据结构采用的正是 B+ 树。
B+ 树相比于 B 树，做了这样的升级：B+ 树中的非叶子节点都不存储数据，而是只作为索引。
由叶子节点存放整棵树的所有数据。而叶子节点之间构成一个从小到大有序的链表互相指向相邻的叶子节点，也就是叶子节点之间形成了有序的双向链表。如下图 B+ 树的结构。
B+ 树是不是有点像前面的跳表，数据底层是数据，上层都是按底层区间构成的索引层，只不过它不像跳表是纵向扩展，而是横向扩展的 “跳表”。这么做的好处即减少磁盘的 IO 操作又提高了范围查找的效率。
接着再来看 B+ 树的插入和删除，B+ 树做了大量冗余节点，从上面可以发现父节点的所有元素都会在子节点中出现，这样当删除一个节点时，可以直接从叶子节点中删除，这样效率更快。
B 树相比于 B+ 树，B 树没有冗余节点，删除节点时会发生复杂的树变形，而 B+ 树有冗余节点，不会涉及到复杂的树变形。而且 B+ 树的插入也是如此，最多只涉及树的一条分支路径。B+ 树也不用更多复杂算法，可以类似黑红树的旋转去自动平衡。
4 总结
从文章的题目开始就是一个问题，我们并没有直接回答为什么MySQL 采用 B+ 树作为索引的答案，而是相反的问出了两个问题，一个问题是那么多数据结构，为什么选树结构？另一个问题是那么多的树结构，又为什么偏偏采用 B+ 树？
要得到果，得先知道因，我们从两个方面开始出发，因为 MySQL 的数据是放在磁盘的，而磁盘的处理速度是毫秒级别的，如果在磁盘 IO 做过多查询操作，会给查询带来负担，所以要尽少在磁盘 I/O 操作中做查询。另一个是从索引本身的首要目的，要能按区间高效地范围查找。
有了因，我们就开始去探索果，我们就可以先来回答第一个问题，“那么多数据结构，为什么选树结构？” 在其他数据结构中按逻辑结构的线性结构有哈希表和跳表。哈希表底层基于数组，虽然可以高效查询，但是只能等值查询，而不能支持范围查询。而跳表底层是链表，通过索引层可以实现高效的区间查询，但是随着数据量的递增，索引层也随着数据量的增多而增加。所以采用树的数据结构，树结构其特性决定了遍历数据方式本身就纯天然的支持按区间查询。树结构在插入等操作不用线性结构数组的开销，所以更适合插入更新等动态操作的数据结构。
接着我们另一个问题，“那么多的树结构，又为什么偏偏采用B+树？” 我们从树结构中父节点最多只能有两个子节点的二叉树，再从二叉树加上二分查找的二叉查找树，二叉树展现了高效的查询能力；但二叉查找树在极端情况下会退化成链表，所以进阶到自平衡二叉树，自平衡二叉树约束了每个节点的左右子树相差不能大于 1，但是二叉树因为只能最多是两个子节点，所以树的高度过高会导致磁盘做过多 I/O 的查询操作负担。
所以最后真正到了 B 树，B 树是多叉树，但只能高效单查询，并不能高效区间查询。所以才有 B+ 树，B+ 树是 B 树的升级，所有非叶子节点都用来做索引，只有叶子节点存储数据而且是有序双向的链表，树节点做了冗余，相比于 B 树既能支持高效的区间查询，插入和删除都比 B 树更加出色。