天鹅绒房间 主页 | Home归档 | Archives分类 | Categories
InnoDB 表结构
|MySQL基础架构
Word count: 6k|Reading time: 18 min

InnoDB 表结构

前言

在 InnoDB 体系结构中已经讲述了后台线程如何在内存中工作，以及如何和磁盘中的内容交互，其中提到 如果内存中没有对应的表中数据，数据库通常会先从磁盘中读取需要数据进入内存后再使用，并且读取数据的最小单位是页而不是行。

作为存储数据的表和数据页的结构，此前并没有详细提及，也就意味着对数据在磁盘中存储的形式并不了解。如果在没有了解数据页的情况下就学习索引中提到的 B+ 树等存储模型，很容易只见其表面而不理解其实质，但是在学习数据页结构之前最好对索引有最基本的了解，否则可能会有些费劲

表空间结构

概述

表空间的主键

  • 无论是否在创建表的时候设置相应的主键，每张表都会拥有唯一的主键
    • 如果创建表的时候就设定了相应的主键，那么这张表的主键那就设置的这个
    • 如果创建表的时候没有设置相应的主键，那么 InnoDB 就会去查询整个表
      • 如果查询到表中存在唯一索引、就会将唯一索引作为主键使用
      • 如果没有查询到唯一索引，那么就会自动生成一个 6B 的 ROWID 作为主键

注：之后的索引篇章还会提到和主键设置相关的内容，这里只是简单根据书中内容提几句

表空间的组成

表空间的组成

  • 每张表的组成部分主要是 表结构的定义和表存储的数据 两个部分，而这两部分数据通常都是分开存储的

    • 每张表的定义部分始终存储在 .frm 文件中，主要记录使用的字符集、引擎、字段、索引等和表相关的信息

    注：无论任何存储引擎都是采用 .frm 文件保存表的定义信息的，也就是说这个是和引擎无关的

    • 每张表的数据部分既可以共同存储在共享表空间中也可以分开存储在独立表空间中 => 通过参数 innodb_file_per_table 控制
      • 如果开启参数的使用，每张表的数据都会独立存储在 .ibd 文件中（独立表空间）
      • 如果没有开启参数的使用，那么每张表的数据都共同存储在 .ibdata 文件中（共享表空间）

    注：无论是否开启参数，表的定义部分始终都是单独存储在 .frm 文件中的

  • 共享表空间会将所有数据库中的数据、索引、插入缓冲、二次写缓冲、事务相关等信息全部存储在一起，但是这样就会存在许多问题

    • 因为所有数据库的内容混合到一起了，备份单个数据库或者单张表中的数据是很麻烦的
    • 删除行为只会将被删除的数据标记为不再使用，之后新的数据直接覆盖，这也就意味着在数据删除之后文件不会变小
    • 删除行为还有可能造成严重的碎片问题，也就是之前被删除的表释放的空间无法容纳之后任何一张表，这也就导致空间的浪费

  • 独立表空间则是将每个数据库中的每张表的信息分开存储，每张表都将数据、索引、插入缓冲独立存储在一个文件中

    • 独立表空间可以回收每个文件中被删除的数据（optimiza table），碎片问题则不会太影响性能
    • 独立表空间中不会存储二次写缓冲、事务等相关信息，这些内容始终是共享表空间存储的

注：MySQL 5.6 之后就默认开启 innodb_file_per_table 这个参数

逻辑存储结构

此前已经提到数据库中的每行数据在磁盘中是按照页的形式进行组织的，这是物理上的形式。在逻辑上还会进行更加细致的划分，不过在解释为什么还要细分的之前，先来看看整体的逻辑存储结构是如何划分的

表的逻辑存储结构

1、行

大多数存储引擎都是面向行进行数据存储的，也就是每张表中的数据是按照行进行存放的。除此之外，现阶段有少部分引擎是按照面向列存储数据的，例如 infobright 存储引擎，不过这里不加以讨论

面向行进行存储通常会涉及到两种行存储的格式

  • Compact 行记录格式
  • Redundant 行记录格式

这两种格式就是行记录在磁盘上的物理存储形式了，将在之后物理存储结构中提及，这里暂且跳过

2、页

注：这里稍微提前涉及点索引相关的内容，方便之后和索引的内容结合，最好先对 B+ 树有一定的了解

每次磁盘的 I/O 读写的最小数据单位就是页，默认大小为 16KB。此外，页也分为多种不同类型从而存储不同类型数据，这里最常提到的是这两类

  • 数据页：仅存储数据的页面，通常作为 B+ 树的叶子结点存在，并且会通过双向链表将所有叶子结点串联起来
  • 索引页：仅存储指向数据页的指针，也就是索引，通常都是作为 B+ 树的非叶子结点存在，传统 B+ 树不会串联非叶子结点
  • 不过 MySQL 对传统的 B+ 树索引模型进行了些微修改，会将每一层结点都采用双向链表串联起来而不仅仅是叶子结点
索引页和数据页

至于为什么要采用 B+ 树组织表空间中的所有页面而不是哈希表、有序数组或者其他的平衡树，这部分在索引模型中详细介绍。不过，这里需要先讲述为什么要使用双向链表将每层结点都串联起来，这个其实也是 B+ 树的优点之一。

数据库中的查询通常分为等值查询和范围查询两种，通常前者查询只会得到一个结果，而后者查询会得到一个结果集

-- 等值查询
select * from T where ID = 1;
-- 范围查询
select * from T where ID between 2 and 5;

在了解查询的种类之后，再来了解为什么要使用双向链表串联叶子结点，那么先思考下如果没有双向链表，要如何进行查询？

首先存储引擎会遍历 B+ 树并根据索引结点找到符合条件的叶子结点，然后遍历数据页找到符合条件的记录

这样确实能够找到部分符合条件记录，但是如果其他的数据页中也有符合条件的记录怎么办？

如果没有双向链表，那么就意味着我们需要重新遍历一次 B+ 树，去找到其他符合要求的数据页，这个过程显然是非常重复且低效的。如果有双向链表，那么就可以直接向后遍历，从而到达下一个数据页并开始遍历数据页中的行记录，这样就避免了重复遍历 B+ 树的行为，提高了查询的效率

3、区

每个区是由 64 个连续的页组成的，而默认每张页的大小都是 16KB，那么每个区的默认大小就是对应 1MB（2^14^ * 2^6^ = 2^20^）

既然页分为不同类型，那么区也会分为不同类型

  • 数据区：表中所有的数据页都会对应存储在数据区中，而不会出现在其他区中
  • 索引区：表中的所有的索引页也都会存储在对应索引区中，而不会出现在其他区

首先，先来想想，为什么区中的页都必须是连续的？不连续可以吗？

理论上 B+ 树确实能够提高查询速度，但是实际上却不一定以能够提高查询速度。如果每个数据页并不是连续存储的话，即使逻辑上是相邻的，磁盘也需要花费相应的时间去查询数据页在磁盘中的位置也就是说理论上的顺序读取实际变成了随机读取，从而导致磁盘读写的效率并不会有理论上的高，所以需要将多个页连续存放

所以区中的页面最好都是连续的，否则就会降低范围查询的效率，其本质原因在于逻辑视图和物理视图不一致

现在，你可能想问为什么区也要分为不同的类型呢？其实理由非常简单，和刚才基本相同

如果直接将索引页和数据页混合在一起，就又可能出现逻辑视图和物理视图不一致的情况，逻辑上两个数据页是相邻的两个叶子结点，但是实际上中间却相隔了好几个索引页，这样又会变成随机读写。磁盘必须花费相应的时间去寻道，从而查找到需要读写的数据，这样还是降低了磁盘读写的效率

注：总的来说，区中的页面必须连续以及对区也进行分类的目的就是为了提高 B+ 树这种索引模型的查询效率

4、段

每个段都是多个区组成的，通常也分为不同的类型，数据段、索引端、回滚段等等

参考博客：InnoDB表结构与页结构详解

物理存储结构

行记录格式

注：MySQL 5.1 之后都是默认采用 Compact 行记录格式，MySQL 5.6 之后都是采用 Dynamic 行记录格式

1、Compact 行记录格式

Compact 行记录格式

  • 事务 ID（6B）& 回滚指针（7B）

  • ROWID：如果没有定义主键，则会增加该列作为主键

  • 每列的数据

2、Redundant 行记录格式

Redundant 行记录格式

Redundant 行记录格式没有 NULL 标志位

  • 字段长度偏移列表

    • 记录每个字段的长度而不仅仅只是可变长字段的长度，其余规则没有任何区别

  • 记录头信息（6B）：只有这两个字段是新增的，并且没有 record_type 这个字段，其余都是一样的

    名称 大小 描述
    n_fields 10bit 该行记录中列的数量
    1btye_offs_flag 1bit 字段长度偏移列表使用的长度是 1B 还是 2B

  • 事务 ID（6B）& 回滚指针（7B）

  • ROWID：如果没有定义主键，则会增加该列作为主键

  • 每列的数据

数据页的结构

参考博客：MySQL系列（4）— InnoDB数据页结构

数据页的结构主要分为两大组成部分，这两个组成部分可以根据记录的内容不同进一步细分为七个组成部分

  • 记录页的信息
    • File Header（38B）：记录这个数据页文件的相关信息
    • Page Header（56B）：记录这个数据页中记录相关的信息
    • File Trailer（8B）：防止数据页在写入磁盘的过程中损坏
  • 存储行记录信息
    • Infimun + Supremum Records：所有记录的上下边界
    • User Records：实际存储行记录的空间
    • Free Space：空间的记录空间
    • Page Directory：加速查询过程的页目录

1、File Header

名称 大小 描述
FIL_PAGE_SPACE_OR_CHKSUM 4B 检验数据页是否发生损坏
FIL_PAGE_OFFSET 4B 数据页在表空间中的地址
FIL_PAGE_PREV 4B 数据页关联的前一个数据页（双向链表）
FIL_PAGE_NEXT 4B 数据页关联的后一个数据页（双向链表）
FIL_PAGE_TYPE 2B 代表该页是什么类型：0x45BF 代表数据页
FIL_PAGE_LSN 8B 页面最后被修改的时候，日志序列的位置（日志篇章会讲）
FIL_PAGE_ARCH_LOG_NO_OR_SPACE_ID 4B 该数据页所属的表空间
  • FIL_PAGE_SPACE_OR_CHKSUM：
    • 如果没有开启 innodb_file_per_table 参数，那么所有表都存储在共享表空间中，这个字段存储就是所属的表空间而不是校验和
    • 如果开启了 innodb_file_per_table 参数，那么存储的就是页的校验和，主要用于检验页是否发生损坏
  • FIL_PAGE_TYPE：常见的两种页类型
    • 数据页：0x45BF
    • 索引页：0x0003
  • FIL_PAGE_PREV & FIL_PAGE_NEXT
    • 这两个字段就证明之前提到的采用双向链表将每层的结点串联起来的说法是正确的
    • 无论页是任何类型，属于同一层的结点（页面）都会采用双向链表串联起来
数据页串联
  • FIL_PAGE_LSN：这个字段和日志有关，所以暂时不在这里讲述

2、Page Header

名称 大小 描述
PAGE_N_DIR_SLOTS 2B 该数据页对应的变量槽的数量
PAGE_HEAP_TOP 2B 指向第一个插入的行记录
PAGE_N_HEAP 2B 该页中存储的行记录的数量
PAGE_FREE 2B 指向空闲空间的第一个行记录
PAGE_GARBAGE 2B 已经被删除的记录占用的总字节数
PAGE_N_RECS 2B 该页中实际存储的行记录数量
PAGE_LEVEL 2B 该页在 B+ 树中对应的位置
PAGE_INDEX_ID 8B 该页对应的索引，实际上就是该页对应的父结点

在之前的行记录头部信息中以及页头部信息中都已经出现了“堆”这种说法，所以需要提前解释下这里的堆到底指的是什么

实际上这里的“堆”并不是我们想象中的那个数据结构，它指的是所有记录在页面中的实际存储形式。

虽然所有记录都是采用单链表维护记录之间的顺序的，但是在页面中的实际存储是无序的。

因为页面中会不停地插入新的记录，如果每次插入新记录都去实际调整记录在磁盘中的物理位置，这显然是非常消耗性能，所以页面中行记录实际存储顺序就是插入顺序，只是采用单链表维护其逻辑上的顺序

所以此前行记录的头部信息中的 heap_no 字段就是指的该记录在页面中的物理顺序，而不是逻辑上的顺序

  • PAGE_N_HEAP && PAGE_N_RECS：
    • PAGE_N_HEAP ：所有记录 + Infimun 记录 + Supremum 记录 + 被标记为删除的记录
    • PAGE_N_RECS：只有实际存储数据的记录，没有其他的记录
  • PAGE_N_DIR_SLOTS
    • 每个页面中都会存储非常多的行记录，这些行记录会分为多个组，每个组中会有多个行记录
    • 每个组都会对应一个变量槽，这个字段记录的就是变量槽的数量，也就是组的数量

注：变量槽和分组的概念会在之后讲述，这里暂时不详细展开

3、Infimun && Supremum

Infimun 记录用于表示所有记录中的最小记录，Supremum 记录用于表示所有记录中的最大记录。

两个虚拟记录不会实际存储用户的数据，只是作为所有记录的边界使用，在任何情况下都不会删除，且在每个数据页中仅存在两个。此外，两个虚拟记录没有可变长字段列表和 NULL 标志位两个字段。

Supremum 记录作为最大的记录，记录头信息中的 n_owned 字段一定会存储所属组的记录的数量，组内记录的数量为 1~8 条

Infimun 记录作为最小的记录，不和其他任何记录形成组，也就是自成一组，记录头中的 n_owned 字段始终为 1

Infimun && Supremum

4、User Records & Free Space

  • User Records：实际存储所有行记录的空间，并且行记录全部采用单链表连接
    • 行记录在页中的物理顺序是按照插入顺序排列的，只是在逻辑上是按照从小到大的顺序排列的
    • 如果每次插入新的数据都实际调整行记录的顺序，这显然是非常消耗性能的，所以就让其保持插入顺序，用单链表维持逻辑顺序
  • Free Space：实际记录所有空闲空间，并且空闲的记录也会采用单链表连接
    • 每次为新记录分配空间就只需要根据 PAGE_FREE 找到第一个空闲记录就可以立即分配了，然后将的指针向后移动就可以了
    • 每次有记录被删除就会被链接到空闲空间的尾部，之后就可以将这个被删除的记录当做空闲记录使用

注：空闲空间的使用方式和碰撞指针的分配方式非常类似

Page Header、User Records、Free Space

6、Page Directory

在了解页目录之前，我们先来根据之前的内容回顾下整个查询过程的逻辑，然后再引出为什么需要使用页目录

查询流程：查找主键 ID = 4 的记录（类似于 B+树 的查询过程）

查找过程

你会发现无论是索引页还是数据页都是会从每个页的 Infimun 记录开始向后遍历，虽然单链表已经将页中的记录维护成有序的形式了，但是这个查询效率依然不高。你可以想象一下查询的最差情况，也就是需要查询的行记录是数据页中的最后一条，那么就意味着需要遍历整个页面才能够找到对应的行记录，这样会导致查询效率低下，所以我们才考虑使用页目录这种形式来加速行记录的查询，而不是每次都从 Infimun 记录开始。

  • 页分组：

    • 每个页中的行记录划分为多个组，每个组中都存放数量不等的行记录
    • 每个组中行记录的数量就是记录在 n_owned 字段中的，也就是之前提到的记录头信息中的字段
    • 但是并不是组内每个记录都会使用这个字段存储这个信息，只有组内最大的记录才会存储这个使用这个字段

  • 每个分组中记录的数量规定：

    • Infimun 是最小的记录，自成一组，不和其余任何记录形成组：n_owned = 1
    • Supremum 是最大的记录，可以和其余的记录形成组：n_owned ∈ [1, 8]
    • 其余行记录形成的组：n_owned ∈ [4, 8]

  • 页目录：

    • 页目录中存储的是变量槽，每个变量槽对应一个分组，并且指向每个分组中的最大行记录
    页目录-变量槽

  • 页目录的形成过程

    • 初始化后，Infimun 记录 和 Supremum 记录都是自成一组的，所以它们的 n_owned 字段初始值就是 1
    • 之后新记录插入分组，主要遵循以下两条规则：
    • 如果组内记录的数量刚好为 4 ，此时删除记录，那么其余组就会尝试向这个组分配一些记录，从而确保满足之前规定的组内数量

  • 页目录的使用过程

    • 首先在页目录中采用 二分查找 的形式去查找到 最接近需要查询的主键的变量槽
    • 如果发现前一个变量槽大于自己，后一个变量槽小于自己，那么就从前一个变量槽指向的最大记录开始向后遍历
    • 这样就可以避免每次都从数据页的最小记录开始遍历，减小了时间复杂度中的常数时间

举个栗子，现在有四个变量槽（Slot），Slot-0 对应的就是 Infimun 记录，Slot-1 对应的是 ID=4 的记录，Slot-2 对应是 ID=10 的记录，Slot-3 对应的就是 ID=12 的记录，现在需要查询 ID=11 的记录。

第一次比较，Slot-1 < ID=11 && Slot-2 < ID=11，不满足刚才提到的小于后一个变量槽的情况，所以需要继续判断

第二次比较，Slot-2 < ID=11 && ID=11 < Slot-3，满足之前提到的条件，那么就会从 Slot-2 开始向后遍历，直到找到 ID=11 的行记录

参考资料：《MySQL 技术内幕：InnoDB 存储引擎》

Author: Fuyusakaiori
Link: http://example.com/2022/01/19/database/mysql/structure/InnoDB 表结构/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
InnoDBB+ 树MySQL