1. 索引基础

• 索引是在存储引擎层而非服务器层实现的。

• B-Tree索引

  关于B-Tree索引更详细地内容，可在数据结构与算法中了解。

  1. 一般而言，如果索引没有特别指明类型，大多则说的是B-Tree索引。（具体为B+Tree）
  2. 虽然"B-Tree"是MySQL的关键字，但一般底层的存储引擎可能选择不同的结构。比如NDB集群存储引擎使用的是T-tree，InnoDB使用的是B+Tree。MyISAM使用前缀压缩技术使得索引更小；InnoDB则按照原数据格式进行存储。
  3. B-Tree对索引列是按顺序组织存储的，所以很适合查找范围数据以及进行ORDER BY操作.
  4. 适合使用B-Tree索引的查询类型有：全值匹配（即索引列直接等于某值）、匹配最左索引列（即联合索引中最左侧索引列的全值匹配）、匹配索引列前缀（只匹配某一索引列的值的开头部分）、匹配索引列范围值（查询索引列的值在某一范围的数据）、精确匹配某一列并范围匹配另一列（联合索引中第一列的全值匹配+第二列的范围匹配）。
  5. 对于联合索引，MySQL遵循最左匹配原则。即当查询条件中出现最左侧的索引列时，才会使用索引，并以此类推联合索引中后续的列。如果查询条件中跳过了联合索引中的中间某列，则该列右边的索引列将无法使用到。如果查询条件中有某个列的范围查询，则该列右侧的索引列无法被使用。
  6. 最左匹配原则与查询条件中列出现的顺序无关，MySQL查询优化器会优化查询列的顺序。

• 哈希索引

  1. 哈希索引基于哈希表实现。存储引擎会对所有的索引列计算一个哈希码并保存在索引中，同时在哈希表中存储指向数据行的指针。哈希索引只对精确匹配的索引所有列的查询才有效。
  2. MySQL中只有Memory引擎显示支持哈希索引。
  3. 哈希索引值包含哈希值和行指针，不存储字段值，故而不能使用索引中的值来避免读取行；哈希索引不是按照索引值顺序存储的，无法用于排，不支持范围查询，不支持索引列的匹配查找；只支持等值比较。
  4. InnoDB中有一个功能叫做“自适应哈希索引”，会在内存中基于B-Tree的索引之上创建一个哈希索引，使其具有哈希索引的一些优点。这是一个完全自动的、内部的行为，不受用户控制。
  5. 存储引擎如果不支持哈希索引，可以创建一个自定义的哈希索引。即新增一列，存储需要索引列的哈希值，后续查找时直接使用这个哈希值进行等值匹配的查找。比如需要存储大量的URL，但URL一般比较长，占用存储比较大。这时可以新增一列url_crc，存储URL的哈希值，查找时则通过 SELECT * FROM url WHERE url="https://www.mysql.com" AND url_crc = CRC32("https://www.mysql.com"); 的方式进行查找。

• 其他索引类型

  • 空间数据索引（R-Tree）。
  • 全文索引。适合查找文本中的关键词，适用于MATCH AGAINST操作而不是WHERE操作。
  • TokuDB的分形树索引。

2. 索引的优点

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

3. 高性能的索引策略

• 独立的列

  • 独立的列是指索引列不能是表达式的一部分，也不能是函数的参数。如下语句将无法使用 user_id 列的索引：SELECT user_id FROM users WHERE user_id + 1 = 5 ，虽然其等价于 user_id = 4

• 索引选择性和前缀索引

  • 索引选择性是指不重复的索引值和数据表记录总数（#T）的比值，范围在 1/#T 到 1 之间。索引选择性越高也查询效率越高，因为其可以让 MySQL 在查找时过滤掉更多的行。唯一索引的选择性是1，这是最好的索引选择性。
  • 如果要索引很长的列，可能会让索引变得大且慢，可以通过只索引列开始部分的字符，以达到节约索引空间，提高索引效率的目的。这种方式称之为前缀索引。
    • 在使用前缀索引时，需要选择合适的前缀长度，以保证较高的索引选择性，同时也要避免前缀过长。一种方案是，通过比较和完整列的索引选择性，以判断当前长度的前缀索引的选择性是否够用。
      计算当前索引的索引选择性：SELECT COUNT(DISTINCT city)/COUNT(*) FROM city_demo;
      计算前缀长度为4的索引的选择性：SELECT COUNT(DISTINCT LEFT(city, 3))/COUNT(*) FROM city_demo;
      比较两者的大小，当两者接近时，则认为该前缀索引的选择性和完整索引的基本一致，否则则继续增加前缀长度，直至前缀索引的选择性接近完整索引时。
    • MySQL 无法使用前缀索引进行 ORDER BY 和 GROUP BY 以及覆盖扫描等。

• 多列索引

  • 在多个列上建立单列索引大部分情况下并不能提高 MySQL 的查询性能。新版本的 MySQL 会通过一种索引合并的策略优化多个单列索引的查询。
  • 如果 EXPLAIN 中有出现索引合并的提示信息，往往代表索引并不是最优的。

• 选择合适的索引列顺序

  • 选择索引的列顺序有一个经验法则：

• 聚簇索引

  • 聚簇索引不是一种单独的索引类型，而是一种数据存储方式。在 InnoDB 中，表的数据行实际放在了 B-Tree 索引的叶子页中。术语“聚簇”表示数据化和相邻的简直紧凑的存储在一起。因为无法同时把数据行存储在两个不同的地方，所以一个表只能有一个聚簇索引。(Oracle 可能称之为索引组织表)

  • InnoDB 默认通过主键聚集索引。如果没有定义主键，MySQL 会选择一个唯一的非空索引代替。如果没有这样的索引，MySQL 会隐式定义一个主键来作为聚簇索引。

  • 聚簇索引的一些优点：

    1. 可以把相关的数据保存在一起，以减少可能的 磁盘IO。
    2. 通过聚簇索引查询数据通常比通过二级索引更快。
    3. 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。

  • 聚簇索引的一些缺点：

    1. 如果数据可以全部放在内存中，则 IO 读取时依赖的访问顺序就没那么重要了，聚簇索引也没有优势。
    2. 插入速度验证依赖插入顺序。按主键顺序插入是将数据写到 InnoDB 表中速度最快的方式。如果不是按主键顺序，那聚簇索引在写入数据时可能会频繁遇到页分裂等问题从而拖慢写入速度。
    3. 更新聚簇索引列的值的代价很高，因为InnoDB 会强制将被更新的行移动到新的位置。
    4. 二级索引的叶子节点包含了引用行的主键列，而非行存储位置的指针。因此二级索引（非聚簇索引）可能比想象的大。而且通过二级索引的访问需要两次索引查找，一次先通过二级索引找到主键列，另一次是再通过聚簇索引找到具体位置。

  • InnoDB 和 MyISAM 的数据分布对比

    • 可以通过下图很直观地看出 InnoDB和 MISAM 存储数据的异同。
      
    • MyISAM（使用非聚簇索引）中，主键索引和二级索引的结构是完全一样的。索引的叶子节点中存储的是行指针，所以需要独立的行存储。
    • InnoDB （使用聚簇索引）中，聚簇索引就是“表”，所以不需要独立的行存储。InnoDB 中二级索引的结构和主键索引有很大不同，二级索引的叶子节点中存储的是主键值。

  • 在 InnoDB 中按主键顺序插入行

    • 使用 InnoDB 时应该尽可能按主键顺序插入数据，并且尽可能使用单调增加的聚簇键的值来插入新行，避免随机的聚簇索引。
      1. 如果使用随机的聚簇索引，会导致 InnoDB 频繁地做页分裂操作，由于聚簇索引中，行数据和索引存储在一起，页分裂将导致移动大量数据。
      2. 由于写入的值是随机的，有可能写入到已经落盘且从缓存中移除的页，这时InnoDB 不得不先从磁盘加载目标页到内存中，将导致大量的随机 IO。
      3. 频繁的页分裂也会导致数据有碎片。
    • 顺序的主键可能会在一些情况造成更坏的结果。主键的上界会成为热点，因为所有的插入都在这里，并发插入可能导致间隙锁竞争。另一个热点可能是AUTO INCREMENT锁机制。

• 覆盖索引

  • 如果一个索引包含了所有需要查询的字段的值，我们称之为覆盖索引。
  • EXPLAIN时如果 extra 列看到 Using Index 的信息，代表这次查询是一个被索引覆盖的查询。
  • 覆盖索引有一些好处：
    1. 索引条目通常远小于数据行的大小，所以如果只读取索引，会极大的减小数据访问量。
    2. 因为索引是按列值顺序存储的，所以范围查询会比随机从磁盘读取一行数据的 IO 小很多。
    3. 由于 InnoDB 是聚簇索引，所以如果二级索引能够覆盖查询，则可以避免对于主键索引的二次查询。
  • MySQL 5.6版本中，包含了一个索引条件推送（index condition pushdown）的优化，将大大改善查询执行方式。

• 使用索引扫描来做排序

  • 有两种方式可以生成有序的结果，通过排序操作；或者按索引顺序扫描。如果EXPLAIN时 type 列看到的值为 index 的信息， 代表 MySQL 使用了索引扫描来排序。
  • 只有当索引列的顺序和 ORDER BY 的顺序完全一致，且所有列的排序方向都一样时，MySQL 才能够使用索引对结果进行排序。
  • 有一种情况。ORDER BY 可以不满足索引列的最左前缀的要求，就是前导列为常量的时候。
  • 假设orders 表种有一列联合索引 KEY user_id_order_id (user_id, order_id)。如下的查询将会有不同的表现：
    • SELECT user_id, order_id FROM orders WHERE user_id = 11 ORDER BY order_id; 将会使用索引排序，因为其最左侧索引列指定了常量。
    • SELECT user_id, order_id FROM orders WHERE user_id = 11 ORDER BY order_id DESC, id ASC;无法使用索引排序，因为 order_id 是降序的，而主键 id 选择了升序，排序方向不一致。
    • SELECT user_id, order_id FROM orders ORDER BY order_id ;无法使用索引排序，因为 ORDER BY 中的列无法组成索引的最左前缀。
    • SELECT user_id, order_id FROM orders WHERE user_id > 11 ORDER BY order_id DESC;无法使用索引排序，因为 索引列的第一列使用了范围查询。

• 冗余索引、重复索引和未使用的索引

  • 冗余索引是指索引内容不同，但是效果相同的索引。比如索引(A)之于索引(A,B)就是一个冗余索引。
  • 一般而言，应当尽量扩展已有的索引而不是创建新的索引。冗余索引、重复索引和未使用的索引都应当删除以节省空间和提高写入效率。
  • 某些COUNT()查询可能需要冗余索引，暂时还没找到 Demo 佐证。
  • 因为二级索引包含了主键值，所以索引(A)等价于索引(A, ID)，索引(A, B)等价于索引(A, B, ID)。

• 索引和锁

  • InnoDB 只有在访问行的时候才会对其加锁，而索引能够减小InnoDB 访问的行数，从而减小锁的数量。但这只对 InnoDB 能够在存储引擎层过滤掉所有不需要的行时才有效。如果索引无法过滤无效行，数据是返回到服务器层后，服务器才能应用WHERE子句，这时已经无法避免锁定行了。
  • InnoDB 在二级索引上使用读锁，在主键索引上需要使用写锁。

4. 案例学习

• 建立索引的一个基本原则是需要做范围查询的列应当尽量放到索引的后面。因为一旦某一列采取了范围查询，则该列其后的索引列都将无法再使用。
• 如果查询条件中，不需要限制索引的最左前缀，但是需要过滤后续的索引。这种情况下的一个技巧是新增一个最左前缀包含其所有可能值的条件。这样既不会过滤任何行，又可以匹配最左索引。假设 people 表中有一索引(sex, age)，我们希望查询16岁的人而使用到这个索引进行优化，则可以这样SELECT * FROM people WHERE sex IN ('m', 'f') AND age = 16。当然如果最左前缀列有很多不同的值，就不适合用这种方法了。另外也不要对太多索引前缀列用使用IN，因为会导致组合以乘积增长。
• 对于条件范围查询，MySQL 将无法再使用其后的索引列，但是对于多个等值条件查询，则没有这个限制。比如，假设有一个索引为(user_id, age)，SELECT * FROM users WHERE user_id > 10 AND user_id < 15 AND age = 16 将只能使用到 user_id 索引，而SELECT * FROM users WHERE user_id IN (11, 12, 13,14) AND age = 16; 将使用(user_id, age)索引。
• MySQL 中 LIMIT + OFFSET对于大表的性能会很差，因为随着偏移量的增加，MySQL 要花费大量的时间来扫描需要丢弃的数据。

5. 维护索引和表

• 损坏的索引可能导致查询返回错误结果或者莫须有的主键冲突等问题。可以使用CHECK TABLE命令来检查表是否损坏；使用REPAIR TABLE命令修复损坏的表；也可以通过一个不做任何操作的 ALTER操作来重建表，比如 InnoDB ：ALTER TABLE test ENGINE=INNODB;。
• MySQL 优化器使用的是基于成本的模型，衡量成本的一个主要的指标就是一个查询需要扫描多少行。如果表没有统计信息或者统计信息不准确，优化器就很有可能做出错误的决定。可以通过ANALYSE TABLE命令重新生成统计信息。