【享学MySQL】系列：MySQL索引的数据结构，索引种类及聚簇索引和非聚簇索引

我是少侠露飞。博客不仅是笔记，更是一种思考，一种分享。

前言

MySQL索引是MySQL关键思想，对提升SQL性能意义颇大，也是每一个后端开发者应该熟稔于心的知识。

MySQL索引本质上是一种数据结构。是MySQL组织数据一种形式，便于提高查询效率。

1 MySQL索引的数据结构

MySQL索引其实有四种：B+树索引、哈希索引、倒排索引、R树索引（这里针对InnoDB引擎）。B+树索引是最常用的数据类型，也是开发、面试中的重点考察内容，其它三种索引仅做了解。

1.1 B+Tree索引

B+树索引是本篇重点介绍的。B的意思是Balance（代表平衡，千万不要理解为是Binary），索引B+树即多路平衡搜索树，而非是二叉树！
B+Tree是在B-Tree基础上的一种优化，使其更适合实现外存储索引结构。在B+Tree中，所有数据记录节点都是按照键值大小顺序存放在同一层的叶子节点上，而非叶子节点上只存储key值信息，这样可以大大加大每个节点存储的key值数量，降低B+Tree的高度。

1.2 哈希索引

InnoDB存储引擎的哈希索引是自适应的，也就是说会根据表的使用情况自动为表生成哈希索引（如观察到建立哈希索引可以带来速度的提升则建立哈希索引），并且只是在某些页建立，不能人为干预是否在一张表生成哈希索引。

1.3 倒排索引

从MySQL5.7.6版本开始支持。是搜索引擎底层数据结构。通过对内容进行分词实现快速查询。仅仅从MySQL的角度可以不去深入研究该索引，但要是专门做搜索引擎，如Lucene或者Elastic Search则必须深入理解该索引结构。

1.4 R树索引

在MySQL很少使用，仅支持geometry数据类型，有个较大的优势是范围查询，对此类型少侠表示也从来没用过。

2 MySQL索引的种类

2.1 普通索引

是最常用的索引类型，没有限制，仅为了加速查询。

2.2 唯一索引

加速查询，列值限制唯一，可以为null但null值只能出现一次。

2.3 主键索引

加速查询，列值唯一且不能为null。一般是自增数字，当然也可以是UUID但强烈不建议。

2.4 联合索引

多个列组成一个索引，专门用于组合查询，其效率大于索引合并。注意组合索引查询时需满足最左前缀匹配原则。

2.5 全文索引

基于倒排索引的数据类型，对文本的内容进行分词，进行搜索。

3 聚簇索引和非聚簇索引

3.1 聚簇索引

我们知道，对于InnoDB存储引擎来说，表中数据是按照主键顺序存放，而聚簇索引就是按照每张表的主键去构造一颗B+树，并且叶子节点中存放着的是整张表的行记录数据。
每张表只能拥有一个聚簇索引，并且MySQL的查询优化器非常倾向于采取聚簇索引，因为聚簇索引能让我们在索引的叶子节点上直接找到行数据。

3.2 非聚簇索引

非聚簇索引也称为辅助索引，叶节点不包含行的全部数据。叶节点除了包含键值以外，每个叶节点的索引行还包含了一个书签（bookmark），该书签就是相应行数据的聚集索引键，用来告诉InnoDB引擎在哪里可以找到与索引相对应的行数据。

当通过非聚簇索引查询数据时，InnoDB引擎会遍历非聚簇索引并通过叶节点的书签来获得指向聚簇索引的主键，然后再通过聚簇索引来找到一个完整的行记录。这个过程其实就叫做回表，所以回表比较慢，因为相比聚簇索引，多了一次索引查询过程。

聚簇索引和非聚簇索引的关系如下图所示：

3.3 聚簇索引和非聚簇索引查询时的区别

根据上面的分析，由于聚簇索引树的叶子节点直接就是我们要查询的整行数据了。而非聚簇索引的叶子节点是主键的值，查到主键的值以后，还需要再通过主键的值再进行一次查询（此过程即为回表）。正因为多了一次回表的操作，所以通过非聚簇索引查询效率经常低于聚簇索引的查询效率。

但是非聚簇索引查询一定就比聚簇索引慢吗？

其实不然，MySQL还有一种技术叫做覆盖索引，没错，就是执行计划的Extra列中经常出现的一个值：covering index，它是指一个查询语句的执行只用从索引中就能够取得，不必从数据表中读取。也可以称之为实现了索引覆盖。当一条查询语句符合覆盖索引条件时，MySQL只需要通过索引就可以返回查询所需要的数据，这样避免了查到索引后再返回表操作，减少I/O提高效率。如，表covering_index_sample中有一个普通索引 idx_key1_key2(key1,key2)。当我们通过SQL语句：select key2 from covering_index_sample where key1 = ‘keytest’;的时候，就可以通过覆盖索引查询，无需回表。

4 B+树索引的使用

4.1 什么时候适合建立索引

首先需要明确，并不是所有场景下都要为每个字段创建索引的。我的经验是：当访问表中很少一部分数据行时，使用B+树索引才有意义。

关于此点，少侠曾经做过测试，当扫描行数高于总表记录的20%时，索引就会失效，退化成全表扫描，这是MySQL优化器的选择，不是SQL书写的问题。

比如说，用户表里有个性别字段，基本上只有’M’和’F’两个选择，并且比例几乎是1:1（这里就不考虑男女比例失衡的社会问题），此时这个字段选择性很小，建立索引有何意义呢，基本上每次都是扫描半张表。而对于用户名，重复的概率很小，即具有高选择性，则很适合建立索引。

4.2 顺序读、随机读与预读取

上面提到当字段值具有高选择性、每次查询只取出表中少部分数据时才适合建立索引。但这根本的原因又是什么呢？这要从顺序读和随机读这两个概念说起…
顺序读是指顺序地读取磁盘上的块（Block）。在数据库中是指根据索引的叶结点数据就能顺序地读取所需的行数据（B+树有个特点：叶节点的数据是以链表的形式顺序关联起来的）。顺序读实际上是逻辑的顺序读，在物理磁盘上可能还是随机读。
随机读是指访问的块不是连续的，需要磁盘的磁头不断的移动。随机读一般是指访问非聚簇索引节点时不能得到完整的结果，需要根据非聚簇索引叶节点中的主键去聚簇索引里查找实际的行数据。
随机读的性能要远远低于顺序读的性能，所以当SQL语句通过某个非聚簇索引查询时，如果预估查询行数很多，达到一定的比例，MySQL优化器会选择全表的扫描方式，而不会走非聚簇索引。
当然MySQL为了提高读取的性能，InnoDB引擎引入了预读取技术（prefetch）。预读取是通过一次IO请求将多个页预读取到缓冲池中，并且预估预读取的多个页马上会被访问。

4.3 索引下推

Index Condition Pushdown（索引下推）是MySQL 5.6引入的索引优化。
官方文档中给的例子和解释如下： people表中（zipcode，lastname，firstname）构成一个索引
SELECT * FROM people WHERE zipcode=‘95054’ AND lastname LIKE ‘%etrunia%’ AND address LIKE ‘%Main Street%’;
如果没有使用索引下推技术，则MySQL会通过zipcode=’95054’从存储引擎中查询对应的数据，返回到MySQL服务端，然后MySQL服务端基于lastname LIKE ‘%etrunia%’和address LIKE ‘%Main Street%’来判断数据是否符合条件。如果使用了索引下推技术，则MYSQL首先会返回符合zipcode=’95054’的索引，然后根据lastname LIKE ‘%etrunia%’和address LIKE ‘%Main Street%’来判断索引是否符合条件。如果符合条件，则根据该索引来定位对应的数据，如果不符合，则直接reject掉。有了索引下推优化，可以在有like条件查询的情况下，减少回表次数。