索引是存储引擎用于快速找到记录的一种数据结构。除了加速查找，索引在其他方面也有一些有用的属性。索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时，不恰当的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急剧下降，索引优化应该是对查询性能优化最有效的手段了。

索引类型

B-Tree索引
使用术语“B-Tree”，是因为MySQL在CREATE TABLE 和其他语句中也使用该关键字。但是底层的存储引擎也可能使用不同的存储结构，如InnoDB使用的是B+Tree。存储引擎以不同的方式使用B-Tree索引，性能也各有不同，各有优劣。例如，MyISAM使用前缀压缩技术使得索引更小，但InnoDB则按照原数据格式进行存储。再如MyISAM索引通过数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。
B-Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同，B-Tree索引的抽象表示如图1-1：

图1-1 建立在B+ Tree上的索引

B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，而是从索引的根节点开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。叶子节点比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页（不同引擎的“指针”类型不同）。

B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据，还可以用于查询中的Order By操作，索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。
B-Tree索引适用于全键值、键值范围或键前缀查找。其中键前缀查找只适用于根据最左前缀的查找：
全值匹配：全值匹配指的是和索引中的所有列进行匹配。
最左匹配原则：使用第一列索引进行全值匹配、模糊匹配、范围匹配。

在Mysql5.5+版本，B tree索引也存在一些限制会导致查询时无法使用索引：

• 如果不是按照索引的最左列开始查找，则无法使用索引。
• 不能跳过索引中的列。
• 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。

哈希索引
哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有它的限制：

• 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
• 哈希索引会随机存储数据，不能很好的支持Order By等排序操作。
• 哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
• 哈希索引只支持等值比较查询，包括=、IN()、<=>（注意<>和<=>是不同的操作），也不支持任何范围查询。
• 当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较。
• 当哈希冲突很多的话，一些索引维护操作的代价也会很高，例如，在某个可选性很低（哈希冲突很多）的列上建立哈希索引，在进行相应操作时，需要遍历对应哈希值的每一行。

索引的优点

索引可以让服务器快速地定位到表的指定位置，但是这并不是索引的唯一作用。根据创建索引的数据结构不同，索引也有一些其他的附加作用。对于B Tree索引，有以下三个优点：

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

Relational Database Index Design and the Optimizers书中介绍了如何评价一个索引是否适合某个查询的“三星系统”（three-star system）：

1. 索引将相关的记录放到一起则获得一星
2. 如果索引中的数据顺序和查找中的排列顺序一致则获得二星
3. 如果索引中的列包含了查询中需要的全部列则获得三星

但索引就是最好的解决方案吗？
索引并不总是最好的工具。总的来说，只有当索引帮助存储引擎快速查找到记录带来的好处大于其带来的额外工作时，索引才是有效的。对于非常小的表，大部分情况下简单的全表扫描更高效。对于中到大型的表，索引就非常有效。但对于特大型的表，建立和使用索引的代价将随之增长。这种情况下，则需要有一种技术可以直接区分出查询需要的一组数据，而不是一条记录一条记录地匹配。

高性能的索引策略

独立的列
如果查询中的列不是独立的，则MySQL就不会使用索引。“独立的列”是指索引列不能是表达式的一部分，也不能是函数的参数。
例如，下面这个查询无法使用actor_id 列的索引：
mysql> SELECT actor_id FROM sakila.actor WHERE actor_id + 1 = 5
很容易看出WHERE中的表达式其实等价于actor_id=4 ，但MySQL无法自动解析这个方程式。我们应该养成简化WHERE条件的习惯，始终将索引列单独放在比较符号的一侧。下面是另一个常见的错误：
mysql> SELECT ... WHERE TO_DAYS(CURRENT_DATE) - TO_DAYS(date_col) <= 1

前缀索引和索引选择性
有时候需要索引很长的字符列，这会让索引变得大且慢。一个策略是模拟哈希索引，除此之外还可以索引开始的部分字符，这样可以大大节约索引空间，从而提高索引效率。对于BLOB 、TEXT 或者很长的VARCHAR 类型的列，必须使用前缀索引，因为MySQL不允许索引这些列的完整长度。诀窍在于要选择足够长的前缀以保证较高的选择性，以使得前缀索引的选择性接近于索引整个列（最好便是每个值都是唯一的）。

多列索引
对于多列索引，一个常见的错误就是，为每个列创建独立的索引，或者按照错误的顺序创建多列索引。
在多个列上建立独立的单列索引大部分情况下并不能提高MySQL的查询性能, MySQL5.0和更新版本引入了一种叫“索引合并”（index merge）的策略，一定程度上可以使用表上的多个单列索引来定位指定的行。例如，表film_actor 在字段film_id 和actor_id 上各有一个单列索引。但对于下面这个查询WHERE 条件，这两个单列索引都不是好的选择：

mysql> SELECT film_id, actor_id FROM sakila.film_actor WHERE actor_id = 1 OR film_id = 1;

查询能够同时使用这两个单列索引进行扫描，并将结果进行合并。这种算法有三个变种：OR条件的联合（union），AND 条件的相交（intersection），组合前两种情况的联合及相交。Explain解释如下：

合适的索引列顺序
正确的顺序依赖于使用该索引的查询，并且同时需要考虑如何更好地满足排序和分组的需要，这仅适用于B-Tree索引，其他索引类型并不会顺序存储数据。在一个多列B-Tree索引中，索引列的顺序意味着索引首先按照最左
列进行排序，其次是第二列，等等。所以，索引可以按照升序或者降序进行扫描，以满足精确符合列顺序的ORDER BY、GROUP BY 和DISTINCT等子句的查询需求。

对于如何选择索引的列顺序有一个经验法则：将选择性最高的列放到索引最前列。这个建议有用吗?在某些场景可能有帮助，但通常不如避免随机IO和排序那么重要，考虑问题需要更全面，场景不同则选择不同。
当不需要考虑排序和分组时，将选择性最高的列放在前面通常是很好的。这时候索引的作用只是用于优化WHERE 条件的查找。在这种情况下，这样设计的索引确实能够最快地过滤出需要的行，对于在WHERE 子句中只使用了索引部分前缀列的查询来说选择性也更高。然而，性能不只是依赖于所有索引列的选择性（整体基数），也和查询条件的具体值有关，也就是和值的分布有关。可能需要根据那些运行频率最高的查询来调整索引列的顺序，让这种情况下索引的选择性最高。以下面的查询为例：
SELECT * FROM payment WHERE staff_id = 2 AND customer_id = 584;
是应该创建一个（staff_id，customer_id ）索引还是应该颠倒一下顺序? 这其实应该基于全局基数来分析列的选择性：

聚簇索引
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。具体的细节依赖于其实现方式，InnoDB的聚簇索引实际上在同一个结构中保存了B-Tree索引和数据行。当表有聚簇索引时，它的数据行实际上存放在索引的叶子页（leaf page）中。术语“聚簇”表示数据行和相邻的键值紧凑地存储在一起。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引(主键)。

聚簇主键可能对性能有帮助，但也可能导致严重的性能问题。聚集的数据有一些重要的优点：

• 数据访问更快。聚簇索引将索引和数据保存在同一个B-Tree中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
• 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。

如果在设计表和查询时能充分利用上面的优点，那就能极大地提升性能。同时，聚簇索引也有一些缺点：

• 插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式。
• 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置。
• 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂（page split）”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次页分裂操作，页分裂会导致表占用更多的磁盘空间，也会导致数据存储不连续，造成随机IO。
• 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。
• 二级索引（非聚簇索引）可能比想象的要更大，因为在二级索引的叶子节点包含了引用行的主键列。
• 二级索引访问需要两次索引查找，而不是一次。

在InnoDB中按照主键顺序插入行
如果正在使用InnoDB表并且没有什么数据需要聚集，那么可以定义一个代理键（surrogate key）作为主键，这种主键的数据应该和应用无关，最简单的方法是使用AUTO_INCREMENT 自增列。这样可以保证数据行是按顺序写入，对于根据主键做关联操作的性能也会更好，顺序插入示意图如下：

图 1-2 向聚簇索引中插入顺序的索引值

但顺序的主键什么时候会造成更坏的结果?
对于高并发工作负载，在InnoDB中按主键顺序插入可能会造成明显的争用。主键的上界会成为“热点”。因为所有的插入都发生在这里，所以并发插入可能导致间隙锁竞争。另一个热点可能是AUTO_INCREMENT 锁机制；如果遇到这个问题，则可能需要考虑重新设计表或者应用，或者更改innodb_autoinc_lock_mode 配置。参考：https://www.jianshu.com/p/e7d2dcd71aad

最好避免随机的（不连续且值的分布范围非常大）聚簇索引，特别是对于I/O密集型的应用。例如，从性能的角度考虑，使用UUID来作为聚簇索引则会很糟糕：它使得聚簇索引的插入变得完全随机，这是最坏的情况，使得数据没有任何聚集特性。在把这些随机值载入到聚簇索引以后，也许需要做一次OPTIMIZETABLE 来重建表并优化页的填充。

图 1-3 向聚簇索引中插入无序的值

覆盖索引
通常大家都会根据查询的WHERE 条件来创建合适的索引，不过这只是索引优化的一个方面。设计优秀的索引应该考虑到整个查询，而不单单是WHERE 条件部分。MySQL可以使用索引来直接获取列的数据，这样就不再需要读取数据行。如果索引的叶子节点中已经包含要查询的数据，那么还有什么必要再回表查询呢?如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”。
覆盖索引是非常有用的工具，能够极大地提高性能。考虑一下如果查询只需要扫描索引而无须回表，会带来多少好处：

• 索引条目通常远小于数据行大小，所以如果只需要读取索引，那MySQL就会极大地减少数据访问量。
• 因为索引是按照列值顺序存储的（至少在单个页内是如此），所以对于I/O密集型的范围查询会比随机从磁盘读取每一行数据的I/O要少得多。
• 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，所以如果二级主键能够覆盖查询，则可以避免对主键索引的二次查询。

不是所有类型的索引都可以成为覆盖索引。覆盖索引必须要存储索引列的值，而哈希索引、全文索引等都不存储索引列的值，所以MySQL只能使用B-Tree索引做覆盖索引。

在select * 时无法使用到覆盖索引，但可以将单个查询转换为关联查询，在子查询中使用聚簇索引减小数据量。如下例所示：

mysql> EXPLAIN SELECT * FROM products WHERE actor='SEAN CARREY' AND title like '%APOLLO%'

索引扩展至覆盖三个数据列（artist，title，prod_id）后重写SQL：

mysql> EXPLAIN SELECT * FROM products JOIN (SELECT prod_id FROM products WHERE actor='SEAN CARREY' AND title LIKE '%APOLLO% ) AS t1 ON (t1.prod_id=products.prod_id)

我们把这种方式叫做延迟关联（deferred join），因为延迟了对列的访问。在查询的第一阶段MySQL可以使用覆盖索引，在FROM 子句的子查询中找到匹配的prod_id ，然后根据这些prod_id 值在外层查询匹配获取需要的所有列值。虽然无法使用索引覆盖整个查询，但总算比完全无法利用索引覆盖的好。这样优化的效果取决于WHERE 条件匹配返回的行数。

使用索引扫描来做排序
MySQL有两种方式可以生成有序的结果：通过排序操作；或者按索引顺序扫描；如果EXPLAIN 出来的type 列的值为“index ”，则说明MySQL使用了索引扫描来做排序。
扫描索引本身是很快的，因为只需要从一条索引记录移动到紧接着的下一条记录。但如果索引不能覆盖查询所需的全部列，那就不得不每扫描一条索引记录就都回表查询一次对应的行，这基本上都是随机I/O，因此按索引顺序读取数据的速度通常要比顺序地全表扫描慢，尤其是在I/O密集型的工作负载时。
只有当索引的列顺序和ORDER BY 子句的顺序完全一致，并且所有列的排序方向（倒序或正序）都一样时，MySQL才能够使用索引来对结果做排序。ORDER BY 子句和查找型查询的限制是一样的：需要满足索引的最左前缀的要求；否则，MySQL都需要执行排序操作，而无法利用索引排序。
有一种情况下ORDER BY 子句可以不满足索引的最左前缀的要求，就是前导列为常量的时候。如果WHERE 子句或者JOIN 子句中对这些列指定了常量，就可以“弥补”索引的不足。如sales_order表中存在index(region_no,order_no,order_type)，运行如下SQL语句，Mysql 可以使用到index为其进行排序, 这是因为索引的第一列被指定为一个常数。

selece region_no, order_no, order_type from sales_order where region_no = 86 order by order_no, order_type

压缩（前缀压缩）索引
MyISAM使用前缀压缩来减少索引的大小，从而让更多的索引可以放入内存中，这在某些情况下能极大地提高性能。默认只压缩字符串，但通过参数设置也可以对整数做压缩。
压缩块使用更少的空间，代价是某些操作可能更慢。因为每个值的压缩前缀都依赖前面的值，所以MyISAM查找时无法在索引块使用二分查找而只能从头开始扫描。测试表明，对于CPU密集型应用，因为扫描需要随机查找，压缩索
引使得MyISAM在索引查找上要慢好几倍。压缩索引的倒序扫描就更慢了。

冗余和重复索引
重复索引是指在相同的列上按照相同的顺序创建的相同类型的索引。应该避免这样创建重复索引，发现以后也应该立即移除。
冗余索引和重复索引有一些不同。如果创建了索引（A，B），再创建索引（A）就是冗余索引。冗余索引通常发生在为表添加新索引的时候。例如，有人可能会增加一个新的索引（A，B ）而不是扩展已有的索引（A ）。还有一种情况
是将一个索引扩展为（A，ID），其中ID是主键，对于InnoDB来说主键列已经包含在二级索引中了，所以这也是冗余的。
大多数情况下都不需要冗余索引，应该尽量扩展已有的索引而不是创建新索引。但也有时候出于性能方面的考虑需要冗余索引，因为扩展已有的索引会导致其变得太大，从而影响其他使用该索引的查询的性能。

索引和锁
索引可以让查询锁定更少的行。如果你的查询从不访问那些不需要的行，那么就会锁定更少的行，从两个方面来看这对性能都有好处。
InnoDB只有在访问行的时候才会对其加锁，而索引能够减少InnoDB访问的行数，从而减少锁的数量。但这只有当InnoDB在存储引擎层能够过滤掉所有不需要的行时才有效。如果索引无法过滤掉无效的行，那么在InnoDB检索到数据并返回给服务器层以后，MySQL服务器才能应用WHERE 子句，这时已经无法避免锁定行了。在MySQL 5.1和更新的版本中，InnoDB可以在服务器端过滤掉行后就释放锁。