MySQL中的索引及其实现

索引，在MySQL中也叫做键（Key）是存储引擎用于快速找到记录的一种数据结构。在MySQL中，存储引擎用类似的方法使用索引，其现在索引中找到对应值，然后根据匹配的索引记录找到对应的数据行。

索引可以包含一个或多个列的值。如果索引包含多个列，那么列的顺序也十分重要，因为MySQL只能高效地使用索引的最左前缀列。

索引的类型

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

B-Tree索引

我们着重看一下InnoDB使用的B-Tree索引。InnoDB使用的B-Tree索引的底层的数据结构是B+Tree

先看看B+Tree的样子：

一颗传统的M阶B+树需要满足以下几个要求：

• 从根节点到叶节点的所有路径都具有相同的长度
• 所有数据信息都存储在叶子节点，非叶子节点仅作为叶子节点的索引存在
• 根节点至少拥有两颗子树
• 每个树节点最多拥有M个子树
• 每个树节点（除了根节点）拥有至少M/2个子树

B+树是为了磁盘及其他存储辅助设备而设计的一种平衡查找树(不是二叉树)，在B+树中，所有记录的节点按大小顺序存放在同一层的叶节点中，各叶子节点用指针进行连接

通常来说，B+树索引用于基于磁盘的数据库系统，即数据最后持久化存放在磁盘上，每个页的叶子节点一般包含较多的记录，因此具有较高的扇出。这意味着在数据库中B+树索引高度一般较小，在2~3层，其高度也决定了磁盘I/O搜索的次数。

还有一点需要注意的是，实际上根据B+树索引并不能找到一个给定值的具体行，B+树索引能找到的只是查找数据行所在的页。然后数据库通过把数据页读入内存，再在内存中进行查找，最后得到查找的数据。

B-Tree对索引列是顺序组织存储的，所以很适合查找范围数据。

适用于B-Tree索引查找的类型

全值匹配

全值匹配指的是和索引中的所有列进行匹配。例如查找姓名为XXX，年龄为YYY的人。

匹配最左前缀

如果索引有多列的话，可以只使用第一列来查找

匹配列前缀

也可以只匹配某一列的值的开头部分。

匹配范围值

匹配值再某个范围区间的查询

精确匹配某一列并范围匹配另一列

对于联合索引来说，可以精确匹配第一列，范围匹配第二列，这样的查询也是支持的

只访问索引的查询

B-Tree通常可以支持“只访问索引”的查询，即查询只需要访问索引，而无需访问数据行。

B-Tree索引的限制

• 如果不是按照索引的最左列开始查找，则无法使用索引。
• 不能跳过索引中的列。如果有联合索引（A、B、C），如果要查询数据（Ai、Cj）是不支持使用联合索引的。查找的时候只会使用第一列这个索引，也就是A列。
• 如果查询中有某个列的范围查询，则其右边所有列都无法使用索引优化查找。例如，存在联合索引（first_name, last_name，dob）。查询语句 where last_name = ‘smiti’ and first_name like ‘J%’ and dob = ‘1990-01-02’，这个查询只能使用到索引的前两列，因为LIKE在这里是一个范围查询。如果范围查询列值的数量有限，那么可以通过使用多个等于条件来代替范围条件。

哈希索引

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

在MySQL中，只有Memory引擎显示支持哈希索引，这也是Memory引擎表的默认索引类型。Memory引擎是支持非唯一哈希索引的。如果多个列的哈希值相同，索引会以链表的方式存放多个记录指针到同一个哈希条目中。

因为索引自身只需存储对应的哈希值，所以索引的结构十分紧凑，这也让哈希索引查找的速度非常快。

哈希索引的限制

• 哈希索引只包含哈希值和行指针，而不存储字段值，所以不能使用索引中的值来避免读取行，不过，访问内存中的行的速度很快，所以大部分情况下这一点对性能的影响并不明显
• 哈希索引数据不是按照索引值顺序存储的，所以也就无法用于排序
• 哈希索引页不支持部分索引列的匹配查找，因为哈希索引始终是所用索引列的全部内容来计算哈希值的。
• 哈希索引只支持等值比较查询，包括=、IN()、<=>，也不支持任何范围查询
• 范围哈希索引非常快，除非有很多哈希冲突。当出现哈希冲突时，存储引擎必须遍历链表中所有的行指针，逐行进行比较，直到找到所有符合条件的行
• 如果哈希冲突很多的话，一些索引维护操作的代价也会很高。冲突越多，代价越大。

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

空间数据索引（R-Tree）

MyISAM表支持空间索引，可以用作地理数据存储。和B-Tree索引不同，这类索引无须前缀查询。空间索引会从所有维度来索引数据。查询时，可以有效地使用任意维度来组合查询。必须使用MySQL的GIS相关函数来维护数据。MySQL的GIS支持并不完善，所以大部分人都不会使用这个特性。

全文索引

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

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