认真学习InnoDB的数据存储结构

索引结构给我们提供了高效的索引方式，不过索引信息以及数据记录都是保存在文件上的，确切说是存储在页结构中。另一方面，索引是在存储引擎中实现的，MySQL服务器上的存储引擎负责对表中数据的读取和写入工作。不同存储引擎中存放的格式一般是不同的，甚至有的存储引擎比如Memory都不用磁盘来存储数据。

由于InnoDB是MySQL的默认存储引擎，所以我们有必要认真学习。

【1】数据库的存储结构-页

① 概述

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

以页作为磁盘和内存之间交互的基本单位，也就是说一次最少从磁盘上读取16KB的内容到内存中，一次最少把内存中的16KB内容刷新到磁盘上。

也就是说在数据库中，无论读一行还是多行，都会将这些行所在的页进行加载。即数据库管理存储空间的基本单位是页（page），数据库IO操作的最小单位是页。

记录是按照行来存储的，但是数据库的读取并不以行为单位，否则一次性读取（也就是一次IO操作）只能处理一行数据，效率会非常低。

页a、页b、页c…页n这些页可以不在物理结构上相连，只要通过双向 链表相关联即可。每个数据页中的记录会按照主键值从小到大的顺序组成一个单向链表，每个数据页都会为存储在它里边的记录生成一个页目录，在通过主键查找某条记录的时候可以在页目录中使用二分法快速定位到对应的槽，然后再遍历该槽对应分组中的记录即可快速找到指定的记录。

② 页的大小

不同的数据库管理系统（DBMS）的页大小不同，比如在MySQL的InnoDB存储引擎中，默认页大小是16KB，我们可以通过下面的命令来进行查看。

show VARIABLES like '%innodb_page_size%'

如下图所示，这里1KB=1024B。

SQL Server中页的大小为8KB，而在Oracle中我们用术语“块”（Block）来代表页，Oracle支持的块大小为2KB、4KB、8KB、16KB、32KB和64KB。

③ 页的上层结构

另外，在数据库中，还存在着区（Extent）、段（Segment）和表空间（Tablespace）的概念。行、页、区、段、表空间的关系如下图所示：

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

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

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

【2】页的内部结构

页如果按类型划分的话，常见的有数据页（保存B+树节点）、系统页、Undo页和事务数据页等。数据页是我们最常使用的页。

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

页结构的示意图如下所示：

这7个部分作用分别如下，我们简单梳理如下表所示：

我们可以把这7个结构分成3个部分。

① File Header和File Tailer

也就是文件头和文件尾。

① 文件头部信息

不同类型的页都会以File Header作为第一个组成部分，它描述了一些针对各种页都通用的一些信息，比方说这个页的编号是多少，它的上一个页、下一个页是谁等，所有的数据页会组成一个双链表。这个部分占用固定的38个字节，是由下边这些内容组成的。

• FIL_PAGE_OFFSET ，每一个页都有一个单独的页号，InnoDB通过页号可以唯一定位一个页。
• FIL_PAGE_TYPE ，代表当前页的类型，InnoDB为了不同的目的而把页分为不同的类型，我们前面提到的都是存储记录的数据页，其实还有很多别的类型的页，具体如下：

我们存放记录的数据页的类型其实是FIL_PAGE_INDEX,也就是所谓的索引页。

② 数据页的链接实现

在文件头部内容中有两个属性：FIL_PAGE_PREV 和 FIL_PAGE_NEXT 。

InnoDB都是以页为单位存放数据的，如果数据分散到多个不连续的页中存储的话需要把这些页关联起来，FIL_PAGE_PREV 和 FIL_PAGE_NEXT 就分别代表本页的上一个和下一个页的页号。这样通过建立一个双向链表把许许多多的页就都串联起来了，保证这些页之间不需要是物理上的连续，而是逻辑上的连续。

③ 检验页的完整性

InnoDB存储引擎以页为单位把数据加载到内存中处理，如果该页中的数据在内存中被修改了，那么在修改后的某个时间需要把数据同步到磁盘中。但是在同步了一般的时候断电了，造成了该页传输的不完整。

为了检测一个页是否完整（也就是在同步的时候可能发生了了只同步一半的情况），这时可以通过文件尾的校验和（checksum值）与文件头的校验和做比对。如果两个值不相等则证明页的传输有问题，需要重新进行传输。否则认为页的传输已经完成。

文件头部和文件尾部都有属性：FIL_PAGE_SPACE_OR_CHKSUM。

④ File Tailer

前4个字节代表页的校验和：这个部分是和File Header中的校验和相对应的。

后4个字节代表页面被最后修改时对应的日志序列位置(LSN):这个部分也是为了校验页的完整性的，如果首部和尾部的LSN值校验不成功的话，就说明同步过程出现了问题。

② 用户记录和最大最小记录及空闲空间

页的主要作用是存储记录，所以最大最小记录和用户记录部分占了页结构的主要空间。

User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表。

User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表。

① Free Space（空闲空间）

我们自己存储的记录会按照指定的行格式存储到User Records部分。但是在一开始生成页的时候，其实并没有User Records这个部分，每当我们插入一条记录，都会从Free Space部分，也就是尚未使用的存储空间中申请一个记录大小的空间划分到User Records部分。

当Free Space部分的空间全部被User Records部分替代掉之后，也就意味着这个页使用完了。如果还有新的记录插入的话，就需要去申请新的页了。

② User Records（用户记录）

User Records中的这些记录按照指定的行格式一条一条摆在User Records部分，相互之间形成单链表。

那么用户记录之间是如何形成单链表的呢？这就涉及到行格式中的记录头信息了。

记录头信息(5字节)：

delete_mask

min_rec_mask

n_owned

heap_no

record_type

next_record

假设表DDL如下所示，那么此时行记录与记录头格式参考下图。

create table page_demo(
  c1 int,
  c2 int,
  c3 varchar(10000),
  primary key (c1)
)charset=ascii row_format=compact;

这部分应该在InnoDB的行格式一章中，这里是为了说明用户记录形成单链表。

这些记录头信息中各个属性如下：

注意，next_record中下一条记录指的并不是按照我们插入顺序的下一条记录，而是按照主键值由小到大的顺序的下一条记录。而且规定Infimum记录（也就是最小记录）的下一条记录就是本页中主键值最小的用户记录。而本页中主键值最大的用户记录的下一条记录就是Supremum记录（也就是最大记录）。

关于delete_mask有个疑问：被删除的记录为什么还在页中存储呢？

实际上记录并没有从磁盘消失。这些被删除的记录之所以不立即从磁盘上移除是因为移除它们之后其他的记录在磁盘上需要重新排列，导致性能消耗。所以只是打一个标记而已，所有被删除掉的记录都会组成一个所谓的垃圾链表，在这个链表中的记录占用的空间称之为可重用空间，之后如果有新纪录插入到表中的话，可能把这些被删除的记录占用的存储空间覆盖掉。

heap_no是没有值为0和1的

这是因为MySQL会自动给每个页里加两个记录，这两个记录并不是我们自己插入的，所以有时候也称为伪记录或者虚拟记录。这两个伪记录一个代表最小记录，一个代表最大记录。最小记录和最大记录的heap_no值分别是0和1，也就是说它们的位置最靠前。

③ 最小最大记录

对于一条完整的记录来说，比较记录的大小就是比较主键的大小（针对InnoDB的聚餐索引来讲）。InnoDB规定的最小记录与最大记录这两条记录的构造十分简单，都是由5字节大小的记录头信息和8字节大小的一个固定的部分组成的，如图所示：

这两条记录不是我们自己定义的记录，所以它们并不存放在页的User Records部分，它们被单独放在一个称为Infimum + Supremum的部分。如图所示：

③ Page Directory（页目录）和Page Header（页面头部）

① 页目录

在页中，记录是以单向链表的形式进行存储的 。单向链表的特点就是插入、删除非常方便但是检索效率不高。最差的情况下需要遍历链表上所有节点才能完成检索。因此在页结构中专门设计了页目录这个模块，专门给记录做一个目录，通过二分查找法的方式进行检索，提升效率。

将所有的记录分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录

第1组，也就是最小记录所在的分组只有1个记录；最后一组，也就是最大记录所在的分组会有1-8条记录；其余的组记录数量在4-8条之间。这样做的好处是，除了第1组（最小记录所在组）以外，其余组的记录数会尽量平分。

在每个组中最后一条记录的头信息中会存储该组一共有多少条记录，作为n_owned字段。

页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称之为槽（slot），每个槽相当于指针指向了不同组的最后一条记录。

② 页面头部

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

【3】从数据页的角度看B+树如何查询

一棵B+树按照节点类型可以分成两部分：

• 叶子节点，B+树最底层的节点，节点的高度为0，存储行记录；
• 非叶子节点，节点的高度大于0，存储索引键和页面指针，并不存储行记录本身；

数据页之间构成了双向链表。故而形成了如下示意图：

当我们从页结构来理解B+树的结构的时候，可以帮我们理解一些通过索引进行检索的原理。

① B+树是如何进行记录检索的？

如果通过B+树的索引查询行记录，首先是从B+树的根开始，逐层检索，直到找到叶子节点，也就是找到对应的数据页为止，将数据页加载到内存中。页目录中的槽（slot）采用二分查找的方式先找到一个粗略的记录分组，然后在分组中通过链表遍历的方式查找记录。

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

我们创建索引的时候可以是普通索引，也可以是唯一索引，那么这两个索引在查询效率上有什么不同呢？

唯一索引就是在普通索引上增加了约束性，也就是关键字唯一，找到了关键字就停止检索。而普通索引，可能会存在用户记录中的关键字相同的情况。根据页结构的原理，当我们读取一条记录的时候，不是单独将这条记录从磁盘上读出去，而是将这个记录所在的页加载到内存中进行读取。InnoDB存储引擎的页大小为16KB，在一个页中可能存储着上千个记录，因此在普通索引的字段上进行查找也就是在内存中多几次“判断下一条记录”的操作。