转载

《高性能 MySQL》 — 第五章创建高性能的索引

索引基础

索引的使用：现在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。

对于有多列的索引，MySQL 只能高效地使用索引的最左前缀列。因此列的顺序很重要。

MySQL 的唯一限制和主键限制都是通过索引实现。

索引的类型

MySQL 中，索引是在存储引擎层而不是服务器层实现的，所以没有统一的索引标准。

B-Tree 索引

B-Tree 通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相等，适合范围查询。

《高性能 MySQL》 — 第五章创建高性能的索引

B-Tree 索引适用于全键值、键值范围或键前缀查找，其中键前缀查找只适用于根据最左前缀的查找。

索引还可以用于查询中的 order by 操作。

B-Tree 索引的限制：

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

这些限制是 MySQL 优化器和存储引擎使用索引的方式导致的。

哈希索引

哈希索引（hash index）基于哈希表实现，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码，哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。

哈希索引只需存储对应的哈希值，所以索引结构十分紧凑，使查找很快。

哈希索引的限制：

哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行。
哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。
哈希索引只支持等值比较查询。
访问哈希索引的数据非常快，除非有很多哈希冲突。
如果哈希冲突很多的话，一些索引维护操作的代价会很高。（哈希冲突时，相同哈希值的行指针会存储在一条链表里，索引的维护操作需要遍历链表来完成。）

InnoDB 引擎有一个特殊的功能叫做 ”自适应哈希索引（adaptive hash index）“。当 InnoDB 注意到某些索引值被使用得非常频繁时，它会在内存中基于 B-Tree 索引之上再创建一个哈希索引，这让 B-Tree 索引也具有哈希索引的一些优点，比如快速的哈希查找。

索引的优点

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

评价一个索引是否适合某个查询的”三星系统“：索引将相关的记录放到一起则获得一星；如果索引中的数据顺序和查找中的排列顺序一致则获得二星；如果索引中的列包含了查询中需要的全部列则获得三星。

高性能的索引策略

正确地创建和使用索引是实现高性能查询的基础。

索引的选择性是指：不重复的索引值的数量（也称为基数，cardinality）和数据表的记录总数的比值。索引的选择性越搞则查询效率越高。唯一性索引的选择性是 1，是最好的索引选择性，性能最高。

独立的列：指索引列不能是表达式的一部分，也不能是函数的参数。始终将索引列单独放在比较符号的一侧。
前缀索引和索引选择性：对于很长的字符列，通常可以索引开始的部分字符，这样可以节约索引空间，提供索引效率，但会降低索引的选择性。前缀的”基数“应该接近于完整列的”基数“。MySQL 无法使用前缀索引做 order by 和 group by，也无法使用前缀索引做覆盖扫描。创建前缀索引： alter table table_name add key(col_name(prefix_length));
多列索引：MySQL 5.0 及更新的版本引入了索引合并策略（index merge），查询能够同时使用这两个单列索引进行扫描，并将结果进行合并。这种算法有三个变种：OR 条件的联合（union）， AND 条件的相交（intersection），组合前两种情况的联合及相交。
选择合适的索引列顺序：在一个多列的 B-Tree 索引中，索引列的顺序意味着索引首先按照最左列进行排序，其次是第二列，等等。索引可以安装升序或者降序进行扫描，以满足精确符合列顺序的 order by, group by, distinct 等子句的查询需求。考虑索引列的顺序时，将选择性最高的列放到索引列最前列，但通常不如避免随机 IO 和排序重要。性能不只是依赖于所有索引列的选择性，也和值的分布有关。（需要总和考虑选择性、基数、排序、分组、范围条件、值分布等因素）

聚族索引

聚族索引（Oracle 里对应的是索引组织表，index-organized table, IOT）并不是一种单独的索引类型，而是一种数据存储方式。

当表有聚族索引时，它的数据行实际上是存放在索引的叶子页中。聚族表示数据行和相邻的键值紧凑地存储在一起。聚族索引的叶子页包含了行的全部数据，但是节点页只包含了索引列。

聚族索引的优点：

可以把相关的数据保存在一起。（利用数据的临近性）
数据访问更快。由于索引和数据都在同一个 B-Tree 中，从聚族索引获取数据比非聚族索引要快。
使用覆盖索引扫描的查询可以直接使用页节点中的主键值。

聚族索引的缺点：

插入速度严重依赖于插入顺序。按照聚族列的顺序插入是最快的方式。
更新聚族索引列的代价很高，因为 InnoDB 将强制每个被更新的行移动到新的位置。
基于聚族索引的表在插入新行，或者主键被更新导致需要移动行的时候，可能面临页分裂（page split）的问题。
聚族索引可能导致全表扫描变慢，尤其是行比较稀疏，或者由于页分裂导致数据存储不连续。

二级索引

MySQL 中每个表都有一个聚簇索引（clustered index ），除此之外的表上的每个非聚簇索引都是二级索引，又叫辅助索引（secondary indexes）。

以 InnoDB 来说，每个 InnoDB 表具有一个特殊的索引称为聚集索引。如果您的表上定义有主键，该主键索引是聚集索引。如果你不定义为您的表的主键时，MySQL 取第一个唯一索引（unique）而且只含非空列（NOT NULL）作为主键，InnoDB 使用它作为聚集索引。如果没有这样的列，InnoDB 就自己产生一个这样的 ID 值，它有六个字节，而且是隐藏的，使其作为聚簇索引。

create  table  layout_test (      col1  int  not  null,      col2  int  not  null,      primary  key  (col1),      key (col2) );

对应的（主键、）表分布：

《高性能 MySQL》 — 第五章创建高性能的索引

其二级索引分布如下：

InnoDB 二级索引的叶子节点存储的不是”行指针“，而是主键，并以此作为指向行的”指针“。这样的策略减少了当出现行移动或数据页分裂时二级索引的维护工作。

聚族和非聚族表对比图：

由于主键的值是顺序的，InnoDB 把每一条记录都存储在上一条记录的后面，当达到页的最大填充因子时（InnoDB 默认的最大填充因子是页大小的 15/16，留出部分空间用于以后修改），下一条记录就会写入新的页中。

最好避免随机的（不连续且值的分布范围非常大）聚族索引，特别是对于 I/O 密集型的应用。会导致的一些缺点：

写入的目标页可能已经刷到磁盘上并从缓存中移除，或者是还没有被加载到缓存中，InnoDB 在插入钱不得不先找到并从磁盘读取目标页到内存中。这将导致大量的随机 I/O。
因为写入是乱序的，InnoDB 不得不频繁地做页分裂操作，以便为新的行分配空间。
由于频繁的页分裂，页会变得稀疏并被不规则地填充，索引最终数据会有碎片。

顺序的主键也可能造成不好的结果：对于高并发工作负载，主键的上界会成为”热点“，因为所有的插入都发生在这里，所以并发插入可能导致间隙锁竞争；另一个热点可能是 AUTO_INCREMENT 锁机制。