MySQL中一些关于索引的知识点

什么是索引

索引是一种数据结构，其作用就是用来提高数据查询效率。比较常用的比喻就是将其类比为书籍的目录。通过目录可以精确的找到某一章节的内容所在页。

在数据量较小的时候使用索引其实也没有什么意义，即使没有索引需要一条一条遍历数据对于计算机来说也并不需要太多时间。而一旦数据量较大，要保证我们能正常的对外提供服务，保证用户使用体验那么索引就是必要的了。

索引类型

索引时一种数据结构，为了应对不同的场景会有多种实现。在MySQL中主要就是Hash索引和B+Tree。

Hash索引

hash相信大家应该都很熟悉，hash是一种key-value形式的数据结构。实现一般是数组+链表的结构，通过hash函数计算出key在数组中的位置，然后如果出现hash冲突就通过链表来解决(拉链法)。当然还有其他的解决hash冲突的方法。hash这种数据结构是很常用的，比如我们系统使用HashMap来构建热点数据缓存，存取效率很好。

hash结构存数据首先通过计算key的hash值来确定其在数组中的位置，如果有冲突就在该数组位置建一个链表。这样很明显有几个问题：

• 即使是具有相同特征的key计算出来的位置可能相隔很远，连续查询效率低下。即不支持范围查询
• hash索引存储的事计算得到的hash值和行指针，而不存储具体的行值，所以通过hash索引查询数据需要进行两次查询(首先查询行的位置，然后找到具体的数据)
• hash索引查询数据的前提就是计算hash值，也就是要求key为一个能准确指向一条数据的key，所以对于like等一类的匹配查询是不支持的。

所以我们可以知道的是hash索引适用于快速选取某一行的数据。

B+Tree结构

从名字上看这明显是一种树结构，在大学期间数据结构的课本上树结构是必讲的。树结构是一种特别重要的数据结构，在很多地方都会使用到。

上面我们说到hash索引无法进行范围查询，在树结构中也有一种方便进行有序查询的结构--二叉搜索树。二叉搜索树的结构中要求父节点的值大于左孩子节点并且小于右孩子节点，如下图。

上图中二叉树的查询的时间复杂度为O(log(n))，当然要保证O(log(n))的时间复杂度就需要保证二叉树时刻保持平衡。

而在MySQL索引中虽然也使用了树结构，但是并不是使用的二叉树。因为在数据库中数据最终都是存放在磁盘上的，而如果树的节点过多的话，那么在节点之间转移会花费较多的时间。在MySQL的实现中选择将更多内容放在同一个节点，对同一个节点的操作转入在内存中完成，减少在外存中节点之间转移的次数，以达到提高效率的目的。这就是B+Tree，在B+Tree的实现中一个三层的树结构就基本上可以满足我们几乎所有的需求了。

B-Tree

要了解B+Tree首先就得了解B-Tree，B-Tree是一种平衡树，这里的B指的是Balance而不是Binary，更确切的说B-Tree是一种多路平衡搜索树。

多路平衡搜索树如下图：

这是一种2-3树，意思就是每个节点存有两个值，同时每个节点分支数为3，从上图中可以看出来着中结构很适合查询数据。每个节点的左子树的值都是小于当前节点中最小的值，中间的子树的值全都是在当前节点两个值的中间，而右子树的值全都大于当前节点的最大值。

比如我们要查找24这个值：

1. 首先从根节点判断24在根节点(15,25)之间，所以左右子树排除，从中间查找。
2. 然后找到中间子树的根节点(18,22)，比较发现24大于该节点最大值，排除左子树和中间子树。
3. 找到右子树，判断节点大值刚好等于24，查询结束

基于上面的流程可以总结B树的搜索：

• 从根结点开始，对结点内的关键字（有序）序列进行二分查找。
• 如果命中则结束，否则进入查询关键字所属范围的子结点；
• 重复上面的流程，直到所对应的子节点为空，或已经是叶子结点；

可以看出其搜索性能相当于在关键字集合内做一次二分查找。从这里看来好像B-Tree没有什么问题，但是需要注意到的是在B-Tree中每一个节点都是存储索引关键字以及其代表的具体行数据。而在MySQL中数据库加载数据是以页为单位加载，每一页的大小是固定的(默认16k)。如果每一个节点都存储所有的值，那么一页中能存下的节点就会很少，一次查询可能就会进行多次从内存中去加载数据，导致性能降低。

B+Tree

B+Tree是对B-Tree的一个变种，让其更加适应于进行外部存储文件索引。

两者之前最大的不同就在于B-Tree的每个节点都存储所有的数据，而B+Tree需要存储的数据都在叶子节点上，并且增加了顺序访问指针，每个叶子节点都有指向下一个相邻的叶子节点的地址。这样的结构保证了在一个内存页中可以存下更多的索引节点，并且更加适合进行范围查询。

索引

因为存储引擎负责实现索引，所以接下来讨论索引都是基于MySQL的InnoDB引擎。

聚簇索引

聚簇的意思是表示数据行和相邻的键值聚簇的存储在一起。一些数据库允许选择具体的某一个索引作为聚簇索引，而在InnoDB的实现中直接将主键索引指定为聚簇索引。如果没有定义主键，InnoDB 会选择一个唯一的非空索引来代替主键索引。如果同样没有定义这样的索引，InnoDB会隐式定义一个主键来作为聚簇索引(row_id)。

聚簇索引实例如图：

非聚簇索引索引

在InnoDB中除主键索引外其他都是非聚簇索引，所以也叫非主键索引。非主键索引的叶节点并不是存储一行的值，而是存储具体行的主键值。不满足聚簇的定义。

非聚簇索引实例如图：

聚簇索引和非聚簇索引在查询时的差异

由上面的两种索引实例图就可以看出来，在查询时如果是通过主键索引查询的话直接查询到数据行然后返回。但是如果是通过非主键索引查询的话首先需要通过该索引确定主键，然后通过得到的主键从主键索引中查到具体行的数据，后面的通过得到的主键从主键索引中获取数据的过程被称为回表。

回表的过程使得通过普通索引查询较主键索引查询多了一步，在很多情况下效率相对较低。所以在我们的查询过程中如果能够仅通过主键确定数据那最好就是直接使用主键进行查询。

覆盖索引

上面介绍了通过非主键查询会有一个回表的过程，但是需要注意的是并不是每一个查询都存在回表这一步，对于一个普通索引来说其叶节点存储的是主键的值，那么假设我现在需要的数据也仅仅就是主键的值呢？通过普通索引取到主键的值后就并不需要再到主键索引中查，那么也就不存在回表这一过程了。

上面例子中该非主键索引已经存在了我们所需要的值，所以该索引也被称为覆盖索引。覆盖索引并不是一个固定的结构，可以使单索引(一个字段的索引)，也可以使复合索引，凡是能够直接提供查询结果而不需要进行回表过程的都可以被称为覆盖索引。

很多时候我们不可能仅仅通过主键来确定数据，使用普通索引可能会导致低效，所以覆盖索引在日常开发过程中也是一个很常用的性能优化的手段。

当然覆盖索引页并不都是好的，比如我现在建立了一个索引index(a,b)。由a，b两个字段来建立索引，好处已经说过了就是查询ab字段时不会回表，但是如果仅仅通过b字段来查询就无法走这个索引了。建立的索引的索引项是按照索引定义里面出现的字段顺序排序的。

最左前缀原则

假设现在存在索引index(a,b)，那么如果通过a和b来查询能够应用该索引，单独使用a来查询也能应用到该索引，但是如果单独使用b来查询则无法应用到该索引。这就是最左前缀原则，在匹配索引时回匹配索引最左边的n个字段，能匹配上就可以应用该索引。

由于最左前缀原则的存在也就要求我们在建立索引时可能需要考虑更多的事情。

首先需要清楚的事索引是一种数据结构，建立索引时需要消耗存储空间的，所以索引并不是建立的越多越好，而是应该根据需求尽可能的减少索引的数量。

而最左前缀原则的存在就使得一个联合索引可以被当成多个索引来使用，当然前提是设计好索引中字段的顺序(实际上最左前缀原则也并不是仅仅适用于联合索引，对于字符串索引也使用，字符串索引中最左n个字符相当于联合索引中的最左n个字段)。

比如index(a,b)，有了这个索引后我们就不需要单独为a建立索引，所以在设计联合索引时一般将使用频率较高的字段放在前面。

然后是将区分度较高的字段靠前，区分度就是字段中值的重复率，重复率越低区分度越高。比如性别就不适合作为索引，区分度越高的字段经过一次筛选能过滤掉更多的行。

然后还需要考虑的是字段的大小，由于索引也需要占据空间所以一般选用较小的字段。