likes
comments
collection
share

简单易懂的MySQL覆盖索引、前缀索引、索引下推

作者站长头像
站长
· 阅读数 14

前言

索引的出现是为了提高数据查询效率，像书的目录一样。对于数据库的表而言，索引其实就是“目录”。

常见的索引类型

  • 哈希表
  • 有序数组
  • 搜索树

哈希表

哈希表是以 KV 形式存储数据的结构，只要输入key，就可以找到对应的 value，思路很简单，就是放到数组中，根据 hash 算法计算出key在数组中确定的索引位置，把 value 存储在这个索引位置。当两个不同的 key 经过 hash 算法计算出的 索引位置相同时，就出现了哈希碰撞，这时用一个链表解决。查询的时候，根据 hash 算法计算出 value 所在数组的索引位置，然后按链表顺序遍历，直到找到 key 对应的 value

哈希表中存储数据不是按照 key 的顺序递增排序的，如果需要做范围查询的话，使用哈希结构就不得不全部扫描一遍了。

所以，哈希结构适用于等值查询的场景，比如 NoSQL

有序数组

有序数组不管是等值查询还是范围查询场景中性能都很好。等值查询时，可以根据二分查找法定位元素，时间复杂度是 O(logn)；如果是范围查询时，可以先用二分法查找到范围的下限，再向右遍历，知道查到第一个不符合范围的值，退出循环。

如果只看查询效率，有序数组是最好的数据结构了。但是，如果要新增数据，往其中数组中插入一个元素，要挪动后面所有记录，成本太高。所以，有序数组只适用于静态存储引擎，比如不会再修改，只需要查询的数据。

搜索树

二叉搜索树的节点是有序的，左节点都小于根节点，右节点都大于根节点。二叉搜索树如果出现极端的情况，性能极差，所以，平衡二叉树的查询性能更好。但是平衡二叉树的结构，每次读数据块都需要从磁盘加载到内存，为了减少 I/O 操作，要尽可能的少读磁盘，平衡多叉树可以解决这个问题，每个节点有多个子节点，这样树的高度相较于二叉树来说，低的多，查询过程中就会访问较少的数据块，从而提高查找效率。

聚簇索引/非聚簇索引

众所周知，InnoDB采用的是B+Tree这种数据结构，B+Tree 也是一种平衡多叉树。InnoDB 表中的数据都是根据主键顺序以索引的形式存放的，每一个索引在 InnoDB 中对应一棵 B+Tree ，索引类型又分为：主键索引和非主键索引。

简单易懂的MySQL覆盖索引、前缀索引、索引下推

主键索引的叶子节点存的是整行数据，在 InnoDB 中，主键索引也被称为聚簇索引。

非主键索引的叶子节点存的是主键的值，在 InnoDB 中，非主键索引也被称为二级索引。

基于主键索引和普通索引的查询有什么区别？

如果 SQL 中的 where 条件是主键，则只需要搜索主键索引的B+Tree即可查询该数据；

如果 SQL 中的 where 条件是普通索引，则先搜索普通索引的 B+Tree，得到主键的值，再根据主键的值搜索主键索引的B+Tree查询到需要的数据，这个过程称为回表。

所以，基于非主键索引的查询需要多扫描一棵树，因此，在应用中应该尽量使用主键查询。

为什么说主键的长度要尽量小并且是自增的？

B+Tree 在插入新节点时，如果插入的节点值比当前树中的值都大时，则直接插入即可。而如果插入的节点值在当前树中的值处于中间位置，就需要挪动部分数据，空出位置再插入新数据。而如果要插入数据页满了，根据B+Tree 的算法，需要申请一个新的数据页，再挪动部分数据，这个过程叫做页分裂。有分裂的情况就有合并的情况，当从树中删除一个节点时，剩余的数据在数据页中的利用率很低的时候，会将数据页做合并操作，就是分裂的逆过程。

而之所以要求主键自增是因为，如果每次要插入的节点都比当前树中最大值还大，都是追加操作，则不会触发叶子节点的分裂。

要求主键的长度要尽量短，上面我们说过，每个非聚集索引的B+Tree中存的是元素对应的主键，如果主键越长，占用的内存空间越大；而主键长度越小，普通索引的叶子节点就越小，普通索引占用的空间就越小。

覆盖索引

这条 SQL中 select * from T where k between 3 and 5，id 为主键，k 为普通索引。这条SQL的执行流程是什么样的？

  • k是普通索引，遍历k索引树，找到范围的下限3，取得对应的主键，再到主键索引树中查询主键对应的数据行。
  • 再回到k索引树取下一个值，判断是不是在要查询数据的范围内，如果在，再取到对应的主键，再去主键索引树查询到对应的数据行。
  • 直到找到超出查找的数据范围时，查找结束

上述过程中不可避免的出现了回表操作，因为数据行只有主键索引上存在，只能去遍历主键索引树。

如果执行的 SQL 是：select id from T where k between 3 and 5

  • 只需要查到遍历 k 索引树从叶子节点查到 id 的值，直到找到超出查找的数据范围时，查找结束，不需要回表操作

在这个查询中，索引 k 已经覆盖了查询需求，称为覆盖索引。由于覆盖索引可以减少树的搜索次数，显著提升查询性能，所以使用覆盖索引是一个常用的性能优化手段。

前缀索引

有一种索引是联合索引，指的是由多个字段组成的索引，也称复合索引。

如果有一个联合索引（name,age），下面通过实例说明最左前缀原则。

根据上面的联合索引，现在有如下需求：

  1. 要求查出所有名字是“张三”的人
  2. 要求查出所有姓“李”的人
  3. 要求查出所有名字中最后一个字是 “山”的人
  4. 要求查出所有年龄为 18 的人

1 的SQL条件写成：where name = "张三"，可以使用(name,age)联合索引查询，也就是从索引的最左侧开始，这个最左前缀可以是联合索引的最左N个字段。

2 的SQL条件：where name = "李%"，这时，也可以使用联合索引。

3 的SQL条件：where name = "%山"，这时，不可以使用联合索引，会导致索引失效

4 的SQL条件：where age = 18，这时，不可以使用联合索引，因为查询条件不是联合索引的最左N个字段。

综上所述，在建立联合索引时，要安排好索引的字段顺序。否则，很有可能导致索引失效。对于(name,age)联合索引，符合条件的查询条件是：

  • where name = …
  • where name = … and age = …
  • where name = … and age in (… , …)
  • order by name,age
  • where name = … order by age

还有很多情况会导致索引失效，看看都有哪些情况：

  • or 前后查询条件不都是索引子段（or 前后查询字段都是索引时会生效）
  • 未遵循最左N个字段
  • 模糊查询 like 以 % 开头
  • 需要类型转换
  • where 中索引列有计算
  • where 中索引列用到了函数
  • 索引字段上使用 not , <> , != （不等于操作符会触发全表扫描）
  • 当全表扫描速度比索引速度快时

索引下推

上面讲解了最左前缀原则，如果联合索引中不符合最左前缀原则的部分，会怎么样呢？

我们还是以联合索引（name, age）为例，要求检索出表中 “名字第一个字是张，而且年龄是10岁的所有男孩”。那么，SQL语句是这么写的：

select * from tuser where name like '张%' and age=10 and ismale=1;

1

  • 1

这个语句在搜索索引树的时候可以使用联合索引，先覆盖了 name 索引，找到第一个name字段满足"张%"的记录后，开始回表查询数据行，再从联合索引树上找下一个字段值做对比。

在MySQL 5.6之前，只能从第一个满足name条件的值开始一个个回表。到主键索引上找出数据行，再对比字段值。

而MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在索引遍历过程中，对索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

如下图，分别是 MySQL 5.6 前 和 5.6 后的执行流程图。

简单易懂的MySQL覆盖索引、前缀索引、索引下推 简单易懂的MySQL覆盖索引、前缀索引、索引下推 第一个图中，也就是无索引下推的流程图中，这个过程InnoDB并不会去看age的值，只是按顺序把“name第一个字是’张’”的记录一条条取出来回表。因此，需要回表4次。

使用了索引下推的流程图中，InnoDB在(name,age)索引内部就判断了age是否等于10，对于不等于10的记录，直接判断并跳过。在我们的这个例子中，只需要对ID4、ID5这两条记录回表取数据判断，就只需要回表2次。