MySQL 索引的分类和优化

​

优质博文：IT-BLOG-CN

索引是什么 ： MySQL 官方对索引的定义：索引（Index）是帮助 MySQL 高效获取数据的数据结构。可以得到索引的本质：索引是数据结构。索引的目的在于提高查询效率。可以简单理解为，排好序的快速查找数据结构。在数据之外，数据系统还维护着满足特定查找算法的数据结构，这些结构已某种特定方式引用（指向）数据，这样就可以在这些数据结构上实现高级查找算法。这种数据结构，就是索引。如下：

为了加快 Col2 的快速查找，可以维护一个右边所示的二叉查找树，每个节点分别包含索引的键值对和一个指向对应数据记录的物理地址的指针，这样就可以运用二叉树查找在一定复杂度内获取相应的数据，从而快速检索出符合条件的记录。
■ 一般来说索引本身也很大，不可能全部存储在内存中，因此索引往往以文件的形式存储在磁盘上。
■ 我们 Java 程序员平常所说的索引：如果没有特别指明，都指的是B树（多路搜索树，并不一定是二叉树）结构组织索引，其中聚集索引、次要索引、覆盖索引、复合索引、前缀索引、唯一索引默认都是B+树索引，统称索引。初B树外，还有哈希（hash index）索引等。
【2】优势：①、类似大学图书馆建书目录，提高数据检索的效率，降低数据库的 IO 成本。
②、通过索引列对数据进行排序，降低数据排序的成本，降低了 CPU 的消耗。
【3】劣势：①、实际上索引也是一张表，该表保存了主键与索引字段，并指向实体记录，索引索引列也是要占用空间的。
②、虽然索引大大提高了查询速度，同时又降低了更新表（Insert、Update、Delete）的速度。因为更新表的时候还要保存一下索引文件每次更新添加了索引列的字段或者更新所带来的键值变化后的索引信息。
③、索引只是提高效率的一个因素，如果 MySQL 有大量的数据表，就需要花时间研究建立最优秀的索引，或优化查询。（索引的建立并非一时）。

索引有很多种类型，为不同的场景提供更好的性能。在MySQL中，索引是在存储引擎层而不是服务器层实现。不同存储引擎的索引其工作方式并不一样。也不是所有存储引擎都支持所有类型的索引。即使多个存储引擎支持同一种类型的索引，其底层实现也可能不同。

一、B-Tree 索引

我们通过提到索引时，多半说的都是 B-Tree 索引，使用 B-Tree 数据结构来存储数据。大多数 MySQL 引擎都支持这种索引。之所以称之为“B-Tree” 是因为 MySQL 在创建表和其他语句中也使用该关键字。不过，底层的存储引擎也可能使用不同的存储结构，例如：InnoDB 则使用 B+Tree。存储引擎以不同的方式使用 B-Tree 索引，性能也各有不同，各有优劣。例如，MyISAM 使用前缀压缩技术使得索引更小，但 InnoDB 则按照原数据格式进行存储。再如 MyISAM 索引通过数据的物理位置引用被索引的行，而 InnoDB 则根据主键引用被索引的行。
【B-Tree（多路搜索树）】：通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。如下图：展示了 B-Tree 索引的抽象表示，大致反映了 InnoDB 索引是如何工作的。InnoDB 的叶子节点称为叶子页，大小为 16K。

B-Tree 索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针指向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。
叶子节点比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页（不同引擎的“指针”类型不同）。如下图，绘制了一个节点和其对应的叶子节点，其实在跟节点和叶子节点之间可能有很多节点页，树的深度和表的大小直接相关。B-Tree 对索引列是顺序组织存储的，所以很适合查找范围数据。例如下图，基于文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以A到C开头的名字”这样的查询效率会非常高。假设数据表信息如下：

CREATE TABLE People(
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    birthday DATE NOT NULL,
    gender ENUM('m','f') NOT NULL,
    KEY(last_name,first_name,birthday)
);
1
2
3
4
5
6
7

对于表中的每一行数据，索引中包含 last_name,first_name 和 birthday列的值，如下图表示索引是如何组织数据的存储的。索引对多个值进行排序的依据是 CREATE TABLE 语句中定义索引时列的顺序，看一下最后两个条目，两个人的姓和名都相同时，则根据他们的出生日期来排列顺序。

可以使用 B-Tree 索引的查询类型。B-Tree 索引使用于全键值、范围键值或键前缀查找（值where条件）。其中键前缀查找只适用于根据最左前缀的查找。前面所述的索引对如下类型的查询有效：
【1】全值匹配： 和索引中的所有列进行匹配，例如前面提到的索引可用于查找姓名为 Cuba Allen、出生于 1960-01-01 的人。
【2】匹配最左前缀： 前面提到的索引可用于查找所有姓为 Allen 的人，即只使用索引的第一列。
【3】匹配列前缀： 也可以只匹配某一列的值的开头部分。例如前面提到的索引可用于查找所有以 A 开头姓的人。这里也只使用了索引的第一列。模糊查询以常量开头，那么可以使用上索引。
【4】匹配范围值： 例如前面提到的索引可用于查找姓在 Allen 和 Barrymore 之间的人。这里也只使用了索引的第一列。
【5】精准匹配某一列并范围匹配另外一列： 前面提到的索引也可用于查找姓为 Allen，并且名字是字母 K 开头的人。即第一列 last_name 全匹配，第二列 first_name 范围匹配。
【6】只访问索引的查询： B_Tree 通常可以支持 “只访问索引的查询”，即查询只需要访问索引，而无需访问数据行。称之为“覆盖索引” 的优化。

所以，索引列的顺序是很重要的，上面的限制都和索引列的顺序有关。在优化性能的时候，可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求。也有些限制并不是 B-Tree 本身导致的，而是 MySQL 优化器和存储引擎使用索引的方式导致的。这部分限制在未来的版本中可能就不再是限制了。

二、哈希索引

哈希索引（hash index）是基于哈希表实现的，只有精确匹配索引所有列的查询才有效。对于每一行数据，存储引擎都会对所有的索引列计算一个哈希码（hash code），哈希码是一个较小的值，并且不同键值的行计算出来的哈希码也是不一样。哈希索引将所有的哈希码存储在索引中，同时在哈希表中保存指向每个数据行的指针。
【MySQL 中】：只有 Memory 引擎显示支持哈希索引。这也是 Memory 引擎表的默认索引类型，Memory 引擎同时也支持 B-Tree 索引。值得一提的是，Memory 引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

CREATE TABLE People(
    last_name VARCHAR(50) NOT NULL,
    first_name VARCHAR(50) NOT NULL,
    KEY USING HASH(last_name)
)ENGINE=MEMORY;
1
2
3
4
5

表中包含的数据如下：

f('Allen')= 1223
f('Peter')= 8493
f('Baron')= 3490
1
2
3

则哈希索引的数据结构如下：索引（hash值，指针），每个槽的编号是顺序的，但是数据行不是。

【举个栗子】： 进行如下查询：

SELECT last_name FROM People WHERE last_name='Peter';
1

MySQL 先计算 ‘Peter’ 的哈希值，并使用该值寻找对应的记录指针。因为 f(‘Peter’)=8493，所以对 MySQL 在索引中查找 8493，可以找到指向第二行的指针，最后一步是比较第二行的值是否为’Peter’，以确保就是要查找的行。因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。然而，哈希索引也有它的限制：
【1】哈希索引只包含哈希值和指针，而不存储字段值，所以不能使用索引中的值来避免读取行。不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显。
【2】哈希索引数据并不是按照索引值顺序存储的，所以也就无法用于排序。
【3】哈希索引也不支持部分索引列匹配查找，因为哈希索引始终是使用索引列的全部内容来计算哈希值的。例如，在数据列（A,B）上建立索引，如果查询只使用A，则无法使用该索引。是不遵循最左前缀的思想。
【4】哈希索引只支持等值查询，也不支持任何范围查询。
【5】访问哈希索引的数据非常快，除非有很多哈希冲突。当出现哈希冲突的时候，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行。
【6】如果哈希冲突很多的话，一些索引维护操作的代价也会很高。

因为上述限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它的性能会将非常显著。除了 Memory 引擎外，NDB 集群引擎也支持唯一哈希索引。InnoDB 引擎有一个特殊的功能叫做“自适应哈希索引（adaptive hash index）” 当InnoDB 注意到某些索引值被使用得非常频繁时，它会在内存中基于 B-Tree 索引之上再创建一个哈希索引，这样就使 B-Tree 索引也具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动化的、内部的行为，用户无法控制或者配置，不过该功能可以关闭。

【创建自定义哈希索引】： 如果存储引擎不支持哈希索引，则可以模拟像 InnoDB 一样创建哈希索引。思路很简单：在 B-Tree 基础上创建一个伪哈希索引，这和真正的哈希索引不是一回事，因为还是使用 B-Tree 进行查找，但是使用 Hash值进行查找而非键值本身。只需要在 WHERE 子句中手动指定使用哈希函数。

【举个栗子】： 例如表中存储了大量的 URL，并需要根据URL 进行搜索查询。如果使用 B-Tree 来存储 URL，存储的内容就会很大，因为 URL本身就很长。若在原有的表中，新增一个被索引的 url_crc列（使用CRC32 对 URL 进行哈希）。使用 CRC32 做哈希就可以使用如下方式查询：性能会提升很多，因为 MySQL 优化器会使用选择性高而体积小的 url_crc 列的索引来查询。

SELECT id FROM url WHERE url="http://www.mysql.com" AND url_crc=CRC32("http://www.mysql.com");
1

上述的缺点是需要维护哈希值。可以手动维护，也可以使用触发器实现。如下：先临时修改一下语句分隔符，这样就可以在触发器定义中使用分号；

DELIMITER //
CREATE OR REPLACE TRIGGER People_insert_trigger BEFORE INSERT ON  People FOR EACH ROW BEGIN
SET NEW.url_cc=CRC32(NEW.url);
END;
//
DELIMITER ;
1
2
3
4
5
6

记住不要使用 SHA1() 和 MD5() 作为哈希函数。因为这两个函数计算出来的哈希值是非常长的字符串，会浪费大量空间，比较时也会更慢。SHA1() 和 MD5() 是强加密函数，设计目的是最大限制消费冲突，但这里并不需要这么高的要求，简单哈希函数的冲突在一个可以接受的范围，同时又能够提供更好的性能。如果数据表非常大，CRC32() 会出现大量的哈希冲突，则可以考虑自己实现一个简单的 64位哈希函数。这个自定义函数要返回整数，而不是字符串。一个简单的办法可以使用 MD5() 函数返回值的一部分作为自定义哈希函数。这可能比自己写一个哈希算法的性能要差。

【处理哈希冲突】： 当使用哈希索引进行查询的时候，必须在 WHERE 子句中包含常量值。CRC32() 返回的是32位的整数，当索引有93,000 条记录时出现冲突的概率是 1%。所以，避免哈希冲突的办法就是在 WHERE 条件中带入列值。或者使用 FNV64()函数，这是移植 Percona Server 的函数，可以以插件的方式在任何 MySQL版本中使用，哈希值为 64位，速度快，且冲突比CRC32() 要少很多。

SELECT id FROM url WHERE url="http://www.mysql.com" AND url_crc=CRC32("http://www.mysql.com");
1

三、空间数据索引（R-Tree）

MyISAM 表支持空间索引，可以用作地理数据存储。和B-Tree 索引不同，这类索引无需前缀查询。空间索引会从所有维度来索引数据。查询时，可以有效地使用任意维度来组合查询。必须使用 MySQL 的 GIS 相关函数如 MBRCONTAINS() 等来维护数据。MySQL 的 GIS 支持并不完善，所以大部分人都不会使用这个特性。开源关系数据库系统中对 GIS 的解决方案做得比较好的是 PostgreSQL 的 PostGIS。

四、全文索引

全文索引是一种特殊类型的索引，他查找的是文本中的关键词，而不是直接比较索引中的值。全文搜索和其他几类索引的匹配方式完全不一样。他有许多需要注意的细节，如停用词、词干和复词、布尔搜索等。全文索引更类似 solr这种搜索引擎，而不是简单的 WHERE 条件匹配。同时在列上创建全文索引和基于值的 B-Tree 索引不会有冲突，全文索引适用于 MATCH AGAINST 操作，而不是普通的 WHERE 条件操作。

CREATE TABLE articles (

     id INT UNSIGNED AUTO_INCREMENT NOT NULL PRIMARY KEY,
     title VARCHAR(200),
     body TEXT,
     FULLTEXT (title,body)

) ENGINE=InnoDB;
1
2
3
4
5
6
7
8

【全文索引的使用】： 通过在 title和body 两个字段中查找含有 ‘database’ 内容的行。

SELECT * FROM articles
WHERE MATCH (title,body)
AGAINST ('database' IN NATURAL LANGUAGE MODE);
1
2
3

五、其他索引类型

还有第三方的存储引擎使用不同类型的数据结构来存储索引。例如 TokuDB 使用分型树索引（fractal tree index），这是一类较新开发的数据结构，既有 B-Tree 的很多优点，也避免了 B-Tree 的一些缺点。

六、优化

问题：性能下降， SQL 慢，执行时间长，等待时间长
■ 表结构设计不当。
■ 查询语句写的烂。
■ 索引失效（①、单值索引②、复合索引）
■ 关联查询太多 join（设计缺陷或者不得以的需求）
■ 服务器调优或者各个参数的设置（缓冲、线程数等）

哪些情况下需要创建索引：
【1】主键会自动创建唯一索引。
【2】频繁作为查询条件的字段。
【3】查询中与其他表关联的字段，外键关系建立索引。
【4】频繁修改的字段不建议创建索引。
【5】where 条件用不到的字段不要创建索引。
【6】单例索引与复合建议选择复合索引。
【7】查询的字段若通过索引的顺序去访问将大大提高排序速度。
【8】查询中统计和分组字段。

什么情况下不建议创建索引：
【1】表记录太少
【2】经常增删改的表
【3】数据重复且分布平均的字段。

索引分析： ①、单表：有范围时，后边的索引失效。②、双表：左连接为右表建索引。③、三表：参考②。结论：
● 永远用小的结果集驱动大的结果集。
● 优先优化NestedLoop内层循环。
● 保证 Join 语句中被驱动表上 Join 条件字段已被索引。
● 当无法保证上述 join 字段时，当内存允许的条件下，不要太吝啬 joinBuffer 字段的设置。

索引失效（应该避免）：
■ 全值匹配我最爱
■ 最佳左前缀法则
■ 不在索引列上做任何操作（计算、函数、类型转换），会导致索引失效而转向全表扫描。
■ 存储引擎不能使用索引中范围条件右边的列。
■ 尽量使用覆盖索引（只访问索引的查询），减少select *。
■ MySQL在使用不等于（！=或<>）的时候无法使用索引会导致全表扫描。
■ is null,is not null 也无法使用索引。
■ like 已通配符开头，MySQL 索引会失效会变成全表扫描。（%右边的是会进行rang索引的同是不同于>它会后面的索引不会失效。同时当使用左%时，想使用索引直接从索引缓存中查询即覆盖索引）
■ 字符串不添加单引号索引会失效。
■ 少用 or，用它来连接时会索引失效。
【总结】： 定值、范围还是排序，一般 order by 是给个范围。group by 基本上都是需要排序，会有临时表产生（如果错乱时）

一般性建议： 在 where 查询条件中条件不安索引的顺序排列查找和顺序排列查找的效果相同，原因是：MySQL 自身会对 sql 进行优化。（都是常量的提前）
1）、对于单值索引，尽量选择针对当前 query 过滤性更好的索引。
2）、在选择组合索引的时候，当前 query 中过滤性最好的字段在索引字段顺序中，位置越靠左越好。
3）、在选择组合索引的时候，尽量选择可以包含当前 query 中的 where 子句中更多字段的索引。
4）、尽可能通过分析统计信息和调整 query 的写法来达到选择合适索引的目的。

​