InnoDB 是一个将表中的数据存储到磁盘上的存储引擎，所以即使关机后重启我们的数据还是存在的。而真正处理数据的过程是发生在内存中的，所以需要把磁盘中的数据加载到内存中，如果是处理写入或修改请求的话，还需要把内存中的内容刷新到磁盘上。而我们知道读写磁盘的速度非常慢，和内存读写差了几个数量级，所以当我们想从表中获取某些记录时，InnoDB存储引擎需要一条一条的把记录从磁盘上读出来么？接下来我们就来深入了解一下 InnoDB 底层存储结构。

行格式

我们平时是以记录为单位来向表中插入数据的，这些记录在磁盘上的存放方式也被称为行格式或者记录格式。InnoDB存储引擎设计了 4 种不同类型的行格式，分别是Compact Redundant、Dynamic 和 Compressed 行格式。我们通过以下命令就可以在创建或修改表的语句中指定行格式：

CREATE TABLE 表名 (列的信息) ROW_FORMAT = 行格式名称

COMPACT

Compact 行格式的具体结构如下图：

变长字段长度列表

我们知道MySQL支持一些变长的数据类型，比如 VARCHAR(M)、VARBINARY(M)、各种TEXT 类型，各种 BLOB 类型，我们也可以把拥有这些数据类型的列称为变长字段，变长字段中存储多少字节的数据是不固定的，所以我们在存储真实数据的时候需要顺便把这些数据占用的字节数也存起来。

如果该可变字段允许存储的最大字节数超过 255 字节并且真实存储的字节数超过 127 字节，则使用 2 个字节，否则使用 1 个字节。

这里为什么是真实存储数据不超过 127 字节用 1 个字节来存储长度？MySQL 为了区分是否是一个字节表示长度，规定，如果最高位为1，那么就是两个字节表示长度，否则就是一个字节。例如，01111111，这个就代表长度为 127，而如果长度是 128，就需要两个字节，也就是 10000000 10000000。同时，这种标识方式，最大长度就是 2^15 - 1 = 32767，也就是32 KB。

NULL 值列表

表中的某些列可能存储 NULL 值，如果把这些 NULL 值都放到记录的真实数据中存储会很占地方，所以 Compact 行格式把这些值为 NULL 的列统一管理起来，存储到 NULL 值列表。NULL 值列表底层其实是一个 BitMap，每个允许存储 NULL 的列对应一个二进制位，二进制位的值为 1 时，代表该列的值为 NULL，二进制位的值为 0 时，代表该列的值不为 NULL。

每个不为 NULL 的字段，占用一位，每超过八个字段，就多一个字节，不足一个字节，高位补 0。假如一个表所有字段都是 not null，那么就没有 NULL 值列表，占用 0 个字节。

记录头信息

记录头信息用于描述记录，它是由固定的 5 个字节组成。5 个字节也就是 40 个二进制位，不同的位代表不同的意思。

• 预留位：有 2 bit 的预留位没有被使用。
• delect_mask：占 1 bit，标记该记录是否被删除，可以看出当我们删除某一条记录时 MySQL 并不会马上从物理磁盘上删除，而是等到某个时间点再把所有被标记为删除的记录删除。
• min_rec_mask：占 1 bit，B+树的每层非叶子节点中的最小记录都会添加该标记。
• n_owned：占 4 bit 表示当前记录所在页面中的槽的记录数（跟页面结构有关，后面会讲）
• heap_no：占 13 bit 表示当前记录在页的位置信息。
• record_type：占 3 bit，表示当前记录的类型，普通数据记录为 000，非 B+数叶子节点记录为 001，页中的伪记录首记录 infimum 行为 010，页中的伪记录最后一个记录 supremum 行为 011。
• next_record：占 16 bit，表示该记录的下一条记录的相对位置。

隐藏列

记录的真实数据除了我们自己定义的列的数据以外，MySQL 会为每个记录默认的添加一些列，也称为隐藏列，包括：

• DB_ROW_ID：非必须，6字节，表示行ID，唯一标识一条记录，当我们创建表时没有指定主键且表中没有值唯一的列，MySQL 会自动帮我们创建该列作为主键。
• DB_TRX_ID：必须，6字节，表示事务 ID，当我们对记录执行事务操作时，会自动生成事务 ID，与 MVCC 机制有关。
• DB_ROLL_PTR：必须，7字节，表示回滚指针，在 undo 日志中通过该指针构成记录的版本链，也是跟 MVCC 机制有关。

特别说明一下，InnoDB 表对主键的生成策略是：优先使用用户自定义主键作为主键，如果用户没有定义主键，则选取一个 Unique 键作为主键，如果表中连 Unique 键都没有定义的话，则InnoDB 会为表默认添加一个名为row_id的隐藏列作为主键。

其他行格式

MySQL5.7 的默认行格式就是 Dynamic，Dynamic 和 Compressed 行格式和 Compact 行格式挺像，只不过在处理行溢出数据时有所不同（什么是数据溢出在文章后面会讲到）。Compressed 行格式和 Dynamic 不同的一点是，Compressed 行格式会采用压缩算法对页面进行压缩，以节省空间。Redundant 行格式是 MySQL5.0 之前使用的一种行格式，不予深究。

数据溢出

如果我们定义一个表，表中只有一个 VARCHAR 字段，如下：

CREATE TABLE test_varchar( c VARCHAR(60000) )

然后往这个字段插入 60000 个字符，会发生什么？MySQL 中磁盘和内存交互的基本单位是页，也就是说 MySQL 是以页为基本单位来管理存储空间的，我们的记录都会被分配到某个页中存储。而一个页的大小一般是 16KB，也就是16384字节，一个 VARCHAR(M) 类型的列就最多可以存储 65532 个字节，这样就可能造成一个页存放不了一条记录的情况。，同时变长字段列表也不够空间来存储该列的长度。

在 Compact 和 Redundant 行格式中，对于占用存储空间非常大的列，在记录的真实数据处只会存储该列的该列的前 768 个字节的数据，然后把剩余的数据分散存储在几个其他的页中，记录的真实数据处用 20 个字节存储指向这些页的地址。这个过程也叫做行溢出，存储超出 768 字节的那些页面也被称为溢出页。

Dynamic 行格式和 Compressed 行格式，不会在记录的真实数据处存储字段真实数据的前 768 个字节，而是把所有的字节都存储到其他页面中，只在记录的真实数据处存储其他页面的地址。

索引页格式

InnoDB 采取的方式是：将数据划分为若干个页，以页作为磁盘和内存之间交互的基本单位，InnoDB 中页的大小一般为 16 KB。也就是在一般情况下，一次最少从磁盘中读取16KB 的内容到内存中，一次最少把内存中的 16KB 内容刷新到磁盘中。InnoDB 为了不同的目的而设计了许多种不同类型的页，存放我们表中记录的那种类型的页自然也是其中的一员，官方称这种存放记录的页为索引（INDEX）页，不过要理解成数据页也没问题，毕竟存在着聚簇索引这种索引和数据混合的东西。

一个InnoDB数据页的存储空间大致被划分成了7个部分：

• File Header：文件头部，占 38 字节，保存页的一些通用信息。
• Page Header：页面头部 56字节，保存数据页专有的一些信息。
• Infimum + Supremum：最小记录和最大记录，占26字节，两个虚拟的行记录，可通过行记录中的 record_type 字段区别该虚拟行记录和普通行记录。
• User Records：用户记录，大小不确定，实际存储的行记录内容。
• Free Space：空闲空间，大小不确定，表示页中尚未使用的空间
• Page Directory：页面目录，大小不确定，记录页中的某些记录的相对位置，起到索引的作用。
• File Trailer：文件尾部，占8字节，校验页是否完整。

User Records

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

当前记录被删除时，则会修改记录头信息中的 delete_mask 为 1，也就是说被删除的记录还在页中，还在真实的磁盘上。这些被删除的记录之所以不立即从磁盘上移除，是因为移除它们之后把其他的记录在磁盘上重新排列需要性能消耗。所以只是打一个删除标记而已，所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为所谓的可重用空间，之后如果有新记录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。

同时我们插入的行记录会记录自己在本页中的位置，并写入了记录头信息中 heap_no 部分。heap_no 值为 0 和 1 的记录是 InnoDB 自动给每个页增加的两个记录，称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录，这两条存放在页的User Records 部分，他们被单独放在一个称为 Infimum、Supremum 的部分。

记录头信息中next_record记录了从当前记录的真实数据到下一条记录的真实数据的地址偏移量。这其实是个链表，可以通过一条记录找到它的下一条记录。但是需要注意注意再注意的一点是，下一条记录指得并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定 Infimum 记录（也就是最小记录） 的下一条记录就是本页中主键值最小的用户记录，而本页中主键值最大的用户记录的下一条记录就是Supremum 记录（也就是最大记录）。

如上图，我们的记录按照主键从小到大的顺序形成了一个单链表，记录被删除，则从这个链表上摘除。

Page Directory

Page Directory 主要是解决记录链表的查找问题。如果我们想根据主键值查找页中的某条记录该咋办？按链表查找的办法：从 Infimum 记录（最小记录）开始，沿着链表一直往后找，总会找到或者找不到，但是链表搜索的时间复杂度是 O(n)，随着链表长度的增加，这样子做的效率并不高。InnoDB 的改进是，为页中的记录再制作了一个目录（Page Directory），他们的制作过程是这样的：

1. 将所有正常的记录（包括 Infimum 记录和 Supremum 记录，不包括标记为已删除的记录）划分为几个组。
2. 每个组的最后一条记录（也就是组内最大的那条记录）的记录头信息中的 n_owned 属性表示该记录拥有多少条记录，也就是该组内共有几条记录。
3. 将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地 方，这个地方就是所谓的 Page Directory，也就是页目录页面目录中的这些地址偏移量被称为槽（英文名：Slot），所以这个页面目录就是由槽组成的。
4. 每个分组中的记录条数是有规定的：对于最小记录所在的分组只能有 1 条记录，最大 记录所在的分组拥有的记录条数只能在 1~8 条之间，剩下的分组中记录的条数范围只能在是 4~8 条之间。

现在看怎么从这个页目录中查找记录。因为各个槽代表的记录的主键值都是从小到大排序的，所以我们可以使用所谓的二分法来进行快速查找。4 个槽的编号分别是：0、1、2、3、4，所以初始情况下最低的槽就是 low=0，最高的槽就是 high=4。比方说我们想找主键值为 6 的记录，过程是这样的：

1. 计算中间槽的位置：(0+4)/2=2，所以查看槽 2 对应记录的主键值为 8，又因为 8 > 6，所以设置 high=2，low 保持不变。
2. 重新计算中间槽的位置：(0+2)/2=1，所以查看槽 1 对应的主键值为 4，又因为 4 < 6，所以设置 low=1，high保持不变。
3. 因为 high - low 的值为1，所以确定主键值为 6 的记录在槽 2 对应的组中。此刻我们需要找到槽 2 中主键值最小的那条记录，然后沿着单向链表遍历槽 2 中的记录。我们可以很轻易的拿到槽 1 对应的记录（主键值为4），该条记录的下一条记录就是槽 2 中主键值最小的记录，该记录的主键值为 5。所以我们可以从这条主键值为 5 的记录出发，遍历槽 2 中的各条记录，直到找到主键值为 6 的那条记录即可。由于一个组中包含的记录条数只能是 1~8 条，所以遍历一个组中的记录的代价是很小的。

这样，一个数据页中查找指定主键值的记录的过程分为两步：

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

Page Header

InnoDB 为了能得到一个数据页中存储的记录的状态信息，比如本页中已经存储了多少条记录、第一条记录的地址是什么、页目录中存储了多少个槽等等，特意在页中定义了一个叫 Page Header 的部分，它是页结构的第二部分，这个部分占用固定的 56 个字节，专门存储各种状态信息。

这里特殊说明两个属性：

• PAGE_DIRECTION：

通过 PAGE_LAST_INSERT 找到上一次插入的数据的位置，假如新插入的一条记录的主键值比上一条记录的主键值大，我们说这条记录的插入方向是右边，反之则是左边。用来表示最后一条记录插入方向的状态就是 PAGE_DIRECTION。

• PAGE_N_DIRECTION

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

File Header

File Header 针对各种类型的页都通用，也就是说不同类型的页都会以 File Header 作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说页的类型，这个页的编号是多少，它的上一个页、下一个页是谁，页的校验和等等，这个部分占用固定的 38 个字节。

File Header 比较重要的是 FIL_PAGE_PREV 和 FIL_PAGE_NEXT 字段，通过这两个字段，我们可以找到该页的上一页和下一页，实际上所有页通过两个字段可以形成一条双向链表。

File Trailer

我们知道 InnoDB 存储引擎会把数据存储到磁盘上，但是磁盘速度太慢，需要以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一半的时候中断电了咋办？为了检测一个页是否完整（也就是在同步的时候有没有发生只同步一半的尴尬情况），InnoDB 每个页的尾部都加了一个 File Trailer 部分，这个部分由 8 个字节组成，可以分成 2 个小部分：

• 前 4 个字节代表页的校验和，这个部分是和 File Header 中的校验和相对应的（ FIL_PAGE_SPACE_OR_CHKSUM）。每当一个页面在内存中修改了，在同步之前就要把它的校验和算出来，因为 File Header 在页面的前边，所以校验和会被首先同步到磁盘，当完全写完时，校验和也会被写到页的尾部，如果完全同步成功，则页的首部和尾部的校验和应该是一致的。如果写了一半儿断电了，那么在 File Header 中的校验和就代表着已经修改过的页，而在 File Trailer 中的校验和代表着原先的页，二者不同则意味着同步中间出了错。
• 后 4 个字节代表页面被最后修改时对应的日志序列位置（LSN），这个也和校验页的完整性有关。

行记录和数据页的存储结构是 MySQL 的基础，只有了解了这些，后面对 MySQL 事务机制、mvcc 机制等才能有深入的认识。