创建高性能索引- 读书笔记

MySQL

前言

索引是存储引擎用于快速找到记录的一种数据结构; 索引能够轻易的将查询性能提高几个数量级，尤其是数据量逐渐变大时.

索引基础

索引可以包含一列或多个列的值，如果包含多个列，那么顺序也很重要，MySQL只能高效的使用索引最左前缀列。创建一个包含两个列的索引，和创建两个只包含一列的索引是大不相同的。
MySQL中索引是在存储引擎层，而不是在服务器层。不同的存储引擎的索引工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。

索引的类型

1、B-Tree索引

• 索引如果没有特别指明类型，多半是B-TREE索引，它使用B-TREE数据结构来存储数据.
• 我们使用术语"B-Tree“，是因为MySQL在create table和其他语句也适用该关键字。
• B-Tree通常意味着所有的值都是按顺序存储，并且每个叶子页到根的距离相同。
• B-Tree索引能够加快访问数据的速度，是因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点进行搜索。
• B-Tree对索引列是按照顺序组织存储的，所以很适合查找范围数据。
• 索引对多个值进行排序的依据是创建表语句中定义索引时列的顺序。
• B-Tree索引适用于全健值，键值范围或键前缀查找。

索引对如下类型的查询有效

• 全值匹配: 和索引中的所有列都进行匹配，比如查找姓名为AB，出生日期为C的人
• 匹配最左前缀： 只使用索引的第一列,比如查找姓为allen的人
• 匹配列前缀: 只匹配某一列的开头部分，比如查找以J开头的姓的人。
• 匹配范围值: 比如查询姓在A到C之间的人
• 精确匹配某一列并范围匹配另外一列: 比如查询所有姓为A，名字是K开头的人。
• 只访问索引的查询: 查询只需要访问索引，无需访问数据行

因为索引树中的节点是有顺序的，所以除了按值查找，还可以用于查询中的order by操作。如果B-Tree可以按照某种方式查找到值，那就可以按照这种方式进行排序。

B-Tree索引限制

• 如果不是按照索引的最左列开始查找，则无法使用索引。比如无法查找姓氏以某个字母结尾的人....
• 不能跳过索引中的列，比如有A,B,C三列索引，不能只查找A,C而跳过B;
• 如果查询中有某个列的范围查询，则右边所有的列都无法使用索引优化查找;

2、哈希索引

• 哈希索引基于哈希表实现，只有精确的匹配索引所有列才有效。对于每行数据，存储引擎会对所有的索引列计算一个哈希码，哈希码是个较小的值，不同的健值的行计算的哈希码也不一样。哈希索引把所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
• 在MySQL中, 只有Memory引擎显式支持哈希索引, 并且支持非唯一的哈希索引。
• 哈希索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，使得哈希索引查找的速度非常快。

哈希索引的限制

• 哈希索引只包含哈希行和指针，不存储字段值，所以不能使用索引中的值来避免读取行。
• 哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序
• 哈希索引不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如在(A,B)列建立索引，如果只查数据列A，则无法使用该索引。
• 哈希索引只支持等值比较查询，例如=,in(), <=>, 不支持任何范围查询例如where price > 100.
• 访问哈希索引的速度非常快，除非有很多哈西冲突(不同的索引列值却有相同的哈希值). 当有哈希冲突时，存储引擎必须遍历链表中所有的行指针，直到找到符合条件的行。
• 如果哈希冲突很多，一些索引的维护操作代价会很高。

InnoDB引擎有个特殊功能叫做 自适应哈希索引。当InnoDB注意到某些索引值被使用得非常频繁时，会在内存中基于B-Tree索引之上在创建一个哈西索引，这样就让B-Tree索引具有哈希索引的一些优点。
伪哈希索引 它和真正的哈希索引不是一回事，它需要在查询时手动指定使用的哈希函数，而且需要维护哈希值,可以手动维护也可以使用触发器实现;

• 如果数据表非常大，CRC32()会出现大量的哈希冲突，则可以考虑自己实现一个简单的64位哈希函数；
• 要避免冲突问题，必须在where条件中带入哈希值和对应的列值。

3、空间数据索引(R-Tree)

• MyISAM表支持空间索引，用来存储地理数据存储。空间索引会从所有纬度来索引数据；查询时，可以有效的使用任意纬度来组合查询。

4、全文索引

• 全文索引是一种特殊类型的索引，他查找的是文本中的关键词，而不是直接比较索引中的值。
• 全文搜索和其他几类索引的匹配方式完全不一样。他有许多要注意的细节，如停用词，词干和附属，布尔搜索等。
• 全文索引更类似于搜索引擎做的事情，而不是简单的where条件匹配。

5、其他索引类别

• 分形树索引 ，InnoDB引擎包括聚簇索引，覆盖索引等。

索引的优点

索引可以让服务器快速定位到表的指定位置，但这不是索引的唯一作用，根据创建索引的数据结构不同，索引也有一些其他的附加作用。

索引三大优点

• 索引大大减少了服务器需要扫描的数据量
• 索引可以帮助索引避免排序和临时表(比如B-Tree索引，按照顺序存储数据)
• 索引可以将随机I/O变为顺序I/O

三星系统

• 索引将相关记录放到一起获得 一星；索引中的数据顺序和查找中的排列顺序一致则获得 二星; 索引中的列包含了查询中需要的全部列则获得 三星;

索引探讨

• 索引并不总是最好的工具，总的来说，只有当索引帮助存储引擎快速的查找到记录带来的好处大于其带来的额外工作时，索引才是有效的。对于非常小的表，大部分情况下简单的全表扫描会更有效。对于大到中型的表，索引就非常有效。但对于特大型的表，建立和使用索引的代价将随着增长，这就需要特殊技术处理。
• 如果表的数量特别多，可以建立一个元数据信息表，用来查询需要用到的某些特性。

高性能的索引策略

1、独立的列

独立的列 是指索引列不能是表达式的一部分，也不能是函数的参数。如果查询中的列不是独立的，那么MySQL就不会使用索引。

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

• 索引选择性 是指不重复的索引值和数据表的记录总数的比值，范围是 1/T 到~ 1之间
• 索引的选择性越高查询效率越高，因为选择性高可以让MySQL在查找时过滤掉更多的行，比如唯一索引的选择性是1，性能最好。
• 一般情况列的前缀选择性也是足够高的，BLOB,TEXT,很长的VARCHAR 必须使用前缀索引，MySQL不允许索引这些列的完整长度。
• 选择足够长的前缀保证较高的选择性，同时又不能太长以便节约空间。前缀应该足够长，以使得前缀索引的选择性接近与索引整个列。
• 计算合适的前缀长度的一个办法就是计算完整列的选择性，并使前缀的选择性接近于完整列的选择性。
• 前缀索引是一种能是索引更小更快的有效方法，但是MySQL无法使用前缀索引做order by和group by，也无法使用其做覆盖扫描。
  创建前缀索引的方法： alter table city add key (city(7))

3、多列索引

• 在多个列上创建独立的单列索引大部分情况下并不能提高MySQL的查询性能。
• 在MySQL 5.0以后的版本中，查询能同时使用单列索引进行扫描，并将结果合并。算法有三个：比如or,and,组合前两种情况的联合及相交。

索引合并策略

• 当服务器对多个索引做相交操作时，通常意味着需要一个包含所有列的多列索引，而不是多个独立的单列索引。
• 当服务器需要对多个索引做联合操作时，需要耗费大量的CPU和内存资源在算法的缓存，排序和并发操作上。
• 优化器不会吧这些计算到查询成本中，优化器只关心随机页面读取。

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

• 当不需要考虑排序和分组时，把选择性最高的列放倒索引最前列通常是可以的，这时候索引的作用只是用于优化where条件的查找。这种情况下，这种设计的索引确实能够最快的过滤出需要的行。
• 性能不只是依赖于索引列的选择性，也和查询条件的具体值有关，也就是和值的分布有关，可能需要根据运行频率最高的查询来调整索引列的顺序。
• 经验法则考虑的是全局基数和选择性，而不是某个具体的查询。
• select count(distinct a)/count(a) as a_selectivity, count(distinct b) /count(b) as b_selectivity from table 计算选择性更平均和公平一点，选择性高的索引作为索引列的第一列。
• 经验法则和推论在多数情况下是有用的，但是不能假设平均情况下的性能也能代表特殊情况下的性能。

5、聚簇索引

• 聚簇索引不是一种单纯的索引类型，而是一种数据存储方式。当表中有聚簇索引时，它的数据行实际上存放在索引的叶子页中。
• 聚簇 表示数据航和相邻的键值紧凑的存储在一起。因为无法把数据行同时存储在两个不同的地方，索引一个表只能有一个聚簇索引(覆盖索引可以模拟多个聚簇索引的情况)
• 存储引擎 负责实现索引，因此不是所有的存储引擎都支持聚簇索引(InnoDB支持)，InnoDB将通过主键聚集数据，被索引的列是主键列；如果没有定义主键，InnoDB会选择一个唯一的非空索引代替。
• 聚簇主键可能对性能有帮助，但也可能导致严重的性能问题。

聚集的数据优点

• 可以把相关的数据保存在一起。比如电子邮箱，可以根据用户id来聚集数据，只需读取少数的数据页就能获取某个用户的全部邮件。
• 数据访问更快。聚簇索引将索引和数据保存在同一个B-Tree中，因此从聚簇索引中获取数据比在非聚簇索引中要快.
• 使用覆盖索引扫描的查询可以直接使用页节点中的主键值。

聚簇索引的缺点

• 聚簇数据最大限度的提高了I/O密集型应用的性能，但是如果数据全部放在内存，访问的顺序就没有那么重要，聚簇索引优势无法显现了。
• 插入速度严重依赖于插入顺序。按主键顺序插入InnoDB表中速度最快，如果不是按主键顺序，那么最好用OPTIMIZE TABLE命令重新组织一下表.
• 更新聚簇索引的代价很高。因为InnoDB强制将每个被更新的行移动到新的位置。
• 基于聚簇索引的表再插入新行，或者主键被更新导致需要移动行的时候，可能面临页分裂的问题。页分裂会导致表占用更多的磁盘空间.
• 聚簇索引可能会导致全表扫描变慢，尤其是比较稀疏，或由于 页分裂导致数据存储不连续。
• 二级索引(非聚簇索引)可能比想象的要更大，因为在二级索引的叶子节点包含了行的主键列。
• 二级索引访问需要两次索引查找，而非一次。二级索引叶子节点保存的不是行指针，而是行的主键值。

InnoDB和MyISAM的数据分布对比

• MyISAM按照数据插入的顺序存储在磁盘上。这种分布方式很容易创建索引。
• MyISAM主键索引和其他索引在结构上没有什么不同。主键索引就是一个名为primary的唯一非空索引。
• InnoDB的数据分布，在InnoDB总，聚簇索引就是表，不需要独立的行存储。
• 聚簇索引 的每一个叶子节点都包含了主键值，事物ID，回滚指针和所有剩余列。如果主键是一个列前缀索引，InnoDB也会包含完整的主键列和剩下的其他列。
• InnoDB的二级索引和聚簇索引很不相同，二级索引的叶子节点存储的是主键值，而非行指针，这样的策略减少了行移动或页分裂时二级索引的维护工作。
• InnoDB非叶子节点包含了索引列和一个指向下级节点的指针。

InnoDB中按照主键的顺序插入行

• 如果是在使用InnoDB表并且没有什么数据需要聚集，那么可以一个和应用无关的主键，最简单的方法是使用AUTO_INCREMENT自增列，保证数据行按顺序写入。
• 最好避免随机的聚簇索引，特别是对I/O密集型的应用。从性能的角度考虑，使用UUID作为聚簇索引会有很大问题，他会是索引插入完全随机，没有任何聚集特性。
• UUID主键索引插入不仅时间长，索引占用空间也大。一方面是字段长，另一方面是因为页分裂和碎片导致的。

UUID作为主键索引的问题

• 写入的目标页不确定，InnoDB再插入之前不得不先并从磁盘找到读取到内存中，导致大量的随机I/O;
• 写入是乱序的，InnoDB不得不频繁做页分裂操作，导致移动大量的数据，一次插入最少要修改三个页。
• 频繁的页分裂，页会变得稀疏并被不规则的填充，最终数据碎片话严重。

顺序的主键什么时候会造成更坏的结果?

• 对于高并发工作负载，在InnoDB中按主见顺序插入可能会造成明显的争用，并发插入会导致间隙锁竞争。
• 对于AUTO_INCREMENT

6、覆盖索引

索引确实是一种查找数据的高效方式，但是MySQL也可以使用索引来直接获取列的数据，这样就不需要读取数据行.如果一个索引包含所有要查询的字段的值，我们就称之为 覆盖索引.

覆盖索引是非常有用的工具，能极大的提高性能：

• 索引条目通常远小于数据行大小，索引如果是需要读取索引，那么就会极大的减少数据访问量。这对缓存负载非常重要，因为这种情况响应时间大部分在数据拷贝上。覆盖索引对 I/O 密集型应用也有帮助，因为索引比数据更小，更容易放入内存.
• 因为索引是按照值顺序存储，索引对于I/O密集型的范围查询会比随机从磁盘读取每一行的I/O要少的多。
• 一些存储引擎入MyISAM在内存中只缓存索引，数据则依赖于操作系统来缓存，因此要访问数据需要一次系统调用。
• 由于InnoDB的聚簇索引，覆盖索引对InnoDB表特别有用。InnoDB的二级索引在叶子节点中保存了行的主键值，如果二级主键能覆盖查询，则可以避免对主键索引的二次查询。

• 覆盖索引必须要存储索引列的值，而哈希索引，空间索引，全文索引不存储列的值，所以MySQL只能使用B-Tree索引做覆盖索引.
• 在大多数的存储引擎中，覆盖索引只能覆盖哪些只访问索引中部分列的查询。

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

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

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

• 如果explain的值的type列的值为index,说明使用了索引扫描排序
• 按照索引顺序读取数据的速度通常比顺序的全表扫描慢，尤其是在I/O密集型的工作负载中，因为它基本上是随机I/O
• MySQL可以使用同一个索引，即满足排序，又用于查找行。
• 只有当索引的顺序和order by子句的顺序完全一致，并且所有列的排序方向都一样，MySQL才能使用索引对结果排序。
• 如果查询需要关联多张表，只有order by 子句饮用的字段全部是第一个表，才能用索引做排序。
• order by子句和查找型查询的限制是一样的，需要满足索引最左前缀的要求；否则，MySQL都需要执行排序操作，而无法使用索引排序，
  除非前导列是常量。

8、压缩(前缀压缩)索引

• MyISAM使用前缀压缩来减少索引的大小，从而让更多的索引可以放入内存中，这在某些情况下能提高性能。
• 默认只压缩字符串，通过参数设置也可以对整数做压缩。
• MyISAM压缩索引块方式: 先完全保存索引块的第一个值，然后将其他值和第一个值比较得到相同前缀的字节数和剩余的不同后缀部分，把这部分存储起来即可。[比如索引块第一个值是perform, 第二个值是performance,那么第二个值前缀压缩后存储类似7,ance这种形式]
• 压缩块节省空间，代价是某些操作可能更慢。每个值的压缩前缀都依赖前面的值，所以MyISAM查找时无法在索引块使用二分查找而只能从头开始扫描，正序还好，倒序就会比较慢了。
• I/O密集型的应用，压缩索引的需要的磁盘空间小，查询带来的好处会比成本多，如果是CPU密集型，扫描需要随机查找，压缩索引使得MyISAM在索引查找上要慢好几倍。

9、冗余和重复索引

MySQL允许在相同的列上创建多个索引，需要单独维护重复的索引，优化器在优化查询时也要逐个考虑，会影响性能。

重复索引 是指在相同的列上按照相同的顺序创建的相同类型的索引。
冗余索引 如果创建了索引(A,B)，在创建索引(A)就是冗余索引，因为这只是前一个索引的前缀索引；其他不同类型的索引不会是B-Tree索引的冗余索引。
冗余索引 一般发生在为表添加新索引的时候，还有就是扩展索引(A,ID)，ID是主键，对于InnoDB来说主键列已经包含在二级索引中了。

大多数情况都不需要冗余索引，应该尽量扩展已有的索引而非创建索引，有时候扩展已有的索引会导致其变得太大，从而影响其他使用该索引的查询的性能。
表中的索引越多插入的速度就会越慢。一般来说增加新索引会导致insert，delete，update等操作速度变慢。

10、索引和锁

• 索引可以让查询锁锁定更少的行
• InnoDB的行锁效率高，内存使用的也少，但是锁定行的时候仍然会带来额外的开销，其次锁定超过需要的行会增加锁争用并减少并发性性
• InnoDB只有在访问行的时候才会对其加锁，而索引能够减少InnoDB访问的行数，从而减少锁的数量
• InnoDB在二级索引上使用共享(读)锁，但访问主键需要排他(写)锁。
• 即使使用了索引，InnoDB也可能锁住一些不需要的数据，如果不能使用索引查找和锁定行的话，MySQL可能会做全表扫描并锁住所有的行，不管是不是需要。

索引案例学习

1、支持多种过滤条件

• 如果MySQL使用某个索引进行范围查询，也就无法在使用另一个索引进行排序。

• 在有更多不同的值的列上创建索引的选择性会更好，一般来说这样做都是对的，因为可以让MySQL更有效的过滤掉不需要的行。

  基本原则: 考虑表上所有的选项，当设计索引时，不要只为现有的查询考虑需要哪些索引，还需要考虑对查询进行优化。如果发现某些查询需要创建新索引，但是这个索引会降低另一些查询的效率，那么应该考虑能否优化原来的查询。应该同时优化查询和索引以找到最佳平衡。

• 尽可能将要做范围查询的列放到索引的后面，以便优化器能使用尽可能多的索引列。

• 每增加一个 IN 条件，优化器需要做的组合都将以指数的形式增加，最终可能会极大降低查询的性能。

2、避免多个范围条件

• 对于范围条件查询，MySQL无法在使用范围列后面的其他索引了，但是对于多个等值条件查询则没有这个限制。
• 从explain的输出很难区分MySQL是要查询范围值还是查询列表值，他们的 type 值都是 range;
• 如果查询中有两个范围条件，可以考虑将其中一个转为in() 的列表，或者间接转换维护;
• 优化器 的特性是影响索引策略的一个很重要的因素，如果未来版本能实现松散索引扫描，就能在一个索引上使用多个范围条件；

3、优化排序

• 对于哪些选择性非常低的列，可以增加一些 特殊的索引 来排序。
• 延迟关联 通过使用覆盖索引查询返回需要的主键，再根据这些主键关联原表获得需要的行。

例子如下sql所示：
mysql> select <cols> from profiles inner join (
        select <primary key cols> from profiles 
        where x.sex = 'M' order by rating limit 100000,10)
        as x using(<primary key cols>);

维护索引和表

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

1、找到并修复损坏的表

• 对于MyISAM存储引擎，表损坏 通常是系统崩溃导致的，其他的引擎也会由于硬件问题，MySQL本身缺陷或者操作系统问题导致索引损坏;
• 索引损坏 会导致查询返回错误结果或莫须有的主键冲突等问题，严重时还会导致数据库崩溃；
• check table table_name 检查是否发生了表损坏(不是所有存储引擎都支持), repair table table_name 修复损坏的表(不是所有存储引擎都支持该命令);
• 如果是InnoDB引擎出现了表损坏，那么一定是发生了严重的错误，InnoDB一般不会出现损坏。
• InnoDB发生了表损坏原因: 数据库的硬件问题如内存或磁盘问题；数据库管理员错误操作例如在外部操作了数据库的文件； 或者是InnoDB本身缺陷(一般不太可能)；
• 设置innodb_force_recovery 参数进入InnoDB的强制恢复模式来修复数据。

2、更新索引统计信息

MySQL的查询优化器会通过两个API了解存储引擎和索引的分布信息

• records_in_range() 向存储引擎存储两个边界值获取在这个范围大概多少记录。MyISAM返回精确值，InnoDB返回一个估算值。
• info() 返回各种类型的数据，包括索引的基数;

• 如果 存储引擎 向 优化器 提供的扫描行数信息不准确，或执行计划本身太复杂导致无法准确获取各阶段匹配的行数，那么优化器会使用 索引统计信息 来估算要扫描的行数。
• MySQL优化器使用的是基于成本的模型，衡量成本的主要指标就是一个查询需要扫描的行数。
• analyze table table_name 命令可以重新生成统计信息。

不同引擎的索引信息

• Memory 引擎不存储索引统计信息
• MyISAM将索引统计信息存储在磁盘，analyze table 需要全索引扫描计算索引基数，过程需锁表。
• InnoDB不在磁盘存储索引统计信息，而是通过随机的索引访问进行评估存储在内存中。
• show index from table \G; 查看索引的基数(Cardinality)。

• InnoDB 引擎通过抽样的方式计算统计信息，先随机读取少量的索引页面，然后以此为样本计算索引的信息，老版本中样本的页数是8，新版本中可以通过参数 innodb_stats_sample_pages来设置样本数量。
• InnoDB 会在表首次打开，或执行analyze table,或表的大小发生非常大变化 (大小变化超过1/16,或插入20亿行都会触发)的时候计算索引统计信息。
• InnoDB 在打开某些INFORMATION_SCHEMA表 或使用show table status和show index，或在客户端开启自动补全功能的时候，都会触发索引统计信息的更新。
• 只要show index 查看索引统计信息，一定会触发统计信息更新，可以关闭innodb_stats_on_metadata参数。
• 如果关闭了索引统计信息的自动更新，那么需要周期性的使用analyze table 手动更新。否则，索引统计信息会永远不变，如果数据分布发生大的变化，可能会出现一些狠糟糕的执行问题。

3、减少索引和数据碎片

B-Tree索引可能会碎片化，碎片化的索引可能会以很差或者无序的方式存储在磁盘上。

数据存储的碎片化类型

• 行碎片 数据行被存储为多个地方的多个片段中，即使查询只从索引中访问一行记录，行碎片也会影响性能。
• 行间碎片 指逻辑上顺序的页或者行在磁盘上不是顺序存储的。行间碎片会影响全表扫描和聚簇索引扫描操作，因为这些操作本可以从磁盘顺序存储去取数据。
• 剩余空间碎片 是指数据页中有大量空余空间。会导致服务器读取大量不需要的数据，导致浪费。

对于MyISAM表，这三类碎片化都可能发生，InnoDB不会出现短小的行碎片，他会移动短小的行重写到一个片段中。

• 可以通过执行OPTIMIZE TABLE命令或导出导入数据方式重新整理数据。
• 对于MyISAM可以通过排序算法重建索引的方式消除碎片。
• 新版的InnoDB可以在线添加和删除索引，用以消除索引的碎片化。
• 对于不支持OPTIMIZE TABLE的存储引擎，可以通过alter table <table> ENGINE=<engine>;重建表，修改表的存储引擎为当前的即可。

总结

• 1、单行访问是很慢的，使用索引可以创建位置引用提升读取数据的效率。
• 2、按顺序访问范围数据是很快的：顺序I/O 无需多次磁盘寻道，比随机I/O快很多；顺序读取数据，无需额外的排序操作，group by查询也无须做排序和将行按组进行聚合计算。
• 3、索引覆盖查询是很快的。如果一个索引包含了查询需要的所有列，存储引擎无需回表查找行，避免大量单行访问。