索引分类概览

现在已经知道了MySQL中的索引设计的数据结构是基于B+树的，但这对于索引这个概念而言还只是冰山一角。在深入MySQL的索引实际应用之前，必须对索引有个全局理解。这篇文章就讨论一下围绕着索引产生的相关前置知识。

索引数据模型

首先就要谈和B+树平行的数据模型概念，实际上MySQL中并不是只有B+树这样一种实现方式。数据模型的常规设计可以分为如下三类。

数组

最好理解的一种，毕竟算是日常用到最多的一种数据结构了。优缺点也很明显，查询高效，更新低效。对应到数据库中的话，就是等值查询和范围查询的性能都非常高，但更新数据的性能就太低了。这样优缺点明显的模型注定只能用到特殊的只查不改的场景下，比如静态存储引擎。

二叉搜索树

这也就是上篇文章中详细分析的数据模型了，作为查询和更新的效率折中模型，被广泛应用到数据库中。

哈希表

也是比较常用的基于key-value的存储结构，通过Hash算法将key转化为一个存储value的确定位置。原理很简单，不过需要关注一个Hash冲突问题：不同的输入可能被映射到同一个位置上，一般解决方案是在确定位置上再设计一个桶结构存储Hash冲突的数据。

了解了哈希表的数据结构后，优缺点也就很明显了。首先是优点：

• 等值查询的性能很高，相比于数组的O(n)更进一步的提升到了O(1)

缺点如下：

• 因为哈希表的无序性，不支持范围查询和排序。
• 即使是等值查询也需要避免hash冲突带来的性能下降。

综上可以看出同样是在特定场景下才能发挥优势的数据模型，相比于数组更为极端一些：排斥范围和排序查询需求，但在等值查询上做到最优。比如Redis就是一个很好的实例。

当然，由于hash索引的等值查询效率实在优秀，MySQL也针对了一些特定场景将其融合到了其设计中。就是自适应Hash索引。

如果某个数据页经常按照某个条件被访问，MySQL就会将这个数据页的地址根据条件存储到Hash表中，这样的话在下次查询就可以跳过B+树索引，采用Hash索引更迅速的得到结果。

可以通过innodb_adaptive_hash_index这个变量控制是否开启这个特性。相信根据变量名你也注意到了，这个特性其实是InnoDB提供的，也是InnoDB的三大关键特性之一。另外两大特性在之后的文章的合适部分再介绍。

按物理实现分类

了解了索引的常用数据模型之后，就可以进一步的探究在InnoDB中更细节的索引划分了。先从最常规的一次索引查询入手：假设我们有一个主键为ID，索引为k的表如下。

如果使用主键查询，则只需要搜索主键构成的索引树。使用k查询的话，要先从k构成的索引树得到结果行对应的主键ID，再根据ID回到主键索引树得到结果。

前者叶子节点中存储的是真实的行数据，也就是说数据行和键值聚簇的存储在一起，这种物理实现称为聚簇索引。后者的叶子节点中不保存真实行数据，只保存真实行数据的指针，也就是数据行和键值分离，不关心数据行的存储结构，这种物理实现相对的就叫非聚簇索引。可以看到非聚簇索引要经过两次查询，第二次查询的过程也就是俗称的回表。

正常来说非聚簇索引的查询效率是不如聚簇查询的，但InnoDB中除了主键索引的大多数索引都是非聚簇索引，因为聚簇索引插入和更新的代价相当高，包括行移动和可能的数据页分裂操作，非聚簇索引相比之下的查询效率降低也还是可以接受。

按功能分类

了解了索引的物理实现，再看在物理实现下的不同索引的功能。先从最特殊的主键索引入手。

主键索引

因为每张表都会有一个主键索引作为约束，即使不声明也会隐式的创建，可以把主键看做这张表的ID。简单来说，就是在普通索引下，新增了数据列的唯一性约束，非空值约束，同时每个表只能有一个，物理实现上使用了聚簇索引。

唯一索引

也就等于在主键索引的数据列唯一性约束了。唯一索引的数据列只包含各不相同的值，除了避免数据重复外，简化了索引管理，还能提高查询速度。

普通索引

就是常规索引，唯一的需求就是新建非聚簇索引对应的B+树提高查询速度。

全文索引

主要用来完成查找文本中的关键字需求，实现和常规索引有很大区别。比如要匹配“abc"这一串文字，正常来说会使用like查询，但没有用左边前缀搜索时是无法命中普通索引的，所以就需要使用全文索引。对于小型的全文索引需求，InnoDB有内置的全文索引，如果处理更复杂的场景，更推荐Elasticsearch这样的专用全文搜索引擎。

空间索引

B+树索引很难处理空间相关的场景数据。想像一下要搜索(x, y, z)的三维数据，只能根据xyz三个字段联合索引，但联合索引有优先级的区分，空间索引的数据都是平行关系。进一步的，当空间数据不止是三维，成多维，线或者面时都是更麻烦的问题，所以需要一种独立的空间索引模式处理这些场景。MySQL也提供了创建空间索引的对应方案。

按字段数量分类

索引不仅可以根据单字段创建，还可以组合多个列一起创建联合索引。基于此又衍生出多种查询优化的相关规则。

覆盖索引

之前提到了基于普通索引的查询有回表的过程，因为普通索引树的叶子节点只记录的主键名。那如果我们查询的信息刚好是主键呢？理所当然的，普通索引树上就能直接返回结果，不需要回表。这种普通索引树已经覆盖了我们需求的查询，就叫做覆盖索引。

基于此，正常来说，覆盖索引只能在主键上的查询起作用，但如果使用联合索引结合覆盖索引，就能优化到具体目标字段了。举例来说，有张表有根据ID频繁查找姓名的需求，我们就可以建立ID和姓名的联合索引。

最左前缀原则

一个索引不仅可以使单字段或者联合字段的查询上收益，还满足最左前缀原则：只要查询字段是字符串索引的最左X个字符，或者联合索引的最左N个字段都能利用该索引提高性能。

举个例子，如果以name建立索引，like查询不以%开头的条件都可以利用上该索引。如果以name和age建立联合索引，单独对name查询也可以利用上该索引，但对age查询则不行。

小结

这篇文章从全局的角度介绍了一下数据库中常见的索引类型，之后就该根据具体案例分析不同场景下应该建立什么类型的索引了。