这篇文章主要用来介绍 mysql 底层 innodb 在索引的选型上可以选择的索引类型，以及为什么最后选择了 B+树索引。

1. B+树索引

B+ 树是一棵完全平衡的 m 阶多叉树。所谓的 m 阶，指的是每个节点最多有 m 个子节点，并且每个节点里都存了一个紧凑的可包含 m 个元素的数组。

B+树的特点：

• 所有的叶子结点都位于同一层。
• B+树内部节点是不保存数据的。（区别于 B-树内部节点是保存数据的）
• 每个节点中的元素从小到大排列，节点当中 k-1 个元素正好是 k 个孩子包含的元素的值域分划。
• B+树相邻的叶子节点（MySQL 中为页）之间是通过链表指针连起来的

B+树内部包含三种数据结构：

• 有序数组：叶子节点位于页（16KB）中，页中的元素按照有序数组的方式存储。操作系统每次读取数据的单位为 16KB，而每个页的大小也为 16KB，因此可以极大的利用操作系统的这一特性。
• 双向链表：每个页之间采用双向链表进行连接，从而保证数据的插入、更新的时间复杂度为 O（logn）
• 树： 索引采取树状存储，可以保证每次随机读取只需要一次磁盘 IO 操作。比如说，一个 4K 的节点的内部可以存储 400 个元素，那么一个 4 层的 B+ 树最多能存储 400^4，也就是 256 亿个元素。第一层节点内存占用：4K， 第二层内存占用：400* 4K = 1.6M， 第三层内存占用：400^2 * 4K= 640M。对于现在常见的计算机来说，前三层的内部节点其实都可以存储在内存中，只有第四层的叶子节点才需要存储在磁盘中。那么对于 MySQL 的随时读取来说，每次只需要一次 IO 操作，

优点：

• 支持范围查询。
• 插入、删除、更新的时间复杂为 O（logn）。
• 查找时间复杂度为 O（logn），只需要一次磁盘 IO。

缺点：

• 每次修改数据都很有可能破坏 B+ 树的约束，我们需要对整棵树进行递归的合并、分裂等调整操作，而不同节点在磁盘上的位置很可能并不是连续的，这就导致我们需要不断地做随机写入的操作。

2.B 树索引

B 树索引和 B+树类似，主要区别如下：

• B+树中只有叶子结点才会存储数据信息，非叶子之间只会存储索引值和页指针。而 B 树非叶子节点也会存储数据信息。
• B+树叶子节点通过链表链接，而 B 树不会。

目前主流的数据库中 MongoDB 底层采取的是 B 树（又叫 B-树）存储。

因此，同样的索引树，B+树可以将更多的节点存入缓存。

优点：

• 插入、删除、更新的时间复杂为 O（logn）。
• 支持范围查询。

缺点：

• 索引结点包含信息更多，相比于 B+树 ，查询数据需要更多的 IO 操作。

3. 跳表索引

什么是跳表：跳表就是支持有序查找的二分链表。

优点：

• 支持范围查询
• 搜索时间复杂度 O（logn）
• 插入时间复杂度 O（logn）

缺点：

• 跳表随数据量增多的情况，索引层也会随着增高，相应的就会增加读取 IO 的次数，从而影响性能。

• 跳表的最底层为链表存储，不适合批量读取。

不过，meta 公司自研的 rocksdb 存储引擎底层就使用了跳表，测试下来跳表的写入性能要比 B+树更好，但是读取性能不如 B+树。由于 MySQL 更多还是读多写少的业务，因此更适合 B+树索引。

4. LSM 树索引

LSM索引至少由两棵树组成：一棵是存储在内存中较小的 C0 树，另一棵是存储在磁盘中较大的 C1 树。

其中C0树由于位于内存中，因此可以选择使用B+树或者跳表实现，业内的rocksdb采取的是跳表实现。C1树位于磁盘上，可以选择使用B+树。

当数据写入时，延迟写磁盘，将数据先存放在内存中的树里，进行常规的存储和查询。当内存中的树持续变大达到阈值时，再批量地以块为单位写入磁盘的树中。由于C0树处于内存中存在断电数据丢失的风险，LSM树采取了WAL技术（顺序写log）来保证数据不会丢失。

优点：数据写入速率比较快，性能要好于MySQL的随机写。

缺点：数据查询时需要同时查询C0树和C1树，查询速率不如MySQL。

5.有序数组索引

有序数组索引的结构如下：

数据的查找流程如下：

1. 在索引中根据索引项进行二分查找，时间复杂度为 O（logn）
2. 根据 1 中查找到的数据的位置在磁盘中进行数据查找，只需要一次磁盘 IO。

优点：

• 支持范围查询
• 索引项支持二分查找，时间复杂度为 O（logn）

缺点：

• 新增、更新、删除索引项涉及到数组的移动、扩容，时间复杂为 O（n）。时间复杂度可参考 blog.csdn.net/eg1107/arti…

6.哈希表索引

哈希表是一种以键 - 值（key-value）存储数据的结构，我们只要输入待查找的值即 key， 就可以找到其对应的值即 Value。哈希的思路很简单，把值放在数组里，用一个哈希函数把 key 换算成一个确定的位置，然后把 value 放在数组的这个位置。

如果不同的 key 经过 Hash 函数运算得到了相同的 Hash 值，则和 HashMap 解决 Hash 冲突的方法一样，拉出一个链表来。

优点

• 对于 key-value 类型的查找，时间复杂度 O（1）
• 插入时间复杂度，时间复杂度为 O（1）

缺点

• 不支持范围查询

7.为什么 MySQL 选择 B+树索引

7.1查询操作

B+树： MySQL 中的 B+ 树一般 4 层高就能够保存 256 亿条数据，而前三层节点内存占用大约 600MB 一般都可以加载到内存中，因此，一般数据查询只需要一次磁盘 IO 操作就可以拿到数据。

跳表：存储相同的数据，跳表的高度相比 B+树要更高。因为跳表平均两个节点就会抽出来一个索引节点，因此跳表索引项占据内存空间更大，能加载进内存的层高有限。和 B+ 树比，跳表的磁盘 IO 次数显然要高很多。另外，跳表底层全部采取链表存储，不适合批量读取数据（局部空间原理）。

LSM: 查询时要从后往前遍历所有segment，因此查询速度较慢。

7.2写操作

B+ 树： 插入操作涉及 B+ 树节点的拆分、合并，相对比较复杂。

跳表：跳表的插入操作不涉及页分裂、页合并等，相比 B+ 树要简单很多，所以跳表的写入方面性能要优于 B+ 树。

LSM: 写操作直接写内存，因此速度相比B+树要快很多。

	查询	写入	适用场景	产品
B+树	快	慢	亿级别数据存储，读多写少	MySQL
跳表	慢	快	数据量不多，全部内存操作	redis zset
LSM	慢	快	对写qps要求高	rocksdb

由于 MySQL 更多是读多写少的场景，并且对查询时间要求比较高，因此MySQL 底层选择的是 B+树。

1. redis为什么底层采取跳表

Redis 是内存数据库，因为不存在操作磁盘的问题，所以层的高度比较高并不是大问题。Redis 有序集合支持的核心操作一般也就是数据的插入、删除、查询，当然这些动作用红黑树、B+ 都可以完成。对于数据的插入、删除、查询等操作：

• 二叉树（包括 AVL 树、红黑树）需要对节点调整平衡（旋转、变色操作）。
• B+ 树存在一系列节点的拆分、合并操作。
• 跳表插入和删除数据时不需要考虑平衡性，也不需要拆分合并等。另外，对于按照某个区间查找数据这个操作，AVL 树、红黑树的效率没有跳表高。

因为跳表能以 O(log2n) 的时间复杂度定位到区间的起点，然后在原始链表中顺序向后遍历即可。此外，跳表的实现代码相对更简单，通过改变创建索引的算法，可以很有效地平衡代码的执行效率和内存的消耗问题。所以，Redis 选择了跳表这种数据结构，因为实现简单，代码易读易懂，开销小（效率高） 。

参考资料

• 为什么 redis 底层使用跳表：time.geekbang.org/column/arti…