【InnoDB数据存储结构】第1章节：数据页存储结构

目录结构

之前整篇文章太长，阅读体验不好，将其拆分为几个子篇章。

本篇章讲解 InnoDB 数据页的存储结构。

数据的存储结构

索引是在存储引擎中实现的，MySQL 服务器上的 存储引擎负责对表数据的读取和写入。

但是不同存储引擎对 数据存放格式一般是不同的，甚至有的存储引擎都不用磁盘存储数据，比如：Memory。

MySQL 默认的存储引擎是 InnoDB，所以下文均以 InnoDB 展开叙述。

MySQL 数据存储目录

先看下 MySQL 数据库的文件存放在哪个目录中？

使用命令：

show variables like 'datadir';
或
select @@datadir

这个是修改后的目录路径，实际上 MySQL 默认的存储路径为：/var/lib/mysql。

我们每创建一个数据库 database_name，这个目录下（包括自定义的）就会创建一个以 数据库名为名的目录，然后里面存储表结构和表数据文件。

Innodb 存储引擎创建的任何一张表的都会有两个文件：

test_table.frm：存储 表结构的文件，保存表的原数据信息
test_table.ibd：存储 表数据的文件，表数据既可以存储共享表空间文件中（ibdata1中），也可以存储在独占表空间中（后缀 .idb中），是否存储在独占表中，可以通过参数 innodb_file_per_table控制，设置为 1，则会存储在独占表空间中，从 MySQL 5.6.6 版本之后，innodb_file_per_table默认值就为 1 了，因此此后的版本，表数据都是存储在独占表中的。

表数据文件存储结构是怎么样的？

表空间由段（segment）、区（extent）、页（page）、行（row）组成，InnoDB存储引擎的逻辑存储结构大致如下图（图源：小林 coding）：

这个图很是形象，也很到位了。

咱从下往上看，介绍下各名词的含义：

**行（row）：**数据库中的数据都是按行（row）存储的，行记录（是统称）根据不同的 行格式，有不同的存储结构。下文我们重点介绍 InnoDB 存储引擎的行格式。
**页（page）：**记录是按行存储的，但是数据库的读取并不是以 行单位，而是以 页 为单位，每页的大小为 16KB，否则读取一次只能读取一行数据（也就是一次 I/O 操作），只能处理一行数据，效率太低了。
**区（extent）：**B+Tree 的每一层节点之间都是通过双向链表链接的，以页为单位，相邻的两个页之间位置并不是连续的，可能离的非常远，那么数据量大的情况在查询的时候就会产生大量的随机 I/O 操作（效率低）。为了解决这个问题，为某个索引分配空间的时候按照 区为单位，一个区的大小为 1MB，对于 16KB大小的页来说，连续的 64 个页划分为一个 区，这样就使得相邻的页的物理位置也是相邻的，就可以使用顺序 I/O 了。
**段（segment）：**表空间由多个段组成，段时由多个区组成。段一般分为数据段、索引段和回滚段等
- 索引段：存放 B+Tree 非叶子节点区的集合
- 数据段：存放 B+Tree 叶子节点区的集合
- 回滚段：存放回滚数据区的集合（MVCC 就是利用了回滚段实现了多版本查询控制）

再对比下康师傅画的图（原理是一样的）：

补充：

段是数据库中的分配单位
不同类型的数据库对象以不同的段形式存储
- 创建一张表默认会创建一个表段（数据段）
- 创建一个索引默认会创建一个索引段
表空间（Tablespace） 是一个逻辑容器，表空间存储的对象是段，在一个空间中可以由一个段或多个段，但是一个段只能属于一个表空间。
数据库是由一个或多个表空间组成，表空间从管理上可以划分为 系统表空间、用户表空间、撤销表空间、临时表空间等。
系统表空间，/var/lib/mysql/下有一个文件 ibdata1文件，这个文件就被称为 系统表空间。加入创建一个表 test_table:
- 表结构的元数据会存储在 test_table.frm中
- 如果采用 系统表空间 模式，数据信息和索引信息都会存储在 ibdata1中
- 如果采用 独立表空间 模式，数据信息和索引信息都会存储在 test_table.ibd中

根据上图，我们对 InnoDB 数据的存储结构有了大致的了解，下面咱接着来。

数据页结构

了解行记录存储格式之前，我们先了解下页的内部存储构造。

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

在数据库中，不论是读取一行还是读取多行数据，都是将这些行所在的页一次性从磁盘中加载到内存中（一次 I/O 操作），数据库 I/O 操作的最小单位就是页。

查看 InnoDB 存储引擎一个数据页的大小：

show variables like '%innodb_page_size%'
或者
select @@innodb_page_size

扩展：

SQL Server 中页的大小为 8KB，而在 Oracle 中我们用术语 块 (Block)来代表 页，Oracle 支持的块大小有：2KB、4KB、8KB、32KB 和 64KB。

页的内部结构

这 7 个部分作用分别如下所示：

归类为三大部分：

第 1 部分：文件头和文件尾

File Header（文件头）

描述各种页的通用信息（比如：页的编号、其上一页、下一页是谁等）。

文件头的大小为 38 字节。构成如下：

重点讲解上述标为黄色的属性。

**FIL_PAGE_OFFSET（4 字节）：**页号、页码，好比人的身份证号一样，InnoDB 可以通过页号 唯一确定一个页。

**FIL_PAGE_TYPE（2 字节）：**代表当前页的类型，页的类型有以下分类（重点是 Undo 日志页 、系统页）。

**FIL_PAGE_PREV（4 字节）和 FIL_PAGE_NEXT（4 字节）：**InnoDB 是以页为单位存储数据的，数据分散到多个不连续的页中需要把这些页关联起来，FIL_PAGE_PREV 和 FIL_PAGE_NEXT就是记录上一页和下一页的页号。这也就是上一篇 索引的数据结构中所说的，页与页之间是通过双向链表关联起来的。

从而保证：页与页之间在物理上不连续，但在逻辑上连续。

**FIL_PAGE_SPACE_OR_CHKSUM（4 字节）：**代表当前页面的校验和（checksum）。

什么是校验和？

简单理解，就是一个很长的字符串，通过某种特定的算法将整个字符串计算出一个比较短的值，这个值就是这个字符串的 校验和。最常见的是 Hash 算法。

校验和有什么作用？

eg：如果要比较两个很长的字符串，直接进行比较，会比较慢，通过比较两个字符串的校验和（生成校验和耗时可以忽略不计），校验和相同，则代表两个字符串相同，反之则不同。

重点： 文件头和文件尾中都有这个属性：FIL_PAGE_SPACE_OR_CHKSUM。

在页面中的作用：

InnoDB 存储引擎以页为单位进行 I/O 操作，如果某个页从磁盘加载到内存中被修改了，那么 在修改后的某个时间段内需要将数据同步到磁盘中，假如在同步到一半的时候断电了，会造成该页数据传输的不完整。

为了验证一个页是否完整（也就是在同步的时候有没有发生只同步到一半的情况），这个时候可以通过 文件头的校验和和 文件尾的校验和进行比对，如果两个值不同则说明页的传输有问题，需要重新进行传输或回滚，否则任务页的传输已经完成。

再具体一点的过程：

每当一个页面在内存中被修改了，在同步之前要把他的校验和算出来，因为 File Header 在页面的最前面，所以最下被同步到磁盘中，当完全写完时，校验和也会被同步到 File Trailer 中，如果完全同步成功，文件头部和尾部的校验和应该相同，如果同步的过程中发生了异常，则文件头的校验和代表已经修改过的页，文件尾的校验和代表原来的页，这就说明同步数据出现了差错，需要进行 数据重试 或者 回滚 等操作。这里的校验方式就是采用的 Hash 算法。

**FIL_PAGE_LSN（8 字节）：**页面最后被修改时对应的日志序列位置（Log Sequence Number，简称：LSN）。

File Trailer（文件尾）

**前 4 个字节：**代表校验和，和文件头中的校验和相对应。

**后 4 个字节：**代表页面最后被修改时的日志序列位置（LSN），这个部分也是为了校验页的完整性，如果文件头和文件尾的 LSN 值不同，也说明在同步的过程中出错了。

第 2 部分：空闲空间、用户记录、最大最小记录

这部分主要是存储记录，所以 用户记录 和 最大最小记录占据了主要空间。

Free Space（空闲空间）

存储的记录会按照指定的 行格式存储到 User Record部分。在最开始生成页的时候，并没有 User Record部分。每次插入一条数据的时候，都会从 Free Space（空闲空间）中申请一条记录大小的空间划分为 User Record部分，当 Free Space 的空间被申请完之后，也就代表 Free Space 全部被 User Record 替代了，这个时候如果要在插入新的数据，就要申请新的数据页了。

User Record（用户记录）

User Record 中的记录按照 指定的行格式相互之间形成 单链表。

这里的每一行的用户记录对应下文中的 InnoDB 一行记录是如何存储的？这里先不描述，下文逐步讲解。

Infimum+Supremum(最大和最小记录)

对于一条完整的记录来说，比较记录的大小是通过 主键值来判断的，记录会按照主键值大小依次递增排列存储。

InnoDB 规定的最小记录和最大记录构造很简单，都是由 5 字节大小的记录头信息和 8 字节大小的固定部分组成，如下图所示：

这两条记录不是我们自定义的，是 InnoDB 在生成页的时候默认创建的，所以它们来并不存放在 User Records 部分，而是单独存放在 Infimum + Supremum部分，如图所示：

这里有个特殊属性 heap_no，当前页的记录序列号，我们插入数据的记录 heap_no值都是从 2开始，就是因为会默认创建两条最大记录和最小记录，分别占了 0和 1。

第 3 部分：页目录、页面头部

Page Directory（页目录）

假设一条查询 SQL

select * from page_demo where c1 = 3;

方式 1：顺序查找

从 Infimum 记录（最小记录）开始，沿着链表一直往后找，数据量非常大的时候，性能非常差。

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

将所有的记录分成若干个组，这些记录中包含最小记录和最大记录，但不包括 被标记为删除 的记录。
第 1 组只有一条记录，最小记录所在的组。最后一组 也就是最大记录所在的分组，会有 1-8条记录。其他分组，数量在 4-8条记录。【这样做的好处是除了第 1 组外，其余组的记录数会 尽量平分】
每个组中的最后一条记录的头信息中会存储该组中一共有多少条记录，作为 n_owned字段的值。
页面录 用来存储 最后一条记录的地址偏移量，这些地址偏移量会按照顺序存储起来，每组的地址偏移量也被称为 槽（Slot），每个槽相当于指针指向了不同组的最后一条记录

每个页中的记录分组之后如下图所示：

根据上文举的例子，库中现在有 4 条真是用户记录，还有两条隐含的最大和最小记录，分组之后如下图所示：

上图的槽位：

槽 0：指向的是最小记录的地址偏移量
槽 1：指向的是最大记录的地址偏移量

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

页目录中分组的个数是如何确定的？

这个问题也就是上述分组中，为什么第 1 组中最小记录的n_owned为 1，第 2 组中最大记录的n_owned为 5的问题？

InnoDB 规定：第 1 组只有一条记录，最小记录所在的组。最后一组 也就是最大记录所在的分组，会有 1-8条记录。其他分组，数量在 4-8条记录。【这样做的好处是除了第 1 组外，其余组的记录数会 尽量平分】

分组的步骤如下所示：

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

页目录结构下如何快速查找记录？

为了模拟大数据量下如何查找记录的过程，新增了 12 条数据：

insert into page_demo values
(5, 500, 'zhou'),
(6, 600, 'chen'),
(7, 700, 'deng'),
(8, 800, 'yang'),
(9, 900, 'wang'),
(10, 1000, 'zhao'),
(11, 1100, 'qian'),
(12, 1200, 'feng'),
(13, 1300, 'tang'),
(14, 1400, 'ding'),
(15, 1500, 'jing'),
(16, 1600, 'quan');

根据 InnoDB 规定，分为以下几组槽位：

这里为了方便展示，只保留了 16 条记录的头信息中的 n_owned和 next_record属性，省略了各个记录之间的箭头。

上图中左边的槽位数组就可以采用二分法查找，查询过程如下：

找到对应的槽位之后，如果要查找的记录的主键值恰巧为 8，对应上述槽 2 中的最大记录，直接返回
如果要查找的记录的主键值为 6，从上图中可以看出也是在槽 2 中，但是我们之前说过，记录与记录之间是通过单链表的形式链接的，所以直接定位到槽 2 是无法往前扫描主键值小的记录
这个时候我们可以找到槽 1 对应的最大记录 主键值为 4，根据 next_record往后查找两个位置即可找到主键值为 6的记录

小结：

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

通过二分法确定 要查找记录所在的槽位的 上一个槽位，并找到该槽所在的分组中主键值最大的记录
通过当前最大记录的 next_record属性往后遍历，也就可以遍历到 要查找的真实记录 所在的分组中的每一个记录

Page Header（页面头部）

为了能得到一个数据页中存储的记录的状态信息，

比如本页中已经存储了多少条记录？
第一条记录的地址是什么？
页目录中存储了多少个槽等

特意在页中定义了一个叫 Page Header 的部分，这个部分占用了固定的 56 个字节，专门存储当前页的各种状态信息。

有以下属性：

PAGE_DIRECTION

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

PAGE_N_DIRECTION

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

第 4 部分：从数据页的角度看 B+Tree 如何查询

B+Tree 数据是如何记性记录检索的？

通过 B+Tree 的索引查询记录，首先通过根节点开始逐层检索，直到找到记录所在的叶子节点，然后将整个数据页从磁盘中加载到内存中，页目录中的槽（slot）可以通过 二分查找的方式定位到记录所在的槽（分组），通过 链表遍历的方式查找到记录。

普通索引和唯一索引在查询效率上有什么不同？

唯一索引就是在普通索引上增加了约束，也就是关键字唯一，找到关键字之后就停止检索。

而普通索引存在关键字重复的情况，我们知道 InnoDB 存储引擎索引的一个数据页的大小为 16KB，每次 I/O 操作会将记录所在的整个数据页加载到内存中，因为关键字存在重复的情况，所以查找到关键字的记录之后，相比 唯一索引还会继续往后再多判断几次记录是否符合关键字查询条件，但是在 CPU 中，多的几次判断消耗的时间可以忽略不计，整体上来来说，普通索引和唯一索引在查询效率上没有多大差别。