聊聊MySQL几大索引类型：B-Tree索引，哈希索引，R-Tree空间数据索引，全文索引

索引（在MySQL中也叫做“键（key）”）是存储引擎用于快速找到 记录的一种数据结构。这是索引的基本功能，除此之外，后面还将讨论 索引其他一些方面有用的属性。 

索引对于良好的性能非常关键。尤其是当表中的数据量越来越大时，索引对性能的影响愈发重要。在数据量较小且负载较低时，不恰当 的索引对性能的影响可能还不明显，但当数据量逐渐增大时，性能则会急剧下降(除非特别说明，我们假设使用的都是传统的硬盘驱动器。固态硬盘驱动器有着完全不同 的性能特性，本书将对此进行详细的描述。然而即使是固态硬盘，索引的原则依然成立，只是 那些需要尽量避免的糟糕索引对于固态硬盘的影响没有传统硬盘那么糟糕)。

不过，索引却经常被忽略，有时候甚至被误解，所以在实际案例中经常会遇到由糟糕索引导致的问题。 

索引优化应该是对查询性能优化最有效的手段了。索引能够轻易将查询性能提高几个数量级，“最优”的索引有时比一个“好的”索引性能要 好两个数量级。创建一个真正“最优”的索引经常需要重写查询。

mysql> SELECT first_name FROM sakila.actor WHERE actor_id=5;

索引有很多种类型，可以为不同的场景提供更好的性能。在 MySQL中，索引是在存储引擎层而不是服务器层实现的。所以，并没有统一的索引标准：

• 不同存储引擎的索引的工作方式并不一样，也不是所有的存储引擎都支持所有类型的索引。
• 即使多个存储引擎支持同一种 类型的索引，其底层的实现也可能不同。 

当人们谈论索引的时候，如果没有特别指明类型，那多半说的是BTree索引，它使用B-Tree数据结构来存储数据(实际上很多存储引擎使用的是B+Tree，即每一个叶子节点都包含指向下一个叶子节点的指针，从而方便叶子节点的范围遍历)。大多数MySQL引擎都支持这种索引。Archive引擎是一个例外：5.1之前Archive不支持任何索引，直到5.1才开始支持单个自增列（AUTO_INCREMENT）的索引。 

我们使用术语“B-Tree”，是因为MySQL在CREATE TABLE和其他语句中也使用该关键字。不过，底层的存储引擎也可能使用不同的存储结构，例如，NDB集群存储引擎内部实际上使用了T-Tree结构存储这种索引，即使其名字是BTREE；InnoDB则使用的是B+Tree。

存储引擎以不同的方式使用B-Tree索引，性能也各有不同，各有优劣。

• 例如，MyISAM使用前缀压缩技术使得索引更小。

• 但InnoDB则按照原数据格式进行存储。

• 再如MyISAM索引通过数据的物理位置引用被索引的行，而InnoDB则根据主键引用被索引的行。 

B-Tree通常意味着所有的值都是按顺序存储的，并且每一个叶子页到根的距离相同。下图展示了B-Tree索引的抽象表示，大致反映了 InnoDB索引是如何工作的。MyISAM使用的结构有所不同，但基本思想是类似的。

B-Tree索引能够加快访问数据的速度，因为存储引擎不再需要进行全表扫描来获取需要的数据，取而代之的是从索引的根节点（图示并未画出）开始进行搜索。根节点的槽中存放了指向子节点的指针，存储引擎根据这些指针向下层查找。通过比较节点页的值和要查找的值可以找到合适的指针进入下层子节点，这些指针实际上定义了子节点页中值的上限和下限。最终存储引擎要么是找到对应的值，要么该记录不存在。

叶子节点比较特别，它们的指针指向的是被索引的数据，而不是其他的节点页（不同引擎的“指针”类型不同）。上图仅绘制了一个节点和其对应的叶子节点，其实在根节点和叶子节点之间可能有很多层节点页。树的深度和表的大小直接相关。

B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。例如，在一个基于文本域的索引树上，按字母顺序传递连续的值进行查找是非常合适的，所以像“找出所有以1到K开头的名字”这样的查找效率会非常高。

假设有如下数据表：

CREATE TABLE People (
    last_name varchar(50) not null,
    first_name varchar(50) not null,
    dob date not null,
    gender enum('m', 'f') not null,
    key(last_name, first_name, dob)
);

到这里读者应该可以明白，前面提到的索引列的顺序是多么的重要：这些限制都和索引列的顺序有关。在优化性能的时候，可能需要使用相同的列但顺序不同的索引来满足不同类型的查询需求。 

也有些限制并不是B-Tree本身导致的，而是MySQL优化器和存储引擎使用索引的方式导致的，这部分限制在未来的版本中可能就不再是限制了。

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

在MySQL中，只有Memory引擎显式支持哈希索引。这也是Memory 引擎表的默认索引类型，Memory引擎同时也支持B-Tree索引。值得一 提的是，Memory引擎是支持非唯一哈希索引的，这在数据库世界里面是比较与众不同的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。 

下面来看一个例子。假设有如下表：

CREATE TABLE testhash (
    fname VARCHAR(50) NOT NULL,
    lname VARCHAR(50) NOT NULL,
    KEY USING HASH(fname)
) ENGINE=MEMORY;

假设索引使用假想的哈希函数f()，它返回下面的值（都是示例数据，非真实数据）：

f('Arjen')= 2323
f('Baron')= 7437
f('Peter')= 8784
f('Vadim')= 2458

则哈希索引的数据结构如下：

注意每个槽的编号是顺序的，但是数据行不是。现在，来看如下查 询：

mysql> SELECT lname FROM testhash WHERE fname='Peter';

MySQL先计算'Peter'的哈希值，并使用该值寻找对应的记录指针。因为f（'Peter'）=8784，所以MySQL在索引中查找8784，可以找到指向第3行的指针，最后一步是比较第三行的值是否为'Peter'，以确保就是要查找的行。

因为这些限制，哈希索引只适用于某些特定的场合。而一旦适合哈希索引，则它带来的性能提升将非常显著。举个例子，在数据仓库应用中有一种经典的“星型”schema，需要关联很多查找表，哈希索引就非常适合查找表的需求。

除了Memory引擎外，NDB集群引擎也支持唯一哈希索引，且在 NDB集群引擎中作用非常特殊。

InnoDB引擎有一个特殊的功能叫做“自适应哈希索引（adaptive hash index）”。当InnoDB注意到某些索引值被使用得非常频繁时，它会在内存中基于B-Tree索引之上再创建一个哈希索引，这样就让B-Tree索引也具有哈希索引的一些优点，比如快速的哈希查找。这是一个完全自动的、内部的行为，用户无法控制或者配置，不过如果有必要，完全可以关闭该功能。

mysql> SELECT id FROM url WHERE url="http://www.mysql.com";

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

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)
);

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 ;

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

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

MyISAM表支持空间索引，可以用作地理数据存储。

和B-Tree索引不同，这类索引无须前缀查询。空间索引会从所有维度来索引数据。查询时，可以有效地使用任意维度来组合查询。必须使用MySQL的GIS相关函数如MBRCONTAINS()等来维护数据。

MySQL的GIS支持并不完善，所以大部分人都不会使用这个特性。开源关系数据库系统中对GIS的解决方案做得比较好的是PostgreSQL的PostGIS。

全文索引是一种特殊类型的索引，它查找的是文本中的关键词，而不是直接比较索引中的值。

全文搜索和其他几类索引的匹配方式完全不一样。它有许多需要注意的细节，如停用词、词干和复数、布尔搜索等。全文索引更类似于搜索引擎做的事情，而不是简单的WHERE条件匹配。

在相同的列上同时创建全文索引和基于值的B-Tree索引不会有冲突，全文索引适用于MATCH AGAINST操作，而不是普通的WHERE条件操作。

我们会在后面的章节讨论更多的全文索引的细节。

还有很多第三方的存储引擎使用不同类型的数据结构来存储索引。例如TokuDB使用分形树索引（fractal tree index），这是一类较新开发的数据结构，既有B-Tree的很多优点，也避免了B-Tree的一些缺点。如 果通读完本章，可以看到很多关于InnoDB的主题，包括聚簇索引、覆 盖索引等。多数情况下，针对InnoDB的讨论也都适用于TokuDB。

ScaleDB使用Patricia tries（这个词不是拼写错误），其他一些存储 引擎技术如InfiniDB和Infobright则使用了一些特殊的数据结构来优化某 些特殊的查询。

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

最常见的B-Tree索引，按照顺序存储数据，所以MySQL可以用来做ORDER BY和GROUP BY操作。因为数据是有序的，所以B-Tree也就会将相关的列值都存储在一起。最后，因为索引中存储了实际的列值，所以某些查询只使用索引就能够完成全部查询。据此特性，总结下来索引有如下三个优点： 

• 1. 索引大大减少了服务器需要扫描的数据量。

• 2. 索引可以帮助服务器避免排序和临时表。

• 3. 索引可以将随机I/O变为顺序I/O。

• 索引将相关的记录放到一起则获得一星；

• 如果索引中的数据顺序和查找中的排列顺序一致则获得二星；

• 如果索引中的列包含了查询中需要的全部列则获得“三星”。

这里的总结也包括了后面几篇索引文章的学习总结。

在MySQL中，大多数情况下都会使用B-Tree索引。其他类型的索引大多只适用于特殊的目的。如果在合适的场景中使用索引，将大大提高查询的响应时间。

总的来说，编写查询语句时应该尽可能选择合适的索引以避免单行查找、尽可能地使用数据原生顺序从而避免额外的排序操作，并尽可能使用索引覆盖查询。这与前面提到的Lahdenmaki和Leach的书中 的“三星”评价系统是一致的。

如果表上的每一个查询都能有一个完美的索引来满足当然是最好的。但不幸的是，要这么做有时可能需要创建大量的索引。还有一些时候对某些查询是不可能创建一个达到“三星”的索引的（例如查询要按照 两个列排序，其中一个列正序，另一个列倒序）。这时必须有所取舍以 创建最合适的索引，或者寻求替代策略（例如反范式化，或者提前计算 汇总表等）。

理解索引是如何工作的非常重要，应该根据这些理解来创建最合适的索引，而不是根据一些诸如“在多列索引中将选择性最高的列放在第 一列”或“应该为WHERE子句中出现的所有列创建索引”之类的经验法则 及其推论。

那如何判断一个系统创建的索引是合理的呢？一般来说，我们建议按响应时间来对查询进行分析。找出那些消耗最长时间的查询或者那些给服务器带来最大压力的查询，然后检查这些查询的schema、SQL和索引结构，判断是否有查询扫描了太多的行，是否做了很多额外的排序或者使用了临时表，是否使用随机I/O访 问数据，或者是有太多回表查询那些不在索引中的列的操作。

如果一个查询无法从所有可能的索引中获益，则应该看看是否可以创建一个更合适的索引来提升性能。如果不行，也可以看看是否可以重写该查询，将其转化成一个能够高效利用现有索引或者新创建索引的查询。这也是下一章要介绍的内容。

如果根据基于响应时间的分析不能找出有问题的查询呢？是否可能有我们没有注意到的“很糟糕”的查询，需要一个更好的索 引来获取更高的性能？一般来说，不可能。对于诊断时抓不到的查询， 那就不是问题。但是，这个查询未来有可能会成为问题，因为应用程 序、数据和负载都在变化。如果仍然想找到那些索引不是很合适的查 询，并在它们成为问题前进行优化，则可以使用pt-query-digest的查询审 查“review”功能，分析其EXPLAIN出来的执行计划。