什么是索引

索引又可以称为键（key）是存储引擎用于快速找到记录的一种数据结构。

索引是提高MySQL查询性能最有效的手段，我们常说的MySQL性能调优基本都是对索引的优化。所以这是每个开发需要掌握并会应用的知识点。

索引是一种数据结构，它也是存储在磁盘的一个文件。上一篇我们学习MySQL的逻辑架构的时候了解了InnoDB和MyISM存储引擎，InnoDB存储引擎索引和数据是同一个文件，MyISAM索引和数据是两个独立的文件。

在MySQL中，索引是在存储引擎层实现的而不是Server层实现的，所以不同的存储引擎的索引的工作方式是不一样的。我们对索引的分析应该是建立在存储引擎的基础上的，InnoDB是MySQL默认的存储引擎。

索引的优点：

• 索引大大减少了服务器需要扫描的数据量。
• 索引可以帮助服务器避免排序和临时表。
• 索引可以随机I/O变为顺序I/O。

索引的缺点：

• 索引是数据结构，它占用了额外的磁盘空间。
• 当表数据量比较大时，维护索引的代价比较大。

索引数据模型

每个存储引擎的数据结构和算法都是存在区别，我们先看下MySQL本身支持的索引类型。

B-Tree索引

一般我们说的索引结构就是指B-Tree索引，MySQL大部分的存储引擎都支持这种索引，但是不同的存储引擎以不同的方式使用B-Tree索引，性能也各有不同。InnoDB使用的是B+Tree，按照原有的数据格式进行存储，根据主键引用被索引的行。

B-Tree所有的值都是按顺序存储的，并且每一个叶子到根的距离相同。下图是B-Tree的抽象图：

B-Tree能够加快访问数据的速度。

存储引擎不需要全表扫描来获取所需要的数据，它是从索引的根节点开始搜索。根节点的槽中存放指向子节点的指针，搜索引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入到下层节点。最终引擎要么找到对应的值，要么该记录不存在。

B-Tree的索引如果多个列，索引值的排序是按照建表时定义的索引顺序，所以索引的顺序是比较重要的。

B-Tree是N叉树，N的大小取决于数据块的大小。

以InnoDB的一个整数字段索引为例，N大概为1200，当树高是4的时候，就可以存1200的3次方的数据，大概为17亿。一个拥有10亿的表上一个整数字段的索引，查找一个值最多访问3次磁盘。其实在应用时，如果第二层被提前加载到内存中，那么磁盘的访问次数就更少了。

哈希索引

哈希索引是基于哈希表实现的，只有精确匹配所有列的查询才有效。

对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个比较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在hash表中保存指向每个数据行的指针。

创建表test_hash，它的存储引擎为memory，索引为full_name，索引类型为hash。

CREATE TABLE `test_hash` (
  `full_name` varchar(255) DEFAULT NULL,
  `short_name` varchar(32) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  KEY `idx` (`full_name`) USING HASH
) ENGINE=MEMORY DEFAULT CHARSET=utf8;

表中的数据如下：

mysql> select * from test_hash;
+-------------------+------------+------+
| full_name         | short_name | age  |
+-------------------+------------+------+
| Dwayne Johnson    | Johnson    | NULL |
| Taylor Swift      | Taylor     | NULL |
| Leonardo DiCaprio | Leonardo   | NULL |
| Vin Diesel        | Diesel     | NULL |
| Kobe Bryant       | Kobe       | NULL |
+-------------------+------------+------+
5 rows in set (0.00 sec)

那么哈希索引的数据结构可能是：

当我们执行查询语句：

mysql> select short_name from test_hash where full_name = 'Dwayne Johnson';

这个sql语句的执行流程：

1）根据where条件 'Dwayne Johnson'计算出哈希码，那么得到的哈希码为1234。

2）MySQL在索引中查找到1234，并根据这个值找到了对应的行记录指针。

3）根据指针地址找到对应的行，最后比较这个行中的full_name列是否为'Dwayne Johnson'。

那现在有个问题，哈希码冲突的时候怎么办呢？学过HashMap的小伙伴此时肯定灵机一动：哈希码冲突的时候使用链表。对的，当键值的哈希码冲突的时候，MySQL也是使用的链表结构。如果是链表结构，在查找的时候就需要遍历每个链表指针指向的行记录做匹配，所以哈希冲突比较大的时候查找的效率是比较低的。

从上面的示例我们可以看出，哈希索引的结构中只存储了哈希值，它的结构是比较紧凑的，对于精确查询的效率是比较快的。

但是哈希索引还是有些限制的：

• 哈希索引中存储的是键值的哈希值，它不是按照索引列的顺序的，所以它不无法用于排序。
• 哈希索引不支持部分索引匹配查找，因为哈希索引始终是索引列的全部内容。如果我们索引有两个列（A，B），查询的时候只想使用A列，这个时候是无法应用索引的。
• 哈希索引只支持等值查询，比如=、in等，它不支持任何范围查询。
• 当哈希冲突的时候，存储引擎必须要遍历链表中的所有行指针，逐行比较，直到找到所有符合条件的行，如果哈希冲突比较多的时候，索引维护的代价比较高。

在MySQL中，目前只有memory引擎显式支持哈希索引。

InnoDB索引模型

我们前面提到，InnoDB的索引结构是B+Tee，它是以主键引用被索引的行。所以在InnoDB中，表都是根据主键顺序以索引的形式存放的，每一个索引在InnoDB里面对应一棵B+树。

B+Tree索引

B+Tree是我们前面提到的B-Tree的扩展，B-Tree的每一个节点都包含了数据项，这样每一块磁盘存储的索引值就会比较少，树的高度就会变大，查询的磁盘I/O次数就会增加。

那B+Tree是怎么样的数据结构呢？下图是B+Tree的抽象图：

B+Tree与B-Tree的区别：

• B+Tree的非叶子节点不保存数据信息，只保存索引值和指向下一层节点的指针。
• B+Tree的叶子节点保存了数据
• B+Tree的叶子节点是顺序排列的，并且叶子相邻节点之间有指针的互相引用

B+Tree能够更好地配合磁盘的读写特性，减少单次查询的磁盘访问次数。

InnoDB的索引类型分为主键索引和非主键索引。

主键索引和非主键索引

创建表user，它的存储引擎为InnoDB，id为主键，name为普通索引。

CREATE TABLE `user` (
  `id` int(10) NOT NULL,
  `name` varchar(32) DEFAULT NULL,
  `age` int(3) DEFAULT NULL,
  `sex` varchar(1) DEFAULT NULL,
  `comment` varchar(255) DEFAULT NULL,
  `date` date DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `idx` (`name`) USING BTREE
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

表中的数据如下：

mysql> select * from user;
+----+-------+------+------+---------+------------+
| id | name  | age  | sex  | comment | date       |
+----+-------+------+------+---------+------------+
|  1 | Alen  |   20 | 1    | NULL    | 2021-02-16 |
|  2 | Alex  |   21 | 1    | NULL    | 2021-02-16 |
|  3 | Saria |   16 | 0    | NULL    | 2021-02-16 |
|  4 | Semyt |   18 | 0    | NULL    | 2021-02-16 |
|  5 | Summy |   17 | 1    | NULL    | 2021-02-16 |
|  6 | Tom   |   19 | 0    | NULL    | 2021-02-16 |
+----+-------+------+------+---------+------------+
6 rows in set (0.00 sec)

主键索引也称为聚簇索引，它的叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有剩余的列。

mysql> select * from user where id = 1;

主键索引只需要搜索ID这棵B+Tree就可以拿到符合条件的行记录。

InnoDB是通过主键索引聚集数据，如果表中没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。这也是勾勾为每个表都创建主键的原因。

聚簇索引的优点：

• 把相关的数据保存在一起，减少了磁盘I/O；
• 聚簇索引将数据和索引保存在同一颗BTree上，数据访问更快；

聚簇索引的缺点：

• 如果数据都在内存中，聚簇索引的查询性能就没有那么好的优势了。
• 插入的速度严重依赖于插入顺序。尽量保证主键索引是有序的。
• 更新聚簇索引列的代价更高。
• 在插入行或者更新主键的时候导致需要移动行的时候可能导致页分裂的问题。当插入到一个已满的页中，存储引擎会将该页分裂为两页来容纳数据，页分裂会导致占用更多的磁盘空间。

非主键索引也称为非聚簇索引，在InnoDB中又被称为二级索引。非主键索引的叶子节点内容是主键的值。

mysql> select * from user where name = 'Alen';

非主键索引查询时，首先根据name普通查询搜索name索引树，找到id为1，再根据id=1到ID索引树查询一次才能获取到符合条件的行记录。

我们把先搜索普通索引树得到主键，再搜索主键索引树的过程称为回表。

普通索引的查询比主键索引多检索了一棵B+Tree，在实际应用场景下如果能用到主键索引尽量选择主键索引。

在创建索引的时候还有其他的原则，我们接下来继续学习高性能的索引策略。

索引策略

小伙伴们在学习索引策略的时候可以利用上一篇文章的explian关键字查询执行计划。

索引的选择

索引的分类有多种，我们可以按照索引字段的个数将索引分为单列索引和联合索引。

单列索引：一个索引只包含一个列，一个表中可以多个单列索引。

联合索引：一个索引包含多个列。

我们还可以将索引分为普通索引、唯一索引和主键索引。

普通索引：基本的索引类型，常用来提高查询效率，对数据没有限制。允许在索引列中插入空值和重复值。

唯一索引：索引列中的值必须是唯一的，允许存在空值。

主键索引：不允许空值的特殊的唯一索引。

索引有这么多分类，我们在创建索引的时候如何选择呢？

索引的三星系统：

一星：索引相关的记录放到一起。

二星：索引中的数据顺序和查找列中的顺序一致。

三星：索引的列包含了查询中需要的全部列。

正确的创建和使用索引是实现高性能查询的基础。索引的选择没有绝对的要求，主要是根据自己的业务需求，但是有些原则我们在创建索引的时候可以作为参考。

• 索引列的区分度越高则查询效率越高。
• 将频繁搜索的列加入索引，可以提高搜索效率。
• 索引不只提高了查询效率，也可以参与排序和分组，经常用来排序和分组的字段也需考虑加入索引。
• 创建索引时，应将区分度高的字段排在前面。即需要注意索引字段的顺序。
• 索引列不能参与任何运算。
• 避免创建重复索引，即在同一个列上按照相同的顺序创建相同类型的索引。
• 对于从未使用的索引，应尽量删除。
• 对于blob、text或者长varchar类型的列，必须要使用前缀索引，取最够长的前缀来保证较高的区分度。
• 普通索引和唯一索引在查询效率上差别并不大，因为引擎是按照页读取数据。对于唯一索引在查询的时候只要找到就不再继续比较了，因为索引已经保证了唯一性。而对于普通索引则在找到满足条件的记录后还需要继续查找直到找到不满足条件的第一条记录，但是对于按照页读取数据的引擎来说，多一次的判断对性能的影响较小。普通索引和唯一索引的选择除了保证业务的准确性之外，其他更多的考虑更新数据时对性能的影响。

独立的列

”独立的列“是指索引不能是表达式的一部分，也不能是函数的参数。

例如，如下sql语句，在查询时索引字段name参与了函数运算，会导致索引失效，全表扫描。

mysql> select * from user where CONCAT(name,'n') = 'Alen';

添加索引age字段，如果我们在查询的时候对age字段进行了运算也会导致索引失效：

mysql> select * from user where age + 1 = 21;

我们平时开发中要养成简化where条件的习惯，始终使用单独的索引列。

覆盖索引

如果我们把按照普通索引查询的sql语句修改如下:

mysql> select name from user where name like 'Al%';

这时只需要查询普通索引树即可得到要查询的列，因为要查询的列已经在索引树了，而不需要再回表查询。

这种索引字段覆盖了我们需要查询的结果字段的场景我们称为覆盖索引。

覆盖索引可以减少回表，减少索引树的搜索次数，显著提高查询性能，所以覆盖索引是一个比较好的优化策略。

在实际开发中，可以按照业务需要把一些常用的检索字段添加到索引中，利用覆盖索引提高查询效率，但是有些场景下不能为了使用覆盖索引而过多的维护索引，毕竟索引的维护成本也是很高的。

最左前缀

这个时候我们还需要思考一个问题，在业务场景中我们的查询是多样化的，不能为了使用索引而为每一种场景都设计一个索引吧？

这个时候我们就要利用B+Tree树索引结构的另外一个特性最左前缀。

最左前缀可以是联合索引的最左的几个字段，也可以是字符串索引的最左的几个字符。

创建联合索引（name,age），顺序一致。

此时执行sql语句：

mysql> select * from user where name = 'Alen';

虽然是联合索引，但是name字段排在第一位，也是可以命中索引的。

mysql> select * from user where name like 'Al%';

如果使用name索引字段的最左N个字符串，也是可以命中索引的。但是如果我们使用%Al是不能命中索引的。

如果我们使用如下的sql查询语句：

mysql>  select * from user where age = '16'；

虽然age也是联合索引的字段，但是他的顺序在name之后，直接使用age查询无法命中索引。所以创建联合索引时一定要考虑索引字段的顺序。

索引维护时有一个原则：如果能通过调整索引顺序，可以少维护一个索引，那么就需要优先调整顺序而不是增加索引。

MySQL可以利用同一个索引进行排序和扫描行，但是只有当索引的列顺序和order by子句的顺序完全一致，并且列的排序方向都一致（正序或者倒序）时，MySQL才能使用对结果进行排序。

order by子句和查询类型限制是一样的，也需要满足”最左前缀“的原则，否则MySQL无法利用索引排序。

索引下推

当我们的查询语句不满足最左前缀的时候会如何呢？

比如我们查询名字第一个字为A，年龄为20，并且性别为1（男）的人员信息，sql语句如下：

mysql>  select * from user where name like 'A%' and age = 20 and sex = 1 ;

按照我们前面学习的最左前缀原则，按照’A‘先搜索到第一个满足条件的主键1，然后回表查询判断其他的两个条件是否满足。

MySQL5.6之后引入了索引下推的优化，即会按照索引中包含的字段优先过滤，减少回表的次数。

我们上述的sql语句在MySQL5.6之前会回表2次分别对比主键1和2两条的数据的其他条件是否满足，但是引入索引下推的优化之后age = 20这个条件不满的会直接过滤掉，只需要对主键1回表一次就可以获取到结果。

总结

索引是用于快速查找数据的一种数据结构。

创建并合理的使用索引是提高查询效率的基础，在了解索引的数据结构的基础之后我们也应该花时间去掌握高性能的索引策略，了解在实际开发中创建索引的一些原则，合理的选择索引。

我是勾勾，一直在努力的程序媛！

在看、点赞、转发和关注是最好的支持！

我们下篇文章见！

参考资料：

《高性能MySQL》

《MySQL实战45讲-丁奇》