创建高性能索引

索引是什么？有什么作用？

索引是存储引擎用于快速找到记录的一种数据结构

如书的目录索引一般，数据库中的索引也是另外存储一些数据表的关键信息，在查询的时候可以更方便定位到想要找的那一些内容页

在数据量小、负载低的时候，索引的作用可能并不明显。但一旦到达一定量级，正确的索引往往可以轻易将性能提升几个数量级。所以，索引优化是查询性能优化最有效的手段

大多数框架都实现了ORM，而ORM可能很难兼顾到 每个开发者、每个业务 专门定制化的索引。但这并不意味着使用框架和ORM就不需要理解索引！最好的方法是：

简单的、数据量较小的查询可以直接使用ORM，当某些复杂的查询出现性能问题时，考虑舍弃ORM，采用原生的SQL语句去优化性能

索引的类型

索引是在存储引擎层上实现的，而非服务器层。所以每个引擎支持的索引类型、实现方法都有所不同。在使用上需要有所注意。这里主要讨论的是InnoDB引擎的索引

B-Tree 索引

最常见的索引类型，绝大多数MySQL引擎都支持。一般没有特殊说明，索引即B-Tree索引（这类索引采用类似B-Tree的结构来存储数据，如 B树、B+树 等）

InnoDB使用B+ Tree的结构存储索引

B+树

参考链接：理解B+树算法和Innodb索引

为什么通过索引查找数据，可以加快访问的速度？

B-Tree 结构存储索引，通常意味着所有数据按照一定的顺序存储。在查找的时候，引擎就可以从根结点比较节点页的值和要查找的值，找到合适的指针进入下层子节点，不断重复比较最终找到相应值。避免了使用全表扫描

特别的，在B+ Tree结构中，所有的非叶子节点都用作“查找”，叶子节点则指向具体的数据。如：有100条记录，对于一个索引树，有且仅有100个叶子节点，它们分别指向每一条记录，这些记录本身是有序且用指针相连

所以，索引在按照索引顺序去查找范围数据的时候，效率也非常高

索引对多个值进行排序的记录顺序

如，组合索引key(last_name, first_name, birth)，这个索引对应的记录的顺序是，先按照last_name排序，如果相同，则按first_name，最后按birth。

这就是为什么条件的顺序必须与组合索引的顺序一致

order by也可以使用索引

因为索引树中的节点是有序的，所以除了按值查找之外，索引还可以用于查询中的order by操作

可以使用B-Tree 索引的查询类型

假设有一索引，key(last_name, first_name, birth)

• 全值匹配 last_name='ABC' and first_name='DEF' and birth='1999-01-01'
• 匹配最左前缀 last_name='ABC'
• 匹配列前缀 last_name LIKE 'AB%'
• 匹配范围值 last_name >= 'A' and last_name <= 'C'
• 精确匹配某一列，并范围匹配另一列 last_name='ABC' and first_name > 'C'
• 只访问索引(不访问值)的查询 (覆盖索引) select last_name, first_name, birth from xxtbl

B-Tree 索引的查询限制

• 必须从最左列开始匹配，否则该索引不可用
• 不能跳过索引的某一列
• 如果查询中有某个列是范围匹配，则右边的其他列无法使用索引

哈希索引

• 基于哈希表实现，只有精确匹配索引所有列的查询才有效
• 存储引擎针对每一行计算出一个哈希码，与行指针保存成一张表，便于查询
• 常用的InnoDB和MyISAM引擎并不支持，但InnoDB引擎有自适应哈希索引，它会根据查询，动态优化（不需要自己设置索引）

自定义(伪)哈希索引

不支持哈希索引的引擎，可以通过新增一个被索引的hash列，用crc32等算法做哈希，可以优化查询

例子：需要存储并查询一个url列

select * from tbl where url = 'http://xx.com/xx/yy/?zz=aa&bb=cc'

上面的语句明显在比较上非常吃力，如果对url列设置索引，需要比较大的代价。如果引入一个被索引的hash列，在查找的时候，性能会变得很高

select * from tbl where url_crc = CRC32('URL...') and url = 'URL...'

注意：

• 不要直接使用强加密的hash算法，如md5、sha1等，否则生成过长的字符串，效果不好
• 也需要注意避免过多的哈希冲突，如果crc32不满足，可以使用fnv64或自行实现一些哈希方案
• 精确匹配查询的时候，必须在条件中同时带上原列和hash列，如where crc=CRC32('xx') and url='xx'
• 如果不想维护hash列，可以创建触发器，在创建的时候自动填充

全文索引

一种特殊类型的索引，查找的是文本中的关键词，而不是直接比较索引中的值。它更类似于搜索引擎做的事情。另外，在列上同时创建全文索引和B-Tree索引，不会有冲突

索引的优点

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

另外需要注意的是，索引的建立和使用需要一些空间和额外工作。所以，如果表本身很小且可控，全表扫描或许更快

高性能的索引策略（如何在SQL语句中使用索引）

独立的列

如果列本身是表达式的一部分，或是函数的参数，这种“不独立的列”无法使用此列索引。如：select * from tbl where id + 1 < 5

前缀索引

有时需要索引一个较长的字符列，这样会使索引变得大且慢，解决方案可以是之前说的哈希索引，但有时这样仍然不够好。这时候需要考虑使用前缀索引。

对于TEXT、BLOB和较长的VARCHAR，如果确实需要索引，则必须创建前缀索引，设置方法如下：

alter table tbl add key (city(7))

这样就设置了一个针对city字段前7个字符做索引的前缀索引。

前缀索引是一种能使索引更小、更快的有效方法。但缺点是不支持order by, group by和覆盖扫描

难点：如何确定一个较好的前缀值？(上面的例子是7)

-- 首先确定所有记录中，distinct的记录占比
select count(distinct city)/count(*) from tbl;

-- 假设上面得到的结果值为0.3，则表示城市平均重复2次左右
-- 为了前缀索引有良好的区分度，要求使用索引之后，占比较接近实际的0.3
select count(distinct left(city, 3))/count(*) as city3,
       count(distinct left(city, 4))/count(*) as city4,
       count(distinct left(city, 5))/count(*) as city5,
       ...
from tbl;
-- 最后取一个接近0.3，且前缀值不太大的一个值，作为最后的前缀值

多列索引

一个错误的索引设置方案：WHERE条件的列都建立一个单独的索引

示例： create table t (c1 int, c2 int, c3 int, KEY(c1), KEY(c2), KEY(c3));

导致的结果是在多条件查询的时候，无论怎么选择，都只能使用其中一个索引，而之后的条件则没有索引可以走

在新版本的MySQL中，查询会被优化成多条走索引的语句，然后联合或相交得出结果。但这样做相当于多次查询，明显不是最优的索引策略

应该采用的方式是，根据查询，设置组合索引

选择合适的索引列顺序

我们已知查询的顺序会影响到索引列顺序的设置

• 将选择性最高的列放在前面通常是比较好的
• 除了考虑WHERE条件的优化，也需要考虑GROUP BY, ORDER BY, DISTINCT
• 考虑值的分布情况。可以把区分度大的列放在前面，适当去调整语句的编写
• 极端的一些情况。比如某一列中，某个值出现的概率极高，这种可能不太适合建立索引

针对第三个情况的例子：

假设有一张表有customer_id和staff_id，这两列经常作为条件用于筛选。此时可以通过实际情况或SQL进行查询，不同的值更多的列可以考虑放在前面

select
count(distinct staff_id)/count(*) as staff_id_selectivity,
count(distinct customer_id)/count(*) as customer_id_selectivity,
count(*)
from payment;

-- res:
-- staff_id_selectivity: 0.0001, customer_id_selectivity: 0.0373
-- 此时应该选择 KEY(customer_id, staff_id)

聚簇索引

聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。对于InnoDB来说，聚簇索引实际上是同一个结构中保存了B-Tree索引和数据行

一张表只能有一个聚簇索引，因为一份数据只能保存在一个地方。在InnoDB中，不能直接选择某一列成为聚簇索引，而是直接通过主键作为聚簇索引

聚簇索引的优点：

• 可以把相关的数据保存在一起。例如通过用户id获取用户的数据，如果用户id不是聚簇索引，则找到用户id节点之后，还需要一次I/O才能拿到用户的数据
• 相比非聚簇索引，数据访问更快，理由同上
• 使用覆盖索引扫描的查询，可以直接使用页节点中的(其他)主键值

聚簇索引的缺点：

• 聚簇索引可以最大限度提高I/O密集型应用的效率。但如果所有数据都已经加载到内存中，则访问顺序没那么重要，聚簇索引也就没什么优势
• 插入速度严重依赖插入排序，如果不是按照主键顺序加载数据，那么在加载完成后最好使用OPTIMAZE TABLE命令重新组织一下表
• 更新聚簇索引列的代价很高，因为会强制InnoDB将每个被更新的行移动到新的位置
• 基于聚簇索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临“页分裂”的问题。当行的主键值要求必须将这一行插入到某个已满的页中时，存储引擎会将该页分裂成两个页面来容纳该行，这就是一次页分裂操作，页分裂会导致表占用更多的磁盘空间
• 聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续的时候
• 二级索引（非聚簇索引）可能比想象中的要更大，因为在二级索引的叶子节点包含了引用行的主键列
• 二级索引访问需要两次索引查找，而不是一次

对于InnoDB引擎的表来说

• 如果没有什么数据需要聚集，可以设置一个自增列作为主键。保证顺序写入和一些操作的便捷性
• 最好避免随机的（不连续且值的分布范围非常大）聚簇索引，特别是对于I/O密集型的应用。从性能上来说，类似UUID这种随机性很大的内容，作为聚簇索引会非常糟糕

所以通常情况下，保证InnoDB的主键是顺序插入的，减少不必要的调整和页分裂，性能更优

在高并发的时候，顺序的主键可能会造成争用，这种情况下不使用顺序的主键

覆盖索引

如果一个索引包含（覆盖）所有需要查询的字段的值，我们就称之为“覆盖索引”

好处：索引中已经包含了全部数据，不需要回表查询。通常来说，索引没有太多多余的数据，规模小，所以查起来速度很快（MySQL中只有B-Tree 索引可以做覆盖索引）

当发起一个覆盖索引的查询时，在EXPLAIN的Extra列可以看到“Using index”的信息

一则简单明了的例子：

有一张products表，有主键prod_id，以及关联其他表的的两个id：aid、bid，这两个id形成一个key(aid, bid)，然后还有其他的一些产品信息

select aid, bid from products;

上述语句就是最简单的覆盖索引查询，涉及的列只有索引列

复杂一些的例子：

products表中有一个key(actor, title)，但是现在要查出满足条件的所有数据项

select * from products where actor='abc' and title like '%abc%';

上述语句并不能覆盖索引。且title前面也有%，故最终只能使用actor索引数据，然后回表查满足条件的title，再返回整行数据

解决方案：

建立索引key(actor, title, prod_id)

select * from products join (
  select prod_id from products where actor='abc' and title like '%abc%'
) t1 on (t1.prod_id = products.prod_id);

上述语句的子查询满足覆盖索引的查询（一个索引包含所有需要查询的字段的值）。另外，where条件也可以匹配最左前缀actor

如果在上述子查询中，过滤掉了大多数的不符合条件的products，且本身此表的规模有一定大小，则优化效果会很好，否则可能适得其反

示例：

1. abc这个actor的条目有30000条，其中20000条title包含有abc => 这个属于规模大、过滤少的，效果不好
2. abc这个actor的条目有30000条，其中40条title包含有abc => 这个属于规模大、过滤多的，效果很好
3. abc这个actor的条目有50条，其中10条title包含有abc => 这个属于规模小，效果不好（子查询需要耗费一些性能）

另外的：

InnoDB引擎的二级索引的叶子节点是包含主键的值的，所以，主键是可以作为查询列覆盖索引的

使用索引扫描来做排序

MySQL有两种方式可以生成有序的结果：

• 通过排序操作
• 按索引顺序扫描

当按索引顺序扫描排序时，在EXPLAIN的type列会显示index。这里注意区分之前的覆盖索引，覆盖索引是在Extra列显示“Using index”

扫描索引本身速度很快，但是如果不能覆盖查询的所有列，就不得不每扫描一条索引记录就回表查询一次对应的行，这样会造成随机I/O，这种情况是不如顺序地全表扫描的

所以，只有以下条件同时满足，引擎才会按索引顺序扫描：

• 满足最左前缀的要求，即order by的列必须是索引列的最左前缀子列
• order by的列顺序和索引列顺序一致，且所有列的排列方向（正序、倒序）必须一致
• 如果查询需要关联多张表，则只有当order by的列都是第一张表的字段才可以

有一种情况可以不满足最左前缀，就是前导列为常量的时候。即假设有KEY(a,b,c)，WHERE或JOIN子句对a已经指定了定值，则ORDER BY可以只针对b和c字段

MySQL可以使用同一个索引满足排序和查找行的任务，如果可能，尽量设计这样的索引

例子：假设有KEY(rental_date, inventory_id, customer_id)

以下方式可以实现索引扫描：

• 前导列为常量，最左前缀：... where rental_date = '2005-05-25' order by inventory_id desc
• 纯粹的最左前缀（与where无关）：... where rental_date > '2005-05-25' order by rental_date, 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 rental_date = '2005-05-25' order by customer_id
• 前导列为范围值：... where rental_date > '2005-05-25' order by inventory_id, customer_id
• 前导列使用了IN，相当于范围值：... where rental_date = '2005-05-25' and inventory_id in (1, 2) order by customer_id

压缩（前缀压缩）索引

MyISAM使用前缀压缩来减少索引的大小，从而让更多的索引放入内存

特点：

• 默认只压缩字符串
• 方式大致是：对于一个索引块，先保存一个完整的字符串，然后后面如果有前缀相同的字符串，则只存储不相同的值。比如，存储一个“perform”，之后存储“performance”只需要存储“7,ance”即可
• 无法在索引块中使用二分查找，如果倒序扫描——order by xx desc的话，由于需要从头开始扫描，所以会比较慢
• 适合I/O密集型的应用，不适合CPU密集型的应用

重复索引、冗余索引

MySQL允许在相同列创建多个索引，并需要维护重复的索引，在优化器优化查询时，逐个考虑（这种情况是影响性能的。有些没有意义，需要去掉，但有时候是需要的）

重复索引：在相同的列按照相同的顺序创建相同类型的索引。这种是必须去掉的

错误示范：

create table t(
  ID int NOT NULL PRIMARY KEY,
  A  int NOT NULL,
  UNIQUE(ID),
  INDEX(ID)
) ENGINE=InnoDB;

上面三种索引（主键、唯一、普通索引）是同类型的B-Tree 索引，必须去掉（如果索引分别是INDEX和FULLTEXT，它们属于不同类型的索引，也不是重复索引，是完全没问题的）

冗余索引：如果已有KEY(A, B)，这时再创建一个KEY(A)，由于前者的左前缀包含A，所以后者是冗余索引。这种需要按实际情况分析

另外，在InnoDB中，主键默认已经包含在二级索引中，所以 KEY(A)
和 KEY(A, ID) 如果同时存在，也属于冗余索引

大多数情况，冗余索引是不需要的，应该尽量扩展已有的索引而不是建立新的索引。但如果扩展索引会导致索引太大，影响原有的查询，这时就需要考虑冗余索引了

例子：如果在整数列上有一个索引，现在需要额外加一个长的VARCHAR列来扩展索引

假设原来有以下需求，记作Q1。对应有一个索引KEY(state_id)

select count(*) from userinfo where state_id = 5;

现在有另外的新需求，记作Q2。如果引入覆盖索引，对应的索引是KEY(state_id, city, address)

select city, address from userinfo where state_id = 5;

由于MyISAM前缀索引的原因，如果采用直接扩展的方式，性能下降很严重；InnoDB影响不太大。书上例子的测试结果：

有两个索引的缺点就是，索引成本高，增删改记录的效率变低。书上例子的测试结果：

在决定删除“认为无用”的冗余索引时，需要检查是否有采用到主键作为二级索引的查询，如... where A = 1 order by id。如果有，当去掉
KEY(A) ，只保留 KEY(A, B)，会导致此查询不能用索引扫描排序

可以使用一些工具检测重复和冗余的索引

未使用的索引

可能会有服务器永远不用的索引，这种也建议删除。同样可以通过工具检测出