【MySQL从入门到精通】【高级篇】（七）设计一个索引&InnoDB中的索引方案

1. 简介

上一篇文章我们介绍了MySQL的存储引擎 【MySQL从入门到精通】【高级篇】（六）MySQL表的存储引擎，InnoDB与MyISAM的对比

前面介绍了MySQL默认采用的是InnoDB的存储引擎，而InnoDB存储引擎是一种事务型引擎，默认采用的是聚簇索引。

2. 环境

1. 索引是什么？

索引是什么呢？熟悉又陌生的一个名词。想象这样一个场景，现在你要在图书馆里查找一本书，最古老的做法是一本一本书进行查找，直到找到自己想要的那本书。这种方式的缺点也是显而易见的，就是效率太低，图书馆里有成千上万的图书，一本本找要找到猴年马月呀。

那么图书馆是怎么做的呢？图书馆首先会根据图书类别将图书放在不同的区域，然后，在同一个类别下在根据字母顺序对图书进行排序这样当读者需要找书时就方便快捷多了。这种划分方式就可以理解成是索引。

再者，我们在数据中查找某部分内容时，是不是首先翻开目录，根据目录去找我们想要的内容，如果没有目录的话就只能一页页的去查找我们想要的内容了，这效率可想而知。这里的目录可以理解成索引。

同样的，在数据表中存在着数以万计的记录，查找某条记录的话如果一条条查找的话效率也比较低，为了提高查询效率就需要使用到索引了。

总而言之，索引是对数据库表中一列或多列的值进行排序的一种结构。MySQL索引的建立对于MySQL的高效运行是很重要的，索引可以大大提高MySQL的检索速度。

2. 设计一个索引

首先，创建一个测试表

CREATE TABLE index_demo(
   id int,
   name varchar(10),
   age int,
   PRIMARY KEY(id)
)ROW_FORMAT=Compact; 

这个新建的index_demo表有2个INT类型的列，1个varchar(10)类型的列，我们规定id列为主键，这个表的主键，这个表使用Compact行格式来实际存储记录。我们可以简化一下index_demo表的行格式示意图：

我们只在示意图展示记录的这几个部分：

record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录，1表示最小记录，3表示最大记录，1暂时还没用过

next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，我们用箭头表示下一条记录是谁。

各个列的值：这里只记录在index_demo表中的三个列：分别是id、name和age。

其他信息：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。

将记录格式示意图的其他信息项暂时去掉并把它竖起来的效果就是这样：

把一些记录放在页里的示意图就是：

下一个数据页中用户记录的主键值必须大于上一个数据页中用户记录的主键值。

假设：每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设后我们向index_demo表插入3条记录：

mysql> insert into index_demo values(1,'张',10),(3,'李',20),(5,'孙',18);
Query OK, 3 rows affected (0.01 sec)
Records: 3  Duplicates: 0  Warnings: 0

那么这些记录已经按照主键值的大小串联成一个单向链表，如图所示：

如图中可以看出，index_demo表中3条记录都被插入到了编号为10的数据页中，此时我们再来插入一条记录。

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

因为页10最多只能放3条记录，所以我们不得不再分配一个新页：

注意，新分配的数据页编号可能并不是连续的，他们只是通过维护着上一页和下一页的编号而建立了链表关系。另外，页10中用户记录最大的主键值是5，而页20中有一条记录的主键值是4，因为5>4,所以这就不符合下一个数据页中用户记录的主键值大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候伴随着一次记录移动，也就是把主键值为5的记录移到页20中，然后，将主键值为4的记录移到页10中。

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

给所有的页建立一个目录项。

由于数据页的编号可能是不连续的，所以在向index_demo表中插入许多条记录后，可能是这样的效果。

因为这些16KB的页在物理存储上时不连续的，所以如果想这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录。每个页对应一个目录项，每个目录项包含下边两个部分：

页的用户记录中最小的主键值，我们用key来表示。

页号，我们用page_no表示。

所以我们为上边几个页做好的目录就像这样子

以页20为例，它对应目录项2，这个目录项中包含着该页的页号20以及该页中用户记录的最小主键值5，我们只需要把几个目录项在物理存储器上连续存储（比如：数组），就可以实现根据主键值快速查找某条记录的功能了。比如：查找主键为13的记录，具体的查找过程分两步：

先从目录项中根据二分法快速确定主键值为13的记录在目录项3中（因为12<13<209）,它对应的页是页8。

再根据前边说的查找记录的方式去页8中定位具体的记录。
至此，针对数据页做的简易目录就搞定了，这个目录有一个别名，就是索引。

3. InnoDB中的索引方案

1. 迭代1次：目录项记录的页

上边称为一个简易的索引方案，是因为我们为了根据主键值进行查找时使用二分法快速定位具体的目录项而假设所有目录项都可以在物理存储器上连续存储，但是这样做有几个问题：

InnoDB是使用页来作为管理存储空间的基本单位，最多能保证16KB的连续空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。

我们时常会对记录进行增删，假设我们把页20中的记录都删除了，那么意味着目录项2也就没有存在的必要了，这就需要把目录项2后的目录项都向前移动一下，这样牵一发而动全身的操作效率很差。

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

0: 普通的用户记录

1: 目录项记录

2: 最小记录
我们把前边使用的目录项放到数据页中的样子就是这样：

从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调目录项记录和普通的用户记录的不同点：

目录项记录的record_type值是1，而普通用户记录的record_type值为0。

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

记录头信息里还有一个叫min_rec_mask的属性，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0。

相同点：两者用的是一样的数据页，都会为主键值生成Page_Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。

现在以查找主键为13的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：

先从目录项中根据二分法快速确定主键值为13的记录在目录项3中（因为12<13<209）,它对应的页是页8。

再根据前边说的查找记录的方式去页8中定位具体的记录。

2. 迭代2次：多个目录项记录的页

虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是无论怎么说一个页只有16KB大小，能存放的目录项也是有限的，那如果表中数据太多，以至于一个数据页不足以存放所有的目录项记录，如何处理呢？

这里我们假设一个存储目录项记录的页最多只能存放4条目录项记录，所以如果此时我们在向上图中插入一条主键值为320的用户记录的话，那就需要分配一个新的存储目录项记录的页：

3. 迭代3次:目录项记录页的目录页

问题来了，在这个查询步骤的第1步中我们需要定位存储目录项记录的页，但是这些页是不连续的，

如果我们表中的数据非常多则会产生很多存储目录项的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？那就为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，

小目录里才是实际的数据，所以现在各个页的示意图就是这样子：

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

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

B+树

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

一个B+树的节点其实可以分为好多层，规定最下边的那层，也就是存放我们用户记录的那层为第0层，之后依次往上加。之前我们做了一个非常极端的假设：存放用户记录的页最多存放3条记录，存放目录项记录的页最多存放4条记录。其实真实环境中一个页存放的记录数量是非常大的，假设所有存放用户记录的叶子加点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：

如果B+树只有1层，也就是只有1个用于存放用户记录的节点，最多能存放100条记录。

如果B+树有2层，最多能存放1000*100=10，0000条记录

如果B+树有3层，最多能存放 10001000100=1000，0000 条记录

如果B+树有4层，最多能存放 100010001000*100=10，00000，0000 条记录。这是相当多的记录了。

所以一般情况下，我们用到的B+树都不会超过4层。那么我们通过主键查找最多经过4次io。

总结

本文首先通过设计一个简单的索引，层层迭代，最后引出了InnoDB的索引方案，它底层的数据结构是B+树的结构，叶子节点存放用户的记录，非叶子节点存放主键以及页编号。每个数据页可以存放16KB的数据。