深入浅出——InnoDB页结构详解，慎入！

上一篇文章对InnoDB的行格式进行了解析，但是却把记录头信息抛到这里来讲，那么开始吧，注意本片需要有一点数据结构和算法基础，如果基础薄弱，请先确保自己会二分查找和链表再来食用

页结构

简单提溜一点儿，页

它是 InnoDB 管理存储空间的基本单位，一个页的大小一般是 16KB 。 InnoDB 为了不同的目的而设计了许多种不同类型的 页 ，比如存放表空间头部信息的页，存放 Insert Buffer 信息的页，存放 INODE 信息的页，存放 undo 日志信息的页等等等等。

但是在这里，我们主要讲的是索引页

简述

虽然只有16kb，但是划分可多咯

image-20230613152347650

image-20230613152525187

记录在页中的存储

我们的存储记录会以行格式存储到User Records中

其实UserRecords是从Free Space里面去划分的

emm... 这里其实就是数据结构的线性表,嗯,也就是数组，好似，又说废话，继续

一个图直接看懂

image-20230613153319733

但是在这里，Inoodb为了更好的管理UserRecords，还是废了很大的力气的，这得从行格式的记录头信息说去

揭秘：行的记录头信息{#line_header}

这里再来处理一波吧

mysql> CREATE TABLE page_demo(
 -> c1 INT,
 -> c2 INT,
 -> c3 VARCHAR(10000),
 -> PRIMARY KEY (c1)
 -> ) CHARSET=ascii ROW_FORMAT=Compact;
Query OK, 0 rows affected (0.03 sec)

注意的是,在这个里面,我们把c1作为了主键，所以说在行格式的内存结构中，c1代替了row_id

内存结构图如下

image-20230613163614279

再把老图拉出来

image-20230613164120289

下面我没来简化一下结构,只用在这里有用的点

image-20230613165925624

基本结构了解了以后，下面我们来试着插入几条数据

mysql> INSERT INTO page_demo VALUES(1, 100, 'aaaa'), (2, 200, 'bbbb'), (3, 300, 'cccc'),
(4, 400, 'dddd');
Query OK, 4 rows affected (0.00 sec)
Records: 4 Duplicates: 0 Warnings: 0

下面是头信息和实际列数据UserRecords中的表示(这里是十进制的,但是本质上是二进制)

image-20230613170731689

• delete_mask 有这个标识符的存在也不是很诧异，多半就是　明修栈道，暗度成仓 查了一下，执行删除之后，delete_mask被标记，只是查不到结果，但是在底层会形成一条垃圾链，垃圾链为可重用空间，如果后面有新纪录，可能会将被重用空间给覆盖掉

为什么不直接移除?

移除后重新排列会有性能消耗

另外，将这个delete_mask位设置为1和将被删除的记录加入到垃圾链表中其实是两个阶段，后面讲事务的时候西索

• min_reck_mask B+树的每层非叶子节点中的最小记录都会添加该标记 我们自己插入的四条记录的 min_rec_mask 值都是 0 ，意味着它们都不是 B+ 树的非叶 子节点中的最小记录。
• n_owned 后面再说
• heap_no 简单来说，就是当前记录（行）在页中的位置 为什么是2，3，4，5呢？？？0和1呢？ Innodb在开发的时候偷偷的插入了两个记录（伪记录）进去，一个代表最大记录，另一个是最小记录

What？比大小

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

当然对于只存储一条记录的部分列的情况，后面会西索

那么这两个崽子长成啥吊样？

跟着:mouse::mouse:来看一下

image-20230613185203780

一个单词，wtf？没错，就是一个单词，但是没有放在UserRecords里面，而是放到了一个称为 Infimum + Supremum 的地方

image-20230613185328414

从图中我们可以看出来，最小记录和最大记录的 heap_no 值分别是 0 和 1 ，也就是说它们的位置最靠前。

• record_type 表示当前记录的类型 一共有4种类型的记录， 0 表示普通记录， 1 表示B+树非叶节点记录， 2 表 示最小记录， 3 表示最大记录。从图中我们也可以看出来，我们自己插入的记录就是普通记录，它们的 record_type 值都是 0 ，而最小记录和最大记录的 record_type 值分别为 2 和 3 。
• next_record 从当前记录的真实数据到下一条记录的真实数据的地址偏移量。 注意：==下一条记录 指得并不是按照我们插入顺序的下一条记录==，而 是按照主键值由==小到大的顺序==的下一条记录。而且规定 Infimum记录（也就是最小记录） 的下一条记录就是 本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是 Supremum记录（也就 是最大记录）
  

  image-20230613190638725

从图中可以看出来，我们的记录按照主键从小到大的顺序形成了一个单链表。 最大记录 的 next_record 的 值为 0 ，这也就是说最大记录是没有 下一条记录 了，它是这个单链表中的最后一个节点。

那么我们试一试这个语句：

mysql> DELETE FROM page_demo WHERE c1 = 2;

Query OK, 1 row affected (0.02 sec)

image-20230613190802262

删除第2条记录前后主要发生了这些变化：

• 第2条记录并没有从存储空间中移除，而是把该条记录的 delete_mask 值设置为 1 。
• 第2条记录的 next_record 值变为了0，意味着该记录没有下一条记录了。
• 第1条记录的 next_record 指向了第3条记录。
• 还有一点你可能忽略了，就是 最大记录 的 n_owned 值从 5 变成了 4 ，后面西索

所以，不论我们怎么对页中的记录做增删改操作，InnoDB始终会维护一条记录的单链表，链表中的各个节点是按照主键值由小到大的顺序连接起来的。

为什么指针指向中间？

这个位置刚刚好，向左读取就是记录头信息，向右读取就是真实数据。 而且 变长字段长度列表 和 NULL值列表 本身为逆序，这样放使得离其所对应字段更近，大大的提高了了高速缓存的命中率

如果这时候，我们又把删除的插进去会怎样？（七进七出？nnd，会玩儿！）

来试一试

mysql> INSERT INTO page_demo VALUES(2, 200, 'bbbb');
-------------------------------------------
Query OK, 1 row affected (0.00 sec)

image-20230613191715331

从图中可以看到， InnoDB 并没有因为新记录的插入而为它申请新的存储空间，而是直接复用了原来被删除记录的存储空间。

tips:

刚刚在介绍delete_mask的时候就已经提到过，当数据页中存在多条被删除掉的记录时，这些记录的next_record属性将会把这些被删除掉的记录组成 一个垃圾链表，以备之后重用这部分存储空间。

Page Directory（页目录）

记录在页中按照主键值由小到大顺序串联成一个单链表，那如果我们想根据主键值查找页中的某 条记录该咋办呢？比如说这样的查询语句：

 SELECT * FROM page_demo WHERE c1 = 3;

先说说最暴力的方法吧，从最小记录一直往后面找，找到第一个比当前记录大的就停止，时间复杂度是$O(N)$

学过算法都知道，小数据这样找是没问题，那么有没有什么更优化的方法呢？

二分？建树？

为了让大家通俗易懂，我们先举个简单的例子。

比如大家平时在看片的时候，想要找车牌号，一般会先看是什么系列，选择国产、日韩、欧美(走错片场了)，然后再去找车牌，再去搜磁力、bt等等，其实InnoDB也是做了个类似的目录

过程如下：

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

image-20230613213010517

不知道你们有没有问题，反正我是有问题的！！！

最小记录的n_owned是1能够理解，到第4条记录也能够理解

但是这个最大记录，为什么还是5？因为最小记录只有它本身，能够理解，这里最大记录的own，其实包括的是最大记录本身和插入的四条数据，为啥这样设定？老规矩，保留疑问！

这里我们还可以这么理解

image-20230613214417847

突然感觉上面的问题好懂多一点了捏:smiley:

其实这就得说到Innodb官方的一个规定了

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

让我们解开帷幕，看看完整的步骤吧！

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

这里我们插入多组来看一下

mysql> INSERT INTO page_demo VALUES
(5, 500, 'eeee'), (6, 600, 'ffff'), (7, 700, 'gggg'),(8, 800, 'hhhh'), 
(9, 900, 'iiii'), (10, 1000, 'jjjj'), (11, 1100, 'kkkk'), (12, 1200, 'llll'), 
(13, 1300, 'mmmm'), (14, 1400, 'nnnn'), (15, 1500, 'oooo'), (16, 1600, 'pppp');
Query OK, 12 rows affected (0.00 sec)
-------------------------------------------------------------------
Records: 12 Duplicates: 0 Warnings: 0

这里我们插入12组数据，加上我们之前插入的和最大最小记录，总共18组，下面来看看内存结构图

image-20230613221349666

owned是0？上面都说了哩，你加的是slot，至于你分的是偶owned这个也好算啊，直接平摊再/2就行

因为把16条记录的全部信息都画在一张图里太占地方，让人眼花缭乱的，所以只保留了用户记录头信息中的 n_owned 和 next_record 属性，也省略了各个记录之间的箭头，没画不等于没有啊！

下面来说查找，其实都到这里了，你用暴力还是二分都行，hhh，暴力不用所，一个个比较主键大小嘛，这里主要说下二分

什么？你不知道二分？百度

我这里假装大家都对基础的二分查找有所掌握（~呃呃呃，学到这里大部分都会的吧~）

假设我们要找id=6的数据

• 计算中间slot = (0+4)/2=2 id=8 8>6 h=2
• 再次计算中间slot = (0+h)/2=2 id=4 4<6 l=1
• h-l=1，确定在slot=2中，直接遍历即可（~小数据你二分个鸡毛~）

所以在一个数据页中查找指定主键值的记录的过程分为两步：

1. 通过二分法确定该记录所在的槽，并找到该槽中主键值最小的那条记录。
2. 通过记录的 next_record 属性遍历该槽所在的组中的各个记录。

这里对算法能力有一点要求，如果不太清除二分查找的话，可以看看我往期文章，不知道我写没写，反正百度都有，二分在计算机科学里面还是很重要的一个思想，除此之外，还衍生出来了一个二分答案，这个算法今年打ACM的时候也用到过

Page Header（页面头部）

行有头部，那么页有头部也不见外。

其实这弄个头部，还不是为了获得一些数据，共56个字节。

image-20230613235954699

从 PAGE_N_DIR_SLOTS 到 PAGE_LAST_INSERT 以及 PAGE_N_RECS 的意思大家一定是清楚的，如果不清楚，对不起，你应该回头再来一次。

PAGE_DIRECTION 和 PAGE_N_DIRECTION：

• PAGE_DIRECTION 假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左 边。用来表示最后一条记录插入方向的状态就是 PAGE_DIRECTION 。
• PAGE_N_DIRECTION 假设连续几次插入新记录的方向都是一致的， InnoDB 会把沿着同一个方向插入记录的条数记下来，这个条数就用 PAGE_N_DIRECTION 这个状态表示。当然，如果最后一条记录的插入方向改变了的话，这个状态的值 会被清零重新统计。

而剩下和索引有关的内容，我们后面重新讲索引的时候进行西索，下面标记黄色的就是你到现在应该掌握的内容

image-20230614000650554

部分内容参考自：MySQL 是怎样运行的：从根儿上理解 MySQL - 小孩子4919 - 掘金小册 (juejin.cn)