什么是索引

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

索引是存储引擎用于快速找到记录的一种数据结构，为数据库检索提供良好的性能。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。

索引的优点

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

索引的类型

索引的实现多种多样，在这里我们从数据结构的角度进行分类介绍下常见的两种索引类型。

B-Tree索引

书中使用“B-Tree”是因为 MySQL 在一些语句中也使用该关键字。不过底层的存储引擎也可能使用不同的存储结构，比如 InnoDB 使用的是 B+Tree。

实现原理

B-Tree 通常意味着所有的值都是按照顺序存储的，并且每一个叶子页到根的距离相同。下图为 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) );

主要支持的查询方式

• 全值匹配
• 匹配最左前缀
• 匹配列前缀
• 匹配范围值
• 精确匹配某一列并范围匹配另外一列
• 只访问索引的查询

B-Tree 的限制

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

哈希索引

实现原理

对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码 (hash code)， 哈希码是一个较小的值，并且不同键值的行计算出来的哈希码不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

哈希索引的限制

• 不能避免读取行，因为索引只包含哈希值和行指针
• 不是按照索引值顺序存储
• 不支持部分索引列匹配查找
• 只支持等值查询
• 需要注意哈希冲突

用例

• Memory 引擎、NDB 引擎支持唯一哈希索引
• InnoDB 可以创建自定义哈希索引
  • 使用 CRC32 实现自定义哈希索引
  • 自定义哈希函数实现哈希索引

高性能的索引策略

索引评星

一星索引：如果与查询相关的索引行是相邻的或者至少相距足够靠近的话，这个索引就可以标记为一星索引。（即where条件能够最大限度的使用索引）
二星索引：在一星的基础上，索引行的顺序和查询语句的需求一致，则为二星索引。
三星索引：如果索引包含了查询语句中的所有列，仅访问索引就能够返回，则为三星索引。

前缀索引

当一个字符列的的字符数据很长时，索引会变得又大又慢，通常遇到这种场景，我们需要考虑使用前缀索引来降低索引空间从而提升索引效率。索引选择性（通常我们称之为索引区分度）是指不重复的索引值和数据表中的记录总数的比值，选择性越高则索引效率越好，最大值为1。

书中示例：比如我们要对一个城市名称进行索引，但是索引字段很长，于是我们开始考虑适应前缀索引方案，那么如何确定前置长度呢？

完成字段的选择性是0.0312

当前缀索引长度到7时，索引的区分度已经很接近完整字段的区分度了，再增加长度的收益非常小，因此7是比较合适的前缀索引长度。

• 前缀索引的缺点：无法做ORDER BY和GROUP BY，也无法进行覆盖扫描。

多列索引

MySQL5.0之前查询只能使用单一索引进行查询，之后的版本引入了一种索引合并（index merge）策略，这种策略可以使用多个索引扫描数据，取得结果后进行合并。

select * from t1 where c1=1 or c2=1     #c1和c2均为独立索引列

在index merge的策略下，可以分别使用c1的索引和c2的索引查询出数据再进行合并。我们可以通过执行计划查看是否使用了索引合并策略。

索引合并缺点：优化器只关心随机页面读取，不会计算数据的缓存、排序和合并的时间成本，由于以上因素的存在，索引合并策略的触发很有可能还不如走全表扫描，因此一旦发现有index merge出现，我们应该考虑如何使用联合索引优化查询场景而不是依赖index merge。

聚簇索引

“聚簇”表示数据行和相邻的键值紧凑地存储在一起，聚簇索引不是一种索引的数据结构而是一种数据的存储方式。因为无法同时把数据行存放在两个不同的地方，所以一个表通常只能有一个聚簇索引。有些数据库服务器允许你选择用于聚簇的索引，但是MySQL内置的存储引擎都不支持这个特性。
InnoDB聚簇索引的创建方式：

• 默认使用主键聚簇数据
• 如果没有创建主键，则会选择一个唯一非空索引替代
• 如果没有唯一非空索引，则会使用隐式定义一个主键作为聚簇索引

聚簇索引的优点：
1. 把相关数据保存在一起。例如实现电子邮箱时，可以根据用户id来聚集数据，这样只需要从磁盘中读取少量的数据页就能获取某个用户的全部邮件。如果没有使用聚簇索引，则每封邮件都可能导致一次磁盘I/O。
2. 根据主键查询时，减少了回表查询的I/O操作
3. 可以使用覆盖索引策略直接命中主键索引
聚簇索引的缺点：
1. 聚簇数据最大限度地提高了io密集型应用的性能，如果数据全部放在内存，则访问的顺序没那么重要
2. 插入速度依赖于插入顺序
3. 更新聚簇索引列的成本很高
4. 全表扫描可能会变得很慢
5. 二级索引可能比想象的要更大，因为二级索引的叶子节点包含了引用行的主键列
6. 二级索引存储的是主键值而不是行指针导致回表需要走索引扫描

覆盖索引

如果一个索引包含所有需要查询的字段的值，我们就称之为覆盖索引，需要注意的是只有B-tree索引可以用于覆盖索引。
索引覆盖的优点：

• 索引条目大小远小于数据行大小，使用索引覆盖能够极大的减少数据访问量
• 索引是有序存储的，在范围查找的场景中能够减少IO次数
  通过执行计划能够确认执行的SQL是否使用了覆盖索引，当使用EXPLAIN时，当Extra列的值为Using index时，代表使用了覆盖索引。
  

索引排序

• 当索引的顺序和ORDER BY子句的顺序完全一致，并且所有列的排序方向（倒序或正序）都一样时，MySQL才能使用索引来对结果做排序。
• 如何判断MySQL是否使用索引进行排序？当使用执行计划EXPLAN时type列的结果是index，则说明MySQL使用了索引对结果进行排序。

使用索引排序也存在一些条件：

• 索引顺序和order by子句的顺序完全一致或者最左前缀匹配，比如索引是（a,b,c）那么排序子句应该是order by a,b,c

例如 test_order 存在索引（a,b）如果以b,a进行排序则无法使用索引排序

EXPLAIN select * from test_order order by b,a DESC limit 10,10

• 如果查询需要联结多张表那么order by子句引用的字段必须全部在第一个表中才能使用索引排序
• 有一种特殊情况是如果最左前缀是字段在where中使用了等值查询（视为常量），则可以使用后面的字段进行排序
  例如：

select * from test_order where a='1' order by b desc

索引维护

冗余和重复索引

MySQL允许在相同列上创建多个索引，当你创建时只会抛出一个警告，并不会阻止创建。MySQL需要单独维护重复的索引，优化器在优化查询的时候需要逐个考虑，会影响性能。
重复索引：如若发现，尽快删除。
冗余索引：冗余索引一般存在于扩展索引的场景。
例如已经存在（a）列的索引，为了业务扩展增加了一个（a,b）的索引，此时（a）索引就变得冗余了，遇到冗余索引不要立即删除，需要重复review业务场景，特别是排序场景，确认没有被用到再进行删除。

未使用的索引

现实情况中有一部分索引因为错误的创建可能永远不会被数据库所使用，这样的索引不但没有提升查询效率还影响到了数据库写入数据时的创建效率和优化器进行索引分析时的性能，如果存在这样的索引建议直接删除。可以通过以下的方式进行未使用索引的检查：

select * from sys.schema_unused_indexes

索引和锁

InnoDB 只有在访问行的时候才会加行锁，而索引能帮助我们选中更少的行，进而减少行锁的数量。但是需要注意，只有 InnoDB 存储引擎过滤掉不需要的行时才能减少行锁。如果索引行过滤后的数据需要到服务器层再次过滤的话，此时 InnoDB 还是会锁住服务器层过滤前的所有的行。

思考下面的例子：

InnoDB 会选择索引列 actor_id，筛选出五条数据对应的 actor_id 为 1 ～4 行。而 MySQL 服务器层会再次过滤数据1， 返回最终结果 2～4 行，但是注意行锁仍会锁定 1～4 行。

开启第二个事务，会发现第一行更新语句被锁住无法执行。

使用 “EXPLAIN” 工具来查看执行计划，其中以下结果列和索引选择相关。

type

性能 ALL < index < range < ref < eq_ref < const

prossible_keys

满足条件的索引列表

keys

MySQL 真正选择的索引。部分特殊场景（如覆盖索引）会导致该索引可能会没有出现在 possible_keys 中。

key_len

索引的长度。联合索引因为最左匹配原则，可能只有部分索引参与计算，此时 key 的长度为参与计算部分的表定义字段总和。

Extra

比较重要的常见值列表：