Lanchester Blog

Leave a leaf

0%

MySQL 索引

Posted on Edited on In

InnoDB 存储引擎支持以下几种常见的索引：B+ 树索引、全文索引、哈希索引。

InnoDB 存储引擎会根据表的使用情况自动为表生成哈希索引，不能人为干预。B+ 树索引是传统意义上的索引。它并不能找到一个给定键值的具体行，它能找到的只是被查找数据行所在的页。然后数据库通过把页读人到内存，再在内存中进行查找，最后得到要查找的数据。

B+ 树索引

在数据库中，B+ 树的高度一般都在 2 ～ 4 层，这也就是说查找某一键值的行记录最多只需要 2 到 4 次 IO。当前一般的机械磁盘每秒至少可以做 100 次 IO，2 ~ 4 次的 IO 意味着查询时间只需 0.02~0.04 秒。

数据库中的 B+ 树索引可以分为聚集索引（clustered index）和辅助索引（secondary
index），但是不管是聚集还是辅助的索引，其内部都是 B+ 树的，即高度平衡的。聚集索引与辅助索引不同的是，聚集索引叶子节点存放的是一整行的信息，非聚集索引叶子结点存放的是索引键值和偏移量。

聚集索引

InnoDB 存储引擎表是索引组织表，即表中数据按照主键顺序存放。而聚集索引（clustered index）就是按照每张表的主键构造一棵 B+ 树，同时叶子节点中存放的即为整张表的行记录数据，也将聚集索引的叶子节点称为 数据页。聚集索引的这个特性决定了索引组织表中数据也是索引的一部分。同 B+ 树数据结构一样，每个数据页都通过一个双向链表来进行链接。

由于实际的数据页只能按照一棵 B+ 树进行排序，因此每张表只能拥有一个聚集索引。在多数情况下，查询优化器倾向于采用聚集索引。因为聚集索引能够在 B+ 树索引的叶子节点上直接找到数据。此外，由于定义了数据的逻辑顺序，聚集索引能够特别快地访问针对范围值的查询。查询优化器能够快速发现某一段范围的数据页需要扫描。

聚簇索引能够加快我们访问数据的速度，但是它也有一些局限性我们需要了解一下：

  • 聚簇索引最大限度地提高了 I/O 密集型应用的性能，但如果 数据全部都放在内存中，则访问的顺序就没那么重要了，聚簇索引也就没什么优势了
  • 插入速度严重依赖于插入顺序。按照主键的顺序插入行是将数据加载到 InnoDB 表中最快的方式。但如果不是按照主键的顺序插入，会因页分裂影响插入速度。最好避免随机的聚簇索引，特别是对于 I/O 密集型的应用
  • 聚簇索引列更新的代价很高，因为它会强制 InnoDB 将每个被更新的行移动到新的位置，这也会发生页分裂，导致性能下降

非聚集索引

非聚集索引（non-clustered index）也叫辅助索引。叶子节点并不包含行记录的全部数据。叶子节点除了包含键值以外，每个叶子节点中的索引行中还包含了一个书签（bookmark）。该书签用来告诉 InnoDB 存储引擎哪里可以找到与索引相对应的行数据。由于 InnoDB 存储引擎表是索引组织表，因此 InnoDB 存储引擎的非聚集索引的书签就是相应行数据的聚集索引键。

非聚集索引的存在并不影响数据在聚集索引中的组织，因此每张表上可以有多个非聚集索引。当通过非聚集索引来寻找数据时，InnoDB 存储引擎会遍历非聚集索引并通过叶级别的指针获得指向主键索引的主键，然后再通过主键索引来找到一个完整的行记录。

对于其他的一些数据库，如 Microsoft SQL Server 数据库，其有一种称为堆表的表类型，即行数据的存储按照插入的顺序存放。这与 MySQL 数据库的 MyISAM 存储引擎有些类似。堆表的特性决定了堆表上的索引都是非聚集的，主键与非主键的区别只是是否唯一且非空（NOT NULL）。因此这时书签是一个行标识符（Row Identifiedr, RID），可以用如“文件号:页号:槽号”的格式来定位实际的行数据。

有的 Microsoft SQL Server 数据库 DBA 问过我这样的问题，为什么在 Microsoft SQL Server 数据库上还要使用索引组织表？堆表的书签使非聚集查找可以比主键书签方式更快，并且非聚集可能在一张表中存在多个，我们需要对多个非聚集索引进行查找。而且对于非聚集索引的离散读取，索引组织表上的非聚集索引会比堆表上的聚集索引慢一些。

当然，在一些情况下，使用堆表的确会比索引组织表更快，但是我觉得大部分原因是由于存在 OLAP（On-Line Analytical Processing,在线分析处理）的应用。其次就是前面提到的，表中数据是否需要更新，并且更新是否影响到物理地址的变更。此外另一个不能忽视的是对于排序和范围查找，索引组织表通过 B+ 树的中间节点就可以找到要查找的所有页，然后进行读取，而堆表的特性决定了这对其是不能实现的。最后，非聚集索引的离散读，的确存在上述的情况，但是一般的数据库都通过实现预读（read ahead）技术来避免多次的离散读操作。因此，具体是建堆表还是索引组织表，这取决于应用，不存在哪个更优的问题。这和 InnoDB 存储引擎好还是 MyISAM 存储引擎好这个问题的答案是一样的，It all depends。

实际上，有两种用二级索引对文档数据库进行分区的方法：基于文档（document-based） 的分区 和 基于关键词（term-based） 的分区。

基于文档的分区

假设我们有一个汽车销售网站，每条数据都有唯一的 ID，我们称之为文档 ID。我们使用文档 ID 进行分区，并为汽车颜色字段创建二级索引，分区结果如下图所示：

这样的二级索引分配方法，使得每个分区都是独立的：每个分区自己维护自己的索引，它不关心其他分区的数据，这种文档分区索引也被称为 本地索引。

当我们查询红色的汽车时，需要将请求发布到所有的分区，并合并所有返回的结果，这种查询数据库的方法被称为 分散/聚集，可能会使得二级索引查询数据比较耗时。

基于关键词的分区

我们也可以构建一个覆盖所有分区数据的 全局索引，比如我们将 a 到 r 开头的颜色的二级索引保存在分区 0 中，将 s 到 z 的保存在分区 1 中，如下图所示：

img

我们将这种分区方法称为 关键词分区，根据关键词本身分区对于范围扫描非常有用，比如说我现在想获取 a 到 r 开头的颜色的所有汽车数据；而对关键词的哈希分区又能够提供分区负载均衡的能力。

基于关键词分区的全局索引优于文档分区索引的地方在于它的读取更加高效，并不需要将请求打到所有分区上，只需要将请求发送到含有对应关键词的分区即可，而它的缺点在于对单个分区文档的写入可能会产生多个分区的索引的数据变更，需要协调跨分区的分布式事务。

Cardinality 值

对于取值范围很广的字段，使用 B+ 树的索引是非常合适的，即属于高选择性。而像性别这种类型的数据，可能通过索引搜索出来的是数据库 50% 的数据，称为低选择性。

怎样查看索引是否是高选择性的呢？可以通过 SHOW INDEX 结果中的列 Cardinality 来观察。Cardinality 值非常关键，表示索引中不重复记录数量的预估值。同时需要注意的是，Cardinality 是一个预估值，而不是一个准确值，基本上用户也不可能得到一个准确的值。在实际应用中，Cardinality/n_rows_in_table 应尽可能地接近1。如果非常小，那么用户需要考虑是否还有必要创建这个索引。故在访问高选择性属性的字段并从表中取出很少一部分数据时，对这个字段添加 B+ 树索引是非常有必要的。

单表访问方式

  1. all

    全表扫描，直接扫描全部的聚簇索引。

  2. const

    通过主键或唯一二级索引与常数的等值比较定位一条记录。

  3. ref / ref_or_null

    通过普通二级索引列与常数（或 null）的等值比较扫描少量记录。

    由于普通二级索引并不限制索引列值的唯一性， 所以位于常数扫描区间中的二级索引记录可能有多条，此时使用二级索引执行查询的代价就取决于该扫描区间中的记录条数。如果该扫描区间中的记录较少，则回表操作的代价还是比较低的。

  4. range

    通过索引进行查询时，对应的扫描区间为若干个单点扫描区间或者范围扫描区间。

  5. index

    通过索引进行查询时，需要扫描全部二级索引记录的单表访问方式。

    举例：现有表 single_table 其有联合索引 idx_key( key1, key2, key3 ) 

    SELECT key1, key2, key3 FROM single_table WHERE key2 = 12

    以下查询过程符合下面两个条件：

    • 查询 key1, key2, key3，而联合索引又恰好包含这三列
    • 搜索条件为 key2，包含在索引中，但不是最左

    显然这种搜索对应的扫描区间是 (-INF,+INF)，由于二级索引记录（包含索引列和主键）比聚簇索引（包含用户定义的字段和隐藏列）记录小的多，因此扫描全部内容的成本也低很多，且不需要回表查。

索引的使用

索引使用时注意事项

  1. 只为用于搜索、排序或分组的列创建索引（缩小扫描范围）
  2. 考虑索引列中不重复值的个数（太多重复值会导致回表查操作次数过多）
  3. 索引列的类型尽量小（缩小索引树所占用的空间，减少加载时的 IO 次数）
  4. 为列前缀建立索引（加快长字符串的查询效率）
  5. 查询时覆盖索引（查询列表只包含索引列，省去回表查的性能损耗）

索引失效的原因

优化器不选择使用索引

MySQL 数据库支持索引提示（INDEX HINT）。在大多数情况下，优化器都会正常而有效的工作，但在比如索引非常多的场景下，优化器选择执行计划本身就是比较耗时的操作，通过 Index Hint 来强制优化器使用某个索引。我们可以通过 USE INDEX 提示优化器使用某索引，也可以通过 FORCE INDEX 强制优化器使用某个索引，避免 MYSQL 的自动优化。提示并不代表优化器一定会接纳，强制会可靠的保证该执行方案的如期进行。

优化器为什么不用索引？

如果查询语句通过二级索引扫描到的区间内数据占总数据量的比例非常高，因此有大量需要回表查的数据行。由于要读取很多 ID 值并不连续的聚簇索引记录，而且这些聚簇索引记录分布在不同的数据页中，这些数据页的页号也毫无规律，因此会造成大量的随机 I/O。因此其效率甚至还低于全表扫描。

优化器什么时候不用索引？

查询优化器会事先针对表中的记录计算一些统计数据， 然后再利用这些统计数据或者访问表中的少量记录来计算需要执行回表操作的记录数。如果需要执行回表操作的记录数越多，就越倾向于使用全表扫描，反之则倾向于使用二级索引+回表的方式。

导致索引失效的场景

  1. 对索引使用函数

select id from std upper(name) = ‘JIM’;

  1. 对索引进行运算

select id from std where id+1=10;
正确的做法应该是：
select id from std where id=10-1;

  1. 对索引使用<> 、not 、!=

select id from std where name != ‘jim’;
不等于操作符是永远不会用到索引的，因此对它的处理只会产生全表扫描。

  1. 对索引进行前导模糊查询

select id from std name like ‘%jim’;

  1. 隐式转换会导致不走索引

比如：字符串类型索引字段不加引号，select id from std name = 100;保持变量类型与字段类型一致

  1. 非索引字段的or连接

并不是所有的or都会使索引失效，如果or连接的所有字段都设置了索引，是会走索引的，一旦有一个字段没有索引，就会走全表扫描。

  1. 联合索引仅包含复合索引非前置列

联合索引包含 key1，key2，key3 三列，但 SQL 语句没有 key1，根据联合索引的最左匹配原则，不会走联合索引。如：select name from table where key2=1 and key3=2;

  1. 在索引列上使用 IS NULL 或 IS NOT NULL操作。索引是不索引空值的，所以这样的操作不能使用索引，可以用其他的办法处理，例如：数字类型，判断大于0，字符串类型设置一个默认值，判断是否等于默认值即可。
  2. 当全表扫描速度比索引速度快时，mysql会使用全表扫描，此时索引失效。

Multi-Range Read 优化

Multi-Range Read 优化的目的就是为了减少磁盘的随机访问，并且将随机访问转化为较为顺序的数据访问，这对于 IO-bound 类型的 SQL 查询语句可带来性能极大的提升。Multi-Range Read 优化可适用于 range，ref，eq_ref 类型的查询。

对于 InnoDB 和 MyISAM 存储引擎的范围查询和 JOIN 查询操作，MRR 的工作方式如下：

  • 将查询得到的辅助索引键值存放于一个缓存中，这时缓存中的数据是根据辅助索引键值排序的。
  • 将缓存中的键值根据 Row ID 进行排序。
  • 根据 Row ID 的排序顺序来访问实际的数据文件。

此外，若 InnoDB 存储引擎或者 MyISAM 存储引擎的缓冲池不是足够大，即不能存放下一张表中的所有数据，此时频繁的离散读操作还会导致缓存中的页被替换出缓冲池，然后又不断地被读入缓冲池。若是按照主键顺序进行访问，则可以将此重复行为降为最低。

Index Condition Pushdown（ICP）优化

Index Condition Pushdown（ICP）是一种根据索引进行查询的优化方式。在不支持 ICP 时，当进行索引查询时，首先根据索引来查询记录，然后再根据 Where 条件来过滤记录。在支持 ICP 后，MySQL 数据库会在取出来索引的同时，判断是否可以进行 Where 条件的过滤，也就是将 Where 部分的过滤操作放在了存储引擎层。在某些查询下可以大大减少上层 SQL 层对记录的索取（fetch），从而提高数据库的整体性能。ICP 优化支持 range、ref、eq_ref、ref_or_null 类型的查询。当前支持 InnoDB 和 MyISAM 存储引擎。

索引合并优化

索引优化需要区间二级索引记录按照主键排序

优化前索引查询方式

以使用索引查询为前提，通过下述 SQL 举例：

SELECT * FROM single_table WHERE key1 = 'a' AND key3 = 'b';

已知表使用 idx_key1 索引执行该查询，此时对应的扫描区间就是 ['a', 'a']。对于获取到的每条二级索引记录，根据它的 ID 值执行回表操作后获取到完整的用户记录，再判断 key3 = 'b' 条件是否成立。

这里需要注意，扫描区间 ['a','a'] 是一个单点扫描区间，也就是说位于该区间中的二级索引记录，其 key1 列的值都为 ‘a’。这也就意味着这些二级索引记录其实是按照主键值进行排序的。

Intersection (交集)索引合并

在索引根据主键排序的前提下，使用多个索引查询到的主键进行取交集操作，再执行回表查的优化方式。

从优化前索引查询方式我们可看出，对多个索引的查询方式要面临多余的回表查操作，我们可以通过对每个索引查询到的主键取交集，筛选掉大多数不符合的条目，后回表查得出结果即可。

具体查询步骤如下：

  1. 先从 idx_key1 索引的扫描区间 ['a', 'a'] 中取出第一条二级索引记录，该记录的主键值为 1。然后从 idx_key3 索引的扫描区间 ['b', 'b'] 中取出第一条二级索引记录，该记录的主键值为 2。因为 1<2，所以直接把从 idx_key1 索引中取出的那条主键值为 1 的二级索引记录丢弃。
  2. 接着继续从 idx key1 索引的扫描区间 ['a', 'a'] 中取出下一条二级索引记录，该记录的主键值为 3。步骤 1 中从 idx key3 索引的扫描区间['b, 'b'] 中取出的二级索引记录的主键值为 2。因为 3>2， 所以直接把步骤 1 中从 idx_ key3 索引的扫描区间 ['b', 'b'] 中取出的主键值为 2 的那条二级索引记录丢弃。
  3. 接着继续从 idx_key3 索引的扫描区间 ['b', 'b'] 中取出下一条二级索引记录，该记录的主键值为 3。步骤 2 中从 idx_key1 索引的扫描区间 ['a', 'a'] 中取出的二级索引记录的主键值为 3。因为 3=3，也就意味着获取主键交集成功，然后根据该主键值执行回表操作，获取到完整的用户记录后将其发送给客户端。
  4. 接着重复上述步骤，直至查询结束

SELECT * FROM single_table WHERE key1 = 'a' AND id > 9000 也可通过 Intersection 索引合并优化。

Union (并集)索引合并

与 Intersection (交集)索引合并基本类似，只是支持 or 语法的并集索引合并。

索引合并失效场景

索引合并执行的重要条件是二级索引记录按照主键值排序，而二级索引/联合索引记录的排序方式是按照 (idx_key1, idx_key2, ...，主键) 的顺序排序，以下方式并不能得到主键顺序的二级索引记录值：

  1. 联合索引 idx_key_part(part1,part2,part3)，如果 WHERE 条件是 part1 = 3 则返回的二级索引记录顺序为按照 part2 排序，不能与其他索引查询条件组成索引合并的优化场景。而如果 WHERE 条件是 part1 = 1 AND part2 = 2 AND part3 = 3 则返回的二级索引记录顺序为按照主键排序，能与其他索引查询条件组成索引合并的优化场景。
  2. 二级索引 idx_key1，如果 WHERE 条件是 idx_key1 > 'a'，返回的二级索引记录顺序按照 idx_key 排序，不能与其他索引查询条件组成索引合并的优化场景。而如果 WHERE 条件是 key = 1 则返回的二级索引记录顺序为按照主键排序，能与其他索引查询条件组成索引合并的优化场景。

Sort-Union 索引合并

对于 Union 索引合并的适用条件过于苛刻，因此有了 Sort-Union 索引合并，即先将从各个索引中扫描到的记录的主键值进行排序，再按照执行 Union 索引合并的方式进行查询。

因此，我们可以对以下 SQL 语句使用 Sort-Union 索引合并：

SELECT * FROM single_table WHERE key1 < 'a' OR key3 > 'z'

Sort-Intersection 索引合并

为啥有 Sort-Union 索引合并，而没有 Sort-Intersection 索引合并呢？是的，在 MySQL 中确实没有 Sort-Intersection 索引合并这一说，不过在 MySQL 的近亲——MariaDB 数据库中实现了 Sort-Intersection 索引合并。

按照我的理解，Sort-Union 索引合并针对的是“单独根据搜索条件从某个二级索引中获取的记录数比较少”的使用场景，这样即使对这些二级索引记录按照主键值进行排序，成本也不会太高。而 Intersection 索引合并针对的是“单独根据搜索条件从某个二级索引中获取的记录数太多，导致回表成本太大”的使用场景，使用 Intersaction 索引合并后可以明显降低回表成本。但是，如果加入 Sort-Intersection 索引合并，就需要为大量的二级索引记录按照主键值进行排序，这个成本可能比使用单个二级索引执行查询的成本都要高。

全文检索优化

全文检索（Full-Text Search）是将存储于数据库中的整本书或整篇文章中的任意内容信息查找出来的技术。它可以根据需要获得全文中有关章、节、段、句、词等信息，也可以进行各种统计和分析。

在之前的 MySQL 数据库中，InnoDB 存储引擎并不支持全文检索技术。大多数的用户转向 MyISAM 存储引擎，这可能需要进行表的拆分，并将需要进行全文检索的数据存储为 MyISAM 表。这样的确能够解决逻辑业务的需求，但是却丧失了 InnoDB 存储引擎的事务性，而这在生产环境应用中同样是非常关键的。

从 InnoDB 1.2.x 版本开始，InnoDB 存储引擎开始支持全文检索，其支持 MyISAM 存储引擎的全部功能。InnoDB 采用 full inverted index 的方式。在 InnoDB 存储引擎中，将（Document Id, Position）视为一个“ilist”。因此在全文检索的表中，有两个列，一个是 word 字段，另一个是 ilist 字段，并且在 word 字段上有设有索引。此外，由于 InnoDB 存储引擎在 ilist 字段中存放了 Position 信息，故可以进行 Proximity Search，而 MyISAM 存储引擎不支持该特性。

正如之前所说的那样，倒排索引需要将 word 存放到一张表中，这个表称为 Auxiliary Table （辅助表）。在 InnoDB 存储引擎中，为了提高全文检索的并行性能，共有 6 张 Auxiliary Table，目前每张表根据 word 的 Latin 编码进行分区。

Auxiliary Table 是持久的表，存放于磁盘上。然而在 InnoDB 存储引擎的全文索引中，还有另外一个重要的概念 FTS Index Cache（全文检索索引缓存），其用来提高全文检索的性能。

FTS Index Cache 是一个红黑树结构，其根据（word， ilist）进行排序。这意味着插入的数据已经更新了对应的表，但是对全文索引的更新可能在分词操作后还在 FTS Index Cache 中，Auxiliary Table 可能还没有更新。InnoDB 存储引擎会批量对 Auxiliary Table 进行更新，而不是每次插人后更新一次 Auxiliary Table。当对全文检索进行查询时，Auxiliary Table 首先会将在 FTS Index Cache 中对应的 word 字段合并到 Auxiliary Table 中，然后再进行查询。这种 merge 操作非常类似之前介绍的 Insert Buffer 的功能，不同的是 Insert Buffer 是一个持久的对象，并且其是 B+ 树的结构。然而 FTS Index Cache 的作用又和 Insert Buffer 是类似的，它提高了 InnoDB 存储引擎的性能，并且由于其根据红黑树排序后进行批量插入，其产生的 Auxiliary Table 相对较小。

需要注意的是 DML 操作并不能删除索引，需要进行额外的删除操作，例如 OPTIMIZE TABLE。

如果想使用全文检索，可以使用 MATCH …. AGAINST …. 语法。