InnoDB数据页结构

测试环境

MySQL 5.6

innodb_ruby(关于它的使用可以参考它的github)

数据页

在行格式文章中提到了一些页的概念,它是InnoDB管理存储空间的基本单位，一个页的大小一般是16KB。InnoDB为了不同的目的而设计了许多种不同类型的页， 例如：存放表空间头部信息的页，存放Insert Buffer信息的页，存放INODE信息的页，存放undo日志信息的页等。而我们的数据就存放在官方所称的索引页中， 通常使用过程中更多称为数据页

数据页结构

我们的数据就存储在User Records这部分空间，User Record在页的建立起初并不存在，User Records这部分空间是从空闲空间Free Space逐渐划分而来，当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了，如果还有新的记录插入的话，就需要去申请新的页。我们先创建一张表，并插入一些数据去解释各个部分的作用。如下：

USE test;
CREATE TABLE `t_test_page` (
	c1 INT NOT NULL DEFAULT '0',
	c2 CHAR NOT NULL DEFAULT '',
	PRIMARY KEY(c1)
)ENGINE INNODB CHARSET=ASCII ROW_FORMAT=COMPACT;

INSERT INTO t_test_page(c1,c2) VALUES (0,"a"),(1,"b"),(2,"c");

把c1列设置为主键是因为在compact行格式中就没必要为我们去创建那个所谓的 row_id 隐藏列了，用户真实数据在User Records空间中是以单向链表方式存储的， 每条记录可以认为是链表的节点，那么节点信息记录在行数据中的额外信息，我们先看看这3条记录的头信息，为了看起来直观下面的信息做了简单修改，同时只列举了讨论问题所需的字段， 详细行格式包含内容可参考行格式文章：

1. deleted

   这个字段标识了当前记录是否被删除，只占用一个二进制位，0：未被删除 1：被删除。这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗，只是打一个删除标记，所有被删除掉的记录都会组成一个垃圾链表，在这个链表中的记录占用的空间称为可重用空间，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。而设置被删除标记和加入到垃圾链表是两个阶段

2. min_rec

   B+树的每层非叶子节点中的最小记录都会添加该标记,我们插入的3条记录的min_rec值都是0，意味着它们都不是B+树的非叶子节点中的最小记录

3. n_owned

   以此记录为页面目录节点所拥有的记录数量，下面页面目录会详细解释，我们的3条记录对应的no_owned字段值都是0

4. heap_number

   表示当前记录在本页中的位置，我们插入的3条记录在本页中的位置分别是：2、3、4，我们从分析工具打出的数据看到system records项，这就是开头提到的2条系统插入的行记录，而这2条记录的heap_number字段对应的值正是0、1，这2条记录其中一条是最小记录，一条是最大记录，这2条记录都是由5字节大小的头信息和8字节的固定部分组成的。我们的记录有大小之分，对于一条完整的记录来说，比较记录的大小就是比较主键的大小，这2条记录存放在称为Infimum + Supremum的部分

5. type

   这个字段表示当前记录的类型，一共有4种类型的记录，0：表示普通记录，1：表示B+树非叶节点记录，2：表示最小记录，3：表示最大记录。从上表我们可以看出来，我们自己插入的记录就是普通记录，而最小记录和最大记录的type值分别为2和3

6. next

   这个字段表示从当前记录的真实数据到下一条记录的真实数据的地址偏移量（所在页的起始偏移）。如果写过单向链表都知道，链表的每个节点里都有一个指向下一个节点的指针，而这里记录了下一条记录的真实数据偏移量，所以这个链表类型这样：

        最小记录Infimum------>(0,"a")------>(1,"b")------>(2,"c")------>最大记录Supermum
   

   下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定最小记录Infimum 的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是最大记录Supremum ，虽然每条记录的指向以链表形式，但是记录的存储形式是这样的：

   最小记录Infimum

   最大记录Supermum

   (0,”a”)

   (1,”b”)

   (2,”c”)

   每条记录还有一个字段offset，它表示的是记录在页中的地址偏移量：

   记录	offset
   Infimum	99
   Supremum	112
   (0,”a”)	125
   (1,”b”)	157
   (2,”c”)	189

   有了上面几张表和解释，思考一下这5条数据的next字段为什么是125、112、157、189、99

Page Directory 页目录

从上面的解释我们的数据记录是以类似链表的形式存储的，但是我们用过链表都知道，遍历是很头疼的事情，最笨的办法就是从链表头开始向后找，如果链表很长会有性能损耗

MySQL的解决办法是：

1. 将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组
2. 每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录
3. 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方，这个地方就是Page Directory 页目录。页面目录中的这些地址偏移量被称为Slot槽，所以这个页面目录就是由Slot槽组成的

通过分析工具输出的数据可以看到Page Directory对应的值是[99,112] ，而存储这部分数据的数据类型是个数组。同时从上一节的表格中看到Infimum最小记录和Supermum最大记录的n_owned字段分别是1、4，最后分析下来地址偏移量99（也就是Infimum最小记录）这组拥有1条记录即它本身，地址偏移量112（也就是Supermum最大记录）这组拥有4条记录（Supermum最大记录+我们插入的3条记录）。这里的地址偏移量指的是从数据页起始到真实数据的偏移量。下图表达的更清晰:

每组的记录数是怎么分配的呢？InnoDB的规定是：

1. 对于最小记录所在的分组只能有 1 条记录
2. 最大记录所在的分组拥有的记录条数只能在 1~8 条之间
3. 剩下的分组中记录的条数范围只能在是 4~8 条之间

分组的过程是这样的：

1. 初始情况下一个数据页里只有最小记录和最大记录两条记录，它们分属于两个分组
2. 之后每插入一条记录，都会从页目录中找到主键值比本记录的主键值大并且差值最小的槽，然后把该槽对应的记录的n_owned值加1，表示本组内又添加了一条记录，直到该组中的记录数等于8条
3. 在一个组中的记录数等于8条后再插入一条记录时，会将组中的记录拆分成两个组，一个组中4条记录，另一个5条记录。这个过程会在页目录中新增一个Slot槽来记录这个新增分组中最大的那条记录的偏移量

有了页目录那么查找起来的速度就很快了，每个Slot槽所包含的记录数是固定的。使用了二分查找法查找记录在哪个Slot槽中，然后在再遍历这个Slot槽里的记录

Page Header 页面头部

这部分通常存储着数据页本身相关的信息，这部分占用56个字节，下表是这部分数据的字段说明:

字段direction表示的是：新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边

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

File Header 文件头部

这部分数据针对各种类型的页都通用，也就是说不同类型的页都会以File Header作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，这个部分占用固定的38个字节，这部分数据包含下表中的字段：

字段type表示页的类型，文章开头提到了一些页，下表列出了所有页的类型：

文章开头提到一个页的大小大概16k，那么当数据很多时一个页放不下，就有多个页存储，而页与页之间的连接方式类似于双向链表，字段prev和字段next就是页与页之间的桥梁。并不是所有类型的页都有上一个和下一个页的属性，类型为index的页是有这两个属性的

File Trailer 文件尾部

这部分数据占用8字节，为了把内存数据同步到磁盘而设计

1. 前4个字节代表页的校验和(checksum)

   这个部分是和File Header中的校验和相对应的。每当一个页面在内存中修改了，在同步之前就要把它的校验和算出来，因为File Header在页面的前边，所以校验和会被首先同步到磁盘，当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的首部和尾部的校验和应该是一致的。如果写了一半断电、宕机等不可抗因素，那么在File Header中的校验和就代表着已经修改过的页，而在File Trialer中的校验和代表着原先的页，二者不同则意味着同步中间出错

2. 后4个字节代表页面被最后修改时对应的日志序列位置(lsn_low32)

   这个字段也和File Header中的lsn相呼应，确保同步的完整性