轻松理解 MySQL InnoDB 索引、B+树索引、查询原理

前言

索引对于DB查询的性能起到至关重要的作用。对于索引如何提升查询性能，通常都会拿查字典来做类比。字典前面会有拼音索引，我们查字典会先查拼音索引，以此来提高查字典的速度。对于这个类比，我们可以思考的更深入点，看看通过拼音索引提升查询速度的根本原因是什么。我们考虑如下几个问题：

1、通过拼音索引能直接定位到字的具体位置吗？

不能，拼音索引只能定位到字所在的页，如果想找到所要的字或者词，还需要在页中再次定位。这个过程和InnoDB的索引设计相同，通过索引只能定位到数据所在页。

2、定位到页后，如何定位到具体字的？

定位到页后，我们一般是从第一个字开始向后查找我们所要的字。或者一眼望过去随机找到所要的字。如果DB也采用这种方式将会比较耗时，因为DB中一页中存储的数据比较多。InnoDB采用了稀疏索引来提升查询页内查找速度。页内数据按主键顺序存放，为主键创建稀疏索引。顾名思义，稀疏索引只为部分键值建立索引，通过索引直接定位到数据所在区间段。区间内再进行查找。这样可以兼顾速度和空间占用。关于稀疏索引我们后面再详细介绍。

3、如果查找“照”这个字，使用拼音索引定位拼音zhao的过程是怎样的？

你肯定不会从A开始往后逐字母查到Z。你应该会先定位到拼音索引最后几页，然后翻到最后一页，在此页中找到Z。提出个问题，其实我是想出入索引的查找机制，也就是如何高效的在索引中定位到想要的值。按照顺序查找显然是效率最低的查找方式。人类可以通过自己的经验得出Z在索引的最后，但是DB没有这个能力。DB依赖查找算法来定位数据。查找相关算法我们应该再熟悉不过了，InnoDB采用的是B+树的数据结构来组织索引数据以提升查找速度。在下一节会重点介绍相关算法。

通过和字典类比，我们已经大致了解了索引的作用和定位数据的过程。数据库定位数据和用字典查字的过程很像。我们在学习索引的过程中，可以多回顾字典查字的例子。

索引相关算法

二分查找

如果不考虑查找算法，索引键值可以以数组或者链表的数据结构来保存。为了查找更快，我们进一步将索引值按字典顺序保存。这样我们就可以采用二分法快速查找。

二分查找法首先需要将数据按顺序排列。先用查找的值比较中间位置数值。如果查找的数值更小，那么查找的范围缩小一半，只需要再按同样的方式查找中间位置的左半部分。反之，则在右半部分进行查找。

可以看到二分查找法，每比较一次都会缩小一半查找范围，直至找到数值。

我们以下图为例，看看用二分查找法查找 52 所在位置的过程：

数据库中的检索也会用到二分查找法。我们都知道数据库采用B+数组织索引，但是通过B+树只能定位到你所要的数据所在的页。在页的内部定位数据时，采用的是二分查找法。字典通过拼音索引也只能定位到页，页内需要再次查找到你所要的字。

二叉树和平衡二叉树

二叉树

二叉树左子树键值小于根节点键值，右子树键值大于根节点键值。我们看下面这个二叉树：

可以看到以上二叉树中查找52的过程也是三步，查找路径是37->56->52。 这和二分查找法完全一样。这是因为这棵二叉树额外满足了其他的一些条件。

还是这些数据，我们还可以构造如下二叉树：

可以看到这次的二叉树直到第8层才有了左侧子树。1到7层虽然也满足二叉树的定义，但实际上已经退化为链表。用这个二叉树进行查找，效率几乎和顺序查找一样了。

平衡二叉树

第二个二叉树为什么查找效率会低呢？因为这个二叉树失衡了，左轻右重，已经近乎退化为链表。失去了二叉查找树的意义。此时我们引出平衡二叉树。平衡二叉树在二叉树的基础上，还需要满足任意根节点的左右子树高度差不能超过1。上文二叉树的两个例子，第一个是平衡二叉树，第二个不是平衡二叉树。

平衡二叉树的查找效率非常高。因为它的根节点就是二分查找的中间位置数据。每一颗子树都是如此。换句话讲，平衡二叉树已经按照我们想要的二分查找方式构造好了数据结构。

平衡二叉树的数据结构匹配查询方式，所以查询很快。但反过来维护平衡二叉树的数据结构，则需要付出较大的代价。有更新的发生时，可以通过一次或者多次左旋、右旋来保持平衡。本文就不再展开讲平衡二叉树的维护。

B+树

B+树也是一种平衡查找树，它是为磁盘或其他直接存取辅助设备设计的一种平衡树。我们直接看下面的B+树例子，该例子是以学号为索引构造的学生数据B+树：

可以看到非叶子节点存储的只是索引键值（学号）以及子节点的指针。完整数据存储在叶子节点中。叶子节点中的数据是按照顺序排列的。叶子节点存储完整数据，非叶子节点则是构造的索引值的平衡树。对于给定的索引值，可以通过B+树快速定位到叶子节点。然后在叶子节点内部再次定位到完整的一行数据。

在B+树的维护过程中可能会出现拆分页的现象。由于B+树主要用于磁盘，这意味着大量的磁盘操作。因此如果表的索引很多，在大数据量写入过程中，由于需要大量维护B+树的操作。那么磁盘IO和CPU使用都会大幅上升。

B+树索引

InnoDB 中采用 B+ 树数据结构来存储索引，所以称之为B+树索引。B+树索引又分为聚集索引和辅助索引。每张表有且仅有一个聚集索引。简单来说聚集索引就是以主键构造的B+树索引。而辅助索引则是根据表中索引列构造的B+树索引。

聚集索引

InnoDB中，表中数据按照主键顺序存放。聚集索引就是按照主键顺序构造的B+树索引。聚集索引中，叶子节点其实就是真实存放数据的页。这意味着聚集索引的叶子节点存放完整数据。而非叶子节点存放的则是主键值和子节点的引用。因此通过主键检索非常快，原因是能够直接定位到数据。

辅助索引

我们经常说为表加索引，实际添加的就是辅助索引。辅助索引的叶子节点并不是数据存储的页。这是为什么呢？首先，B+树的叶子节点是有序的。数据页已经按照主键顺序存储了，因此就无法再按照别的顺序存储。此外，如果我们按照添加的索引字段顺序把完整的数据多存储一份，不但会有很大的冗余，而且当数据发生变化时会有一致性的问题。这也是不可取的。因此，InnoDB采用的方式是，辅助索引的叶子节点中存储的数据只是主键值。叶子节点中的主键值按照当前索引字段的顺序保存。

使用辅助索引查询时，在辅助索引B+树上只能定位到符合条件的主键值。数据库拿到主键值后还需要用聚集索引再做一次查询拿到完整的数据。

稀疏索引

如果我们不是为所有的数据都加上索引，而是以一定的步长去添加索引，那么这就是稀疏索引。

我们看个例子，学生表中有10名学生的数据，按照学号建立索引如下：

如果我们按照3为步长来索引这10名学生（稀疏索引），那么索引如下：

可以看到稀疏索引只能定位到某个学生的所在区间段。区间段内需要二次查找。例如我们想要查询学号为5的学生数据，通过稀疏索引我们先定位到学号为4的数据位置，然后再向下查找一次，找到学号为5的学生数据。稀疏索引其实是以时间换取空间，从而达到更好的平衡。

数据库页内部的查找使用了稀疏索引。数据页的一个组成部分叫做 Page Directory。Page Directory 中按顺序存储了数据的主键和数据在页中的相对位置。并不是每条数据都会被索引到 Page Directory。而是以一定步长跳跃的选择数据保存，也就是稀疏索引。通过 B+ 树索引定位到具体的页后，页内部再通过 Page Directory 定位到数据的具体位置。

索引查找示例

我们通过下面这个例子，来总结下InnoDB通过索引查询数据的过程。

我们有如下 student 表：

CREATE TABLE `student` (
  `id` INT NOT NULL,
  `name` VARCHAR(20) NULL,
  `age` INT NULL,
  PRIMARY KEY (`id`),
  INDEX `idx_name` (`name`)
);

id作为主键，InnoDB会为id创建聚集索引。此外还为name建立了辅助索引。

查询 name=xxx 的记录。查找的过程是这样的：

自适应哈希

哈希表是一种查询速度很快的数据结构，一般情况下只需要 1 次查找就可以定位到数据。而 B+ 树的查找速度和自身的高度有关系，n 层的 B+ 树至少需要 n 次查询才能定位到数据。因此可以看到哈希表会比 B+ 树检索速度更快。

InnoDB 通过监控索引页的使用，如果分析出建立哈希索引速度会更快，就会建立哈希索引。之所以叫做自适应哈希索引，是因为哈希索引的建立由数据库自己来控制。

如果对于某张表的查询一直以同样的字段作为检索条件，那么可能会触发自适应哈希索引的建立。例如一直使用where a=xxx查询，但是如果中间穿插 where b=xxx或者 where a=xxxx and b=xxx，则不会创建自适应索引。此外自适应哈希的建立还需满足如下要求：

1、以同样的查询条件查询100次

2、通过同样的方式查询了某个页N次。N=页中数据总数/16

通过以上建立哈希索引的条件可以看出，数据库在寻求效率最高的方式。哈希索引固然检索更快，但是建立哈希索引同样需要成本，不管是时间还是空间。只有在大量使用某个索引列做查询，并且频繁定位到同一个页的时候，数据库才认为有必要建立哈希索引。

索引使用

Cardinality值

通过show index from table_name可以看到DB中索引的情况。列出的属性中你可以找到Cardinality，对应的值是一个数字。代表的含义是表中此索引唯一值的数目估算值。这个值越接近行数，意味着索引重复值越少。此时索引的意义会更大。如果索引的重复值很多，比行数小很多，那么此索引并不会为搜索性能带来很大提升。

搜索优化器会更具此值来判断是否走索引。但是这个值并不会实时更新，我们可以根据analyze table命令来刷新Cardinality值。

InnoDB对Cardinality的更新发生在insert或者Upate操作。为了避免给数据库带来过大的负荷，并不是每次都会去计算。更新的策略为：

1、1/16的数据发生了变化

2、stat_modified_counter>2000000000。这个值是一个计数器，表示数据发生变化的次数

计算过程是随机对8个叶子节点进行采样，计算不重复的记录数量。求出8个叶子节点的平均值后，用平均值乘以叶子节点总数。

公式如下：

(P1+P2+P3+P4+P5+P6+P7+P8)*Total/8

由于8个叶子节点随机选取，因此同样的数据，计算出的Cardinality可能不同。

联合索引

联合索引指的是对表中多个列进行索引。例如我们创建如下员工上班记录表：

我们为employee_no和sign_in_date创建联合索引。联合索引同样采用的是B+树的数据结构，那么这个联合索引B+树的叶子节点存储的数据是按照什么排序的呢？

这是一个辅助索引，因此叶子节点存储的数据是索引值。叶子节点存储数据的排序规则和你创建联合索引时列的顺序保持一致。比如索引顺序是 employee_no在先，sign_in_date在后，那么先按employee_no排序，重复的话再按照sign_in_date排序。

这个顺序会带来如下两个特性：

1、最左匹配原则。多个字段的联合索引，按照索引创建的字段顺序，如果你的检索条件中使用索引左边连续的字段。那么检索字段都会会走索引的。如果不连续使用索引字段，那么只有左侧连续的字段可以走索引。

举个例子，一张表有a,b,c三个字段，联合索引按照a,b,c顺序创建。检索条件和索引使用情况如下：

	检索使用字段	走索引情况
1	a,b,c	3个字段都走索引
2	a,b	2个字段都走索引
3	a,c	a走索引，c不走索引
4	b,c	2个字段都不走索引

情况1和2，因为你符合最左匹配原则，所以使用的字段都会走索引。情况3，由于没有连续使用索引字段，跳过了b，所以只有a走索引，c不会走索引。第4种情况，由于最左侧的a没有作为检索字段，所以b,c都不会走索引。
为什么只会最左匹配呢，这是因为联合索引叶子节点存储数据的顺序是按索引字段顺序从左到右进行排序的。因此只有索引字段是按照创建顺序从左到右连续用来检索，才符合B+树构造的顺序，从而才能通过B+树快速查询。

2、某些场景可以避免一次排序。例如第一个例子中，索引顺序是employee_no、sign_in_date。如果我们查询某个employee，最近三次的sign_in_date。由于sign_in_date在联合索引中，已经排好序，所以DB不会再做排序操作。如果这张表只对employee_no创建了索引，那么同样的查询，DB还需要做一次排序操作。

覆盖索引

覆盖索引的含义是，通过辅助索引即可查询到所需要的数据，不需要搜索聚集索引中的记录。辅助索引的数据包含索引键值以及主键。那么只要检索出的字段在这个范围内，就可以仅使用一次辅助索引即可完成。例如某张表主键为a，b，c。还有一个辅助索引，字段为d，e。那么如下查询只会走辅助索引，不需要再去用聚集索引查询具体数据：

select a, b, c, d, e from table where d = xxxx

字段a,b,c,d,e任意组合都会只走辅助索引。

索引提示

Mysql 支持使用索引提示显示告知索引优化器使用哪个索引。通常我们用到索引提示是下面两个场景：

1. 索引优化器错误的使用了索引，导致查询很慢。此时我们可以通过索引提示强制优化器选择指定的索引
2. 某张表的索引很多，索引优化器在选择索引的时候会消耗比较长的时间。此时我们可以直接指定索引

我们可以通过以下方式使用索引提示：

select * from table use index(a) where a=1 and b=1

通过user index可以告知索引选择器可以使用某个索引，但是索引选择器可能并不会最终选择这个索引。如果想强制优化器使用你指定的语法，可以使用force关键字，如下：

select * from table force index(a) where a=1 and b=1

上面的sql会指定优化器使用index a。

总结

本文从查字典的过程做类比讲起，先讲解了索引相关的基本算法，然后重点介绍了B+树索引。最后讲了一些索引使用的小技巧。数据库的设计和字典十分相近，数据库的数据也存储在页上，对索引的使用、查找数据的过程也是类似的。

数据库通过B+树加快索引查找速度，页内查找则采用稀疏索引的方式。而查字典则是依赖人脑的智能，查找方式并不固定。可能是凭经验，比如字母Z应该在拼音索引最后面。或者是遍历查找，比如拼音定位到某一页后，页内再定位到具体的字。我很期待未来数据库可以引入人工智能来加速查询。