前言

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

本文描述了索引的结构，介绍了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的大叔们需要