My-Notes

Search

SearchSearch

002.数据存储

Sep 09, 2024, 19 min read

面试题：

  • MySQL 的 NULL 值是如何存储的？
  • MySQL 的 NULL 值会占用空间吗？
  • MySQL 怎么知道 varchar(n) 实际占用数据的大小？
  • varchar(n) 中 n 最大取值为多少？
  • 行溢出后，MySQL 是怎么处理的？

MySQL 存储行为是由存储引擎实现的，MySQL 支持多种存储引擎，不同的存储引擎保存的文件也不同，本文主要以 InnoDB 存储引擎展开讨论

数据库文件存放位置

MySQL 数据库文件存放的目录：

mysql> SHOW VARIABLES LIKE 'datadir';
+---------------+-----------------+
| Variable_name | Value           |
+---------------+-----------------+
| datadir       | /var/lib/mysql/ |
+---------------+-----------------+
1 row in set (0.00 sec)

每创建一个 database（数据库）都会在 /var/lib/mysql/ 目录下创建一个以 database 为名的目录，其中保存表结构和表数据的文件

比如，有一个名为 my_test 的 database，里有一张名为 t_order 数据库表：

> ls /var/lib/mysql/my_test
db.opt
t_order.frm
t_order.ibd
  • db.opt：存储当前数据库的默认字符集和字符校验规则
  • t_order.frm：保存表的元数据信息，主要包含表结构定义
  • t_order.ibd：保存表数据，称为独占表空间文件

表空间文件的结构

  • 表空间（table space）包含多个段（segment）
  • 每个段包含多个区（extent）
  • 每个区包含多个页（page）
  • 每个页包含多个行（row）

行（row）

数据库表中的记录都是按「行」进行存放的，每行记录根据不同的行格式，有不同的存储结构

页（page）

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

因此，InnoDB 的数据是按「页」为单位来读写的，也就是说，当需要读一条记录时，并不是将这个行记录从磁盘读出来，而是以页为单位，将其整体读入内存

默认每个页的大小为 16KB，页是 InnoDB 存储引擎磁盘管理的最小单元，意味着数据库每次读写都是以 16KB 为单位的

页的类型有很多，常见的有数据页、undo 日志页、溢出页等。数据表中的行记录是用「数据页」来管理的

数据页包括七个部分，从上到下为：

名称大小说明
文件头（File Header）38 字节记录页的信息
页头（Page Head）56 字节记录页的状态信息
最大最小记录（Infimum+Supremum）26 字节两个虚拟的伪记录，分别表示页中的最小和最大记录
用户记录（User Space）不确定存储行记录的内容
空闲空间（Free Space）不确定页内还没有被使用的空间
页目录（Page Directory）不确定记录用户记录的相对位置，对记录起到索引作用
文件尾（File Tailer）8 字节校验页是否完整

在 File Header 中有两个指针，分别指向上一个数据页和下一个数据页，连接起来的页相当于一个双向的链表。采用链表的结构是让数据页之间不需要物理上连续，而是逻辑上连续

数据页的主要作用是存储记录，也就是数据库的数据，所以重点说一下 User Records 是怎么组织数据的

数据页中的记录按照「主键」顺序组成单向链表，单向链表的特点就是插入、删除非常方便，但是检索效率不高，最差的情况下需要遍历链表上的所有节点才能完成检索，因此，数据页中有一个页目录，起到记录的索引作用

页目录与记录的关系：

  • 第一个分组中的记录只能有 1 条记录
  • 最后一个分组中的记录条数范围只能在 1-8 条之间
  • 剩下的分组中记录条数范围只能在 4-8 条之间

页目录创建的过程：

  1. 将所有的记录划分成几个组，这些记录包括最小记录和最大记录，但不包括标记为“已删除”的记录
  2. 每个记录组的最后一条记录就是组内最大的记录，并且最后一条记录的头信息中会存储该组一共有多少条记录，作为 n_owned 字段（上图中粉红色字段）
  3. 页目录用来存储每组最后一条记录的地址偏移量，这些地址偏移量会按照先后顺序存储起来，每组的地址偏移量也被称为槽（slot），每个槽相当于指针，指向了不同组的最后一个记录

页目录就是由多个槽组成，槽相当于分组记录的索引。因为记录是按照「主键值」从小到大排序的，所以通过槽查找记录时，可以使用二分法快速定位要查询的记录在哪个槽（哪个分组），定位到槽后，再遍历槽内的所有记录，找到对应的记录

以上图举个例子，5 个槽的编号分别为 0，1，2，3，4，想查找主键为 11 的用户记录：

  • 先二分得出槽中间位是 (0+4)/2=2，2 号槽里最大的记录为 8。因为 11 > 8，所以需要从 2 号槽后继续二分
  • 再使用二分搜索出 2 号和 4 槽的中间位是 (2+4)/2=3，3 号槽里最大的记录为 12。因为 11 < 12，所以主键为 11 的记录在 3 号槽里
  • 这里有个问题，槽对应的值都是这个组的主键最大的记录，如何找到组里最小的记录？比如槽 3 对应最大主键是 12 的记录，那如何找到最小记录 9。解决办法是：通过槽 3 找到槽 2 对应的记录，也就是主键为 8 的记录。主键为 8 的记录的下一条记录就是槽 3 当中主键最小的 9 记录，然后开始向下搜索 2 次，定位到主键为 11 的记录，取出该条记录的信息即为要查找的内容

区（extent）

InnoDB 存储引擎用 B+Tree 来组织数据，B+Tree 中每一层都是通过双向链表连接起来的，如果是以页为单位来分配存储空间，那么链表中相邻的两个页之间的物理位置并不连续，可能离得非常远，那么磁盘查询时就会有大量的随机I/O，随机 I/O 是非常慢的

解决这个问题也很简单，就是让链表中相邻的页的物理位置也相邻，这样就可以使用顺序 I/O 了，在范围查询（扫描叶子节点）时性能会很高

在表中数据量大的情况下，为某个索引分配空间时就不再按照页为单位分配了，而是按照区为单位分配。每个区的大小为 1MB，对于 16KB 的页来说，连续的 64 个页会被划为一个区

段（segment）

段一般分为数据段、索引段和回滚段等：

  • 索引段：存放 B+Tree 的非叶子节点的区的集合
  • 数据段：存放 B+Tree 树的叶子节点的区的集合
  • 回滚段：存放回滚数据的区的集合（详见）

InnoDB 的行格式

行格式（row_format），就是一条记录的存储结构

InnoDB 提供了 4 种行格式：

  • Redundant：很古老的行格式， MySQL 5.0 之前使用
  • Compact：一种紧凑的行格式，设计的初衷就是为了让一个数据页可以存放更多的行记录。MySQL 5.1 之后，默认使用 Compact 行格式
  • Dynamic 和 Compressed：都是紧凑的行格式，都是基于 Compact 改进而来。MySQL 5.7 之后，默认使用 Dynamic 行格式

重点介绍 Compact 行格式，因为 Dynamic 和 Compressed 这两个行格式和 Compact 非常像

示例数据：

CREATE TABLE `t_user` (
  `id` int(11) NOT NULL,
  `name` VARCHAR(20) DEFAULT NULL,
  `phone` VARCHAR(20) DEFAULT NULL,
  `age` int(11) DEFAULT NULL,
  PRIMARY KEY (`id`) USING BTREE
) ENGINE = InnoDB DEFAULT CHARACTER SET = ascii ROW_FORMAT = COMPACT;

表中有三条记录：

idnamephoneage
1a12318
2bbb(NULL)(NULL)

记录的额外信息

变长字段长度列表

  • varchar(n)：变长字段，存储数据的长度（大小）不固定
  • char(n)：存储定长字符串

所以，在存储数据时，也要存储数据占用大小的信息，读取数据时才能根据这个「变长字段长度列表」去读取对应长度的数据。其他 TEXT、BLOB 等变长字段的实现同理

第一条记录：

  • name 列的值为 a，真实数据占用 1 字节，十六进制 0x01
  • phone 列的值为 123，真实数据占用 3 字节，十六进制 0x03
  • age 和 id 列不是变长字段，不用管

这些变长字段的真实数据占用的字节数会按照列的顺序逆序存放，所以「变长字段长度列表」里的内容是「03 01」，而不是「01 03」：

第二条记录中 phone 列的值是 NULL，NULL 不会存放在行格式中记录的真实数据部分中，所以「变长字段长度列表」里不需要保存值为 NULL 的变长字段的长度：

为什么「变长字段长度列表」的信息要按照逆序存放？

因为「记录头信息」中指向下一个记录的指针，指向的是下一条记录的「记录头信息」和「真实数据」之间的位置，这样的好处是向左读是记录头信息，向右读是真实数据，比较方便

「变长字段长度列表」中的信息逆序存放，是因为这样可以使得位置靠前的记录的真实数据和数据对应的字段长度信息可以同时在一个 CPU Cache Line 中，提高 CPU Cache 的命中率

同样的道理， NULL 值列表的信息也需要逆序存放

每个数据库表的行格式都有「变长字段字节数列表」吗？

变长字段字节数列表不是必须的，它只出现在数据表有变长字段的时候

NULL 值列表

表中的某些列可能是 NULL，如果把 NULL 值都放到记录的真实数据中会比较浪费空间，所以 Compact 行格式把这些值为 NULL 的列存储到 NULL值列表中

每个允许 NULL 值的列对应一个二进制位（bit），二进制位按照列的逆序排列

  • 二进制位的值为 1 时，代表该列的值为 NULL
  • 二进制位的值为 0 时，代表该列的值不为 NULL

另外，NULL 值列表必须用整数个字节的位表示，如果使用的二进制位个数不足整数个字节，则在字节的高位补 0

第一条记录：所有列都有值，不存在 NULL 值

第二条记录：phone 和 age 列是 NULL 值

每个数据库表的行格式都有「NULL 值列表」吗？

NULL 值列表也不是必须的，当数据表的字段都定义成 NOT NULL 时，不会有 NULL 值列表

「NULL 值列表」是固定 1 字节空间吗？

不是，当一条记录有 9 个字段值都是 NULL，就会创建 2 字节空间的「NULL 值列表」，以此类推

记录头信息

记录头信息中包含的内容很多，说几个比较重要的：

  • delete_mask：标识此条数据是否被删除
    • 执行 detele 删除记录，并不会真正删除，只是将 delete_mask 标记为 1
  • next_record：下一条记录的位置
    • 记录与记录之间通过链表组织
    • 指向的是下一条记录的「记录头信息」和「真实数据」之间的位置，好处是向左读就是记录头信息，向右读就是真实数据，比较方便
  • record_type：表示当前记录的类型
    • 0：普通记录
    • 1：B+Tree 非叶子节点记录
    • 2：最小记录
    • 3：最大记录

记录的真实数据

记录真实数据部分除了用户定义字段的数据，还有三个隐藏字段：

  • row_id：非必需，占用 6 个字节。建表时指定了主键或唯一约束列，就没有 row_id 隐藏字段（详见）
  • trx_id：必需，占用 6 个字节。事务 id，表示这个数据是由哪个事务生成的
  • roll_pointer：必需，占用 7 个字节。这条记录上一个版本的指针

trx_id 和 roll_pointer 都与 事务隔离的 MVCC 相关

MySQL 规定除了 TEXT、BLOBs 这种大对象类型之外，其他所有的列占用的字节长度加起来不能超过 65535 个字节

这个其他所有的列：

  • 包含用户定义字段
  • 包含「变长字段长度列表」和 「NULL 值列表」
  • 不包含「隐藏列」和「记录头信息」

varchar(n) 字段类型的 n 代表的是最多存储的字符数量，并不是字节大小。要算 varchar(n) 最大能允许存储的字节数，还要看数据库表的字符集

行溢出

MySQL 中磁盘和内存交互的基本单位是页，一个页的大小一般是 16KB，也就是 16384 字节，而一个 varchar(n) 类型的列最多可以存储 65532 字节，一些大对象如 TEXT、BLOB 可能存储更多的数据，这时一个页可能就存不了一条记录，会发生行溢出，多的数据会存到另外的「溢出页」中

Compact：发生行溢出时，在记录真实数据处只会保存一部分数据，剩余的数据放在「溢出页」中，记录真实数据处用 20 字节存储指向溢出页的地址：

Compressed 和 Dynamic：采用完全的行溢出方式，记录真实数据处不会存储该列的任何数据，只存储 20 个字节的指针来指向溢出页，而实际数据都存储在溢出页中：

MyISAM

建表时，InnoDB 存储引擎默认会创建一个主键索引，也就是聚簇索引，其它索引都属于二级索引

MyISAM 存储引擎支持多种索引数据结构，比如 B+Tree 索引、R 树索引、Full-Text 索引。MyISAM 存储引擎在创建表时，创建的主键索引默认使用的是 B+Tree 索引

InnoDB 和 MyISAM 都支持 B+Tree 索引，但是数据的存储结构实现方式不同：

  • InnoDB：B+Tree 索引的叶子节点保存数据本身
  • MyISAM：B+Tree 索引的叶子节点保存数据的物理地址

Graph View

Backlinks