MySQL底层为什么选择用B+树作为索引

首先，我们来想想为什么这么多数据结构，为什么要用树这种数据结构？

众多的数据结构在逻辑层面可分为：线性结构 和 非线性结构。

线性结构有：数组、链表，基于它们衍生出的有哈希表（哈希表也称散列表）、栈、队列等。

非线性结构有：树、图。

还有其他数据结构如：跳表、位图 也都由基础数据结构演化而来，不同的数据结构存在即都是为了解决某些场景问题。

如果要知道索引适合什么数据结构，那我们得先来回答索引需要来解决什么样的问题（痛点）？和发挥着什么样的作用？其次再才是选择什么样的数据结构；后者只是果，前者才是因。

我们都知道MySQL存储的数据是在磁盘里，因为即使设备断电，放在磁盘的数据是不会有影响的，保障了数据不丢失，这意味着MySQL在磁盘上的数据是持久化的。

但数据存储在磁盘得到保障的同时也是有代价的，这代价就是磁盘的处理速度是毫秒级别的，相比内存纳秒级别的速度，简直是小巫见大巫。

这里简单介绍一下跳图的概念：

跳表底层实质就是可以进行二分查找的有序链表。而且在链表基础加上索引层。即能支持插入、删除等动态操作，也支持按区间高效查询。而且不管是查找、插入、删除对应的时间复杂度都是 O(logn)。

要理解跳表，先来看链表，假设链表存储是有序的数据，我们要想查询某一个数据，在最差的情况下要从头全遍历整个链表，时间复杂度是 O(n)。

从上图所示，我们如果要查询一个 26 的节点，跳表就可以先从索引层遍历，当遍历到在索引层的 21 节点，会发现下一个索引层的节点是 36 节点时，很明显要找的 26 的节点就在这区间。此时我们只要再通过索引层指向原始链表的指针往下移到原始链这一层遍历，只要遍历 2 个节点即可找到 26 了。如果用原来的链表需要遍历 10 个节点，现在只要遍历 8 个节点。

如下图中，一图胜千言。当数据量大时，一个包含多个结点的链表，在建立了五级索引后可以突显的看到索引层的优势。同时注意道这样一个规律 “加一层索引，查询所需要遍历的节点个数减少，查询效率也就提高了。” （从用户的角度就是，跳表这家伙其实就是在告诉链表从什么地方开始找比较快）

那为什么不用跳表作为MySQL的底层索引结构呢？

可以从尽量减少从磁盘查询这个角度寻找答案，这里就不做过多描述了~

接下来看树，这么多树，为什么要选择B+树？

直接跳到AVL(平衡二叉树)树来讲讲，AVL树可以保证每一个节点他的左右子树的高度差都不会超过1，这样相较于二叉查找树来讲可以有效防止链化，但是随着数据变多，这棵树整个高度也会变高，同样会提高磁盘的查询效率~

为了解决这样的问题，我们后面又引入了B树(B-树)，因为B树这种数据结构他的一个节点就可以存在多个子节点，同时，一个节点里面又可以存储多个元素，这样就有效解决了前面AVL树带来的问题

那我们来看一下上图所示，当一颗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带来很多负担。

好，那最后我们再来看看为什么要用B+树？

B+树这种结构他的每一个节点存放的都是索引，所有值都是存放在叶子结点里面的，而叶子节点之间构成一个从小到大有序的链表互相指向相邻的叶子节点，也就是叶子节点之间形成了有序的双向链表。

所以，相对于B树而言，B+树在删除节点过程中会添加复杂的删除节点的操作，没有冗余节点，但是对于B+树来说，只会在叶子结点上进行操作，非叶子节点不做处理，有冗余节点，但是不会涉及到复杂的树变形；而且对于插入来讲，B+树的插入最多也只需要修改一条路径，也不涉及复杂度算法实现，可以类似于红黑树的旋转去实现平衡。