第 5 章 创建高性能的索引
__索引__是存储引擎用于快速找到记录的一种数据结构。
索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急速下降。
5.1 索引基础
要理解MySQL中索引是如何工作的，最简单的方法就是去看看一本书的“索引”部分如果想在一本书中找到某个特定主题，一般会先看书的“索引”，找到对应的页码，然后直接翻到那一页即可。MySQL中的索引与一本书的目录作用差不多，都是用来快速定位想要找的内容。
在MySQL中，存储引擎先在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。例如要运行下面的查询：
1 | SELECT first_name FROM actor WHERE actor_id = 5; |
MySQL会先在索引上按值进行查找，找到actor_id等于5的索引项，这个索引项中包含数据行的地址，然后返回所有包含该值的数据行。
索引可以包含一个或多个列的值。如果索引包含多个列，那么列的顺序也十分重要，因为 MySQL只能高效地使用索引的最左前缀列。
5.1.1 索引的类型
在MySQL中，索引是在存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准：不同存储引擎的索引的工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。
5.1.2 B-Tree索引
大多数 MySQL引擎都支持这种索引，它使用B-Tree数据结构来存储数据
B-Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。如下图所示
B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点（图示并未画出）开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。
叶子节点比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页。此外，树的深度和表的大小直接相关。
B-Tree对索引列是顺序组织存储的，所以很适合査找范围数据。例如像“找出所有以I到K开头的名字”这样的查找效率会非常高。
5.1.2.1 B-Tree索引的一个例子
下面举一个B-Tree索引的例子
假设有如下数据表
对于表中的每一行数据，索引中包含了last_name、first_name和dob列的值，下图显示了该索引是如何组织数据的存储的。
请注意，索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。看下最后两个条目，两个人的姓和名都一样，则根据他们的出生日期来排列顺序。
5.1.2.2 可以使用B-Tree索引的查询类型
-
全值匹配
- 全值匹配指的是和索引中的所有列进行匹配
- 例如前面提到的索引可用于查找姓名为Cuba Allen、出生于1960-01-01的人
-
匹配最左前缀
- 前面提到的索引可用于查找所有姓为Allen的人，即只使用索引的第一列
-
匹配列前缀
- 也可以只匹配某一列的值的开头部分。
- 例如前面提到的索引可用于查找所有以J开头的姓的人。这里也只使用了索引的列的开头。
-
匹配范围值
- 例如前面提到的索引可用于查找姓在Allen和Barrymore之间的人。这里也只使用了索引的第一列
-
精确匹配某一列并范围匹配另外一列
- 前面提到的索引也可用于查找所有姓为Allen，并且名字是字母K开头（比如Kim Karl等）的人。
- 即第一列
last_name全匹配，第二列first_name范围匹配。
-
只访问索引的查询
- B-Tree通常可以支持“只访问索引的查询”
- 它会直接读取索引中保存的数据信息，这样就无需访问数据行了
5.1.2.3 B-Tree索引的其他作用
因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的ORDER BY操作。一般来说，如果B-Tree可以按照某种方式查找到值，那么也可以按照这种方式用于排序。所以，如果ORDER BY子句满足前面列出的几种査询类型，则这个索引也可以满足对应的排序需求
5.1.2.4 使用B-Tree索引的限制
-
如果不是按照索引的最左列开始查找，则无法使用索引。例如上面例子中的索引无法用于查找名字为Bill的人，也无法查找某个特定生日的人，因为这两列都不是最左数据列。类似地，也无法查找姓氏以某个字母结尾的人。
-
不能跳过索引中的列。也就是说，前面所述的索引无法用于查找姓为Smith并且在某个特定日期出生的人。如果不指定名(
first name)，则MySQL只能使用索引的第一列。 -
如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。例如有查询
WHERE last_name='Smith' AND first name LIKE'J%' AND dob != '1976-12-23'，这个查询只能使用索引的前两列，因为这里LIKE是一个范围条件
5.1.3 哈希索引
哈希索引基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针
在MySQL中，只有Memory引擎显式支持哈希索引。这也是Memory引擎表的默认索引类型，Memory引擎同时也支持B-Tree索引。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。
5.1.3.4 哈希索引的限制
-
哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
-
哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
-
哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
-
哈希索引只支持等值比较查询，包括
=、IN()。也不支持任何范围查询，例如，WHERE price > 18 -
如果哈希冲突很多的话，一些索引维护操作的代价也会很高。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
5.1.3.4 哈希索引与InnoDB
InnoDB引擎有一个特殊的功能叫做“自适应哈希索引"。当InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过如果有必要完全可以关闭该功能。
5.2 索引的优点
索引可以让服务器快速地定位到表的指定位置。根据创建索引的数据结构不同，索引也有一些其他的附加作用。
例如B-Tree索引，最常见的B-Tree索引，按照顺序存储数据，所以MySQL可以用来做ORDER BY和GROUP BY操作。因为数据是有序的，所以B-Tree也就会将相关的列值都存储在一起。最后，因为索引中存储了实际的列值，所以某些査询只使用索引就能够完成全部查询。
泛泛而谈，索引有如下优点
- 索引大大减少了服务器需要扫描的数据量。
- 索引可以帮助服务器避免排序和临时表。
- 索引可以将随机I/O变为顺序I/O。
Lahdenmaki和Leach在书中介绍了如何评价一个索引是否适合某个查询的“三星系统”
- 索引将相关的记录放到一起则获得一星
- 如果索引中的数据顺序和查找中的排列顺序一致则获得二星
- 如果索引中的列包含了查询中需要的全部列则获得三星
5.3 高性能的索引策略
正确地创建和使用索引是实现髙性能査询的基础。下面介绍高性能使用索引的策略。
5.3.1 独立的列
独立的列是指索引列不能是表达式的一部分，也不能是函数的参数。如果查询中使用的不是独立的列，则MySQL不会使用索引。下面就是两个反例
反例1，表达式，无法使用索引
1 | SELECT actor_id FROM actor WHERE actor_id + 1 = 5; |
反例2，函数的参数，无法使用索引
1 | SELECT ... WHERE TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col) <= 10; |
5.3.2 前缀索引和索引选择性
有时候需要索引很长的字符列，这会让索引变得大且慢。通常可以索引开始的部分字符，这样可以大大节约索引空间，从而提高索引效率。
下面演示一下如何创建前缀索引
1 | ALTER TABLE city_demo ADD KEY (city(7)); |
但使用前缀索引会降低索引的选择性。索引的选择性是指，不重复的索引值和数据表的记录总数的比值(T)，范围从l/T到1之间。索引的选择性越高则查询效率越高，因为选择性高的索引可以让MySQL在查找时过滤掉更多的行。无重复索引的选择性是1，这是最好的索引选择性，性能也是最好的。
后缀索引：有时候后缀索引（suffix index）也有用途（例如，找到某个域名的所有电子邮件地址）。MySQL原生并不支持反向索引，但是可以把宇符串反转后存储，并基于此建立前缀索引。
5.3.3 多列索引
在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能。MySQL5.0和更新版本引入了一种叫“索引合并”（index merge）的策略，一定程度上可以使用表上的多个单列索引来定位指定的行。更早版本的MySQL只能使用其中某一个单列索引，然而这种情况下没有哪一个独立的单列索引是非常有效的。
索引合并虽然是一种很好的策略，但是有时成本比较高。如果在EXPLAIN中看到有索引合并，应该好好检查一下查询和表的结构，看是不是已经是最优的。
5.3.4 选择合适的索引列顺序
正确的顺序依赖于使用该索引的查询，并且同时需要考虑如何更好地满足排序和分组的需要。
在一个多列B-Tree索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，等等。所以，索引可以按照升序或者降序进行扫描，以满足精确符合列顺序的ORDER BY、GROUP BY和DISTINCT等子句的查询需求。
对于如何选择索引的列顺序有一个经验法则：将选择性最高的列放到索引最前列。
5.3.5 聚簇索引
当表有聚簇索引时，它的数据行实际上存放在索引的叶子页（leaf page）中。术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。
下图展示了聚簇索引中的记录是如何存放的。注意到，叶子页包含了行的全部数据，但是节点页只包含了索引列。在这个案例中，索引列包含的是整数值。
InnoDB将通过主键聚集数据，如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引， InnoDB会隐式定义一个主键来作为聚簇索引。
InnoDB只聚集在同一个页面中的记录包含相邻键值的页面可能在物理空间中相距甚远。但是通常前页会保存后页的指针，这样方便寻找。
5.3.5.1 聚簇索引的优点和缺点
优点
- 可以把相关数据保存在一起。例如实现电子邮箱时，可以根据用户ID来聚集数据，这样只需要从磁盘读取少数的数据页就能获取某个用户的全部邮件。如没有使用聚簇索引，则每封邮件都可能导致一次磁盘I/O。
- 数据访问更快。聚簇索引将索引和数据保存在同一个B-Tree中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
- 使用覆盖索引扫描的查询可以直接使用页节点中的主键值（这点要后面再解释，看不懂没关系）。
缺点
- 如果数据全部都放在内存中，则访问的顺序就没那么重要了，聚簇索引也就没什么优势了。
- 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。
- 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置
- 聚簇索引可能导致全表扫描变慢，比如由于页分裂导致数据存储不连续的时候。
- 二级索引（非聚簇索引，也就是此表上的其他索引）可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列
- 二级索引访问需要两次索引查找，而不是一次。因为通过二级索引査找行，存储引擎需要找到二级索引的叶子节点获得对应的主键值，然后根据这个值去聚簇索引中查找到对应的行。这里做了重复的工作：两次B-Tree查找而不是一次。
5.3.5.2 InnoDB与MyISAM数据分布对比
InnoDB是使用聚簇索引的存储引擎，而MyISAM不使用。通过它们的对比，我们将更好的理解聚簇索引的概念和存储方式。
这里为了方便理解，我们先写一个样例表
1 | CREATE TABLE layout_test( |
首先介绍MyISAM。
当插入数据时，MyISAM按照数据插入的顺序存储在磁盘上，如下图。
这种分布方式下，主键索引和非主键索引其实结构上没什么区别，如下图。
然后是InnoDB
首先，它的主键索引是聚簇索引，如下图结构
它其实就是整张表，表中所有的数据都存储在这颗B-Tree中。聚簇索引的每一个叶子节点都包含了主键值、事务ID、用于事务和MVCC的回滚指针以及所有的剩余列。
InnoDB的二级索引和聚簇索引很不相同。InnoDB二级索引的叶子节点中存储的不是“行指针”，而是主键值，并以此作为指向行的“指针”这样的策略减少了当出现行移动或者数据页分裂时二级索引的维护工作。但是使用主键值当作指针会让二级索引占用更多的空间。
下面是一个二级索引的结构图
最后，我们通过下图来看看InnoDB和MyISAM保存数据和索引的区别
5.3.5.3 InnoDB主键的选择
如果正在使用InnoDB表并且没有什么数据需要聚集，那么可以定义一个代理键（surrogate key）作为主键，这种主键的数据应该和应用无关，最简单的方法是使用AUTO_INCREMENT自增列。这样可以保证数据行是按顺序写入，对于根据主键做关联操作的性能也会更好。
原因如下图，因为主键的值是顺序的，所以InnoDB把每一条记录都存储在上一条记录的后面。当达到页的最大填充因子时，下一条记录就会写入新的页中。一旦数据按照这种顺序的方式加载，主键页就会近似于被顺序的记录填满。
但是，假如我们选择一个相对随机无插入顺序的主键呢？
如下图
这将造成大量的随机I/O，大量的页分裂操作，并产生很多磁盘碎片。
因此，尽可能使用单调增加的聚簇键的值来插入新行。
5.3.6 覆盖索引
如果索引的叶子节点中已经包含要查询的数据，那么就没有必要再回表查询。如果一个索引包含所有需要查询的字段的值，我们就称之为“覆盖索引”。
5.3.6.1 覆盖索引的好处
-
索引条目通常远小于数据行大小，所以如果只需要读取索引，那MySQL就会极大地减少数据访问量。
-
因为索引是按照列值顺序存储的（至少在单个页内是如此），所以对于I/O密集型的范围查询会比随机从磁盘读取每一行数据的I/O要少得多。
-
由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。
5.3.7 使用索引扫描来做排序
MySQL可以使用同一个索引既满足排序，又用于查找行。因此，如果可能，设计索引时应该尽可能地同时满足这两种任务，这样是最好的。
只有当索引的列顺序和ORDER BY子句的顺序完全一致，并且所有列的排序方向都一样时，MySQL才能够使用索引来对结果做排序。如果查询需要关联多张表，则只有当ORDER BY子句引用的字段全部为第一个表时，才能使用索引做排序。ORDER BY子句和查找型查询的限制是一样的：需要满足索引的最左前缀的要求；否则，MySQL都需要执行排序操作，而无法利用索引排序。
但是同时还要注意与where条件的交互，假设表rental有索引(rental_date, inventory_id, customer_id)，下面举例说明
下面这个查询可以使用索引，因为第一列被指定为了常数rental_date='2015_05_25'，然后使用第二列排序，将两列组合起来就形成了索引的最左前缀。
1 | ... where rental_date = '2005-05-25' ORDER BY inventory_id; |
下面这个查询也没问题，因为ORDER BY使用的两列就是索引的最左前缀：
1 | WHERE rental_date > '2005-05-25' ORDER BY rental_date, inventory_id; |
下面是一些不能使用索引做排序的查询
-
下面这个查询的
ORDER BY子句中引用了一个不在索引中的列1
WHERE rental_date = '2005-05-25' ORDER BY inventory_id, staff_id;
-
下面这个查询的
WHERE和ORDER BY中的列无法组合成索引的最左前缀1
WHERE rental_date = '2005-05-25' ORDER BY customer_id;
-
下面这个查询在索引列的第一列上使用了范围条件，这个列倒是可以使用索引，但是会导致后面的列无法使用
1
WHERE rental_date > '2005-05-25' ORDER BY inventory_id, customer_id;
-
下面这个查询在
inventory_id列上有多个等于条件，对于排序来说，这也是一种范围查询1
WHERE rental_date = '2005-05-25' AND inventory_id IN(1, 2) ORDER BY customer_id
5.3.8 压缩（前缀压缩）索引
MyISAM使用前缀压缩来减少索引的大小，从而让更多的索引可以放入内存中，这在某些情况下能极大地提高性能。默认只压缩字符串，但通过参数设置也可以对整数做压缩。
MyISAM压缩每个索引块的方法是，先完全保存索引块中的第一个值，然后将其他值和第一个值进行比较得到相同前缀的字节数和剩余的不同后缀部分，把这部分存储起来即可。例如，索引块中的第一个值是perform，第二个值是performance，那么第二个值的前缀压缩后存储的是类似7, ance这样的形式。
5.3.9 重复索引
重复索引是指在相同的列上按照相同的顺序创建的相同类型的索引。
MySQL允许在相同列上创建重复索引，但是这会大大影响性能。因为MySQL需要单独维护重复的索引，并且优化器在优化查询的时候也需要逐个地进行考虑。
应该避免这样创建重复索引，发现以后也应该立即移除。
例如下图
一个经验不足的用户可能是想创建一个主键，先加上唯一限制，然后再加上索引以供查询使用。事实上，MySQL的唯一限制和主键限制都是通过索引实现的，因此，上面的写法实际上在相同的列上创建了三个重复的索引。
5.3.10 冗余索引
冗余索引和重复索引有一些不同。如果创建了索引(A, B)，再创建索引(A)就是冗余索引，因为这只是前一个索引的前缀索引。但是如果再创建索引(B,A)，则不是冗余索引。另外，将一个索引扩展为(A, ID)，其中ID是主键，对于InnoDB来说主键列已经包含在二级索引中了，所以这也是冗余的。
但也有时候出于性能方面的考虑需要冗余索引，因为扩展已有的索引会导致其变得太大，从而影响其他使用该索引的查询的性能。
建立过多冗余索引的缺点是导致写操作过慢
5.3.11 未使用的索引
可能还会有一些服务器永远不用的索引。这样的索引完全是累赘，建议考虑删除。
5.3.12 索引和锁
InnoDB只有在访问行的时候才会对其加锁，而索引能够减少InnoDB访问的行的次数，从而减少锁的数量。
此外，InnoDB在二级索引上使用共享（读）锁，但访问主键索引需要排他（写）锁。
5.4 索引案例学习
假设要设计一个在线约会网站，用户信息表有很多列，包括国家、地区、城市、性别、眼睛颜色，等等。网站必须支持上面这些特征的各种组合来搜索用户，还必须允许根据用户的最后在线时间、其他会员对用户的评分等对用户进行排序并对结果进行限制。如何设计索引满足上面的复杂需求呢？
5.4.1 支持多种过滤条件
现在需要看看这两方面
- 哪些列拥有很多不同的取值，在有更多不同值的列上创建索引的选择性会更好。
- 哪些列在
WHERE子句中出现得最频繁，更频繁则用到此索引的机会越多
按照这两点，我们筛选出了(sex, country)列作为前缀。
sex的选择性很低，但是为什么要选择它呢？因为我们有方法去绕过它：
- 如果某个査询不限制性别，那么可以通过在查询条件中新增
AND SEX IN('m', 'f')来让MySQL选择该索引。 - 这样写并不会过滤任何行，和没有这个条件时返回的结果相同。
- 但是必须加上这个列的条件，MySQL才能够匹配索引的最左前缀
接下来我们又选出了(sex, country, age)，(sex, country, region, age)，(sex, country, city, age)这样的组合。由于我们有了(sex, country, age)，而age并不会导致性能的太多下降，所以我们去掉(sex, country)
我们一直把age放到索引的最后面，age有什么特殊的地方吗
- 前面提到的列在
WHERE子句中都是等于条件，但是age列则多半是范围查询（例如查找年龄在18-25岁之间的人） - 原则上，尽可能将需要做范围查询的列放到索引的后面，以便优化器能使用尽可能多的索引列。
5.4.2 避免多个范围条件
假设我们有一个last_online列并希望通过下面的查询显示在过去几周上线过的用户
1 | WHERE eye_color IN('brown', 'blue', 'hazel') |
这个查询有一个问题：它有两个范围条件，last_online列和age列，MySQL可以使用last_online列索引或者age列索引，但无法同时使用它们。
我们可以用下面的方法避免这个问题
- 我们需要事先计算好一个
active列，这个字段由定时任务来维护。当用户每次登录时，将对应值设置为1，并且定时任务定时将过去连续七天未曾登录的用户的值设置为0。 - 这个方法可以让MySQL使用
(active,sex, country,age)索引。 - 并且我们还可以使用上面5.4.1提到的方法来绕过
active属性
5.4.3 优化排序
使用文件排序对小数据集是很快的，但如果一个查询匹配的结果有上百万行的话就很慢了。所以根据5.3节我们可以创建一些索引用于排序。
但是分页是另一个性能瓶颈，例如下面的查询
1 | SELECT col1 FROM profiles WHERE sex = 'M' ORDER BY rating LIMIT 100000, 10; |
- 无论如何创建索引，这种査询都是个严重的问题。
- 因为随着偏移量的增加，MySQL需要花费大量的时间来扫描需要丢弃的数据。反范式化、预先计算和缓存可能是解决这类查询的仅有策略。
优化这类索引的另一个比较好的策略是使用延迟关联，通过使用覆盖索引查询返回需要的主键，再根据这些主键关联原表获得需要的行。如下所示
