高性能索引

作者

一、索引基础

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

  • 索引在大数据量时对性能的影响很重要
  • 索引优化是查询优化最有效的手段

1、索引的类型

MySQL 中的索引是存储在引擎层，不同引擎的索引工作方式不同。

B-Tree 索引

  • B-Tree 是比较常用的引擎，InnoDB 使用的是 B+Tree
  • B-Tree 索引能够加快访问数据的速度，从索引的根节点扫描，不需要全表扫描
  • B-Tree 对索引列是顺序组织存储的，所以很适合查找范围数据
  • B-Tree 索引适用于全键值‘键值范围或者键前缀查找

有效范围：

  1. 全值匹配
  2. 匹配最左前缀
  3. 匹配列前缀
  4. 匹配范围值
  5. 精确匹配某一列并范围匹配另外一列
  6. 只访问索引的查询

限制：

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

Hash索引

  • 基于 hash 表实现，只有精确匹配索引的所有列的查询才有效
  • 对于每一行数据，存储引擎都会根据键值计算出一个 hashCode，存到 hash 索引中，同时保存指向每行数据的指针
  • 只有 Memory 引擎显示支持 非唯一hash 索引。出现 hash 冲突的时候，会用链表存放多个记录指针到同一个 slot

限制：

  1. 只包含 hashcode 和指针，不存储字段值，所以不能用索引中的值来避免读取行。
  2. hash 索引数据不是按照索引值顺序，而是按照槽 slot 顺序来排序的，所以不支持排序。
  3. 不支持对部分索引列进行匹配查找，因为 hashcode 是根据索引列全部内容计算的。
  4. 只支持等值比较查询，=、IN()、<=>
  5. 访问 hash 索引速度非常快，但是出现 hash 冲突时，存储引擎必须遍历链表中所有指针
  6. 如果 hash 冲突很多，索引维护的代价会很高

在 InnoDB 中使用 hash 索引

InnoDB 自适应 hash 索引：当某些索引值被用的很频繁时，他会在内存中基于 B-Tree 索引之上再创建一个 hash 索引。

创建自定义hash索引：

在 B-Tree 上创建一个伪 hash 索引，查找的时候 B-Tree 使用 hashcode 进行索引查找，在 where 中指定使用 hash 函数。

1、

select id from url where url="www.baidu.com" and url_crc=CRC32("www.baidu.com")

Mysql优化器会使用这个选择性很高而性能很好的 url_crc 列的索引来查找。

2、需要手动维护 hashcode：

CREATE TRIGGER pseudohash_crc_ins BEFORE INSERT ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc=crc32(NEW.url);

CREATE TRIGGER pseudohash_crc_upd BEFORE UPDATE ON pseudohash FOR EACH ROW BEGIN SET NEW.url_crc=crc32(NEW.url);

这样在每次insert 和 update 时都会利用crc32()自动生成 hashcode

3、当有大量 hash 冲突的时候，可以自己实现一个64位 hash 函数

同时需要在查询的时候where包含常量值。

select id from url where url_crc=CRC32("www.baidu.com") AND url="www.baidu.com"

空间数据索引（R-Tree)

用作存储地理数据

全文索引

查找的是文本中的关键词，而不是直接比较索引中的值。

二、索引的优点

  1. 大大减少了服务器需要扫描的数据量，可以快速定位到表的指定位置
  2. 可以帮助服务器避免排序和临时表
  3. 可以将随机 IO 变为顺序 IO

限制：

  1. 只有对于中到大型的表，索引才非常有效。小型表全表扫描更快。
  2. 表太多时可以建立一个元数据表，用来查询需要用到的特性

三、高性能的索引策略

1、独立的列

  • 索引列不能是表达式的一部分，也不能是函数的参数，否则索引失效

2、前缀索引和索引选择性

对于很长字符串的索引列，我们可以：

1、采用模拟 hash 索引

2、可以索引开始的部分字符，选择列的一个足够长的前缀

选择性：不重复的索引值和数据表记录总数的比值。

选择性低指的是，根据索引找到的记录需要过滤很多行。

如何选择合适长度的列前缀？

  1. 通过 select count找出每个记录的count
  2. 通过select count,left(column,n)来多次尝试，直到每行记录的 count 接近完整列。
    • 每次截取N 位前缀，进行 count
  3. 也可以通过计算完整列的选择性来判断
//count(DISTINCT city)不重复的索引值
//count(*)            记录总数
select count(DISTINCT city)/count(*) from tb

//选取不重复的前 N 位的前缀的 count，和记录总数对比
select count(DISTINCT LEFT(column,n))/count(*) AS selN

这个方法有个缺点：

当数据分布不均匀时，即使选择性比较大，实际可能select count,left(column,n)的重复会比较多，因为他用了 DISTINCT

缺点：MySQL 无法使用前缀索引做 OrderBy 和 GroupBy，也无法使用前缀索引做覆盖扫描。

3、多列索引

  • 在多个列上建立单独的索引，或者多列索引顺序错误并不能提高查询性能。
  • 如果不能创建一个三星索引，不如忽略 where， 集中精力优化索引列的顺序，或者创建一个全覆盖索引。

MySQL5.0引入了索引合并策略（index merge）：

一定程度上可以使用多个单列索引来定位数据。

mysql> select film_id,actor_id from movie 
    —> where actor_id=1 or film_id=1

从Explain命令结果可以看出，该语句执行使用了合并索引。能够同时使用这俩单列索引进行扫描，并将结果合并。

索引合并的缺点：

  • 当有多个 AND 条件时，意味着需要一个多列索引
  • 当有多个 OR 条件时，需要耗费大量 CPU和内存资源在算法的排序缓存合并上，特别是选择性不高需要筛选的时候
  • 优化器不会将这些计算到 cost 查询成本中，导致这种操作不如走全表扫描，而且还会影响查询的并发性。不如改写成UNION。

4、选择合适的索引列顺序

B-Tree 索引列的顺序是从左至右依次排序。所以索引可以按照升序降序进行扫描，以满足 ORDER BY、GROUP BY和 DISTINCT 需求。

如何选择合适的顺序？

  • 经验法则：将选择性最高的列放到索引的最前列。这时候索引的作用只是优化 where 的查找。
  • 性能不只是依赖于索引的选择性，对待具体数据集要进行具体分析，可以根据高频的查询来调整索引列顺序。
  • 当使用前缀索引，某些条件值基数高于正常值时，需要考虑对数据集进行分组查询、范围查询。

5、聚簇索引

1）什么是聚簇索引

  • 聚簇索引是一种数据存储方式。
  • 聚簇索引是指键值和数据 data 存储在一起

2）聚簇索引的优势

  • 可以把相关数据保存在一起，减少磁盘 IO 次数
  • 从聚簇索引中访问数据比非聚簇索引快，因为存储在同一个 B+Tree 中
  • 使用覆盖索引扫描的查询，可以直接使用页节点中的主键值

3）聚簇索引的缺点

  • 当数据放在内存中时，聚簇索引没有优势
  • 插入速度严重依赖于插入顺序
  • 更新聚簇索引列的代价很高
  • 当插入、主键更新等移动行的时候，可能会导致“页分裂”问题，导致占用更多磁盘空间
  • 会导致全表扫描变慢，特别是数据稀疏，页分裂导致数据不连续的时候
  • 二级索引会很大，因为包含了主键列
  • 二级索引访问需要两次索引查找

二级索引：又叫非聚簇索引，辅助索引。指B+Tree 上存放的 data 不是数据行，而是主键值。仅当主键发生改变时，才会更新二级索引

4）InnoDB 的数据分布

  • 在 InnoDB 中，聚簇索引“就是”表
  • 聚簇索引的每一个叶子节点都包含了完整的数据
  • InnoDB 中，二级索引存储的是主键值，减少了行移动和页分裂时二级索引的维护

5）在 InnoDB 中按主键顺序插入行

  • 应该避免使用随机的，分布范围大的聚簇索引，不然会因为页分裂和碎片导致占用的时间和空间都很大
    • 因为如果主键值是顺序的，当达到页的最大填充因子（15/16）时，下一条记录就会写进新的页中。
    • 如果主键是随机的，那么每次插入都要寻找合适的位置并分配空间，导致大量随机 IO
    • 因为写入是乱序的，所以页分裂操作很频繁，导致移动大量数据，最终会有数据碎片
  • 所以使用 InnoDB 应该尽可能的按照主键顺序插入数据，使用单调增的聚簇键

6、覆盖索引

1）什么是覆盖索引

如果一个索引包含了所有要查询的字段的值，就是覆盖索引

2）覆盖索引的优点

  • 覆盖索引只需要扫描索引而无需回表查询，极大的减少数据访问量和 IO，提高性能
  • 如果 InnoDB 的二级索引可以覆盖查询，就可以避免对主键索引的二次查询

3）覆盖索引的陷阱和使用技巧

  • 只有 B-Tree 索引才能做覆盖索引，因为必须存储列索引的值

  • 使用延迟关联来使用覆盖索引：先使用索引的列进行筛选，然后再关联查询

  • 使用覆盖索引优化的效果取决于 where 条件返回的行数，也就是数据集不同，效果不同
  • InnoDB 可以使用主键列来覆盖查询

7、使用索引扫描来做排序

MySQL 排序的方式：通过排序操作，或者按索引顺序扫描。

EXPLAIN TYPE='index'说明使用了索引扫描来做排序。

索引排序的条件：

  • 只有索引的列顺序和 ORDER BY的顺序完全一致，并且所有列要么都倒序要么都正序
  • 关联多表时，只有当 ORDER BY 引用的字段都是第一张表时，才能使用索引排序
  • 需要满足最左前缀要求
  • 当前一列指定了常量值时，可以不满足最左前缀
where a ='1' order by b

8、压缩（前缀压缩）索引

  • MyISAM 通过前缀压缩来减少索引的大小，让更多的索引放入内存中。
  • 默认只压缩字符串
  • 先保存索引块中第一个值，然后其他值和第一个进行比较，得到相同前缀的字节数和剩余的后缀
    • 1.perform 2.performance-->7.ance

缺点：

  • 无法使用二分法查找，只能从头扫描
  • 倒序扫描的速度很差，因为在块中查找某一行的操作，平均都要扫描半个索引块
  • 对于 CPU 密集型应用，扫描需要随机查找，所以比索引查找慢好几倍
  • 对于 IO 密集型应用，对某些查询会带来好处

9、冗余和重复索引

重复索引：在相同的列上按照相同的顺序创建的相同类型的索引。

冗余索引：和已有索引不重复，但是功能已经包含的索引。

  • 大多数情况不需要冗余索引，应该尽量扩展已有索引而不是创建新索引
  • 在扩展索引变得过大时，可以考虑冗余索引
  • 表中的索引越多，增删改速度会越慢

10、索引和锁

InnoDB 只有在访问行的时候才会对其加锁，而索引能够减少 InnoDB 访问的行数，从而减少锁的数量。

当 InnoDB 检索到数据并返回给服务层以后，这时候才能应用 where，然后锁定行。

所以就算用了索引，也可能会锁住一些不需要的数据。

InnoDB 在二级索引上使用读锁，但是访问主键索引需要写锁，这就不能使用覆盖索引了。

四、索引案例学习

1、支持多种过滤条件

  • 考虑表上所有的选项，将高频但是选择性低的列加入索引，通过IN()绕过
  • 通过 IN()的技巧避免冗余索引
  • 忽略选择性高，使用频率低的列
  • 将范围查询放到最后，尽可能使用更多的索引

2、避免多个范围条件

MySQL 的EXPLAIN 无法区分范围查询和多等值查询：

对于where actor_id>54 和 where actor_id in (1,2,45)，EXPLAIN 的结果都是 Range。

但是后者对后面的列使用索引没有限制。

为什么要避免多个范围条件？

因为即使在多个条件上都有索引，在查询的时候也只能使用一个，其他的都不会起作用。

可以将一些范围查询转换为等值比较。

3、优化排序

  • 对于翻页到很后面的查询，MySQL 需要随着偏移量的增加，花大量时间来扫描需要丢弃的数据
  • 可以用反范式化、预先计算和缓存来解决，或者限制用户翻页
  • 可以用延迟关联，先使用覆盖索引查询返回的主键，再根据主键关联原表查询行。

五、维护索引和表

1、找到并修复

2、更新索引统计信息

3、减少索引和数据的碎片