前言
学完前面我们讲解了InnoDB数据页的7个组成部分，知道了各个数据页可以组成一个双向链表，而每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边儿的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。所以我们画一个简单的关系示意图如下：
其中页1、页2、页3…页n这些页可以不在物理结构上相连，只用通过双向链表相关联即可。
之前一直听说，给数据库创建索引，可以提高查询性能，但是索引到底是个啥，又是怎样工作的，今天的就来学习InnoDB存储引擎的B+树索引
一、没有索引的查找
在正式的学习索引之前，我们需要了解一下没有索引的时候是怎么查找记录的，为了方便理解，我们只用搜索条件为对某个列精确匹配（精确匹配，就是搜索条件中用等于=连接起的表达式）做个案例，就像下面这种语句：
select[列名列表] from 表名 where 列名 = xxx;
1.1 一个页中查找
我们知道一个数据页的大小为16KB（16384字节），除去页中必须的元数据信息需要一部分存储空间之外，还会剩下很多空间来存放我们的User Records。假设目前表中的记录比较少，所有的记录都可以被存放到一个页中，在查找记录的时候可以根据搜索条件的不同分为两种情况：
已主键为搜索条件
在页目录中使用二分法快速定位到对应的槽（Slot），然后再遍历该槽对应分组中的记录即可快速找到指定的记录
以其他列作为搜索条件
对非主键列的查找的过程可就不这么幸运了，因为在数据页中并没有对非主键列建立所谓的页目录，所以我们无法通过二分法快速定位相应的槽。这种情况下只能从最小记录开始依次遍历单链表中的每条记录，然后对比每条记录是不是符合搜索条件。很显然，这种查找的效率是非常低的。
1.2 在很多页中查找
大部分情况下我们表中存放的记录都是非常多的，需要好多的数据页来存储这些记录。在很多页中查找记录的话可以分为两个步骤：
定位到记录所在的页。
从所在的页中查找相应的记录。
在没有索引的情况下，不论是根据主键列或者其他列的值进行查找，由于我们并不能快速的定位到记录所在的页，所以只能从第一个页沿着双向链表一直往下找，在每一个页中根据我们刚刚唠叨过的查找方式去查找指定的记录。因为要遍历所有的数据页，所以这种方式显然是超级耗时的，如果一个表有一亿条记录，使用这种方式去查找记录那要等到猴年马月才能等到查找结果。
所以，索引闪亮登场。
二、索引
为了方便展示，我们先创建一张表：
mysql> create table demo6(c1 int primary key,c2 int,c3 char(1)) row_format=compact;
Query OK, 0 rows affected (0.02 sec)
这个新建的demo6表中有2个int类型的列，1个char(1)类型的列，而且我们规定了c1列为主键，这个表使用Compact行格式来实际存储记录的。为了方便理解索引，我们对demo6表的行格式示意图做了简化：
再来回顾一下展示的这几部分的具体含义：
record_type：记录头信息的一项属性，表示记录的类型，0表示普通记录、2表示最小记录、3表示最大记录、1我们还没用过，马上就会说到
next_record：记录头信息的一项属性，表示下一条地址相对于本条记录的地址偏移量，为了方便理解，都用箭头来表明下一条记录是谁
各个列的值：这里只记录在demo6表中的三个列，分别是c1 、c2和c3
其他信息 ：除了上述3种信息以外的所有信息，包括其他隐藏列的值以及记录的额外信息。
我们再来对示意图做一下调整，将记录格式示意图的其他信息去掉并把它竖起来的效果就是这样：
把一些记录放到页里面的示意图如下（见颜色知其意哈）：
2.1 一个简单的索引方案
回到正题，根据某个搜索条件查找一些记录时为什么要遍历所有的数据页呢？因为各个页中的记录并没有规律，我们并不知道我们的搜索条件匹配哪些页中的记录，所以不得不依次遍历所有的数据页。所以如果我们想快速的定位到需要查找的记录在哪些数据页中该咋办？还记得我们为根据主键值快速定位一条记录在页中的位置而设立的页目录么？我们也可以想办法为快速定位记录所在的数据页而建立一个别的目录，建这个目录必须完成下边这些事儿：
第一： 下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值
我们这里需要做一个假设：假设我们的每个数据页最多能存放3条记录（实际上一个数据页非常大，可以存放下好多记录）。有了这个假设之后我们向demo6表插入3条记录：
mysql> insert into demo6 values(1, 4, 'u'), (3, 9, 'd'), (5, 3, 'y');
Query OK, 3 rows affected (0.01 sec)
Records: 3 Duplicates: 0 Warnings: 0
那么这些记录已经按照主键值的大小串联成一个单向链表了，如图所示：
从图中可以看出来，demo6表中的3条记录都被插入到了编号为10的数据页中了。此时我们再来插入1条记录：
mysql> insert into demo6 values(4, 4, 'a');
Query OK, 1 row affected (0.01 sec)
页10最多只能放3条记录，所以我们不得不再分配一个新页
新分配的数据页编号可能并不是连续的，也就是说我们使用的这些页在存储空间里可能并不挨着。它们只是通过维护着上一个页和下一个页的编号而建立了链表关系。
页10中用户记录最大的主键值是5，而页28中有一条记录的主键值是4，因为5 > 4，所以这就不符合下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值的要求，所以在插入主键值为4的记录的时候需要伴随着一次记录移动，也就是把主键值为5的记录移动到页28中，然后再把主键值为4的记录插入到页10中，这个过程的示意图如下：
将主键值为5的记录移到页28
将主键为4的插入到页10
这个过程表明了在对页中的记录进行增删改操作的过程中，我们必须通过一些诸如记录移动的操作来始终保证这个状态一直成立：下一个数据页中用户记录的主键值必须大于上一个页中用户记录的主键值。这个过程我们也可以称为页分裂。
第二： 给所有的页建立一个目录项
由于数据页的编号可能并不是连续的，所以在向demo6表中插入许多条记录后，可能是这样的效果：
因为这些16KB的页在物理存储上可能并不挨着，所以如果想从这么多页中根据主键值快速定位某些记录所在的页，我们需要给它们做个目录，每个页对应一个目录项，每个目录项包括下边两个部分：
页的用户记录中最小的主键值，我们用key 来表示
页号，我们用page_no表示
所以我们上边几个页做好的目录就像这个样子：
以页28为例，它对应目录项2，这个目录项中包含着该页的页号28以及该页中用户记录的最小主键值5。我们只需要把几个目录项在物理存储器上连续存储，比如把他们放到一个数组里，就可以实现根据主键值快速查找某条记录的功能了。比方说我们想找主键值为20的记录，具体查找过程分两步：
先从目录项中根据二分法快速确定出主键值为20的记录在目录项3中（因为12<20<209），它对应的页是页9。
再根据前边说的在页中查找记录的方式去页9中定位具体的记录。
至此，针对数据页做的简易目录就搞定了。这个目录有一个别名，称为索引。
2.2 InnoDB中的索引方案
上边之所以称为一个简易的索引方案，是因为我们为了在根据主键值进行查找时使用二分法快速定位具体的目录项而假设所有目录项都可以在物理存储器上连续存储，但是这样做有几个问题：
InnoDB是使用页来作为管理存储空间的基本单位，也就是最多能保证16KB的连续存储空间，而随着表中记录数量的增多，需要非常大的连续的存储空间才能把所有的目录项都放下，这对记录数量非常多的表是不现实的。
我们时常会对记录进行增删，假设我们把页28中的记录都删除了，页28也就没有存在的必要了，那意味着目录项2也就没有存在的必要了，这就需要把目录项2后的目录项都向前移动一下，这种牵一发而动全身的设计不是什么好主意～
所以InnoDB需要一种可以灵活管理所有目录项的方式。这些目录项其实长得跟我们的用户记录差不多，只不过目录项中的两个列是主键和页号而已，所以他们复用了之前存储用户记录的数据页来存储目录项，为了和用户记录做一下区分，我们把这些用来表示目录项的记录称为目录项记录。那InnoDB怎么区分一条记录是普通的用户记录还是目录项记录呢？别忘了记录头信息里的record_type属性，它的各个取值代表的意思如下：
0：普通的用户记录
1：目录项记录
2：最小记录
3：最大记录
record_type值为1的意思大家明白了吗，我们把前边使用到的目录项放到数据页中的示意图如下：
从图中可以看出来，我们新分配了一个编号为30的页来专门存储目录项记录。这里再次强调一遍目录项记录和普通的用户记录的不同点：
目录项记录的record_type值是1，而普通用户记录的record_type值是0
目录项记录只有主键值和页的编号两个列，而普通的用户记录的列是用户自己定义的，可能包含很多列，另外还有InnoDB自己添加的隐藏列
还记得我们之前在唠叨记录头信息的时候说过一个叫min_rec_mask的属性么，只有在存储目录项记录的页中的主键值最小的目录项记录的min_rec_mask值为1，其他别的记录的min_rec_mask值都是0
除了上述几点外，这两者就没啥差别了，它们用的是一样的数据页（页的类型都是0x45bf），页的组成结构也是一样的，都会为主键值生成Page Directory（页目录），从而在按照主键值进行查找时可以使用二分法来加快查询速度。现在以查找主键为20的记录为例，根据某个主键值去查找记录的步骤就可以大致拆分成下边两步：
先到存储目录项记录的页，也就是页30中通过二分法快速定位到对应目录项，因为12<20<209，所以定位到对应的记录所在的页就是页9
再到存储用户记录的页9中根据二分法快速定位到主键值为20的用户记录
虽然说目录项记录中只存储主键值和对应的页号，比用户记录需要的存储空间小多了，但是不论怎么说一个页只有16KB大小，能存放的目录项记录也是有限的，那如果表中的数据太多，以至于一个数据页不足以存放所有的目录项记录，该咋办呢？
当然是再多整一个存储目录项记录的页喽～ 为了大家更好的理解新分配一个目录项记录页的过程，我们假设一个存储目录项记录的页最多只能存放4条目录项记录（请注意是假设哦，真实情况下可以存放好多条的），所以如果此时我们再向上图中插入一条主键值为320的用户记录的话，那就需要分配一个新的存储目录项记录的页喽：
从图中可以看出，我们插入了一条主键值为320的用户记录之后需要两个新的数据页：
为存储该用户记录而新生成了页31
因为原先存储目录项记录的页30的容量已满（我们前边假设只能存储4条目录项记录），所以不得不需要一个新的页32来存放页31对应的目录项
现在因为存储目录项记录的页不止一个，所以如果我们想根据主键值查找一条用户记录大致需要3个步骤，以查找主键值为20的记录为例：
确定目录项记录页，我们现在的存储目录项记录的页有两个，即页30和页32，又因为页30表示的目录项的主键值的范围是[1, 320)，页32表示的目录项的主键值不小于320，所以主键值为20的记录对应的目录项记录在页30中
通过目录项记录页确定用户记录真实所在的页
在真实存储用户记录的页中定位到具体的记录
问题来了，在这个查询步骤的第1步中我们需要定位存储目录项记录的页，但是这些页在存储空间中也可能不挨着，如果我们表中的数据非常多则会产生很多存储目录项记录的页，那我们怎么根据主键值快速定位一个存储目录项记录的页呢？其实也简单，为这些存储目录项记录的页再生成一个更高级的目录，就像是一个多级目录一样，大目录里嵌套小目录，小目录里才是实际的数据，所以现在各个页的示意图就是这样子：
如图，我们生成了一个存储更高级目录项的页33，这个页中的两条记录分别代表页30和页32，如果用户记录的主键值在[1, 320)之间，则到页30中查找更详细的目录项记录，如果主键值不小于320的话，就到页32中查找更详细的目录项记录。随着表中记录的增加，这个目录的层级会继续增加。这图像不像一个倒过来的树呀，上头是树根，下头是树叶！其实这是一种组织数据的形式，或者说是一种数据结构，它的名称是B+树。
不论是存放用户记录的数据页，还是存放目录项记录的数据页，我们都把它们存放到B+树这个数据结构中了，所以我们也称这些数据页为节点。从图中可以看出来，我们的实际用户记录其实都存放在B+树的最底层的节点上，这些节点也被称为叶子节点或叶节点，其余用来存放目录项的节点称为非叶子节点或者内节点，其中B+树最上边的那个节点也称为根节点。
从图中可以看出来，一个B+树的节点其实可以分成好多层，InnoDB为了讨论方便，规定最下边的那层，也就是存放我们用户记录的那层为第0层，之后依次往上加。真实环境中一个页存放的记录数量是非常大的，假设，假设，假设所有存放用户记录的叶子节点代表的数据页可以存放100条用户记录，所有存放目录项记录的内节点代表的数据页可以存放1000条目录项记录，那么：如果B+树有4层，最多能存放1000×1000×1000×100=100000000000条记录。所以一般情况下，我们用到的B+树都不会超过4层，那我们通过主键值去查找某条记录最多只需要做4个页面内的查找（查找3个目录项页和一个用户记录页），又因为在每个页面内有所谓的Page Directory（页目录），所以在页面内也可以通过二分法实现快速定位记录。这便是索引为什么可以加速查询的原因。
三、聚簇索引（Clustered Index）
我们上边介绍的B+树本身就是一个目录，或者说本身就是一个索引。它有两个特点：
使用记录主键值的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照主键的大小顺序排成一个单向链表
各个存放用户记录的页也是根据页中用户记录的主键大小顺序排成一个双向链表
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的主键大小顺序排成一个双向链表。
B+树的叶子节点存储的是完整的用户记录
所谓完整的用户记录，就是指这个记录中存储了所有列的值（包括隐藏列）
我们把具有这两种特性的B+树称为聚簇索引，所有完整的用户记录都存放在这个聚簇索引的叶子节点处。这种聚簇索引并不需要我们在MySQL语句中显式的使用index语句去创建，InnoDB存储引擎会自动的为我们创建聚簇索引。另外有趣的一点是，在InnoDB存储引擎中，聚簇索引就是数据的存储方式（所有的用户记录都存储在了叶子节点），也就是所谓的索引即数据，数据即索引。
四、二级索引（Secondary Index）
聚簇索引只能在搜索条件是主键值时才能发挥作用，因为B+树中的数据都是按照主键进行排序的。那如果我们想以别的列作为搜索条件该咋办呢？难道只能从头到尾沿着链表依次遍历记录么？
不，我们可以多建几棵B+树，不同的B+树中的数据采用不同的排序规则。比方说我们用c2列的大小作为数据页、页中记录的排序规则，再建一棵B+树，效果如下图所示：
这个B+树与上边介绍的聚簇索引有几处不同：
使用记录c2列的大小进行记录和页的排序，这包括三个方面的含义：
页内的记录是按照c2列的大小顺序排成一个单向链表
各个存放用户记录的页也是根据页中记录的c2列大小顺序排成一个双向链表
存放目录项记录的页分为不同的层次，在同一层次中的页也是根据页中目录项记录的c2列大小顺序排成一个双向链表。
B+树的叶子节点存储的并不是完整的用户记录，而只是c2列+主键这两个列的值。
目录项记录中不再是主键+页号的搭配，而变成了c2列+页号的搭配。
所以如果我们现在想通过c2列的值查找某些记录的话就可以使用我们刚刚建好的这个B+树了。以查找c2列的值为4的记录为例，查找过程如下：
所以如果我们现在想通过c2列的值查找某些记录的话就可以使用我们刚刚建好的这个B+树了。以查找c2列的值为4的记录为例，查找过程如下：
确定目录项记录页
根据根页面，也就是页44，可以快速定位到目录项记录所在的页为页42（因为2<4< 9）
根据根页面，也就是页33，可以快速定位到目录项记录所在的页为页30。
通过目录项记录页确定用户记录真实所在的页。
在页42中可以快速定位到实际存储用户记录的页，但是由于c2列并没有唯一性约束，所以c2列值为4的记录可能分布在多个数据页中，又因为2<4≤ 4，所以确定实际存储用户记录的页在页34和页35中
在真实存储用户记录的页中定位到具体的记录。
到页34和页35中定位到具体的记录
但是这个B+树的叶子节点中的记录只存储了c2和c1（也就是主键）两个列，所以我们必须再根据主键值去聚簇索引中再查找一遍完整的用户记录。
我们根据这个以c2列大小排序的B+树只能确定我们要查找记录的主键值，所以如果我们想根据c2列的值查找到完整的用户记录的话，仍然需要到聚簇索引中再查一遍，这个过程也被称为回表。也就是根据c2列的值查询一条完整的用户记录需要使用到2棵B+树！
小提示：
如果把完整的用户记录放到叶子节点是可以不用回表，但是太占地方了呀～相当于每建立一棵B+树都需要把所有的用户记录再都拷贝一遍，这就有点太浪费存储空间了。因为这种按照非主键列建立的B+树需要一次回表操作才可以定位到完整的用户记录，所以这种B+树也被称为二级索引（英文名Secondary Index），或者辅助索引。由于我们使用的是c2列的大小作为B+树的排序规则，所以我们也称这个B+树为为c2列建立的索引。
