MySQL 索引

1. 索引介绍

1.1. 优缺点

优点：

• 可以提高数据检索的效率，降低数据库的 IO 成本，类似于书的目录；
• 通过索引列对数据进行排序，降低数据排序的成本，降低了 CPU 的消耗；

缺点：

• 索引会占据磁盘空间；
• 降低更新表的效率；

每次对表进行增删改操作，MySQL 不仅要保存数据，还有保存或者更新对应的索引记录。

2. 索引类型

2.1. 按功能分类

• 主键索引：索引列中的值必须是唯一的，不允许有空值。

• 普通索引：MySQL 中基本索引类型，没有什么限制，允许在定义索引的列中插入重复值和空值。

• 唯一索引：索引列中的值必须是唯一的，但是允许为空值。

• 全文索引：只能在文本类型 CHAR、VARCHAR、TEXT 类型字段上创建全文索引。字段长度比较大时，如果创建普通索引，在进行 LIKE 模糊查询时效率比较低，这时可以创建全文索引（MyISAM 和 InnoDB 都支持全文索引）。

• 空间索引：MySQL 在 5.7 之后的版本支持了空间索引，而且支持 OpenGIS 几何数据模型。MySQL 在空间索引这方面遵循 OpenGIS 几何数据模型规则。

• 前缀索引：在文本类型如 CHAR、VARCHAR、TEXT 类列上创建索引时，可以指定索引列的长度，但是数值类型不能指定。

2.2. 按存储形式分类

• 聚集索引：物理结构索引，索引结构的叶子结点保存了行数据。必须有，有且只有一个；
• 非聚集索引/二级索引：逻辑结构索引，索引结构的叶子节点关联的是对应的主键。可以存在多个；

聚集索引选取规则：

• 如果存在主键，则将主键索引作为聚集索引；
• 如果不存在主键，将使用第一个 UNIQUE 索引作为聚集索引；
• 如果表没有主键，或没有合适的唯一索引，则 InnoDB 会自动生成一个 rowid 作为隐藏的聚集索引；

2.3. 按照列数量分类

1. 单列索引；
2. 组合索引；

组合索引的使用，需要遵循最左前缀匹配原则（最左匹配原则）。一般情况下在条件允许的情况下使用组合索引替代多个单列索引使用。

3. 索引的数据结构

3.1. Hash 表

Hash 表，在 Java 中的 HashMap、TreeMap 就是 Hash 表结构，以键值对的方式存储数据。我们使用 Hash 表存储表数据 Key 可以存储索引列，Value 可以存储行记录或者行磁盘地址。Hash 表在等值查询时效率很高，时间复杂度为 $O(1)$；但是不支持范围快速查找，范围查找时还是只能通过扫描全表方式。

Tip：InnoDB 支持自适应 Hash 索引，它是根据 B+ 树索引在指定条件下自动构建的。

3.2. 二叉查找树

二叉树，我想大家都会在心里有个图。

图 3.1 - 二叉树

二叉树特点：每个节点最多有 2 个分叉，左子树和右子树数据顺序左小右大。

这个特点就是为了保证每次查找都可以这折半而减少 IO 次数，但是二叉树就很考验第一个根节点的取值。在有序插入的情况下，很容易导致二叉树失衡。

图 3.2 - 失衡二叉树

3.3. 平衡二叉树

平衡二叉树是采用二分法思维，平衡二叉查找树除了具备二叉树的特点，最主要的特征是树的左右两个子树的层级最多相差 1。在插入删除数据时通过左旋/右旋操作保持二叉树的平衡，不会出现左子树很高、右子树很矮的情况。

使用平衡二叉查找树查询的性能接近于二分查找法，时间复杂度是 $O(log2n)$。查询 id = 6，只需要两次 IO。

图 3.3 - 平衡二叉树

就这个特点来看，可能各位会觉得这就很好，可以达到二叉树的理想的情况了。然而依然存在一些问题：

1. 时间复杂度和树高相关。树有多高就需要检索多少次，每个节点的读取，都对应一次磁盘 IO 操作。树的高度就等于每次查询数据时磁盘 IO 操作的次数。磁盘每次寻道时间为 10ms，在表数据量大时，查询性能就会很差。

2. 平衡二叉树不支持范围查询快速查找，范围查询时需要从根节点多次遍历，查询效率不高。

3.4. B 树

MySQL 的数据是存储在磁盘文件中的，查询处理数据时，需要先把磁盘中的数据加载到内存中，磁盘 IO 操作非常耗时，所以我们优化的重点就是尽量减少磁盘 IO 操作。访问二叉树的每个节点就会发生一次 IO，如果想要减少磁盘 IO 操作，就需要尽量降低树的高度。那如何降低树的高度呢？

假如 key 为 BIGINT = 8 字节，每个节点有两个指针，每个指针为 4 个字节，一个节点占用的空间 16 个字节（$8+4\ast 2=16$）。

因为在 MySQL 的 InnoDB 存储引擎一次 IO 会读取的一页（默认一页 16K）的数据量，而二叉树一次 IO 有效数据量只有 16 字节，空间利用率极低。为了最大化利用一次 IO 空间，一个简单的想法是在每个节点存储多个元素，在每个节点尽可能多的存储数据。每个节点可以存储 1000 个索引（16k / 16 = 1000），这样就将二叉树改造成了多叉树，通过增加树的叉树，将树从高瘦变为矮胖。构建 1 百万条数据，树的高度只需要 2 层就可以（1000 * 1000 = 1 百万），也就是说只需要 2 次磁盘 IO 就可以查询到数据。磁盘 IO 次数变少了，查询数据的效率也就提高了。

这种数据结构我们称为 B 树，B 树是一种多叉平衡查找树，如下图主要特点：

1. B 树的节点中存储着多个元素，每个内节点有多个分叉；
2. 节点中的元素包含键值和数据，节点中的键值从大到小排列。也就是说，在所有的节点都储存数据；
3. 父节点当中的元素不会出现在子节点中；
4. 所有的叶子结点都位于同一层，叶节点具有相同的深度，叶节点之间没有指针连接；

图 3.4 - B 树

假如我们查询值等于 10 的数据。查询路径：磁盘块 1 -> 磁盘块 2 -> 磁盘块 5：

• 第一次磁盘 IO：将磁盘块 1 加载到内存中，在内存中从头遍历比较，10 < 15，走左路，到磁盘寻址磁盘块 2。

• 第二次磁盘 IO：将磁盘块 2 加载到内存中，在内存中从头遍历比较，7 < 10，到磁盘中寻址定位到磁盘块 5。

• 第三次磁盘 IO：将磁盘块 5 加载到内存中，在内存中从头遍历比较，10 = 10，找到 10，取出 data，如果 data 存储的行记录，取出 data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。

相比二叉平衡查找树，在整个查找过程中，虽然数据的比较次数并没有明显减少，但是磁盘 IO 次数大大减少。同时，由于我们的比较是在内存中进行的，比较的耗时可以忽略不计。B 树的高度一般 2 至 3 层就能满足大部分的应用场景，所以使用 B 树构建索引可以很好的提升查询的效率。

看到这里一定觉得 B 树就很理想了，但是前辈们会告诉你依然存在可以优化的地方：

1. B 树不支持范围查询的快速查找，你想想这么一个情况如果我们想要查找 10 和 35 之间的数据，查找到 15 之后，需要回到根节点重新遍历查找，需要从根节点进行多次遍历，查询效率有待提高。

2. 如果 data 存储的是行记录，行的大小随着列数的增多，所占空间会变大。这时，一个页中可存储的数据量就会变少，树相应就会变高，磁盘 IO 次数就会变大。

3.5. B+ 树

B+ 树，作为 B 树的升级版，在 B 树基础上，MySQL 在 B 树的基础上继续改造，使用 B+ 树构建索引。B+ 树和 B 树最主要的区别在于非叶子节点是否存储数据的问题

• B 树：非叶子节点和叶子节点都会存储数据。

• B+ 树：只有叶子节点才会存储数据，非叶子节点只存储键值。叶子节点之间使用双向指针连接，最底层的叶子节点形成了一个双向有序链表。

图 3.5 - B+ 树

B+ 树的最底层叶子节点包含了所有的索引项。从图上可以看到，B+ 树在查找数据的时候，由于数据都存放在最底层的叶子节点上，所以每次查找都需要检索到叶子节点才能查询到数据。

Tip：在 InnoDB 中 Data 存储的为行数据，而 MyIsam 中存储的是磁盘地址。

所以在需要查询数据的情况下每次的磁盘的 IO 跟树高有直接的关系，但是从另一方面来说，由于数据都被放到了叶子节点，放索引的磁盘块所存放的索引数量是会跟着增加的，相对于 B 树来说，B+ 树的树高理论上情况下是比 B 树要矮。

也存在索引覆盖查询的情况，在索引中数据满足了当前查询语句所需要的全部数据，此时只需要找到索引即可立刻返回，不需要检索到最底层的叶子节点。

• 等值查询：

  假如我们查询值等于 9 的数据。查询路径磁盘块 1 -> 磁盘块 2 -> 磁盘块 6：

  • 第一次磁盘 IO：将磁盘块 1 加载到内存中，在内存中从头遍历比较，9 < 15，走左路，到磁盘寻址磁盘块 2。

  • 第二次磁盘 IO：将磁盘块 2 加载到内存中，在内存中从头遍历比较，7 < 9 < 12，到磁盘中寻址定位到磁盘块 6。

  • 第三次磁盘 IO：将磁盘块 6 加载到内存中，在内存中从头遍历比较，在第三个索引中找到 9，取出 data，如果 data 存储的行记录，取出 data，查询结束。如果存储的是磁盘地址，还需要根据磁盘地址到磁盘中取出数据，查询终止。

• 范围查询：

  假如我们想要查找 9 和 26 之间的数据。查找路径是磁盘块 1 -> 磁盘块 2 -> 磁盘块 6 -> 磁盘块 7：

  • 首先查找值等于 9 的数据，将值等于 9 的数据缓存到结果集。这一步和前面等值查询流程一样，发生了三次磁盘 IO。

  • 查找到 15 之后，底层的叶子节点是一个有序列表，我们从磁盘块 6，键值 9 开始向后遍历筛选所有符合筛选条件的数据。

  • 第四次磁盘 IO：根据磁盘 6 后继指针到磁盘中寻址定位到磁盘块 7，将磁盘 7 加载到内存中，在内存中从头遍历比较，9 < 25 < 26，9 < 26 <= 26，将 data 缓存到结果集。

可以看到 B+ 树可以保证等值和范围查询的快速查找，因此 MySQL 索引使用的是 B+ 树。

4. InnoDB 索引高度计算

InnoDB 存储引擎最小储存单元是页，一页大小就是 16k。

B+ 树叶子存的是数据，内部节点存的是键值 + 指针。索引组织表通过非叶子节点的二分查找法以及指针确定数据在哪个页中，进而再去数据页中找到需要的数据；

假设 B+ 树的高度为 2 的话，即有一个根结点和若干个叶子结点。这棵 B+ 树的存放总记录数为根结点指针数 * 单个叶子节点记录行数。假设一行记录的数据大小为 1k，那么单个叶子节点可以存的记录数为 $16k/1k=16$。

非叶子节点内存放多少指针呢？我们假设主键 ID 为 BIGINT 类型，长度为 8 字节（INT 类型的话，一个 INT 就是 32 位，4 字节），而指针大小是固定的在 InnoDB 源码中设置为 6 字节，假设 n 指主键个数即 key 的个数，$n\ast 8+(n+1)\ast 6=16K=16\ast 1024B$，算出 n 约为 1170，意味着根节点会有 1170 个 key 与 1171 个指针。因此，一棵高度为 2 的 B+ 树，能存放 $1171\ast 16=18736$ 条这样的数据记录。同理一棵高度为 3 的 B+ 树，能存放 $1171\ast 1171\ast 16=21939856$，也就是说，可以存放两千万左右的记录。B+ 树高度一般为 1 ~ 3 层，已经满足千万级别的数据存储。

5. 索引覆盖

5.1. 避免回表

在 InnoDB 的存储引擎中，使用辅助索引查询的时候，因为辅助索引叶子节点保存的数据不是当前记录的数据而是当前记录的主键索引，索引如果需要获取当前记录完整数据就必然需要根据主键值从主键索引继续查询。这个过程我们成位回表。想想回表必然是会消耗性能影响性能。那如何避免呢？

例如 select id, name, sex from user where name ='zhangsan'; 这个语句在业务上频繁使用到，而 user 表的 sex 字段更新频率很低，在这种情况下，如果我们在建立 name 字段的索引的时候，不是使用单一索引，而是使用联合索引 (name, sex) 这样的话再执行这个查询语句，根据辅助索引查询到的结果就可以获取当前语句的完整数据。这样就可以有效地避免了回表，再获取 sex 的数据。

5.2. 联合索引的使用

在建立索引的时候，尽量在多个单列索引上判断下是否可以使用联合索引。联合索引的使用不仅可以节省空间，还可以更容易的使用到索引覆盖。

试想一下，索引的字段越多，是不是更容易满足查询需要返回的数据呢。比如联合索引 (a_b_c)，是不是等于有了索引：(a)、(a_b)、(a_b_c) 三个索引，这样是不是节省了空间，当然节省的空间并不是三倍于 (a)、(a_b)、(a_b_c) 三个索引，因为索引树的数据没变，但是索引 data 字段的数据确是真实的节省了。

联合索引的创建原则，在创建联合索引的时候因该把频繁使用的列、区分度高的列放在前面，频繁使用代表索引利用率高，区分度高代表筛选粒度大，这些都是在索引创建的需要考虑到的优化场景，也可以在常需要作为查询返回且更新频率极低的字段增加到联合索引中，如果在联合索引上增加一个字段而使用到了覆盖索引，那我建议这种情况下使用联合索引。