MySQL 索引及其分类

1. 概述

mysql 索引能够轻易将查询性能提高几个数量级，而一个“最优”索引有时比一个“好的”索引性能要高两个数量级。

在 MySQL 中，索引可以包含一个活多个列的值，因为 MySQL 只能高效地使用索引的最左前缀列，所以包含多个列的索引中列的顺序也十分重要。 而创建一个包含两个列的索引和创建两个分别包含一列的索引是大不相同的。

2. 索引的类型

MySQL 中，索引的类型有很多类型，能够为不同场景提供更好的性能。 索引是在存储引擎层实现的，不同存储引擎的索引工作方式不同，也并不是所有引擎都支持全部的索引类型，而对于同一类索引，不同引擎的底层实现也可能是不同的。

3. B-Tree 索引

大多数 MySQL 存储引擎都支持 B-Tree 索引，也因此，B-Tree 索引是最常用的索引类型，如果未加说明，索引一般都指的是 B-Tree 索引。 然而，虽然在创建表时关键字都是 B-Tree，但是各个存储引擎的底层实现可能是不同的，如 NDB 集群存储引擎内部实际上使用了 T-Tree 结构，而 innoDB 使用的 B+ Tree。

3.1. 磁盘 IO 与预读

由于磁盘读取靠的是机械运动，每次都要花费寻道时间、旋转延迟、传输时间三部分时间才能读取数据，总计时间是非常长的，如果针对数据库的动辄十万百万乃至千万级的数据查询，每次几毫秒的时间，结果将会是灾难性的。 因此操作系统对此进行了一些优化，每次读取时并不仅仅读取需要的数据，而是把相邻数据全部读取到内存缓冲区中，这样，每次都读取一页数据（4KB 或 8KB），而针对一页上数据的读取，事实上仅进行了一次磁盘 IO 操作。

3.2. B-Tree 的特性

B-Tree 的结构如下图：

由于 B 树的多分支结构特性，导致树的高度可以大幅下降，这样，如果每个节点都存储一页数据，如果需要访问第三层数据，则只需要进行三次磁盘 IO，这显然大幅的节省了时间。 B+ 树与 B 树的区别在于只有叶子节点存储真实数据，其余非叶子结点仅作为指引搜索方向的数据项。 这样存储引擎不再需要全表扫描，而是根据每个节点的指引可以快速找到需要的数据。

同时，由于 B 树的结构特性，也导致所有的值通常都是按顺序存储的，因此在使用 ORDER BY 操作时，这个索引也可以满足对应的排序需求。

3.3. 多列索引的匹配规则

CREATE TABLE People (
    a    varchar(50)    not null,
    b    varchar(50)    not null,
    c    date        not null,
    d    date        not null,
    e    enum('m', 'f')    not null,
    key(a, b, c, d)
);

复制

对于上面这个表，创建了四列索引，他们遵循下列规则。

• 最左前缀匹配原则 这是一个非常重要的原则，MySQL 会一直向右匹配直到遇到范围查询（>、<、between、like） 比如查询 a="" and b="2" and c >= 3 and d = 4。 在这个查询中，d 是用不到索引的，而如果建立 (a, b, d, c) 则是可以的。 同时 where 语句中查询的顺序是可以任意调整的，即 a、b、c、d 的顺序可以任意调整，MySQL 总是按照索引建立的顺序进行查询。
• 最大区分度原则 尽量选择区分度高的列作为索引，或是将其放置在左端，区分度越高，即选出的结果行越少，则实际查询的次数就会越少。
• 索引列不能参与计算 对于 from_unixtime(a) = ’2014-05-29’ 这样的查询是不能应用索引的，而应该优化成 a = from_unixtime(‘2014-05-29’) 比如 a+1>5 只有优化为 a > 4 才会应用索引。
• 必须以最左列开始查询 如果查询 b = 5 and c < 2014 则不会应用索引，这也正是最左前缀匹配原则。
• 不能跳过索引中的列 对于查询 a=5 and c > 2015，由于跳过了 b 列，所以 c 不会应用索引。
• 说明 上述限制存在于 MySQL 5.5 及以前的数据库版本中，未来的版本可能会取消某些限制。 然而，可以看到，创建表时怎样选取索引的列，以及他们的排列顺序是非常重要的。

4. 哈希索引

4.1. 简介

CREATE TABLE testhash (
    a varchar(50) not null,
    b varchar(50) not null,
    KEY USING HASH(a)
) ENGINE=MEMORY;

复制

上面创建表的过程中创建了一个哈希索引。

顾名思义，哈希索引的底层数据结构是用哈希表实现的，只有精确匹配索引所有列的查询才有效。 索引会为每一行数据建立一个很小的哈希码，因此哈希索引占用空间小，执行效率高，但只支持等值查询，而不支持范围查询。 同时，由于哈希表并不按照值的大小顺序存储，因此在 ORDER BY 操作中并不会应用该索引，也不支持仅使用索引中部分列进行查找。 但是，如果是某些特定适合使用哈希索引的场合，索引所带来的性能提升将非常显著，如经典的“星型” schema，需要关联很多查找表，哈希索引就非常适合查找表的需求。

4.2. 哈希索引与存储引擎

哈希索引是 MEMORY 存储引擎的默认索引方式，MEMORY 引擎同时也支持 B-Tree 索引，目前，在 MySQL 中，只有 MEMORY 引擎显式支持哈希索引。

InnoDB 引擎有一个特殊的功能 — 自适应哈希索引，对于被频繁使用的索引值，InnoDB 引擎会自动在内存中创建一个哈希索引，用户只能通过配置选择是否启用这一特性，一旦启用，该过程将是完全自动，用户无法察觉的。 InnoDB 创建的自适应哈希索引和真正的哈希索引并不是一回事，而是在原有的 B-Tree 索引的基础上，将检索的值变成哈希码，以降低磁盘使用。

4.3. 自定义哈希索引

针对不支持哈希索引的存储引擎，用户也可以采用类似 InnoDB 的思路去自定义哈希索引。 典型的如将 url 变成 CRC32，可以有效节省磁盘使用，并且提高查询速度。

如针对下面的查询：

SELECT id FROM url WHERE url = 'http://www.techlog.cn/article/list/10182793';

复制

这样的查询显然是很耗时的，且如果为 url 创建索引，索引也将非常庞大。

优化成以下这样：

SELECT id FROM url WHERE crc32_url = CRC32('http://www.techlog.cn/article/list/10182793');

复制

这样，我们为 crc32_url 字段创建索引，索引的大小、查询效率都会有显著的提升。

但是，这样又需要维护一个新的字段 crc32_url，通过创建触发器，可以自动的添加该字段：

CREATE TABLE pseudohash (
    id    int unsigned NOT NULL auto_increment,
    url    varchar(255) NOT NULL,
    url_crc    int unsigned NOT NULL DEFAULT 0,
    PRIMARY KEY(id)
    KEY(url_crc);
);

DELIMITER //

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

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

DELIMITER ;

复制

这样，每当添加或修改 url 字段，触发器会自动更新 url_crc 字段。

由于可能存在的哈希冲突，所以直接查询可能会出现多条记录，可以优化为：

SELECT id FROM url WHERE crc32_url = CRC32('http://www.techlog.cn/article/list/10182793') and url = 'http://www.techlog.cn/article/list/10182793';

复制

5. 空间数据索引（R-Tree）

MyISAM 表支持空间索引，可以用作地理数据存储。 与 B-Tree 索引不同，空间数据索引无需前缀查询，他会从所有维度索引数据，可以任意组合查询。 但是必须使用 MySQL 的 GIS 相关函数，如 MBRCONTAINS() 来维护数据，然而 MySQL 对 GIS 支持并不完善，所以大部分人不会使用这个特性。 PostgreSQL 的 PostGIS 对 GIS 支持很好。

6. 全文索引

全文索引查找的是文本中的关键词，而不是比较索引中的值，类似于搜索引擎。 使用 MATCH AGAINST 操作进行索引，目前不支持中文。

7. 其他索引

还有很多第三方存储引擎使用其他不同类型的数据结构来存储索引，他们各自有不同的适用场景和优势。