说说MySQL索引相关

关于索引，这是一个非常重要的知识点，同样，在面试的时候也会被经常的问到；

本文描述了索引的结构，介绍了InnoDB的索引方案等知识点，感兴趣的可以看一下；

引入

本文参考文章：MySQL的索引

回顾

在上篇文章中我们说到InnoDB的数据页结构 ,了解到了 InnoDB 数据页的 7 个组成部分，知道了各个数据页可以组成一个 双向链表 ，而每个数据页中的记录又可以组成一个 单向链表 （按照大小排序），每个数据页都会为存储在它里边儿的记录生成一个 页目录 ，在通过主键查找某条记录的时候可以在 页目录 中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。也了解到了在页中各个部分的作用是啥，如果没看的，建议回去看一下。

附上地址：InnoDB的数据页结构

索引

起步

首先，我们先来了解一下如果没有索引的话，当我们查找一条记录的时候是怎样进行的，当然，我们就说精准匹配的时候，先附上一句 SQL 语句：

SELECT column FROM table WHERE column = xxx;
复制代码

上面这个类型的语句是我们常用的，也比较简单，下面我们来看一下：

在一页中查找

假设这个表中的数据量比较小，只有一页的数据，这个时候的查找分为以下情况：

• 当条件为主键
  • 这个过程我们在上篇文章已经说过了，通过页结构中的 Page Directory ，通过二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。
• 当条件是其它列
  • 当条件是其它列不是主键的时候，数据页中是没有对应非主键的而建立页目录的，所以无法像主键那样通过二分查找定位，只能通过最笨的方法，直接遍历整个数据页一条一条的进行匹配。当然，这种方法的效率就不说了。

在多页中查找

上面的情况是一种假设，但真实的情况还是需要现在整个居多，一个表中的记录一般都是有很多的数据页组成的，同时，在多个数据页中的查找方式是这样的：

• 首先需要找到该记录对应的页
  • 上面假设的是只有一页的数据，所以我们根据对应主键的而建立的页目录进行查找。但是现在没有针对页的页目录，所以我们不能快速的定位到记录所在的页，就只能从第一页开始进行遍历进行慢慢从查找，这样一说可能您看着就头皮发麻了，要是很多记录怎么办？那得等到什么时候？
• 从页中查找对应的记录。
  • 这个过程我们就不再说了

准备

我们先准备一个表：

mysql> CREATE TABLE index_demo(
    ->     c1 INT,
    ->     c2 INT,
    ->     c3 CHAR(1),
    ->     PRIMARY KEY(c1)
    -> ) ROW_FORMAT = Compact;
Query OK, 0 rows affected (0.03 sec)
mysql>
复制代码

这个表使用 Compact 行格式来实际存储记录的。为了我们理解上的方便，我们简化了一下 index_demo 表的行格式示意图：

先介绍一下上面几个部分代表的含义：

• record_type : 记录头信息的一项属性，表示记录的类型， 0 表示普通记录、 2 表示最小记录、 3 表示最大记录、 1 我们还没用过，等会再说～
• next_record : 记录头信息的一项属性，表示下一条地址的偏移量，为了方便大家理解，我们都会用箭头来表明下一条记录是谁。
• 数据列 ：就是各个数据列的值，其中我们用橘黄色的格子代表 c1 列，深蓝色的格子代表 c2 列，红色格子代表 c3 列。
• 其它信息 ：除了上述 3 种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

但放入一些记录之后的在页的图如下：

一个简单的索引方案

刚才说了，为什么找记录对应的页的时候需要依次遍历查找呢？因为没有对应页的目录，没有的话怎么办呢？建一个不就行了？我们来看看。

我们知道一页中的记录是 按照大小进行依次链接的 单向链表 ，所以，我们使用页建立目录也需要遵守同样的规则，所以我们首先需要保障第二页的记录的主键值是大于第一页的。所以就有了一个前提了。

• 下一个数据页的主键值必须大于上一个页中的主键值。

为了下面我们更好的说明，我们先做一个假设：

假设我们的每个数据页最多能存放 3 条记录（实际不是），有了这个假设之后我们向 index_demo 表插入 3 条记录：

mysql> INSERT INTO index_demo VALUES(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0
mysql>
复制代码

那么页中的图如下：

按主键进行大小 排序 的单向链表；

上面我们做了假设，一个页中最多只能放三条记录，这个时候我们再插入一条数据：

mysql> INSERT INTO index_demo VALUES(4, 4, 'a');
Query OK, 1 row affected (0.00 sec)

mysql>
复制代码

这个时候应该重新再分配一个页：

咦？怎么分配的页号是 28 呀，不应该是 11 么？需要注意的一点是，新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。

上面我们也说了，要先建立目录需要遵守规则，上面图中的页明显没有，所以需要进行移动，过程如下:

这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页的主键值必须大于上一个页中的主键值。

• 目录建立

上面说到条件已经满足了，下面需要进行目录的建立了。

我们接着往表中插入数据，得到以下的结构：

注：数据页的编号可能并不是连续的

现在我们来针对每一个页来建立目录项，每个目录项包含以下两个部分：

• 页目录中的一部分是存储的该页中最小的主键值，我们用key来表示；
• 页目录中的另一部分是页号，我们用page_no表示；

见下图：

看到这样的图了，大家再来想想，我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为 20 的记录，我们来看一下查找记录的过程：

• 先从目录项中根据二分法快速确定出主键值为 20 的记录在 目录项3 中（因为 12 < 20 < 209 ），它对应的页是 页9 。
• 再根据前边说的在页中查找记录的方式去 页9 中定位具体的记录。

针对数据页做的简易目录就搞定了，怎么样？这样是不是好多了，可能大家也知道了，没错，这个目录也被我们称作 索引 。

InnoDB的索引方案

上面的方案是一个简单的索引方案，因为我们假设所有目录项都可以在物理存储器上连续存储，这样的方案存在几个问题：

• InnoDB是使用页作为管理存储空间的基本单位，最多只能保证16KB的连续存储空间，当表中的记录慢慢增多的时候就需要非常大的连续的存储空间才能把所有的目录放下。
• 再从我们常做的操作来分析，当我们对表中的记录进行增删的时候，假设我们对以上页28中的记录进行删除，那么页28页就没有存在的必要了，同时目录2也一样没有存在的必要，这个时候就需要把目录2后面的目录项往前移动，影响这么大可不是什么好办法。

忠于以上的情况，我们需要有更好的方式。

设计 InnoDB 的大叔们需要一种可以灵活管理所有 目录项 的方式。他们灵光乍现，忽然发现这些 目录项 其实长得跟我们的用户记录差不多，只不过 目录项 中的两个列是 主键 和 页号 而已，所以他们复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为 目录项记录 。那 InnoDB 怎么区分一条记录是普通的用户记录还是 目录项记录 呢？别忘了记录头信息里的 record_type 属性，它的各个取值代表的意思如下：

原来这个值为 1 的 record_type 是这个意思呀，我们把前边使用到的目录项放到数据页中的样子就是这样：

我们来说一下 目录项记录 和 用户记录 的区别：

1. 目录项记录 的 record_type 值是 1，而普通用户记录的 record_type 值是 0。
2. 目录项记录 只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有 InnoDB 自己添加的隐藏列。

除了上述几点外，这两者就没啥差别了，它们用的是一样的数据页，页的组成结构也是一样一样的（就是我们前边介绍过的 7 个部分），都会为主键值生成 Page Directory （页目录）以加快在页内的查询速度。

所以现在根据某个主键值去查找记录的步骤可以大致拆分成下边两步，以查找主键为 20 的记录为例（因为都是从一个页中通过主键查某条记录，所以都可以使用 Page Directory 通过二分法而实现快速查找）：

• 先到存储 目录项记录 的页中通过二分法快速定位到对应目录项，因为 12 < 20 < 209 ，所以定位到对应的记录所在的页就是 页9 。
• 从 页9 中根据二分法快速定位到主键值为 20 的用户记录（这个过程不再多说）。

虽然说目录项记录中只是存储主键值和对应的页号，由于一个页中只有16KB的大小，能存放的目录项记录也是有限的，所以当一个页存储目录项满了之后再有的话就需要再来一个存储目录项记录的页。

为了大家更好的理解如何新分配一个 目录项记录 页的过程，我们假设一个存储 目录项记录 的页最多只能存放 4 条 目录项记录 （请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插入一条主键值为 320 的用户记录的话，那就需要一个分配一个新的存储 目录项记录 的页喽：

以上图中，由于我们新增了一条记录，所以得到了一个新的数据页，里面存放的是数据记录，又因为页30的页目录记录存储满了（上面做了假设，假设每页最多只能存储4条），所以有了页32来存放页31对应的目录项。

因为存储 目录项记录 的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要 3 个步骤：

1. 确定 目录项记录 页；
   1. 我们现在的存储 目录项记录 的页有两个，即 页30 和 页32 ，又因为 页30 表示的目录项的主键值的范围是 [1, 320) ， 页32 表示的目录项的主键值不小于 320 ，所以主键值为 20 的记录对应的目录项记录在 页30 中。
2. 通过 目录项记录 页确定用户记录真实所在的页；
   1. 在一个存储 目录项记录 中定位一条目录项记录的方式说过了（通过二分查找进行定位，找到对应的页）。
3. 在真实存储用户记录的页中定位到具体的记录；
   1. 不多说了。

那么问题来了，在这个查询步骤的第 1 步中我们需要定位存储 目录项记录 的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储 目录项记录 的页，那我们怎么根据主键值快速定位一个存储 目录项记录 的页呢？

其实也简单，为这些存储 目录项记录 的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

如图，我们生成了一个存储更高级目录项的 页33 ，这个页中的两条记录分别代表 页30 和 页32 ，如果用户记录的主键值在 [1, 320) 之间，则到 页30 中查找更详细的 目录项记录 ，如果主键值不小于 320 的话，就到 页32 中查找更详细的 目录项记录 。

随着表中记录的增加，这个目录的层级会继续增加，如果简化一下，那么我们可以用下边这个图来描述它：

其实这是一种组织数据的形式，或者说是一种数据结构，它的名称是 B+ 树。

因为我们把数据页都存放到 B+ 树这个数据结构中了，所以我们也把我们的数据页称为 节点 。从图中可以看出来，我们的实际用户记录其实都存放在 B + 树的最底层的节点上，这些节点也被称为 叶子节点 或 叶节点 ， 其余的节点都是用来存放 目录项 的 ，这些节点统统被称为 内节点 或者说 非叶节点 。其中最上边的那个节点也称为 根节点 。

从图中可以看出来，一个 B+ 树的节点其实可以分成好多层，设计 InnoDB 的大叔们为了讨论方便，规定最下边的那层，也就是存放我们用户记录的那层为第 0 层，之后依次往上加。上边我们做了一个非常极端的假设，存放用户记录的页最多存放 3 条记录，存放目录项记录的页最多存放 4 条记录，其实真实环境中一个页存放的记录数量是非常大的，假设，假设，假设所有的数据页，包括存储真实用户记录和目录项记录的页，都可以存放 1000 条记录，那么：

• 如果 B+ 树只有 1 层，也就是只有 1 个用于存放用户记录的节点，最多能存放 1000 条记录。
• 如果 B+ 树有 2 层，最多能存放 1000×1000=1000000 条记录。
• 如果 B+ 树有 3 层，最多能存放 1000×1000×1000=1000000000 条记录。
• 如果 B+ 树有 4 层，最多能存放 1000×1000×1000×1000=1000000000000 条记录。

你的表里能存放 1000000000000 条记录么？所以一般情况下，我们用到的 B+ 树都不会超过 4 层，那我们通过主键去查找某条记录最多只需要做 4 个页面内的查找，又因为在每个页面内有所谓的 Page Directory （页目录），所以在页面内也可以通过二分法实现快速定位记录。

聚簇索引

上面所说的B+树，我们知道了B+树本身就是一个目录，或者说它本身就是一个索引，它有以下特点：

• 使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
  • 页内的记录是按照主键的大小顺序排成一个单向链表；
  • 各个存放用户记录的页也是根据页中记录的主键大小顺序排成一个双向链表；
  • 各个存放目录项的页也是根据页中记录最小值的主键大小顺序排成一个双向链表；
• B+ 树的叶子节点存储的是完整的用户记录。
  • 所谓完整的用户记录，就是指这个记录中存储了所有列的值。

我们把具有这两种特性的 B+ 树称为 聚簇索引 ，所有完整的用户记录都存放在这个 聚簇索引 的叶子节点处；

换句话说主键索引就是聚簇索引；

聚簇索引 并不需要我们在 MySQL 语句中显式的去创建， InnoDB 存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是， 在 InnoDB 存储引擎中， 聚簇索引 就是数据的存储方式（ 所有的用户记录都存储在了 叶子节点 ） ，也就是所谓的索引即数据。

二级索引

上面也说到了聚簇索引是针对主键值时才能发挥作用，那么当索引为其它列的时候，又是怎样的呢？难道只能从头到尾沿着链表依次遍历记录么？

不，我们可以多建几棵 B+ 树，不同的 B+ 树中的数据采用不同的排序规则。比方说我们用 c2 列的大小作为数据页、页中记录的排序规则，再建一棵 B+ 树，效果如下图所示：

这个B+树与上边介绍的聚簇索引有几处不同：

• 使用记录c2列的大小进行记录和页排序
  • 页内是按照c2列的大小进行排序形成的一个单向链表。
  • 各个存放用户记录的页也是根据页中记录的c2列大小顺序排成的一个双向链表。
  • 各个存放目录项的页根据页中记录的c2列的大小排成的双向链表。
• B+树的叶子节点并不是完整的用户记录，而是c2列+主键这两个列的值
• 目录项记录不再是主键+页号，而是c2列+页号

所以如果我们现在想通过 c2 列的值查找某些记录的话就可以使用我们刚刚建好的这个 B+ 树了，以查找 c2 列的值为 4 的记录为例，查找过程如下：

• 确定 目录项记录 页
  • 根据 根页面 ，也就是 页44 ，可以快速定位到 目录项记录 所在的页为 页42 （因为 2 < 4 < 9 ）。
• 通过 目录项记录 页确定用户记录真实所在的页。
  • 在 页42 中可以快速定位到实际存储用户记录的页，但是由于 c2 列并没有唯一性约束，所以 c2 列值为 4 的记录可能分布在多个数据页中，又因为 2 < 4 ≤ 4 ，所以确定实际存储用户记录的页在 页34 和 页35 中。
• 在真实存储用户记录的页中定位到具体的记录。
  • 到 页34 和 页35 中定位到具体的记录。
• 但是这个 B+ 树的叶子节点中的记录只存储了 c2 和 c1 （也就是 主键 ）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。

大家可能页看到了，当最后定位到对应记录的时候，得到的是一个主键，而得到主键后仍然需要到 聚簇索引 中再查一遍，这个过程也被称为 回表 。也就是根据 c2 列的值查询一条完整的用户记录需要使用到 2 棵 B+ 树！！！

可能您会想，为什么需要回表呢？直接查出来不行吗？

当然可以，但是您想想，一个表中，每当我们建立一个索引就需要把记录拷贝一份到B+树，是不是太浪费存储空间了。因为这种按照 非主键列 建立的 B+ 树需要一次 回表 操作才可以定位到完整的用户记录，所以这种 B+ 树也被称为 二级索引 或者 辅助索引 。

联合索引

我们有时候也会使用多个列做联合索引，也就是同时为多个列建立索引，比方说我们想让 B+ 树按照 c2 和 c3 列的大小进行排序，这个包含两层：

• 先把各个记录和页按照 c2 列进行排序。
• 在记录的 c2 列相同的情况下，采用 c3 列进行排序

为 c2 和 c3 列建立的索引的示意图如下：

• 每条 目录项记录 都由 c2 、 c3 、 页号 这三个部分组成，各条记录先按照 c2 列的值进行排序，如果记录的 c2 列相同，则按照 c3 列的值进行排序。
• B+ 树叶子节点处的用户记录由 c2 、 c3 和主键 c1 列组成。

以 c2 和 c3 列的大小为排序规则建立的 B+ 树称为 联合索引 ，它的意思与分别为 c2 和 c3 列建立索引的表述是不同的，不同点如下：

• 建立 联合索引 只会建立如上图一样的 1 棵 B+ 树。
• 为 c2 和 c3 列建立索引会分别以 c2 和 c3 列的大小为排序规则建立 2 棵 B+ 树。