MySQL索引那些事儿

1.写在前面

索引对于良好的性能非常关键，特别是当表中的数据量越来越大的时候，索引对性能的影响愈发重要。而索引优化应该是对查询优化最有效的手段了，索引能够轻易将查询性能提高几个数量级。本文是对MySQL索引的一个总结，希望通过本文能够回答以下问题：

• 聚簇索引和非聚簇索引的区别？
• 对于InnoDB引擎，为什么建议使用一个与业务无关的自增代理键做为主键？
• 对于InnoDB引擎，为什么索引列的顺序会影响到查询的性能？

2.索引基础

按照MySQL官方的定义：索引（在MySQL中也叫键(key)）是存在引擎用于快速找到记录的一种数据结构。

从索引的定义可以知道，索引其本质是一种数据结构。索引有多种类型，如B-Tree索引、哈希索引、全文索引、空间数据索引（R-Tree）等。对于MySQL，索引是在存储引擎层实现，如果没有特别说明，我们说的索引都是使用B-Tree索引，从技术实现上来讲，MySQL B-Tree索引是其变种B+Tree实现的，下图大致反映InnoDB索引是如何工作的，MyISAM使用的结构有所不同，但基本思想类似，后边会详细说：

简单来说，对于非叶子结点：除了保存键值（key）外，还保存了指定子页结点的指针，且key左边指针指向的结点的值均小于key，key右边指针指向的值均大于等于key；对于叶子结点，结点中的每一个key包含了一个指向数据的指针（依赖于不同存储引擎，InnoDB存储了原始数据，MyISAM存储了被索引行的物理位置）并且每个结点包含一个指向下一个叶子页的指针。

为什么说B-Tree索引能够加快访问数据的速度呢？因为存储引擎不需要再进行全表扫描来获取需要的数据，取而代之的是从索引根结点开始进行二分查找，如果找到则返回对应节点的值，否则对相应槽中的指针指向的页结点递归进行查找，直到找到节点或记录不存在。

3.索引的优缺点

3.1优点

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

3.2缺点

• 索引占用存储空间；
• 索引降低了修改操作（增加、修改、删除）的性能；

4. B-Tree索引的查询类型

通过上节已经知道了B-Tree索引的数据结构，下面通过例子看看为什么B-Tree索引的顺序至关重要，假如有如下数据表：

CREATE TABLE People (
    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)
)ENGINE=InnoDB;

对于每一行数据，索引中包含 last_name, first_name和dob列的值，下图展示了索引是如何组织数据存储的：

需要注意的是，索引对于多个值进行排序的依赖是CREATE TABLE语句中定义索引时列的顺序。如最后两个人的姓我名都一样，则根据他们的出生日期进行排序。

B-Tree索引适合于全键值、键值范围或键前缀查找。其中键前缀查找只适用于最左前缀查找，上例索引对如下类型的查询有效：

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

• 匹配最左前缀
  前面提到的索引可以用于查找所有姓为Allen的人，即只使用索引的第一列。

• 匹配列前缀
  也可以匹配某一列的值的开头部分。如前面提到的索引可以用于查找所有以J开头的姓的人。这里也只使用了索引的第一列。

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

• 精确匹配某一列并范围匹配另一列
  前面提到的索引可以用于查找姓为Allen，并且名是以字母K开头（如Kim Karl）的人，即第一列last_name全匹配，第二列first_name范围匹配。

• 只访问索引的查询
  从B-Tree的数据结构中可以看出，索引已经存储在了数据结构中，B-Tree通常可以支持只访问索引的查询，即查询只需要访问索引，也称为“覆盖索引”。

如果不按索引的最左列开始查找，则无法使用索引。例如上面例子中如果我们查找名字为Bill的人或查找某个特定生日的人，则无法使用索引，存储引擎会进行会表扫描，这便是为什么索引列的顺序会影响到查询的原因。

5. 高性能索引策略

正确地创建和使用索引是实现高性能查询的基础。通过下面这些索引策略可以真正发挥索引的优势。

5.1 前缀索引和索引选择性

有时候需要索引很长的字符串，这会让索引变得大且慢，根据前面讲过的最左前缀，通过可以索引字符串开始的部分字符，这样可以大大节约索引存储空间，提高索引效率。但这会降低索引的选择性。

索引的选择性是指不重复的索引值，也称为基数（cardinality）和数据表的记录总数（#T）的比值，范围从1/#T到1之间，索引的选择性越高则查询效率越高。我们通常可以采用以下公式进行选择性计算：

Selectivity = COUNT(DISTINCT(field)) / COUNT(*)

来看一个例子，例子来源MySQL employee example：

CREATE TABLE `employees` (
  `emp_no` int(11) NOT NULL,
  `birth_date` date NOT NULL,
  `first_name` varchar(14) NOT NULL,
  `last_name` varchar(16) NOT NULL,
  `gender` enum('M','F') NOT NULL,
  `hire_date` date NOT NULL,
  PRIMARY KEY (`emp_no`),
) ENGINE=InnoDB;

如上表，出于业务的需求，我们需要根据first_name和last_name进行查找，可以为<first_name，last_name>建立索引，但fist_name和last_name加起来长度为30，可以考虑用first_name和last_name的前几个字符建立索引。但last_name取几个字符呢，我们可以通过计算其选择性来决定，比如<first_name, left(last_name, 3)>，其选择性如下：

mysql> SELECT count(DISTINCT(concat(first_name, left(last_name, 3))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
|      0.7879 |
+-------------+

看起来还不错，如果把last_name的前缀加到4，看看选择性如下：

mysql> SELECT count(DISTINCT(concat(first_name, left(last_name, 4))))/count(*) AS Selectivity FROM employees.employees;
+-------------+
| Selectivity |
+-------------+
|      0.9007 |
+-------------+

这个选择性已经比较好了，而且索引长度也只有18，比起<first_name, last_name>短了近一半，于是可以建立索引：

ALTER TABLE employees.employees
ADD INDEX `first_name_last_name4` (first_name, last_name(4));

5.2 多列索引

多列索引也叫联合索引。很多人对多列索引理解不够，一个常见的错误就是为每一个列创建独立的索引，或者按照错误的顺序创建多列索引。这种理解是非常错误的，在多个列上建立独立的索引大部分情况下并不能提高MySQL的查询性能。

当出现服务器对多个索引做相交操作（通常是多个AND条件），通常意味着需要一个包含所有相关列的多列索引，而不是多个独立的单列索引。

5.3 选择合适的索引列顺序

在一个多列的B-Tree索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，等等。索引是按照升序或降序进行扫描，以满足精确符合列顺序的ORDER BY、GROUP BY、和DISTINCT等子句的查询需求。所以多列索引的列顺序至关重要。

5.4 聚簇索引和非聚簇索引

聚簇索引并不是一种单独的索引类型，而一种数据存储方式。

InnoDB采用的是聚簇索引，其实现原理是在同一个结构中保存了B-Tree索引和数据行，如下图是聚簇索引的分布图，索引列是包含的整数值，叶子页中包含了行的全部数据：

对于聚簇索引，插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。另外基于聚簇索引表在插入新行，或主键被更新导致需要移动行的时候，可能面临“页分裂”的问题，如果主键采用递增方式顺序插入，也能避免页分裂造成随机I/O和占用更多磁盘空间的问题。

对于InnoDB引擎是通过主键聚集数据的，也就是说上图中的被索引的列就是主键。如果没有定义主键，InnoDB会选择一个惟一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。

对于InnoDB引擎，二级索引的叶子节点保存的不是指向行的物理位置，而是行的主键值，也就是说二级索引访问需要两次索引查找，而不是一次。

相对于聚簇索引，非聚簇索引是指索引和数据是分离的。MyISAM存储引擎是采用的非聚簇索引。其索引的叶结点存放的不再是数据，而是存储的数据的物理地址，为了简单说明，可以理解为“行号”，如下图所示：

下图可以很容易看出InnoDB（聚簇索引）和MyISAM（非聚簇索引）保存数据和索引的区别：

5.5 覆盖索引

如果一个索引包含（或者说覆盖）所有需要查询的字段值 ，我们就称之为覆盖索引。覆盖索引能极大提高查询性能，因为只需要扫描索引而无须回表，有如下好处：

• 索引条目通常远小于数据行大小，所以如果只需要读索引，那MySQL就会极大地减小数据访问量。
• 因为索引是按照列值顺序存储的，所以对于I/O密集型的范围查询会比随机从磁盘读取一行数据的I/O要少得多。
• 一些存储引擎如MyISAM在内存中只缓存索引，数据则依赖于操作系统来缓存。而访问数据需要一次系统调用。这可能导致严重的性能问题。
• 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。

5.6 使用索引扫描做排序

MySQL有两种方式可以生成有序结果：

• 通过排序操作；
• 按照索引顺序扫描；

如何判断使用发哪些方式呢？可以使用explain查看type列的值（这里强烈建议看看MySQL帮忙手册中对explain中各个字段的解释，这对优化查询的时候至关重要），如果是index则表示MySQL使用了索引扫描来排序。

扫描索引本身是很快的，因为只需要从一条索引记录移动到紧接着的下一条记录。但如果索引不能覆盖查询所需的全部列，那就不得不扫描一条索引记录就都回表查询一次对应的行。这基本上都是随机I/O，因此按索引顺序读取数据的速度通常比顺序地全表扫描慢，尤其是在I/O密集型的工作负载时。

5.7 冗余和重复索引

MySQL允许在相同的列上创建多个索引。重复索引是指在相同的列上按照相同的顺序创建的相同类型的索引。

注意重复索引不是冗余索引。如果创建的索引<A, B>，再创建索引<A>就是冗余索引，因为索引<A>只是索引<A,B>的前缀索引。因此<A,B>可以当作索引<A>来使用。但如果再创建索引<B,A>，则不是冗余索引，因为<B>不是<A，B>的最左前缀。

大多数情况下都不需要冗余索引，但有时候出于性能方面的考虑需要冗余索引，因为扩展已有的索引会导致其变得太大，从而影响其他使用该索引的查询性能。

总结

选择索引和编写利用这些索引的查询时，有三个原则始终需要记住：

1. 单行访问是很慢的。特别是在机械硬盘中。最好读取的块中能包含尽可能多所需要的行。使用索引可以创建位置引用以提升效率。
2. 按照顺序访问数据是很快的，主要有两个原因。第一，顺序I/O不需要多次磁盘寻道；第二，如果服务器能够按照需要顺序读取数据，那么就不再需要额外的排序操作。
3. 索引覆盖是很快的。如果一个索引包含了查询所需的所有列，那么存储引擎就不需要再回表查找行。这避免了大量单行访问。

理解索引如果工作对优化查询非常重要。如果判断一个系统创建的索引是否合理？一般来说先按响应时间来对查询进行分析。找出消耗最长时间的查询或者那么给服务器带来最大压力的查询（查询性能分析方法），然后检查这些查询的schema、SQL和索引结构，判断是否有查询扫描了太多的行（通过explain)，是否做了额外的排序或者使用了临时表，是否使用了随机I/O访问数据，或者是否有太多回表查询那些不在索引中的列的操作。

参考

[1] High Performance MySQL
[2] http://blog.codinglabs.org/articles/theory-of-mysql-index.html
[3] https://zh.wikipedia.org/wiki/B%E6%A0%91#%E6%90%9C%E7%B4%A2