MySQL索引分析

索引在官方定义中是：索引是存储引擎用于快速找到记录的一种数据结构。如果没有索引，当查询数据时MySQL必须从第一行开始，然后读取整个表来查找对应行。表越大，查询成本越高。如果表中有相关列的索引，MySQL可以快速确定要在数据文件中间寻找的位置，而无需查看所有数据。这比按顺序读取每一行要快得多。但当数据越来越多的时候，不恰当的使用索引会使性能急剧下降。

提取句子主干，就可以得到索引的本质：索引是数据结构。

大多数索引使用B树，哈希。少数有R树(空间数据索引)，FULLTEXT(全文索引)。在Mysql中需要注意不同存储引擎的索引工作方式不一样，不同存储引擎支持的索引类型也不同，即使都支持同一种索引内部实现也可能不同。下面主要分析下B树，和哈希索引。

索引的数据类型

索引有在Mysql的存储引擎中实现，不同的存储引擎的索引实现方式不同，即使每个存储引擎支持同一种索引，但其内部实现或数据结构也可能有所差别。在这里主要分析使用频率很高的B树和哈希索引。

B树索引

B树是一种在数据库索引中很常用的树数据结构。索引数据始终保持排序，从而能够快速查找完全匹配（等于运算符）和范围（例如，大于，小于和BETWEEN 运算符）。这种类型的索引可用于大多数存储引擎，例如InnoDB和 MyISAM。

InnoDB的B+树

在InnoDB中B树索引其实现实际为B+树，B+树比B树主要有以下不同

非叶子结点仅具有索引作用，跟记录有关的信息均存放在叶子结点中。

树的所有叶子结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。

这里找了网上的一颗B+树的结构图可以看一下，用于后文更加直观的了解索引实现。你也可以点击这里自己制作一颗B+树观察过程。

假设我们创建这样一张表。

在上述表定义中，我们定义了一个name和birthday列的联合索引，同时还有一个id主键，主键也是索引的一种。在联合索引中多个值的顺序就是根据表定义DDL语句中的顺序，当数据插入时经过主键索引的比较操作找到对应的位置，类似B+树添加节点的方式，插入后这些数据在表中的顺序是按照主键排序好的，并不是按照插入顺序排列的。下图为联合索引indexnamebir的结构图。

可以看出索引每个节点都包含一个key和value值，在indexnamebir索引中key为索引列的值，value值指向主键的值，这种索引也叫做二级索引，而在主键索引中它的数据都是放在叶子节点中的，叶子节点包含了行的所有数据，key为主键id的值，value为行的数据，但是非叶子节点只包含了索引列。因此主键索引也叫做聚簇索引。如果表中没有定义主键，InnoDB会选择一个唯一的非空索引代替。如果没有这样的索引，则会隐式的定义一个主键来做聚簇索引。

在InnoDB的聚簇索引中，聚簇索引就是整张表，因为它的叶子节点中包含了整张表的数据。换句话说聚簇索引是和表绑定在一起的。

聚簇索引只是一种数据的存储方式，因为是存储引擎负责实现索引，所以不是所有的存储引擎都支持聚簇索引。需要了解的是在根据二级索引查询时，存储引擎需要找到二级索引中对应的主键值，根据主键值去聚簇索引中查找对应的行。需要注意的是在支持聚簇索引的存储引擎中，根据二级索引查询某些数据行时，会有两次B树查找，而不是一次查找取到数据。这种操作叫做回表。

MyISAM引擎中的索引

MyISAM存储引擎不支持聚簇索引，两种索引的结构有所不同，MyISAM按照数据插入的顺序存储在磁盘上，我们来创建下表。

然后插入一些数据，但是id列并不按照数字顺序插入，来看看索引的结构。

图中省略了一些树节点，因为那些与B+树的节点没啥两样。在图中插入的顺序也就是行号，可以看出索引叶子节点中每个列值对应的是表中数据的行号，而且主键与二级索引除了索引列值外并没有什么差异。这就是与InnoDB中的聚簇索引的主要不同。

还有一点，MyISAM二级索引的叶子节点存储的是表数据行号相当于指针，而InnoDB存储的是主键值，这样InnoDB的二级索引会占用更多的内存。但是，当数据行因为增加和删除出现行移动时，MyISAM需要根据情况跟新维护这些索引中的“指针”。

B树索引有一下特性：

最左前缀匹配，只要满足索引的前缀数据，就可以利用索引来加速。这个最左前缀可以是联合索引的最左 N 个字段，也可以是字符串索引的最左N个字符。

匹配范围值，再查询id从1到5之间或id>2时的人时，也可以用到索引。

只查找索引数据，某些sql只需要查询索引列的值，比如select id from ...，这时可不需要回表操作，直接在索引中找到相应的值，这种操作叫做覆盖索引，后面细讲。

哈希索引

哈希索引根据哈希表实现，对于每一个索引行都会生成一个哈希值存储在索引中，并保存值对应的行。在MySQL中，Memory存储引擎默认使用哈希索引，它是支持非唯一哈希索引的，如果多个列的哈希值相同，则冲突的值将会以链表的方式存放在同一个哈希条目中。

由于数据结构的特性，它与B树索引有一下不同的特征：

它们仅用于使用=或 运算符的相等比较 （但速度非常快）。它们不用于比较运算符，例如

优化器无法使用哈希索引来加速 ORDER BY操作。（哈希索引不能用于按顺序搜索下一个条目。）

只能用整个索引的值用于搜索。（使用B树索引，键的任何最左边的前缀都可用于查找。） 因为哈希索引的数据结构影响，它的查询速度非常快，哈希索引的结构很简单，这里就不画图演示了。

索引使用策略

最左前缀

上面已经提到过，对于字符类型的B树索引在查询时仅靠前缀字符模糊查询也可使用索引进行快速扫描。例如在对上面的c_user表进行下面查询时，

根据explain可以得出如下结果：

这样的话，在创建联合索引时的列顺序至关重要。正确的顺序通常优先考虑查询使用，并且同时具备排序和分组的需要。

覆盖索引

在上诉cuser表中执行语句：select id from cuser where name = 'Acheson'

这时id列的值已经在联合索引indexnamebir上了，所以不需要回表操作可直接提供结果。这种情况下不需要在去主键中查询数据，这就叫做覆盖索引。它减少了查询索引的次数，性能能得到明显的提升。但是不是所有的索引都可以使用覆盖索引，哈希索引，全文索引等都不存储列值，所以在这些索引中不存在覆盖索引操作。

通常在使用到覆盖索引的操作时，在EXPLAIN信息的Extra列会显示“Using index”。例如刚才的操作的EXPLAIN如下：

再观察语句 select * from c_user where name = 'Acheson' 的EXPLAIN信息：

可以看到 Extra列没有任何信息。