40张图总结MySQL是如何组织数据的！

开发中，免不了和 MySQL 数据库打交道，为了弄明白 MySQL 到底是如何存储数据的，花费了一些时间，详细阅读相关资料后，写下此文，方便后续自己复习相关知识。

本文的主要参考资料：

• 书籍：从根上理解MySQL

重要的事情说三遍！！！

注：图中的 File Tail 对应的是 File Trailer，并不影响理解，因此我错了但我不就是不改！(手动狗头保命.jpg)。

写在前面一些无关紧要的内容：

在 MySQL 中，可通过如下命令查看默认的行格式

show variables like '%row_format%';

可以通过如下命令修改表的行格式

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

不同版本的 MySQL 的默认行格式不一样，MySQL 支持四种行格式

• Compact: 本文主要介绍的行格式。
• Redundant: 5.0 之前的行格式，不做介绍。
• Dynamic: 和Compact行格式差不多，在处理页溢出时不同于 Compact，不介绍。
• Compressed：和Compact行格式差不多 会采用压缩算法，对页面压缩，节省空间，不介绍。

开始吧！

图片来自网络

InnoDB之Compact行格式

在介绍行格式之前，先说以下如何查看MySQL支持的存储引擎，命令如下：

SHOW ENGINES;

可通过此输出查看数据库的默认存储引擎。

Compact 行格式主要由几部分构成，如下图所示：

其中可变长字段长度列表，空值列表都不一定会存在，取决于具体的建表语句！

可变长字段长度列表

可变长字段列表：该列表不一定存在，取决于在定义字段时，是否使用VARCHAR(M)、VARBINARY(M)、各种TEXT类型，各种BLOB类型字段来进行定义字段，如果存在上述类型的定义的列，则列表就会存在；该列表中字段长度的顺序为字段自定义顺序的逆序。 除此之外变长字段长度列表中只存储值为 非NULL 的列内容占用的长度，值为 NULL 的列的长度是不会储存的。以下表为例，说明逆序

CREATE TABLE `test`  (
  `id` int(11) NOT NULL AUTO_INCREMENT,
  `username` varchar(10) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `password` varchar(10) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `char_col` char(10) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  `nickname` varchar(10) CHARACTER SET utf8 COLLATE utf8_general_ci NULL DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB AUTO_INCREMENT = 1 CHARACTER SET = utf8 COLLATE = utf8_general_ci ROW_FORMAT = Dynamic;
​
SET FOREIGN_KEY_CHECKS = 1;
INSERT INTO `test` VALUES (1, 'aaaa', 'bbb', NULL, 'bababa');

在上面的SQL语句中，添加了一条记录，其变长字段的长度顺序如下图所示：

上面的情况比较简单，因为变长字段的值长度比较小，当字段的值较大时，MySQL 是如何知道我该用一个字节还是两个字节来存储数据呢？

InnoDB操作的最小单元是页，一个页的大小为16kb即 24 Kb，因此 2 个字节 16个bit完全够用！

这个和我们在创建数据库时使用的字符集有关！以utf8为例。 可变长列的长度计算 W M L

• W：该字符集中一个字符能够占用最大的字节数，在utf8中一个行字代表3个字节。
• M：该列最多存储的字符数，即创建列时 varchar(M) 中的值 M
• L ：实际的存储长度
• M * W ≤ 255：当 W * M的值小于等于255时 则用一个字节来表示
• M * W ＞255
  • 如果 L ≤ 127 则用一个字节
  • 如果 L > 127 则用两个字节 通过判断字节的最高位是否为 1 来判断当前字节的有效数据是半字节还是一个字节，极限情况下取值为 214 。

NULL 值列表

和可变长列表一样，该列表不一定存在，是否存在取决于在自定义表字段时，是否允许值为null，如果没有允许为null的字段，则没有null值列表，如果允许字段为null，则一个字段对应一个bit位，该列表中的顺序是字段定义顺序的逆序，为 1 时代表该列的值为null，为 0 时代表不为null，null值列表的长度必须是整个字节，不满一个字节则高位补 0。如下图，4 个列的值可以取 null ，则只需要一个字节即可，如果是 9 个列，则需要两个字节！

记录头信息

记录头信息：是 MySQL 给每一条记录添加的信息，每一条记录都有！！共五个字节长度！具体组成由以下基本分构成

• 2个预留位：1个1bit，共 2 个bit，没有用到！
• delete_mask：删除位，1 个bit， 1 删除 0未删除！从这里也可以看出，MySQL 底层做的也是逻辑删除。
• min_rec_mask：b+树每层非叶子节点中的最小记录会添加此标记，将值置为 1 占据1个bit
• n_owned： 当前记录拥有的记录数 取值不会超过8， 4个bit。后面详细说！
• heap_no: 堆号，占据13bit
• record_type：记录类型 3个bit
• next_record: 下一条记录的相对位置，2个字节，实际上就是一个指针！

简单图示如下图所示：

详细构成：

第一个字节：

第2-3字节：

第4-5字节：

五个字节分别所起的作用在图中已说明！

隐藏列

隐藏列也是 MySQL 给我们额外添加的数据，主要由三部分组成！

• row_id：6个字节，非必须，当建表时，没有主键且没有唯一列时，会生成此列。
• trx_id：6个字节，必须有，最后修改此纪录的事务id，混个脸熟，本文不涉及。
• roll_point：7个字节，必须，混个脸熟，本文不涉及。

示意图如下：

行格式小结

注：char(M)这种列，在定长字符集如ASCII字符集，不会加入到变长字符集列表，在变长字符集下，会加入到可变长列表，同时要求必须占用M个字节，即使是一个空字符串，也会占据这么多。

数据页

在上面的内容中，介绍了 Compact 行格式的具体格式，但是 MySQL 和磁盘打交道的最小单位是一个页，一个页的大小为 16KB，数据页的通用格式如下图：

其中 File Head 和 File Tail 是通用的，唯一的就是中间部分的不同，存储我们存入的数据的数据页的结构如下图

上图中的几部分主要有

• File Head 38 Bytes
• Page Head 56 Bytes
• infimum + supremum 26 Bytes
• user record
• Free Space
• Page Directory >= 4 Bytes
• File Tail 8 Bytes

首先还是从记录部分说起即 User Record部分

User Record

首先是最大最小记录 Infimum supremum，这两条记录各占 13 个字节即 5 个字节的记录头信息和8个字节的数据组成，其图示如下图

最大记录图示：

最小记录图示：

暂时不要管图中的数字！

在我们创建表后，我们通常会插入数据，不然建表的意义干啥？当我们 insert 数据之后，此时数据页的user record 部分的结构就如下图所示。

上图中有如下几个属性要关注：

n_owned：最小记录里的值是 1，最大记录的值是 4，而三条用户记录是 0，图中没有画出！ 为什么他们的值不是一样，这是因为为了方便我们高效的查找数据，InnoDB 把记录分了组，最小记录只能自己一组，这就是为什么它的值为 1，最大记录的组取值范围为 1~8，其余的组的取值范围只能是 4~8。这里只有三条插入的记录加上自身所以最大记录的取值为 4！

heap_no: 当前记录在本数据页的位置， 插入的记录的 heap_no 是从 2 开始的，这是因为最小最大记录的堆号为 0 和 1。

next_record：当前记录的下一条记录，这个下一条记录不是指的我们插入的顺序，是指按照主键大小的进行排序的下一条记录。next_record 指向的不是变长字段，而是下一条记录的 next_record 位置，这是因为这个位置向右就是数据，向左就是记录相关的统计信息！！

Page Directory

当在数据页中插入了大量的数据之后，假设数据页布局的示意图如下图：

此时如何进行数据搜索呢？这就进行需要这一部分的主角出场了 Page Directory 页目录！我们在前面已经知道了，数据是按照主键大小进行排列的，也就是说他们实际上是一个主键递增的序列！想到了什么！二分查找算法！在说如何利用二分查找算法进行查找数据之前，首先来看看页目录是如何形成的。

将所有正常的记录（包括最大和最小记录，不包括标记为已删除的记录）划分为几个组。

每个组的最后一条记录（也就是组内最大的那条记录）的头信息中的n_owned属性表示该记录拥有多少条记录，也就是该组内共有几条记录。

将每个组的最后一条记录的地址偏移量单独提取出来按顺序存储到靠近页的尾部的地方，这个地方就是所谓的Page Directory，也就是页目录（此时应该返回头看看页面各个部分的图）。页面目录中的这些地址偏移量被称为槽（英文名：Slot）占据2个字节，所以这个页面目录就是由槽组成的。

假设数据页上有三条用户插入的数据，此时页目录结构如下图所示：

99 和 112 代表的是距离文件开头的偏移距离为 99 字节 和 112 字节。

如果数据页有超过8条数据时，那么 slot 的情况是如何呢？这就需要讨论下，InnoDB是如何进行数据分组的了！

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

假定此时插入了 9 条数据 ，则情况如下：

上面说了，在数据页内数据较多，因此在查找记录时，最好不要遍历该链表，而我们提到了二分查找。因此，就来看看这个查找过程！

• 首先找到对应数据所在的页面中的那一组，即所在的 slot
• 因为 slot 记录的是该组的最大记录，因此只要找到上一个slot的记录，该记录的下一条记录就是所在slot 的最小记录
• 通过 next_record 遍历即可

假定上图中的 heap_no 和记录的主键是一样的，查找主键为8的数据其过程如下

• ( 0 + 2 ) / 2 = 1，找到第2个槽，他对于的 id 为 5 < 8
• 此时可以确定数据在槽 2 所对应的组里
• 从 5 + 1 = 6 处向后遍历即可！

Page Header

Page Header的作用就是为了得到数据页中存储数据的信息，该部分占据56个字节是固定的，具体构成如下表：

File Header

Page Header 描述的业内相关的信息，那么 File Header 的主要作用就是描述当前页的一些通用信息！就有一点感觉一个主内一个主外一样！

File Header的结构。固定占据38个字节

从具体作用来看：

主外的负责和其他数据页形成双向链表，如下图

File Trailer

即图中的 File Tail，写错了！但是意思是那么个意思！，占据八个字节！

• 前4个字节代表页的校验和
• 后4个字节代表页面被最后修改时对应的日志序列位置（LSN）

索引

在介绍索引之前，先记住一句话：在使用 InnoDB 存储引擎时，索引即数据！至于为什么，看完这部份相关内容就明白了！

另外修改一下页面的作图方式，如下图：

首先对这个图做一个说明：

• 记录从上到下来看，第一个代表当前记录的类型
• 从左往右看最左的为最小记录，最右边的为最大记录，即record_type 为 2 和 3。
• 灰色的框里面的数据对应的是这两条记录的 n_owned，
• 枣红色的框对应的是我们插入的用户记录的主键值
• 最下面的两个框 99 112 代表的是页目录，为什么是 99 呢 38 + 48 + 5 = 99， 38 + 48 +13 + 5 = 112，至于为什么看看页目录的处的图即可！

其他信息就省略了！

我们知道数据页内的数据是依照主键从小到大的顺序形成的单向链表，数据页与数据页之前形成双向链表。数据页内是通过分组+二分法进行查找数据的。那么我们该如何高效的确定数据页在哪呢？或者说该如何组织这些数据页以便我们查找时，不需要从头开始遍历整个数据页组成的数据页集合呢？可不可以也利用类似于二分查找的方式来确定数据在哪一个页面呢？答案就需要聚簇索引来揭秘了！

聚簇索引

我们知道数据页内的数据是按照主键大小排列的，这一点和数据页内的分组好像有相似之处，因此为了设计InnoDB的大佬就复用了数据页，只不过这个页存储的就不再是我们的记录，而是一条条目录项记录，由所在页面的最小记录 + 所在页面的页号构成！就如下图所示，

这样的一个结构我们就称之为B+树，这个结构也是我们说得索引！由主键构成的索引就是聚簇索引！先来看看这个图

• 图中红框全球的数据中，有一个红色小框的1，这个就对应在讲行格式时，记录头信息的第四个bit min_rec_mask，其余的在上面也介绍过！
• 最上面的页面是根页面，在建立索引时，根页面一旦分配就不会改变，即根页面万年不动窝！
• 需要注意各个页面的页号的变化！
• 最底层的是叶子节点，即叶子节点存储了完整的数据，而非叶子节点存储的主键 + 页号，并没有存储完整的用户记录！
• 页目录都有，只是非叶子节点没有画出来！并不是没有！！

到这里你是否明白了索引即数据？

非聚簇索引

非聚簇索引：指的是根据其他非主键列形成的索引，又称二级索引。整体结构和聚簇索引没有区别，但是在目录项和叶子节点的内容上有一点点不同，假定是根据某一个列创建的二级索引，那么存储的目录项是 该列的值 + 主键的值 + 页号

如下图所示：根页面没有画出

• 为什么需要主键的值？这是因为我们通过其他列建立的索引，不能保证值是唯一的，如果只存储该值就如页号 12 所画的那样，假定此时插入一条主键为28，索引列的值也是 a 的话，在更新该二级索引时，应该把他放在 17-5 之间 还是 5-20 之间呢？所以这就是为什么需要存储主键值了！
• 叶子节点上存储的是非完整的记录，只存储了索引列 + 主键 ，这是为了节约空间，如果每一个索引都存储完整的用户记录，那么几乎都要将数据复制一遍。
• 由于存储的是索引列 + 主键 ，因此在使用此二级索引查找时，需要根据主键回表查询完整的数据记录

Question：为什么不把数据存在非叶子节点上？

这是因为，如果把数据存储在非叶子节点上，那么二叉树的层级不好控制，进而导致大量的随机IO出现，因为插入的数据的大小未知，有可能一个页面的数据很少，也有可能很多，如果页面数据很少则会导致二叉树的层级很深！

Question：这样做就不会导致页面层级深吗？

不会，假定一个数据页可以存储的数据为1000条，那么一个目录页按照10000 条来算，假定目录层级为 3 + 1，则可以存储 10000 * 10000 * 10000 * 1000 条数据！而如果放在非叶子节点上，由于每一层存储的数据减少，就必然导致层级增加，从而就会导致随机IO数量增多！降低效率！想一想这是为什么规定一个数据页必须存储两条以上的数据的原因，防止二叉树链表化！这大概也是 heap_no 用 13 个 bit 就能表示的原因！2 * 213 = 214 = 2 4 * 2 10 = 16Kb ！(假定一个记录占据2字节，实际上由于记录头和隐藏字段的原因不可能这么小！)

独立表空间

我们知道数据是存在数据页上的，那么数据页又存在哪里的？索引又是怎么和数据表对应的起来的呢？这就是这部分的主题——表空间，

表空间分为独立表空间和系统表空间，表空间是一个抽象的概念，对于系统表空间来说，对应着文件系统中一个或多个实际文件；对于每个独立表空间来说，对应着文件系统中一个名为表名.ibd的实际文件。

在表空间之前，首先要明白区、组、段这几个概念：

区：一个区由64个页组成，在物理上连续的64个页！

组：由256个区组成！

段：是一个逻辑概念，某些零散的页以及一些完整的区的集合。分为叶子节点段，非叶子节点段和回滚段等，回滚段不介绍，叶子节点段和非叶子节点的如下图所示，后面会有详细的图示介绍

表空间：由一个一个组构成，其中第一个组的第一个分区的第一个页面记录了整个表空间的属性，简单图示就如下图所示

区

区是由连续的64个页组成的，是一个逻辑概念，为了管理好区，InnoDB的设计者设计了一个40字节的XDES Entry结构，如下图

• Segment ID：每一个段都有一个唯一的编号，用ID表示，此处的Segment ID字段表示就是该区所在的段。前提是已分配给某个段。
  • 分配给具体的某一个段，该段中有相应的链表进行管理。属于段而非表空间！！
• List Node：将若干个XDES Entry结构串联成一个链表
• State：表明区的状态，分别是：FREE、FREE_FRAG、FULL_FRAG和FSEG
• Page State Bitmap：占用16个字节，也就是128个比特位。我们说一个区默认有64个页，这128个比特位被划分为64个部分，每个部分2个比特位，对应区中的一个页。第一位表示页是否空闲，第二位暂时没有使用。

详细结构如下图

XDES链表

表空间中，通过如下三个链表来管理分区：

• 把状态为FREE的区对应的XDES Entry结构通过List Node来连接成一个链表，这个链表我们就称之为FREE链表。
• 把状态为FREE_FRAG的区对应的XDES Entry结构通过List Node来连接成一个链表，这个链表我们就称之为FREE_FRAG链表。
• 把状态为FULL_FRAG的区对应的XDES Entry结构通过List Node来连接成一个链表，这个链表我们就称之为FULL_FRAG链表。

链表基节点：这个结构中包含了链表的头节点和尾节点的指针以及这个链表中包含了多少节点的信息，这样我们就可以通过链表基节点快速找到对应的链表

• 占据16个字节长，List Length 属性记录了当前链表的节点个数。
• First Node Page/Offset：组成一个指针，指向头节点
• Last Node Page/Offse：指向尾节点

链表的状态转换过程：即数据的插入过程。

首先会查看表空间中是否有状态为FREE_FRAG的区，也就是找还有空闲空间的碎片区，如果找到了，那么从该区中取一些零碎的页把数据插进去；否则到表空间下申请一个状态为FREE的区，也就是空闲的区，把该区的状态变为FREE_FRAG，然后从该新申请的区中取一些零碎的页把数据插进去。之后不同的段使用零碎页的时候都会从该区中取，直到该区中没有空闲空间，然后该区的状态就变成了FULL_FRAG。

注：上面所提到的这三个链表是直属于表空间的。

段

在前文提过，段是完成的区加上一些松散的页的集合，段其实不对应表空间中某一个连续的物理区域，而是一个逻辑上的概念。设计InnoDB的大佬为每个段都定义了一个INODE Entry结构来记录一下段中的属性。

• Segment ID：在前面提到过，就是指这个INODE Entry结构对应的段的编号（ID）。
• NOT_FULL_N_USED：指的是在NOT_FULL链表中已经使用了多少个页。下次从NOT_FULL链表分配空闲页时可以直接根据这个字段的值定位到。而不用从链表中的第一个页开始遍历着寻找空闲页。
• 3个List Base Node：这三个链表基节点不上指的表空间的三个链表，而是指的这三个，在NOT_FULL_N_USED所提到的链表也是指的这里的链表，不是表空间，不是表空间，不是表空间！！！
  • FREE链表：同一个段中，所有页都是空闲的区对应的XDES Entry结构会被加入到这个链表。此处的FREE链表是附属于某个段的。
  • NOT_FULL链表：同一个段中，仍有空闲空间的区对应的XDES Entry结构会被加入到这个链表。
  • FULL链表：同一个段中，已经没有空闲空间的区对应的XDES Entry结构会被加入到这个链表。
• Magic Number：标记这个INODE Entry是否已经被初始化。如果这个数字是值的97937874，表明该INODE Entry已经初始化，否则没有被初始化。
• Fragment Array Entry：这个结构一共4个字节，表示一个零散页的页号。结合示意图，充分说明段是一些零散页和一些完整的区的集合。

注：一个索引对应两个段，叶子节点段和非叶子节点段，因此如果表中有2个索引，则上述提到的链表数量为 3 + 4 * 3 = 15个链表！

Question：表可以看做由不同的组组成的，那么一个表空间里最多有多少个组？

• 这需要回到File Header结构中去看，在File Header中有一个FIL_PAGE_OFFSET属性，具有4个字节长度也就是32位，也就是说一个表空间里最多有 232个数据页，那么就最多存储 2 32个数据页即64TB的数据，而一个组的大小为256M。

Question：一个索引有两个段，一个段又是以区为单位的，是不是建立一个索引就会占据2M的空间？

• 不是，这就不得不提到碎片区了。在一个碎片区中，并不是所有的页都是为了存储同一个段的数据而存在的，而是碎片区中的页可以用于不同的目的，比如有些页用于段A，有些页用于段B，有些页甚至哪个段都不属于。碎片区直属于表空间，并不属于任何一个段。所以此后为某个段分配存储空间的策略是这样的：
  • 在刚开始向表中插入数据的时候，段是从某个碎片区以单个页为单位来分配存储空间的。
  • 当某个段已经占用了32个碎片区页之后，就会以完整的区为单位来分配存储空间。

好巧，一个INODE结构刚好有32个Fragment Array Entry。

组

组就是由256个分区组成的一个逻辑结构，在第一个组的第一个分区的第一个页里，记录整个表空间的一些属性。其中在独立表空间里，第一个组的前三个页是和其他组不同的，从第二组开始，后续的组的前两个页都是相同的，为一个XDES页面和IBUF_BitMap。

组简单的示意图

FSP_HDR

第一个页面的页面类型是 FSP_HDR 类型，其结构如下图。

大部分属性我们都见过了，就看一下FIle Space Header结构。示意图如下图所示！

看重点首先是三个链表基节点！我们前面提到的直属于表空间的三个链表的基节点就在这里！天上飞了半天，终于落地了！

然后是List Node for INODE Page List 结构

• List Node for INODE Page List : 通用链表节点 12字节 存储上一个 INODE 页和下一个 INODE 页的指针

其次是最下面的两个结构在介绍完XDES类型页和INODE类型页之后，再来介绍这个。

XDES 和 INODE 类型页的作用都查不多，只不过用于存储的数据结构不同罢了，如下图

INODE 页面详细结构

XDES存储的是区相关的，INODE存储的是段的信息，前者存储了256 个区即这个组里的区的信息，后者存储了85个段的相关信息！那么当表空间超过85个段怎么办？这就是刚刚没有介绍的两个属性了！

因为一个表空间中可能存在超过85个段，所以可能一个INODE类型的页不足以存储所有的段，此时就需要额外的INODE类型的页来存储这些结构。为了方便管理这些INODE类型的页，设计InnoDB的大佬们将这些INODE类型的页串联成两个不同的链表：

• SEG_INODES_FULL链表：该链表中的INODE类型的页中已经没有空闲空间来存储额外的INODE Entry结构了。
• SEG_INODES_FREE链表：该链表中的INODE类型的页中还有空闲空间来存储额外的INODE Entry结构了。

那么问题来了，在第一个组中的第三个页面就是存储段结构的页面，我们可以通过定位这个页面的方式去定位段页所形成的列表，为什么还需要这2个节点？

• 这是因为假定当前表空间中有 86 个段，则需要两个页去存储这86个Inode结构，但此时这两个页对应的是两种状态，一个是FULL，一个是Not_FULL，因此如果通过这个页去定位，另一种状态的咋办呢？毕竟他们没在一条链表上，所以这才定位了两种基节点咯。

Question：数据页是如何确定他是属于那个段的？

• 这个问题又需要回到File Header 中，在这里有PAGE_BTR_SEG_LEAF、PAGE_BTR_SEG_TOP这两个结构，前者是叶子节点段的头部信息，后者是非叶子节点段的头部信息，他们都对应了一个SegmentHeader结构，如下图

图已经写的很清楚了，就不介绍了！幸苦各位看官了

最后用一张图总结一下在独立表空间中前文所提到的各种概念吧！