第五章、创建高性能的索引
1、简介
索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量小且负载较低时，不恰当的索引对性能的影响可能还不明显，但是当数据量逐渐增大时，性能会急剧下降。索引可以包含一个或者多个列的值。如果索引包含了多个列，那么列的顺序也十分重要。因为MySQL只能高效地使用索引的最左前缀列（B+树的数据结构决定的）。创建一个包含两个列的索引和创建两个包含一列的索引是大不相同的。
2、索引的类型
索引有很多类型，可以为不同的场景提供更好的性能。在MySQL中，索引是在存储引擎层而不是服务器层实现的。所以并没有统一的索引标准，不同的存储引擎的索引的工作方式是不同的，也不是所有的存储引擎都支持所有类型的索引。
（1）B-Tree索引。
正常情况下，如果不指定索引的类型，那么一般是指B-Tree索引（或者B+Tree索引）。存储引擎以不同的方式使用B-Tree索引。性能也各有不同，MyIsam使用前缀压缩技术使得索引更小，但是InnoDB按照原数据格式进行存储。MyIsam索引引用数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。
B-Tree索引能够加快数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，相反是从索引的根节点开始进行搜索，通过相应的指针移动，最终存储引擎要么找到了对应的值，要么该记录不存在。树的深度与表的大小直接相关。
B-Tree索引是按照顺序组织存储的，所以适合范围查找数据
B-Tree索引使用与全键值、键值范围或者键前缀查找，其中键前缀进适用于根据最左前缀的查找。
a、 全值匹配
b、 匹配最左前缀。
c、 匹配列前缀。
d、 匹配范围值
e、 精确匹配某一列并范围匹配另外一列。
f、 只访问索引的查询（覆盖索引）
B-Tree索引的限制：
a、 如果不是按照索引的最左列开始查找，那么无法使用索引
b、 不能跳过索引中的某些列。
c、 如果查询中使用了某个列的范围查询，那么该列右边的所有列都无法使用索引。
（2）、哈希索引
哈希索引基于哈希表实现，只有精确匹配索引所有列时才有效。对于每一行数据，存储引擎都会根据索引列计算一个哈希值，哈希索引将所有的hash值存储在索引中，同时在哈希表中保存指向每个数据行的指针。
MySQL中只有Memory引擎显式支持哈希索引。这也是Memory引擎的默认存储引擎，Memory引擎同时也支持B-Tree索引。哈希索引解决碰撞的方式是使用链表。
因为索引本身只出处对应的哈希值，因此索引的结构十分紧凑，这也让哈希索引查找的速度非常快。哈希索引的限制有：
（1）、哈希索引只包含值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
（2）哈希索引数据并不是按照索引值进行排序的，所以也就无法用于排序。
（3）哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列内的全部内容来计算哈希值的。例如，在数据列（A,B）上建立哈希索引，如果查询只有数据列A，则无法使用该索引。
（4）哈希索引只支持等值比较查询，包括=,IN, <=>等，也不支持任何范围查询。
（5）访问哈希索引的数据非常快，除非有很多哈希冲突，当出现哈希冲突的时候，储存引擎必须遍历列表中的所有行指针，逐行比较，直到找到所有符合条件的行。
（6）如果哈希冲突很多的话，一些索引维护操作的代价比较高。
InnoDB引擎有一种特殊的功能叫“自适应哈希索引”，当InnoDB注意到某些索引值被引用得非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引。这会让B-Tree索引也具有哈希索引的一些优点，比如快速查询。这是一个完全自主的、内部的行为，用户无法控制或者配置，不过可以关闭该功能。
创建自定义哈希索引。
例如为url创建url_crc哈希列：
alter table xxx add column url_crc intunsigned NOT NULL default 0;
然后为url_crc列加上索引：
alter table xxx add index idx_url_crc(`url_crc`);
查询时可以根据url和url_crc的值进行查询：
select * from xxx whereurl='http://www.mysql.com' and url_crc=crc32("http://www.mysql.com")
explain的结果如下：
这样实现的缺陷是需要维护哈希值（插入和更新时都要维护url_crc列）。可以在应用程序中维护，也使用触发器实现：
delimiter //
create trigger hash_crc_trigger beforeinsert on hash for each row begin
set NEW.url_crc=crc32(NEW.url);
END;
create trigger hash_crc_trigger_updatebefore update on hash for each row begin
set NEW.url_crc=crc32(NEW.url);
END;
delimiter ;
然后插入时只需要插入url列而不需要维护url_crc列（由触发器维护）。
采用这种方式时，不要使用SHA1()和MD5作为哈希函数，因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。
如果数据比较大，crc32()会出现大量的哈希冲突，则可以考虑自己实现同一个简单的64位哈希函数，如：
SELECTconv(right(md5("http://www.mysql.com"), 16), 16, 10);
处理哈希冲突：当使用哈希索引进行查询的时候，由于可能发生哈希冲突，因此必须在WHERE子句中包含常量值而不能只根据hash值查询：
select * from hash where url = 'http://www.twv.cn' and url_crc=2310657924;
空间索引：MyIsam表支持空间索引，Mysql本身对GIS的支持并不完善，开源关系数据库中对GIS的解决方案做的比较好的是PostgreSQL的PostGIS
全文索引：全文索引是一种特殊的索引，它查找的是文本中的关键词而不是直接比较索引中的值。全文索引更加类似与搜索引擎做的事情，而不是简单的WHERE匹配。在同一列上同时创建全文索引和基于值的B-Tree索引不会有冲突。
索引的优点：最常见的B-Tree索引，按照顺序存储数据，索引MySQL可以做ORDER BY和GROUP BY操作。因为数据是有序的，所以B-Tree也会将相关的列存储在一起，因为索引中存储了实际的列值，所以某些查询只是用索引就能够完成全部查询（覆盖索引）。总结一下，索引的3个优点：
（1） 索引大大减少了服务器需要扫描的数据量
（2） 索引可以帮助服务器避免排序和临时表
（3） 索引可以将随机I/O和顺序I/O
Three-Star System，如何评价一个索引是否适合某个查询：索引将相关的记录放到一起则获得一星；如果索引中的数据顺序和查找中的排列顺序一致则获得二星，如果索引中的列包含了查询中全部列则获得三星。
1、 高性能的索引策略
独立的列：指索引不能是表达式的一部分，也不能是函数的参数。常见的非独立的列：
（1） select act_id from table whereact_id+1 = 5; //(表达式的一部分，不是独立列)
（2） select * from table where TO_DAYS(CURRENT_DATE)-TO_DAYS(date_col)<=10;//函数的参数
索引的选择性：不重复的值（Cardinality, 基数）占数据表总数的比值。索引的选择性越高则查询效率越高，因为选择性高的索引可以让MySQL在查找时过滤掉更多的行。唯一索引的选择性是1，这时最好的索引选择性，性能也是最好的。选择索引时应该选择足够长的前缀以保证较高的选择性，同时又不能太长。
前缀索引：前缀索引能够使得索引更小、更快的索引办法，但是另一方面也有缺陷，MySQL无法使用前缀索引做Order by和group by操作，也无法使用前缀索引做覆盖扫描（意味着前缀索引一定不是覆盖索引？）。一个常见的场景是针对很长的十六进制唯一ID使用前缀索引（例如MD5的结果，或者SESSION会话的数据），这时如果使用长度为8的前缀索引通常能够显著地提升性能。
多列索引：对于多列，最常见的错误是，为每个列创建独立的索引或者按照错误的索引创建多列索引。explain查询的结果
（1）：（extra部分）当出现服务器对多个索引做相交操作时（通常有多个AND条件），通常意味着需要建立一个包含了所有相关列的多列索引，而不是多个独立的单列索引。
（2）：当索引需要对多个索引做联合操作时（通常有多个OR条件），通常需要耗费大量的CPU和内存资源在算法的缓存、排序和合并操作上。特别是当其中的有些索引的选择性不高，需要合并扫描返回的大量数据的时候。
如果在EXPLAIN的时候看到有索引合并，应该检查一下查询和表的结构，看是不是应该建立多列索引。
选择合适的索引列顺序：
（适用于B-Tree索引，哈希索引和其他类型的索引不会像B-Tree索引一样按顺序存储数据）。在一个多列的B-Tree索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列。索引可以按照升序或者降序进行扫描，以满足ORDER BY, Group by和distinct等子句的查询请求。对于选择索引列的顺序有一个经验法则：将选择性高的列放在索引的最前列。根据场景的不同，这条经验法则并不是完全准确的，在某些场景下，可能需要根据运行频率最高的查询来调整索引列的顺序。
聚簇索引：
聚簇索引并不是一种单独的索引类型，而是一种数据存储方式。InnoDB的聚簇索引实际上在同一个结构中保存了B-Tree索引和数据行（索引的顺序与数据的物理存放位置一致，“聚簇”表示数据行和相应的键值紧凑地存储在一起），因为无法同时把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。并不是所有的存储引擎都支持聚簇索引。在Oracle数据库中，索引组织表与“聚簇索引”是一样的意思。InnoDB通关过主键聚集数据。如果没有定义主键，InnoDB会选择一个唯一的非空索引作为替代。如果没有这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引。InnoDB只聚集在同一个页面中的记录，包含相邻键值的页面可能会相距很远。
聚集索引的一些优点：
（1）、可以把相关的数据保存在一起
（2）、数据访问更快。聚集索引将索引和数据保存在同一个B-Tree中，因此从聚簇索引中获取数据通常比在非聚簇索引中更快。
（3）、使用覆盖索引扫描的查询可以直接使用页节点中的主键值。
但是，聚簇索引也有一些缺点：
（1）、聚簇索引最大限度的提高了I/O密集型应用的性能，但是如果数据全部都保存在内存中，则访问的顺序就没那么重要了，聚簇索引也就没有优势了。
（2）、插入速度严重依赖于插入顺序。按照主键的顺序插入是加载数据到InnoDB表中速度最快的方式，如果不是按照主键顺序加载数据，最好在加载完成后使用OPTIMIZE TABLE命令重新组织一下表。
（3）、更新聚簇索引列的代价更高，因为会强制InnoDB将每个被更新的行移动到新的位置。
（4）、基于聚簇索引的表在插入新行或者主键被更新需要移动行的时候，可能面临“页分裂”的问题。
（5）、聚簇索引可能导致全表扫描变慢，尤其是行比较稀疏，或者页分裂导致的数据存储不连续的时候
（6）二级索引（非聚簇索引）通常更大，因为在二级索引中包含了引用行的主键列。也是因为如此，二级索引访问需要两次索引查找，而不是一次（第一次查找二级索引得到主键，第二次根据主键在聚簇索引中查找数据行）。
InnoDB和MyIsam的数据分布对比：
MyIsam的数据分布：
MyIsam按照数据插入的顺序存储在磁盘上。MyIsam的主键索引与其他的索引没有什么不同，主键索引就是一个名为PRIMARY的唯一非空索引。
InnoDB的数据分布：
InnoDB实际上是“索引组织表”，因为在InnoDB中，聚簇索引就是表。聚簇索引的每一个叶子节点包含了主键值、事务ID,用于事务和MVCC的回滚指针以及所有的剩余列。如果主键是一个列前缀索引，InnoDB也会包含完整的主键列和剩余的其他列。InnoDB的二级索引和聚簇索引有很大不同。InnoDB二级索引中存储的是主键值而不是行指针。这样的策略减少了当出现行移动或者数据页分裂时二级索引的维护工作。
TODO(MySQL索引背后的数据结构及算法原理):
http://www.360doc.com/content/11/0718/11/28217_134236866.shtml
在InnoDB表中按照主键顺序插入行：
如果在使用InnoDB表并且没有什么数据需要聚集，那么可以定义一个代理键作为主键，最简单的方法是使用AUTO_INCREMENT自增列，这样可以保证数据行是按照顺序写入，对于根据主键做关联操作的性能也会更好。最好避免随机的聚簇索引，特别对于I/O密集型的应用，从性能的角度考虑，使用UUID作为聚簇索引则会很糟糕，它使得聚簇索引聚簇索引的插入变得完全随机，其缺点有：
（1） 写入的目标页可能已经从缓存中删除，或者是还没有加载到缓存中，InnoDB在插入之前不得不先找到并从磁盘读取目标页到内存中。这将导致大量的随机I/O
（2） 因为写入是随机的，InnoDB不得不频繁地做页分裂操作，以便为新的行分配空间，页分裂会导致移动大量的数据，一次插入最少需要修改三个页而不是一个页。
（3） 由于频繁的页分裂，页会变得稀疏并且不规则填充，所以最终数据会有碎片。
（4） 在随机数值插入到聚簇索引之后，也许需要做一次optimize table来重建表并优化页的填充。
使用InnoDB时应该尽量按主键顺序插入数据，并且尽可能使用单调增加的聚簇键来插入新行。
对于高并发工作负载，InnoDB中按照主键顺序插入可能造成明显的锁争用，所以并发插入可能导致所竞争。
6、覆盖索引
通常大家设计索引都会根据查询的WHERE条件来创建合适的索引，不过这只是索引优化的一个方面。设计优秀的索引应该考虑整个查询，而不单单是WHERE条件部分。如果一个索引中包含了所需要查询的字段的值，我们就称为“覆盖索引”，覆盖索引能够极大的提高性能，覆盖索引带来的好处有：
（1） 索引条目远小于数据行大小，能够极大地提高性能，所以如果只需要读取索引，那么MySQL就会极大地减少数据访问量
（2） 因为索引是按照值顺序存储的，所以对于I/O密集型的范围查询会比随机从磁盘中读取每一行数据的I/O要少的多。
7、使用索引扫描做排序：
如果Explain出来的Type列为“index”, 则说明MySQL使用了索引扫描来做排序。扫描索引本身是很快的，因为只需要从一条索引记录移动到紧接着的下一条记录。但如果索引无法覆盖所有的列，那就不得不扫描一条索引记录就回表查询一次对应的行，这基本上属于随机I/O，因此按索引顺序读取数据的速度通常比顺序地全表扫描要慢。
如果查询需要关联多张表时，只有当ORDER BY子句引用的字段全部为第一个表时，才能使用索引做排序，ORDER BY子句与查找型查询的限制是一样：需要满足最左前缀的要求。有一种情况下ORDER BY子句可以不满足索引的最左前缀的要求，就是当前导列为常量时。
使用索引做排序的一个最重要的用法是当查询同时具有ORDER BY和LIMIT子句的时候。
8、前缀压缩索引
MyISAM使用前缀压缩来减少索引的大小，从而让更多的索引可以放入内存中，这在某种情况下可以极大地提高性能。默认只压缩字符串，但通过参数设置也可以对整数压缩。MyISAM压缩每个索引块的方法是：先完全保存索引块的第一个值，然后将其他值和第一值比较得到相同前缀的字节数和剩余的不同后缀部分。
对于CPU密集型的应用，因为扫描需要随机查找，压缩索引使得MyISAM在索引上查找要慢很多，压缩索引的倒序扫描更慢。
9、冗余和重复索引
重复索引指在相同的列上按照相同的顺序创建的相同类型的索引，应该避免创建重复索引，发现之后应该立即删除，否者会影响性能。
冗余索引与重复索引不同，如果创建了索引(A,B)，之后又创建了索引(A)就是冗余索引。大多数情况下不需要冗余索引，应该尽量扩展已有的索引而不是创建新索引。冗余索引的缺点是维护索引的成本更高（典型的如：插入表的速度变慢。实际上，增加索引会导致INSERT, UPDATE, DELETE等操作变慢）
10、索引和锁
索引可以让查询锁定更少的行。如果你的查询从不访问哪些不需要的行，那么就会锁定更少的行，从两个方面来看这对性能都有好处。首先，虽然InnoDB的行锁的效率很高，内存使用也很少，但是锁定行的时候依然会带来额外开销；其次，锁定需要的行会增加所争用并减少并发性。
InnoDB只有在访问行的时候才会对其加锁。而索引能够减少InnoDB访问的行数，从而减少锁的数量。但这只有当InnoDB在存储引擎能够过滤掉不需要的行时才有效，如果索引无法过滤掉无效的行，那么在InnoDB检索到数据并返回给服务器层之后，MySQL服务器才能应用Where子句，这时已经无法避免锁定行了：InnoDB已经锁住了这些行，到适当的时候才释放。Explain的Extra列显示“Using Where”，说明MySQL服务器将存储引擎返回行之后再应用where过滤条件。（SELECT xxx for update会获得排它锁）
InnoDB在二级索引上使用共享锁（读锁），但访问主键索引需要排它锁（写锁）。
使用延迟关联优化LIMIT 与 order by（TODO,P187）
11、维护索引和表
维护表的主要目的有三个：找到并修复损坏的表，维护准确的索引统计信息，减少碎片。
Check Table可以找出大多数表和索引的错误。可以使用RepairTable来修复损坏的表。也可以通过alter table的方式来修复表（修改表的引擎为当前的引擎，如alter table xxx ENGINE=InnoDB）.一般情况下，InnoDB表不容易损坏，如果损坏，很大可能是数据库的硬件问题（内存或者硬盘）。
MySQL优化器使用基于成本的模型，衡量成本的主要指标是查询需要扫描的行数，如果表没有统计信息，或者统计信息不准确，优化器很有可能做出错误的决定，可以通过Analyze table来重新生成统计信息来解决这个问题，不同引擎的运行成本不同：
（1） Memory不存储索引统计信息
（2） MyIsam将统计信息存储在磁盘中，Analyzetable需要进行一次全索引扫描来计算索引基数，在整个过程中需要锁表
（3） MySQL 5.5之前，InnoDB也不在磁盘中存储索引统计信息，而是通过随机的索引访问进行评估并将其存储在内存中
可以通过Show index from xxx 来查询索引的基数。
InnoDB会在首次打开表的时候，或者执行Analyzetable的时候，或者标的大小发生非常大的变化时计算索引的统计信息。
12、减少索引和数据的碎片
B-Tree索引可能会碎片化，这会降低查询的效率，碎片化的索引可能会以很差或者无序的方式存储在磁盘上。表的数据存储也可能碎片化，有三种类型的数据碎片：
（1）、行碎片
这种碎片指的是数据行被存储在多个地方的多个片段中，即使查询只从索引中访问一行记录，也会因为行碎片导致性能下降。
（2）、行间碎片
行在磁盘上并不是顺序存储的，行间对片对于全表扫描和聚簇索引草庙之类的操作有很大的影响，因为这些操作原本能够从磁盘上顺序存储的数据中获益。
（3）、剩余空间碎片
剩余空间碎片指的是数据页中有大量的剩余空间，这会导致服务器读取大量的不需要的数据局，从而造成浪费。
可以通过Optimize TABLE或者导出再倒入的方式来重新整理数据。
在选择索引和编写利用这些索引的查询时，有三个原则始终要记住：
（1） 单行访问是很慢的。
（2） 按顺序访问数据是很快的
（3） 索引覆盖查询是很快的。