一本书的目录就是它的索引。

索引基础

索引的类型

不同存储引擎的索引的工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引，其底层的实现也可能不同。

B-tree索引

InnoDB使用的是其变种 B+tree。B-tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。

建立在B-tree结构（准确地说是B+tree）上的索引

数据存储示例

sql
CREATE TABLE People (
 last_name varchar(50) not null,
 first_name varchar(50) not null,
 dob date not null,
 key(last_name, first_name, dob)
);

（最上面一行有问题，Angelina < Cuba，应该在前面）

索引对多个值进行排序的依据是CREATE TABLE语句中定义索引时列的顺序。

InnoDB存储引擎有一个被称为自适应哈希索引的特性。当InnoDB发现某些索引值被非常频繁地被访问时，它会在原有的B-tree索引之上，在内存中再构建一个哈希索引。可以通过参数关闭这个特性。

todo: 书中说可以使用非前缀。 可以使用B-tree索引的查询类型。

全值匹配

指索引中的列全部出现在 where 条件中。

匹配最左前缀

指索引中从左到右顺序的列出现在 where 条件中。

匹配列前缀

指 where 的某个条件是某个索引的第一个字段，并且是该字段值的前缀。

匹配范围值

指 where 指定的两个限定范围的条件都是某个索引的第一个字段。

精确匹配某一列而范围匹配另外一列

即索引的第一列全匹配，第二列是范围匹配。

只访问索引的查询

即覆盖索引。

因为索引树中的节点是有序的，所以除了按值查找，索引还可以用于查询中的ORDER BY操作（按顺序查找）。

B-tree索引的限制

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

全文索引

FULLTEXT是一种特殊类型的索引，它查找的是文本中的关键词，而不是直接比较索引中的值。

相关概念

• 停用词
• 词干
• 复数
• 布尔搜索

索引的优点

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

高性能的索引

前缀索引和索引的选择性

可以对字段的前一部分进行索引，可以减少空间占用，但是会降低选择性。索引的选择性指不重复的索引值（也称为基数，cardinality）和数据表的记录总数（＃T）的比值。选择性越大查询效率越高。对于BLOB、TEXT或很长的 VARCHAR 类型，必须使用前缀索引，因为 MySQL 不支持这些列的完整内容索引。

设计索引时可以使前缀索引的选择性接近完整列的选择性来优化索引。这需要测试不同的前缀长度的选择性。但是需要注意数据分布不均匀的情况。

创建前缀索引

sql
ALTER TABLE tb_name ADD KEY (column(7));

MySQL无法使用前缀索引做ORDER BY和GROUP BY操作，也无法使用前缀索引做覆盖扫描。

多列索引

一个常见的错误是对多个列单独建立索引，这在大部分情况下不能提升性能。因为 MySQL 引入了一种叫索引合并（index merge）的策略，其同时使用那些单独的索引进行扫描，并将结果合并。

这种算法有三个变种：

• OR条件的联合（union）
• AND条件的相交（intersection）
• 组合前两种情况的联合及相交

索引合并的问题在于

• 当优化器需要对多个索引做联合操作时（通常有多个OR条件），通常需要在算法的缓存、排序和合并操作上耗费大量CPU和内存资源，尤其是当其中有些索引的选择性不高，需要合并扫描返回的大量数据的时候。
• 更重要的是，优化器不会把这些操作计算到“查询成本”（cost）中，优化器只关心随机页面读取。这会使得查询的成本被“低估”，导致该执行计划还不如直接进行全表扫描。这样做不但会消耗更多的CPU和内存资源，还可能会影响并发的查询，但如果单独运行这样的查询则往往会忽略对并发性的影响。

可以通过参数optimizer_switch来关闭索引合并功能，还可以使用IGNORE INDEX语法让优化器强制忽略掉某些索引，从而避免优化器使用包含索引合并的执行计划。

选择合适的索引列顺序

正确的顺序依赖于使用该索引的查询语句，同时，还需要考虑如何更好地满足排序、分组和范围查询操作的需要。

经验法则

• 将选择性最高的列放到索引最前列。
• 考虑如何避免大量随机I/O和排序。

聚簇索引

聚簇索引不是新的的索引类型，而是一种存储方式。在 InnoDB 中聚簇索引就是 B-tree，但是会在叶子页中存储数据行。因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引（不过，覆盖索引可以模拟多个聚簇索引的情况。）

聚簇索引的数据分布。中间的节点页没有数据，叶子节点存储了数据。

MySQL 内置的存储引擎都不支持选择用于聚簇的索引，InnoDB 根据主键聚簇数据。如果你没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。这样做的缺点在于，所有需要使用这种隐藏主键的表都依赖一个单点的“自增值”，这可能会导致非常高的锁竞争，从而出现性能问题。

聚簇数据的优点

• 相关联的数据保存在一起，如果需要查询这些数据，磁盘 I/O 会很少。
• 聚簇索引将索引和数据保存在同一个B-tree中，因此从聚簇索引中获取数据通常比在非聚簇索引中查找要快。
• 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。

聚簇索引的缺点

• 聚簇索引的优势在于提高了I/O的性能，如果数据能够全部放入内存，那么就没什么优势了。
• 插入速度严重依赖于插入顺序。按照主键的顺序插入行是将数据加载到InnoDB表中最快的方式。
• 更新聚簇索引列的代价很高，因为它会强制InnoDB将每个被更新的行移动到新的位置。
• 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临页分裂（page split）的问题。页分裂会导致表占用更多的磁盘空间。
• 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候。
• 二级索引（非聚簇索引）可能比想象中的要更大，因为二级索引的叶子节点包含了引用行的主键列。
• 二级索引访问需要两次索引查找，而不是一次。

二级索引的叶子节点存储的是主键的值，所以查询数据需要访问两次索引。

sql
CREATE TABLE layout_test (
 col1 int NOT NULL,
 col2 int NOT NULL,
 PRIMARY KEY(col1),
 KEY(col2)
);

InnoDB表layout test的主键物理存储分布

InnoDB表layout test的二级索引分布

代理键（surrogate key）

这种主键的值和应用无关，最简单的方法是使用AUTO_INCREMENT自增列。这样可以保证数据行是按顺序写入的，对于根据主键做联接操作的性能也会更好。

最好避免随机的（不连续且值的分布范围非常大）聚簇索引，特别是对于I/O密集型的应用。例如，从性能的角度考虑，使用UUID作为聚簇索引会很糟糕：它使得聚簇索引的插入变得完全随机，这就是最糟糕的情况，数据本身没有任何聚集特性。

顺序的插入 vs 随机插入

向聚簇索引顺序地插入索引值

向聚簇索引中插入无序的记录

随机插入的缺点

• 写入的目标页可能已经刷到磁盘上并从缓存中移除，或者还没有被加载到缓存中，InnoDB在插入之前不得不先找到，并从磁盘将目标页读取到内存中。这将导致大量的随机I/O。
• 因为写入是乱序的，所以InnoDB不得不频繁地做页分裂操作，以便为新记录分配空间。页分裂会导致移动大量数据，一次插入最少需要修改三个页而不是一个。
• 由于频繁的页分裂，页会变得稀疏并被不规则地填充，所以最终数据会有碎片。

在把这些随机值载入聚簇索引后，最好做一次OPTIMIZE TABLE来重建表并优化页的填充情况。

sql
OPTIMIZE TABLE tb_name;

什么时候按主键顺序插入反而会更糟

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

覆盖索引

如果一个索引包含（或者说覆盖）所有需要查询的字段的值，我们就称之为覆盖索引。需要注意的是，只有B-tree索引可以用于覆盖索引。当然，二级索引的叶子节点包含主键值，所以在查询列出现主键也可以覆盖。

覆盖索引的优点

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

使用索引扫描来做排序

MySQL有两种方式可以生成有序的结果：通过排序操作，或者按索引顺序扫描。如果在EXPLAIN的输出结果中，type列的值为“index”，则说明MySQL使用了索引扫描来做排序。

如果索引不能覆盖查询所需的全部列，那么就不得不每扫描一条索引记录都回表查询一次对应的记录。这基本上都是随机I/O，因此按索引顺序读取数据的速度通常要比顺序地全表扫描慢。

只有当索引的顺序和ORDER BY子句的顺序完全一致，并且所有列的排序方向（倒序或正序）都一样时，MySQL才能使用索引来对结果做排序。如果查询需要联接多张表，则只有当ORDER BY子句引用的字段全部在第一个表中时，才能使用索引做排序。ORDER BY子句和查找型查询的限制是一样的：需要满足索引的最左前缀的要求，否则，MySQL需要执行排序操作，而无法利用索引排序。

例子

sql
CREATE TABLE rental (
 ...
 PRIMARY KEY (rental_id),
 UNIQUE KEY rental_date (rental_date,inventory_id,customer_id),
 KEY idx_fk_inventory_id (inventory_id),
 KEY idx_fk_customer_id (customer_id),
 KEY idx_fk_staff_id (staff_id),
 ...
);

可以使用索引排序的例子

sql
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC;
... WHERE rental_date > '2005-05-25' ORDER BY rental_date, inventory_id;

不能使用索引排序的例子

sql
-- 索引中的列都是按正序排序的, 下面的 inventory_id 使用逆序了
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id DESC, customer_id ASC;
-- 引用了一个不在索引中的列
... WHERE rental_date = '2005-05-25' ORDER BY inventory_id, staff_id;
-- WHERE和ORDER BY中的列无法组合成索引的最左前缀
... WHERE rental_date = '2005-05-25' ORDER BY customer_id;
-- 在索引列的第一列上是范围条件，所以MySQL无法使用索引的其余列排序
... WHERE rental_date > '2005-05-25' ORDER BY inventory_id, customer_id;
-- 这个查询在inventory_id列上有多个等于条件。对于排序来说，这也是一种范围查询
... WHERE rental_date = '2005-05-25' AND inventory_id IN(1,2) ORDER BY customer_id;

冗余和重复索引

MySQL允许在相同列上创建多个相同的索引，这会影响性能同时也浪费磁盘空间。

• 重复索引是指在相同的列上按照相同顺序创建的相同类型的索引。应该避免创建这样的重复索引，发现以后应该立即移除。
• 冗余索引和重复索引不同，如果创建了索引（A，B），再创建索引（A）就是冗余索引。另一种冗余索引是，将一个索引扩展为（A，ID），其中ID是主键，因为主键列已经包含在二级索引中了。

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

未使用的索引

没什么用，应该删除。查找未使用的索引：

sql
SELECT * FROM sys.schema_unused_indexes;

维护索引和表

维护表有三个主要目的：找到并修复损坏的表，维护准确的索引统计信息，减少碎片。

找到并修复损坏的表

如果你遇到了古怪的问题，可以尝试运行CHECK TABLE来检查是否发生了表损坏（有些存储引擎不支持）。可以使用REPAIR TABLE命令来修复损坏的表，但同样不是所有的存储引擎都支持该命令。如果存储引擎不支持，可通过一个不做任何操作（n o-o p）的ALTER操作来重建表，例如，将表的存储引擎修改为当前的引擎。

sql
ALTER TABLE <table> ENGINE=INNODB;

此外，还可以将数据导出再导入一次。不过，如果损坏的是系统区域，或者是表的“行数据”区域，而不是索引，那么上面的办法就没有用了。在这种情况下，可以从备份中恢复表，或者尝试从损坏的数据文件中尽可能地恢复数据。

更新索引统计信息

MySQL的优化器使用的是基于成本的模型，而衡量成本的主要指标就是一个查询需要扫描多少行。如果表没有统计信息，或者统计信息不准确，优化器就很有可能做出错误的决定。可以通过运行ANALYZE TABLE来重新生成统计信息，以解决这个问题。

可以使用SHOW INDEX FROM命令来查看索引的基数（cardinality）。

sql
SHOW INDEX FROM tb_name\G

索引统计信息何时更新

• InnoDB会在表首次打开
• 执行ANALYZE TABLE
• 表的大小发生非常大的变化时
• InnoDB在打开某些INFORMATION_SCHEMA表
• 使用SHOW TABLE STATUS和SHOW INDEX
• 在MySQL客户端开启自动补全功能的时候
• 使用SHOW INDEX查看索引统计信息

如果有大量的表，会带来性能问题，可以关闭innodb_stats_on_metadata参数来避免。

减少索引和数据的碎片

B-tree索引可能会产生碎片化，这会降低查询的效率。碎片化的索引可能会以很差或者无序的方式存储在磁盘上。根据设计，B-tree索引需要随机磁盘访问才能定位到叶子页，所以随机访问总是不可避免的。

表的数据存储也可能发生碎片化。有三种类型的数据碎片：

• 行碎片（Row fragmentation）这种碎片指的是数据行被存储在多个地方的多个片段中。即使查询只从索引中访问一行记录，行碎片也会导致性能下降。
• 行间碎片（Intra-row fragmentation）是指逻辑上顺序的页或者行，在磁盘上不是顺序存储的。行间碎片对诸如全表扫描和聚簇索引扫描之类的操作有很大的影响。
• 剩余空间碎片（Free space fragmentation）
• 指数据页中有大量的空余空间。这会导致服务器读取大量不需要的数据，从而造成浪费。

可以通过执行OPTIMIZE TABLE或者导出再导入的方式来重新整理数据。对于那些不支持OPTIMIZE TABLE的存储引擎，可以通过一个不做任何操作（no-op）的ALTER TABLE操作来重建表。

sql
ALTER TABLE <table> ENGINE=<engine>;

小结

总的来说，编写查询语句时应该尽可能选择合适的索引以避免单行查找，尽可能地使用数据内部顺序从而避免额外的排序操作，并尽可能地使用索引覆盖查询。

参考

• 深入了解 B-Tree 和 B+Tree 的区别
• Sakila Sample Database
• B+树索引的使用
• mysql show index from table 各参数含义