1 InnoDB详解 （1）

1 概念介绍

聚簇索引：innodb的聚簇索引 根据主键构建索引，B+数的叶子节点存储一条完整的数据。若果创建的表没有主键，会隐式生成一个字段构建B+树。

非聚簇索引：也叫二级索引或辅助索引，只记录主键值和二级索引的值。根据二级索引构建B+数，末尾记录了主键值。

如一个学生表id是主键，包含age,name等字段。创建一个索引 idx_age ，叶子节点记录了age值和该表的主键id的值。此时查询语句select * from student where age >18; 就会走age索引，叶子节点记录了id值，就根据id再回表查询name和其他值。

只有叶子节点存储数据，内节点存储的是叶子节点的主键值与页号（在磁盘中的位置）。

页的大小为16K，页中的数据是以单链表的形式构成的。

2 页介绍

由上图可知 页之间 是双向链表连接组成的，页间每条记录是单链表连接的，单链表遍历很慢，在查询数据时，是一条条遍历吗？

1 页内部结构介绍

1 File Header（文件头部）（38字节）

FIL_PAGE_OFFSET（4字节）：唯一标识一个页号。

FIL_PAGE_TYPE（2字节）：标明该页的类型。类型如下：

FIL_PAGE_PREV（4字节）和FIL_PAGE_NEXT（4字节）： 记录上一页下一页地址；页之间是双向链表。

FIL_PAGE_SPACE_OR_CHKSUM（4字节）：简单来说就是通过hash来算出一个唯一值，mysql同步数据是以页为单位的，写入数据到磁盘是先计算校验和存到页头和页尾，同步时先向磁盘写入头部校验和，如果突然中断，头尾校验和机会不一样，就可以根据日志进行数据回滚。详细介绍如下

什么是校验和？
就是对于一个很长的字节串来说，我们会通过某种算法来计算一个比较短的值来代表这个很长的字节串，这个比较短的值就称为校验和。
在比较两个很长的字节串之前，先比较这两个长字节串的校验和，如果校验和都不一样，则两个长字节串肯定是不同的，所以省去了直接比较两个比较长的字节串的时间损耗。
文件头部和文件尾部都有属性：FIL_PAGE_SPACE_OR_CHKSUM
作用：
InnoDB存储引擎以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候断电了，造成了该页传输的不完整。
为了检测一个页是否完整（也就是在同步的时候有没有发生只同步一半的尴尬情况），这时可以通过文件尾的校验和（checksum 值）与文件头的校验和做比对，如果两个值不相等则证明页的传输有问题，需要重新进行传输，否则认为页的传输已经完成。
具体的：
每当一个页面在内存中修改了，在同步之前就要把它的校验和算出来，因为File Header在页面的前边，所以校验和会被首先同步到磁盘，当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的首部和尾部的校验和应该是一致的。如果写了一半儿断电了，那么在File Header中的校验和就代表着已经修改过的页，而在File Trailer中的校验和代表着原先的页，二者不同则意味着同步中间出了错。这里，校验方式就是采用 Hash 算法进行校验。

FIL_PAGE_LSN（8字节）：页面被最后修改时对应的日志序列位置。

2 File Trailer（文件尾部）（8字节）

• 前4个字节代表页的校验和：

这个部分是和File Header中的校验和相对应的。

• 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）：

这个部分也是为了校验页的完整性的，如果首部和尾部的LSN值校验不成功的话，就说明同步过程出现了问题。

3 Free Space (空闲空间)

插入记录来来空闲空间申请，然后划分到用户空间，当空闲空间没有时，就要划分到新的页里了。

行格式是啥？下文再详细介绍

我们自己存储的记录会按照指定的行格式存储到User Records部分。但是在一开始生成页的时候，其实并没有User Records这个部分，每当我们插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页了。

4 User Records (用户记录)

User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表。

5 Infimum + Supremum（最小最大记录）

存入最大最小记录是为了干啥呢？下面会揭晓。

对于一条完整的记录来说，比较记录的大小就是比较主键的大小。比方说我们插入的4行记录的主键值分别是：1、2、3、4，这也就意味着这4条记录是从小到大依次递增。

InnoDB规定的最小记录与最大记录这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的，如图所示：

这两条记录不是我们自己定义的记录，所以它们并不存放在页的User Records部分，他们被单独放在一个称为Infimum + Supremum的部分，如图所示：

6 Page Directory（页目录）重点

为什么需要页目录？

在页中，记录是以单向链表的形式进行存储的。单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。

需求：根据主键值查找页中的某条记录，如何实现快速查找呢？

SELECT * FROM page_demo WHERE c1 = 17;

方式1：顺序查找

从Infimum记录（最小记录）开始，沿着链表一直往后找。查询效率为O(n)

如果一个页中存储了非常多的记录，这么查找性能很差。

方式2：使用页目录，二分法查找

简单描述一下

将页中的记录按照主键值进行分组，第一组是Infimum最小记录，后面每组是怎么分的呢？

插入数据时连上supremum组成的第二组已经有8条记录了，此时又插入了一条位于最大最小值之间的记录，第二组就会裂开，变成第二组4条记录，第三组5条记录。所以最后一组可能包含1至8条记录。中间组都是4条记录。

每个分组称之为槽（slot)

页目录中记录的是槽中最大记录的地址偏移量。

若页 中原来有18条主键从1 递增的记录。

经过分组之后就变成了 1 2345 6789 abcd efghg 5个组 （为了方便表示 采用18进制）槽编号分别为 0 1 2 3 4

原来查询 id = 17 时 需要遍历17次

现在分完组后，采用二分查找

1. 找到中间槽 （0+ 4）/2 得到2号槽 根据2号槽记录的地址偏移获得值为 9 ， 9 <17。
2. 收缩边界，左边界变为2号槽，中间槽为（2+4）/2 ,得到3号槽，3号槽中地址偏移得到的值为14 ，14 小于 17
3. 再次二分确定记录在 4号槽中，但是4号槽记录的是最大地址偏移，怎么找到17号呢？单链表不能逆序查找。
4. 我们可以从3号槽获取地址偏移，顺着该地址遍历，就能找到17号了

页中每条记录中有个next_record字段记录的是下一条记录的偏移量，由此构成单链表。

这也解释了为什么要记录最大记录与最小记录，便于分组。

详细描述如下

1. 将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录。

2. 第 1 组，也就是最小记录所在的分组只有 1 个记录；

最后一组，就是最大记录所在的分组，会有 1-8 条记录；

其余的组记录数量在 4-8 条之间。

这样做的好处是，除了第 1 组（最小记录所在组）以外，其余组的记录数会尽量平分。

3. 在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段。

4. 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽（slot），每个槽相当于指针指向了不同组的最后一个记录。

举例1：

举例2：

现在的page_demo表中正常的记录共有6条，InnoDB会把它们分成两组，第一组中只有一个最小记录，第二组中是剩余的5条记录。如下图：

从这个图中我们需要注意这么几点：

• 现在页目录部分中有两个槽，也就意味着我们的记录被分成了两个组，槽1中的值是112，代表最大记录的地址偏移量（就是从页面的0字节开始数，数112个字节）；槽0中的值是99，代表最小记录的地址偏移量。

• 注意最小和最大记录的头信息中的n_owned属性

• 最小记录的n_owned值为1，这就代表着以最小记录结尾的这个分组中只有1条记录，也就是最小记录本身。

• 最大记录的n_owned值为5，这就代表着以最大记录结尾的这个分组中只有5条记录，包括最大记录本身还有我们自己插入的4条记录。

用箭头指向的方式替代数字，这样更易于我们理解，修改后如下：

再换个角度看一下：（单纯从逻辑上看一下这些记录和页目录的关系）

7 Page Header（页面头部）

页面头部包含两个信息

PAGE_DIRECTION：假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是PAGE_DIRECTION。

PAGE_N_DIRECTION：假设连续几次插入新记录的方向都是一致的，InnoDB会把沿着同一个方向插入记录的条数记下来，这个条数就用PAGE_N_DIRECTION这个状态表示。当然，如果最后一条记录的插入方向改变了的话，这个状态的值会被清零重新统计。