InnoDB 数据存储结构

1. 数据库的存储结构：页

索引是在存储引擎中实现的，MySQL 服务器中的存储引擎负责对表中数据的读取和写入操作。
不同的存储引擎中 存放的格式 不同，例如：Memory 都不使用磁盘来存储数据

注意：本章讨论的是 InnoDB 存储引擎中的数据存储结构

1.1 磁盘与内存交互基本单位：页

InnoDB 将数据划分为 多个 页 ，InnoDB 的大小默认为 16KB

页是磁盘和内存之间交互的基本单位。也就是磁盘一次读取内容到内存中时，一次至少是内存中的 16KB 内容刷新到磁盘中。也就是，在数据库中，无论读多少行数据，都是一次性将该行所在的页 整一页都进行加载。 数据库管理存储空间的基本单位是 页，数据库 I/O 操作的最小单位是 页

若一次读取(一次I/O操作)只能处理一行数据，效率会很低

1.2 页结构概述

页a、页b、页c…可能在物理结构上并不相连，只需要通过双向链表 链接即可。页中的记录按照 主键值 从小到大 组成一个单向链表，由于单向链表查找数据时只可依次遍历，所以每个数据页中都会生成一个 页目录(结构为数组)，则可以在页目录中使用二分法进行查找

1.3 页的大小

MySQL 的 InnoDB 存储引擎中，默认页的大小为 16KB
show variables like '%innodb_page_size%';

SQL Server 中页的大小为 8KB，Oracle 中用 "块"表示页，默认大小为 2/4/16/32/64 KB

1.4 页的上层结构

在数据库中，还存在 区(Extent)、段(Segment) 和表空间(Tablespace) 的概念。空间关系如下图：

区(Extent) 是比页大一级的存储结构，在 InnoDB 存储引擎中，一个区会分配 64 个连续的页，因为 InnoDB 的页大小默认为 16KB ，所以一个区的大小为 64 * 16KB = 1MB

段(Segment) 是由一个或多个区组成，区是文件系统中连续分配的空间 (在InnoDB 中是 连续的 64 个页)，段中的区与区之间不一定是相连的。段是数据库中的分配单位，不同类型的数据库对象以不同的段形式存在。例如：当我们创建数据表、索引时，就会创建相应的段，创建一张表时会创建一个表段，创建一个索引时会创建一个索引段

表空间(Tablespace) 是一个逻辑容器。表空间存储的是段，一个表空间可以有一个或者多个段，但是一个段只能属于一个表空间中。数据库由一个或者多个表空间组成。表空间从管理上可以划分为 系统表空间、用户表空间、撤销表空间、临时表空间等

2. 页的内部结构 ⭐

页按类型划分，常见的有 数据页(保存 B+ 树节点)、系统页、Undo页和 事务数据页。数据页是最常使用的页

数据页的 16KB 存储空间被划分为七个部分：文件头（File Header）、页头（Page Header）、最大最小记录（Infimum+supremum）、用户记录（User Records）、空闲空间（Free Space）、页目录（Page Directory）和 文件尾（File Tailer）

各个部分的作用：

第一部分：File Header（文件头）和 File Trailer（文件尾）

文件头（File Header）：
大小为 38 字节。
作用：描述各种页的通用信息。(例如：页的编号、上下页分别是谁等)
构成：

文件尾 （File Trailer）：
大小为：8 字节

第二部分：Free Space（空闲空间） 和 User Records（用户记录） 和 Infimum + Supremum（最大最小记录）

第二部分主要是存储数据部分

Free Space（空闲空间）：

每次插入数据(按照指定行格式存储)，都会从 Free Space 申请出一个记录大小的空间来给 User Records 。

当 Free Space 所有的空间都被 User Records 替换掉时，则这个页就用完了。若想再插入新的数据，则会申请新的页进行插入。

User Records(用户记录)：
按照指定行格式存储的，相互之间形成单链表

页中一条条数据存储方式：记录行格式的记录头信息

Infimum + Supremum（最大最小记录）：
是由 5 字节的记录头信息 和 8 字节的固定部分组成

因为这两条记录不是我们定义的，所以不存放在 User Records 中

第三部分：Page Directory(页目录) 和 Page Header（页头部）

Page Directory（页目录）：

1. 将页中记录分为多个组（组中不包含已经被标记为“已删除”的记录）
2. 第一组，由最小记录自成一组
   1. 最后一组，包含最大记录所在的组，有 1~8 条记录
   2. 其余组数据为 4~8 条之间
3. 每组最后一条记录的头信息会存储该组一共有多少条记录，作为 n_owned 值
4. 页目录存储每组最后一条记录的地址偏移量，会按照主键值大小进行排序，每组的地址偏移量也称为 槽(slot)，每个槽指向了不同组的最后一条记录

总结：
B+树检索数据：从 B+ 树根开始，知道找到叶子节点，将数据页加载到内存中，页中的槽(slot)使用二分法查找 找到粗略的分组，然后再在分组中通过 链表遍历 查找具体数据

Page Header（页面头部 56 字节）：
数据页中的状态信息：例如本页已经存储了多少条数据

3. InnoDB 行格式 ⭐

查看 MySQL 8.0 的默认行格式：Dynamic
SELECT @@innodb_default_row_format;

查看指定表的行格式：
show table status like '表名'\G
修改
alter table 表名 row_format='xxx';

3.1 COMPACT 行格式 ⭐

3.1.1 变长字段长度列表

字段是变长类型(例如：varchar)，将字段值内容长度转换为16进制后逆向存放在 变长字段长度列表 中

3.1.2 NULL 值列表

Compact 行格式 会将值为 NULL 的列统一管理(逆序)，若表中没有可以为 NULL 的列，则 NULL 值列表不存在

3.1.3 记录头信息(5 字节)

CREATE TABLE page_demo(
	c1 INT,
	c2 INT,
	c3 VARCHAR(10000),
	PRIMARY KEY(c1)
) CHARSET=ascii ROW_FORMAT=Compact;

表中记录的行格式示意图：

记录头信息属性如下：

简化后：

若插入数据：

INSERT INTO page_demo
VALUES (1,100,'song'),
(2,200,'tong'),
(3,300,'zhan'),
(4,400,'lisi');

图示(底层紧密排列且2进制存储)：

delete_mask：值0：表示记录并没有被删除，值1：表示记录被删除

heap_no：表示当前记录在本页的位置；数据库会自动给每页添加两个记录，一个表示最小记录，一个表示最大记录。其 heap_no 值分别为 0 和 1，所以用户数据记录从 2 开始

n_owned：记录该组有多少条记录 (最小记录自成一组) ^af5553

next_record：从当前记录到下一条记录的真实数据的地址偏移量

删除操作：

链表中各个节点始终是按照主键值从小到大排列

添加操作：

直接复用原本被删除的记录的存储空间

若数据页中有多条被删除的记录时，这些被删除的记录会构成一个垃圾链表。为了以后复用方便

3.1.4 记录的真实数据

除了记录真实数据，还有三个隐藏列：

row_id： 在 InnoDB 中，必须要有主键，若没有手动定义主键 则 MySQL 会找一个 Unique 的字段满足非空且唯一的 作为主键，若也没有，则 MySQL 自动生成隐藏列 row_id 来作为主键

3.2 Dynamic 和 Compressed 行格式 ⭐

行溢出：一个页的默认大小为 16KB(即16384字节)。VARCHAR(M) 类型最多存储 65535 个字节。
会出现一个页存储不了一条记录。

解决方案：
分页存储：对于可能出现行溢出的问题，在 Compact 和 Reduntant 行格式中，占用存储空间很大的列，在存储时只会存储一部分数据，将剩余的部分分散存储到其他几个页中进行分页存储，后用 20 个字节指向这些页的地址(其中还包含有其他页中的数据的占用字节数)。

3.2.1 Dynamic 和 Compressed

在 MySQL 8.0 中，默认行格式为 Dynamic

• Dynamic 和 Compressed 行格式存储 BLOB 类型数据时采用完全行溢出的方式存储。即若超出页的存储范围，数据页只存放 20 个字节的指针(指向溢出页的地址)，实际数据都存储在 Off Page （溢出页）中
• Compact 和 Redundant 这两种行格式会在真实数据页中，存储一部分数据(存放 768 个前缀字节)

Compressed 行格式特殊：存储的数据会以 zlib 的算法进行压缩。

3.3 Redundant 行格式

Redundant 是 MySQL5.0 之前的 InnoDB 的行格式存储方式

字段长度偏移列表：按照列的顺序逆序排列的

与其他行格式的不同点：

• 在 字段长度偏移列表中：会将该数据中所有的字段(包含隐藏列)的长度信息都逆序存储到 字段长度偏移列表
• 偏移：计算列值长度时，采用两个相邻数值的差值来计算各个列值的长度 。（不直观）
• 无 Null 列表

记录头信息(占用 6 个字节(48 位))：

• 与 Compact 行格式的区别：
  • Redundant 行格式多了 n_field 和 1byte_offs_flag 两个属性
  • Redundant 没有 record_type 属性

4. 区、段与碎片区

4.1 为什么需要区？

由于 B+ 树中页与页之间是使用双向链表进行存储，若以 页 为单位进行存储，双向链表相邻的页之间的物理位置可能距离较远。当距离较远时，跟磁盘 I/O 的时间较长，这个过程称为 随机I/O。随机I/O 的时间较长，为了解决这个问题，我们尽量让链表中相邻的页在物理位置中也相邻。该过程称为 顺序I/O

所以，引入了区的概念，一个区(每页16KB则区为1MB)在物理位置上是连续的 64 个页。在数据量较大时，索引分配空间时，不按照页为单位进行分配，而是区为单位分配。若数据特别多时，则可以一次性分配多个区（可能会导致空间浪费数据不足填满区）。但是可以消除很多的随机 I/O。

4.2 为什么需要段？

区中存放的页可能是(叶子节点)存储数据的页，也可能是目录项页(非叶子节点)。查询范围数据时，并不方便。所以将叶子节点分为一个区 和 非叶子节点分为一个区，后存放叶子节点的区分为 一个段，存放非叶子节点的区分为一个段(segment)。即一个索引会生成 2 个段，一个叶子节点段，一个非叶子节点段。

除了索引的非叶子节点段和叶子节点段之外，InnoDB中还存储了一些特殊的段，例如：数据段、索引段、回滚段。数据段即为 B+ 树的叶子节点段，索引段即为 B+ 树的非叶子节点段

区和段 的管理都是由存储引擎自身完成的。段只是逻辑上的概念，由一些零散的页和一些完整的区组成

4.3 为什么需要碎片区？

以完整的区作为单位进行分配给某个段时，若数据量较小的表会出现浪费存储空间的情况。
解决方案：
碎片（fragment）区：在碎片区中，并不所有的页都是为了存储同一个段中的数据，而是其中的页可以用于不同的段，例如：有些页用于 段A，有些页用于段B，甚至有些页不属于段。

碎片区直属于表空间，并不属于任何一个段。

为段分配存储空间的策略：

• 开始向表中插入数据时，段是先从某个碎片区以单页为单位进行分配存储空间
• 当段已经占用了 32个碎片区后，则会申请完整的区作为单位进行分配存储空间

4.4 区的分类

大致有 4 中类型

• 空闲区(FREE)：没有用到该区中的任何页面
• 有剩余空间的碎片区（FREE_FRAG）： 表示碎片区中还有空页
• 没有剩余空间的碎片区（FULL_FRAG）： 表示碎片区中所有页都被使用
• 附属于某个段的区（FSEG）：：每个索引都可用分为 叶子节点段和非叶子节点段

处于 FREE、FREE_FRAG 及 FULL_FRAG 的状态下的区都是独立的，直属于表空间。处于 FSEG 状态的区是附属于某个段的

5. 表空间

表空间是 InnoDB 存储引擎逻辑结构的最高层，所有的数据都存放在表空间中。

表空间是一个逻辑容器，表空间存储的是段，在一个表空间中可以有多个段，一个段只可以属于一个表空间。表空间数据库由 一个或多个表空间组成。

表空间可用分为：系统表空间(System tablespace)、独立表空间(File-per-table tablespace)、撤销表空间(Undo Tablespace)、临时表空间(Temporary Tablespace)等

5.1 独立表空间

每张表都有一个独立的表空间，也就是数据和索引都会保存到自己的表中。独立的表空间(即：单表)可以在不同的数据库之间进行 迁移

空间可以进行回收操作（DROP TABLE 操作可以自动回收表空间；）
若是用于统计分析或者是日志表，删除大量数据后可以使用 alter table 表名 engine=innodb；回收不用的空间。

真实表空间对应的文件大小

新创建的表对应的 .ibd 文件只占用了 96K ，6个页的大小（在 MySQL 5.7 中）。注意：.ibd 文件是自扩展的

5.2 系统表空间

系统表空间和独立表空间结构基本一致 ，但整个MySQL 进程只有一个系统表空间，系统表空间会额外存储一些关于整个系统信息的页。