作为一个curd boy，整天和mysql打交道。索引是我们写sql语句时，一个经常需要考虑的问题。

索引对良好的性能非常关键，在数据量少时，不恰当的索引对性能的影响可能还不明显，但随着数据量增多，性能则会急剧下降。

索引优化应该是对查询性能优化最简单有效的手段了，索引能够轻易将查询性能提高几个数量级。索引就像一本书的目录，如果没有目录，我们查找其中的某个知识点，就需要翻阅整本书。有了目录，我们就可以浏览下目录，找到知识点所在的页码，直接翻到页码那页。这大大提高了我们的查找效率。

底层数据结构

判断索引能不能对我们的查询生效，网络上有很多文章，都直接总结了索引生效的规则，但是死记硬背，不弄清楚背后的原理，很容易过段时间就忘记了。搞清楚mysql底层实现索引的数据结构，有助于我们判断索引是否生效。

就从我们常用的InnoDB存储引擎的B-Tree索引开始。

先简单了解一些数据结构的知识。

二叉查找树(Binary Search Tree)：左子树的键值总是小于根的键值，右子树的键值总是大于根的键值。

二叉查找树会出现极端不平衡的构造情况，这种情况下，查找效率就很低，和顺序查找差不多。

平衡二叉树(Balance Binary Tree/AVL Tree)：是二叉查找树，同时满足任意节点的两个子树的高度最大查为1。这一特点，使得在平衡二叉树中查找特定的键值，时间复杂度是logN。

平衡二叉树的查找效率看起来不错，但是检索每个节点都需要进行一次磁盘IO，假设我们的表里有三千万条记录，使用完全平衡二叉树来存储表的索引，树的高度会是25，最坏的情况下，我们需要进行25次磁盘IO。

为了减少磁盘IO的次数，InnoDB最终使用B+树来存储索引。
B+树中所有键值都是按顺序存储的，并且每一个叶子节点到根节点的距离相同。

下面是一颗高度为2，每个节点存放4条记录的B+树。

InnoDB中，记录节点都是存放在叶子节点上，查找时，从根节点开始，通过键值比较，得到指向子叶的指针，进入到子叶节点，继续执行比较，递归这一过程，直到叶子节点，找到键值对应的指向数据的指针。

InnoDB使用16K逻辑页来存放一个节点，所以一个节点可以存放的记录数很大，在数据库中，B+树的高度一般都在2到4层，一次IO可以读取一个节点，所以查找某一个键值所在记录最多只需要2到4次IO。

而且因为每个节点内的键值都是按顺序存储的，读取节点后，在内存中，使用二分查找法来比较键值，得到指向子叶的指针或者最终得到指向数据的指针。

联合索引

前面讨论的情况都是只对表上的一个列进行索引，联合索引是指对表上的多个列进行索引。

假设有如下数据表

CREATE TABLE People (
    id int primary key,
    last_name varchar(50)    not null,
    first_name varchar(50)   not null,
    dob date                 not null,
    gender enum('m', 'f')  not null,
    key(last_name, first_name, dob)
);

对列last_name，first_name，dob建立了联合索引。

联合索引也是一颗B+树，只是键值的数量不是1了。但是和最开始的单个索引没什么不同，节点上的键值都是排序好的。

注意：索引对多个键值的排序依据是CREATE TABLE语句中定义索引时的顺序。key(last_name, first_name, dob)和key(first_name, last_name, dob)是不同的。

上面的联合索引，排序规则是先按照last_name排序，如果last_name相同，则按first_name排序，如果last_name和first_name都相同，则按dob排序。

生效规则

根据B+树的数据结构和查找算法，我们可以很容易地判断索引是否生效。

Where

全值匹配
全值匹配指的是和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名为Cuba Allen、出生于1960-01-01的人。

select * from People where last_name="Cuba" and first_name="Allen" and dob="1960-01-01"

匹配最左前缀
前面提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列。只需要找到第一个last_name=Allen的记录，然后往右一直扫描到第一个last_name!=Allen的记录停止。

select * from People where last_name="Allen"

匹配列前缀
也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于查找所有以J开头的姓的人。这里也只使用了索引的第一列。只需要找到第一个last_name以J开头的记录，然后往右一直扫描到第一个last_name不以J开头的记录停止。

select * from People where last_name like "J%"

匹配范围值
例如前面提到的索引可用于查找姓在Allen和Barrymore之间的人。这里也只使用了索引的第一列。

select * from People where last_name >= "Allen" and last_name <= "Barrymore";

精确匹配某一列并范围匹配另外一列
前面提到的索引也可用于查找所有姓为Allen，并且名字是字母K开头（比如Kim、Karl等）的人。即第一列last_name全匹配，第二列frst_name范围匹配。只需要找到第一个last_name=Allen，first_name以K开头的记录，然后往有扫描，直到第一个last_name=Allen, first_name不以K开头的记录。

select * from People where last_name="Allen" and first_name like "K%"

Order By

索引除了可以用于按值查找，还可以用于查询中的ORDER BY操作。
使用explain来分析一条使用了ORDER BY的查询sql时，常常能看到extra列里的using filesort，即需要额外的一次排序操作才能完成查询。

因为B+树的节点键值都是按照索引定义时的顺序，已经排好序的，利用这个特点，我们可以避免额外的排序操作。

如果eplain出来的type列值是index, extra列里没有using filesort，则说明使用索引扫描来做排序。

只有当索引的列顺序和ORDER BY子句顺序完全一致，并且所有的列的排序方向（倒序或正序)都一样时，才能够使用索引来对结果做排序。

例如下面的sql可以使用索引来排序。

select * from People order by last_name, first_name;

select * from People order by last_name desc, first_name desc

下面的sql不可以使用索引来排序，这都是由索引的B+树的特性决定的，如果不明白，可以回去看下上面的B+树。

select * from People order by fist_name, last_name;

select * from People order by last_name desc, first_name

当同时存在WHERE和ORDER BY子句时，也可以用上索引排序。

select * from People Where last_name = "Allen" order by first_name

在B+树中，找到第一个last_name=Allen的记录，这时候first_name是已经排序好的了，往右扫描索引，直到第一个last_name!=Allen的记录。

下面是一些不能使用索引做排序的查询：

使用了两种不同的排序方向，但是索引列都是正序排序的

select * from People order by last_name desc, first_name

ORDER BY子句中引用了一个不在索引中的列

select * from People Where last_name = "Allen" order by gender

在索引列的第一列上是范围条件

select * from People Where last_name >= "Allen" and last_name <= "Bob" order by first_name

in查询对排序来说也是一种范围查询

select * from People Where last_name in ("Allen", "Bob") order by first_name

Group by

GROUP BY子句的索引生效规则，其实和ORDER BY的类似，只要能够通过扫描索引来排序，避免额外的排序操作，索引就能用于GROUP BY子句。

聚簇索引和辅助索引

注意，聚簇索引和辅助索引不是一种单独的索引方式，而是一种数据存储方式。

聚簇索引还是B+树，只是在这颗B+树中，同时保存了索引和数据行。数据行存放在B+树的叶子节点。

InnoDB一般使用主键列的索引作为聚簇索引。

辅助索引也是一颗B+树, 只是叶子节点保存的不是数据行， 而是行的主键值。

所以如果通过辅助索引去查找行，需要先找到辅助索引的叶子节点，获取相应的主键值，然后根据这个值去聚簇索引中查找对应的行。整个过程需要进行两次B+树查找。

覆盖索引

如果在辅助索引中，可以直接获取要查询的列的数据，那么就没有必要再去聚簇索引查找数据行了。

覆盖索引就是这样一种优化手段，如果一个索引包含所有需要查询的列的值，我们就称之为"覆盖索引"

select last_name, first_name, dob from People where last_name >= "Allen"

上面的sql，可以只扫描last_name, first_name, dob组成的辅助索引，就可以得到所有的列值了。这样整个过程就只需要查找一次B+树。

使用eplain分析上面的sql语句，可以看到extra里出现using index。

总结

只要弄明白索引的数据结构B+树，就可以很容易地判断索引能否用于我们的sql语句。当然有些限制不是B+树本身导致的，而是Mysql优化器导致的，这时候需要更多地技巧来判断。

参考资料

《高性能Mysql：第三版》

《Mysql技术内幕：InnoDB存储引擎(第二版)》