InnoDB 的“记录”存储

1. 准备测试数据
2. 找到数据页
- 2.1 为什么是第四个页面
- 2.2 数据页二进制数据
3. InnoDB 用户“记录”格式概述
4. InnoDB 页内的记录
5. 其他

了解InnoDB的物理存储可以为后续进一步了解其日志存储打下基础。在前述的内容，较为详细的介绍了InnoDB内部的B⁺-Tree存储，本文在此基础上，继续介绍，一个B⁺-Tree的节点（经常称作“页面”）中，如何存储单条记录的。本文，仅介绍其一般实现，并不对InnoDB记录格式的各种类型、场景做详细介绍。

这部分倒没有什么复杂的理论的，更多的是一些实践经验以及实际应用场景中各种情况的考虑与适配。

最为直接的，则是按照“数据表”各个列的元数据顺序排列即可。而事实上，这也是InnoDB实现的基本原则。但在实践中，还有很多的问题要去解决：

总是要考虑存储与读取效率：存储空间尽量不要有浪费，这样可以保持单个页面存储更多的数据，则有更高的磁盘和内存的利用率。例如，需要考虑Default值如何存储？NULL值如何存储？变长字段如何存储？超大的字段如何存储等。
如何较为便捷的实现各种类型的DDL，例如新增一个字段、删除一个字段等

一条记录分为两个部分，Record Header

1. 准备测试数据

这里新建表，并写入两条新的数据：

DROP TABLE IF EXISTS t_r; 
CREATE TABLE t_r (
  id int auto_increment primary key ,
  nick varchar(32),
  birthday date,
  password_hash char(32),
  email varchar(32)
);

INSERT INTO t_r VALUES 
  (1,"zzx","1989-02-11","a76e5fc27899ada11b4eafd0b1a7a4fc",'zzx@example.com'),
  (2,"yhq","2012-05-18","b6bdc8dcddeacece09d5697145d373d9",'yhq@example.com')
;

（注：最好不要这样存储hash值）

2. 找到数据页

这需要一些背景知识，但并不是本文介绍的重点。在独立表空间（当前MySQL的默认行为）的情况下，：

在数据目录下找到表数据文件：db.t_r.ibd
查看该页面的第四个Page即为第一个数据页面，因为这里写入的数据较少，所以，一般就存储在该页面

2.1 为什么是第四个页面

如果对于这个问题感兴趣的话，可以参考 The basics of InnoDB space file layout 中关于“Per-table space files”的描述。可以看到，第四个页面即为INDEX: Root page of first index。

使用vim（:%!xxd)查看时，每行16 Bytes，一个页面就是1024行，第四个页面，即从3073行开始，到4096行结束。

2.2 数据页二进制数据

$ view -b t_r.ibd
3073 0000c000: 646e 9e73 0000 0003 ffff ffff ffff ffff  dn.s............
3074 0000c010: 0000 0007 de81 961e 45bf 0000 0000 0000  ........E.......
3075 0000c020: 0000 0000 01d0 0002 0114 8004 0000 0000  ................
3076 0000c030: 00ce 0002 0001 0002 0000 0000 0000 0000  ................
3077 0000c040: 0000 0000 0000 0000 030c 0000 01d0 0000  ................
3078 0000c050: 0002 00f2 0000 01d0 0000 0002 0032 0100  .............2..
3079 0000c060: 0200 1d69 6e66 696d 756d 0003 000b 0000  ...infimum......
3080 0000c070: 7375 7072 656d 756d 0f03 0000 0010 004e  supremum.......N
3081 0000c080: 8000 0001 0000 0090 f05b bb00 0001 3101  .........[....1.
3082 0000c090: 107a 7a78 8f8a 4b61 3736 6535 6663 3237  .zzx..Ka76e5fc27
3083 0000c0a0: 3839 3961 6461 3131 6234 6561 6664 3062  899ada11b4eafd0b
3084 0000c0b0: 3161 3761 3466 637a 7a78 4065 7861 6d70  1a7a4fczzx@examp
3085 0000c0c0: 6c65 2e63 6f6d 0f03 0000 0018 ffa2 8000  le.com..........
3086 0000c0d0: 0002 0000 0090 f05b bb00 0001 3101 1d79  .......[....1..y
3087 0000c0e0: 6871 8fb8 b262 3662 6463 3864 6364 6465  hq...b6bdc8dcdde
3088 0000c0f0: 6163 6563 6530 3964 3536 3937 3134 3564  acece09d5697145d
3089 0000c100: 3337 3364 3979 6871 4065 7861 6d70 6c65  373d9yhq@example
3090 0000c110: 2e63 6f6d 0000 0000 0000 0000 0000 0000  .com............
3091 0000c120: 0000 0000 0000 0000 0000 0000 0000 0000  ................
3092 0000c130: 0000 0000 0000 0000 0000 0000 0000 0000  ................
     ......
4094 0000ffd0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
4095 0000ffe0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
4096 0000fff0: 0000 0000 0070 0063 646e 9e73 de81 961e  .....p.cdn.s....

3. InnoDB 用户“记录”格式概述

关于该格式的描述，可以参考innobase/rem/rem0rec.c中的注释说明部分，有比较详细的说明。

/*
...
| length of the last non-null variable-length field of data:
  if the maximum length is 255, one byte; otherwise,
  0xxxxxxx (one byte, length=0..127), or 1exxxxxxxxxxxxxx (two bytes,
  length=128..16383, extern storage flag) |
...
| length of first variable-length field of data |
| SQL-null flags (1 bit per nullable field), padded to full bytes |
| 4 bits used to delete mark a record, and mark a predefined
  minimum record in alphabetical order |
| 4 bits giving the number of records owned by this record
  (this term is explained in page0page.h) |
| 13 bits giving the order number of this record in the
  heap of the index page |
| 3 bits record type: 000=conventional, 001=node pointer (inside B-tree),
  010=infimum, 011=supremum, 1xx=reserved |
| two bytes giving a relative pointer to the next record in the page |
ORIGIN of the record
| first field of data |
...
| last field of data |
...
*/

4. InnoDB 页内的记录

在一个页面内，InnoDB存储每条物理记录时，都会在记录中存储一个“指针”，该“指针”指向下一条记录的物理位置，并且在实现时，该“指针”是以当前记录偏移的方式存储的。

所以，如果我们能够找到页面内的第一条记录，那么就可以依此顺序的遍历整个页面内的记录了。找到第一条记录大概有很多的方法，这里说说InnoDB的实现：infimum和supremum。简单来说，InnoDB会在页面中存储一个infimum记录，该记录可以认为是该页面的极小值，该记录中的“Next Record”即为实际的该页面最小值。

4.1 系统记录(system record)：infimum 和 supremum

infimum和supremum是每个InnoDB页面内存储两条物理记录，分别代表“起始最小记录”和“结束最大记录”。所以如果使用上述的下一条记录“指针”遍历页内所有记录，则总是从infimum开始，以supremum结束，中间就是所有的用户记录。

在页面找到infimum和supremum记录的方法有两种：

infimum和supremum在页面的偏移，总是99和112
从Page Directory的slot中查找：第一个slot总是指向infimum；最后一个slot总是指向supremum

4.2 从Page Directory找到infimum

在前文“B⁺-Tree的内部搜索：InnoDB的实现”，已经概述了slot 0中总是存储的infimum记录，则可以通过页面底部向前偏移PAGE_DIR（InnoDB中PAGE_DIR的值是8），然后找到slot 0对应的记录的偏移，即infimum的偏移，而因为一个slot存储的偏移地址都是2 bytes 。所以，在页面内的倒数第10、9个字节，即为infimum在页内的偏移地址，即0x0063。

4.3 “记录”指针

这里有两点需要注意：

一般“记录”指针通常是指向记录的“the origin of the record”，即实际数据开始的地方。不包含“记录头”部分
一般“记录”指针会使用两种方式表示：(a) 页内偏移；(b) 相当于当前记录的偏移。不同的地方会不同，例如“记录头”中存储next record的指针则是“相对偏移”，而slot内存储的则是页内绝对偏移。

理解上述两点，对于理解后续内容是很重要的，要不然，可能会算错地址。

例如，上述的slot 0中记录的infimum的偏移0x0063就是绝对偏移；而infimum中存储的next record偏移，则是相对于infimum的偏移地址。例如，next record偏移是00 1d，那么意味着这条记录的偏移是0x0063+0x001d，即绝对偏移是：0x0080。

4.4 记录头 record header

按照上述方法，这里已经找到第一条（按大小顺序）记录的“记录指针”，即0x0080。把记录的头部（record header）和记录本身数据从上述二进制数据单独取出来，如下：

                                   |<-record header->|
3080 0000c070: ................... 0f03 0000 0010 004e  supremum.......N
               |<---------- field data   ----------->|
3081 0000c080: 8000 0001 0000 0090 f05b bb00 0001 3101  .........[....1.
               ^
               |--> record pointer/offset (the origin of the record)
3082 0000c090: 107a 7a78 8f8a 4b61 3736 6535 6663 3237  .zzx..Ka76e5fc27
3083 0000c0a0: 3839 3961 6461 3131 6234 6561 6664 3062  899ada11b4eafd0b
3084 0000c0b0: 3161 3761 3466 637a 7a78 4065 7861 6d70  1a7a4fczzx@examp
3085 0000c0c0: 6c65 2e63 6f6d ........................  le.com..........
              |<-field data->|

注：

在获得了 record pointer后，是无法简单的、直接获得record header长度的，也无法简单的获取记录本身的长度的。而是需要根据元数据库、以及record header中的部分数据，计算而来。
record header 的长度获取，是比较复杂的。这里做一定的简化，描述如下：
- record pointer向前（record header方向）移动，5个bytes是相对固定的，包含了
  - 2 bytes: next record
  - 3 bits: record type
  - 13 bits: the order number of this record
  - 4 bits: the number of records owned by this record(slot)
  - 4 bits: delete mark and mark a predefined minimum record
- record pointer再向前的 n个bytes则用于存储 null 的field，该存储模式为按标记位存储，且按bytes补齐：
  - 例如，这里一共有5个fields，则需要1 bytes，作为标记位；如果某个field为null则对应的bit即标记位1
  - 所以，这里的 n=1
- record pointer再向前的m个bytes则用于存储变成列的实际长度。本示例中，共有两个变成列，故这里的 m = 2

4.5 记录的解析Record Header

这里以页面中的第一条记录为示例，继续解析该记录的头部信息。详情如下：

(<------------- record header / hex ----------------->) (<----- data/hex ----->)
0f03 0000             0010             004e             8000 0001 0000 0090 f05b 

(hex)(<---------------  binary   -------------------->) (<----- data/hex ----->)
0f03 0000000000000000 0000000000010000 0000000001001110 8000 0001 0000 0090 f05b
| |  |<----->|<->|<-->|<---------->|   |<------------>|
| |  |       |   |    |            |   |
| |  |       |   |    |            |   |-->(2 bytes) next record
| |  |       |   |    |            |
| |  |       |   |    |            |-->(3 bits) record type: 000=conventional
| |  |       |   |    |
| |  |       |   |    |-->(13 bits) the order number of this record
| |  |       |   |
| |  |       |   |-->(4 bits) the number of records owned by this record(slot)
| |  |       |
| |  |       |-->(4 bits) delete mark and mark a predefined  minimum record
| |  |
| |  |-->(8 bits) null-flag (here ,no null field at all, 5 field, so 1 bytes )
| |
| |-->(1 byte) length of 1st variable field, so length is 03
|
|-->(1 byte) length of 2nd variable field, so length is 0f(15)

结合记录头部信息，再结合“元数据信息”，则就可以解析出记录本身的信息了。

5. 其他

有很多人对这个问题已经有了非常深入到说明或研究，如下给出主要的参考链接：

MySQL Documentation: InnoDB Row Formats 非常详细的介绍了多种InnoDB行格式类型：REDUNDANT、COMPACT 、DYNAMIC 、COMPRESSED等
Jeremy Cole 2013 The physical structure of records in InnoDB
Jeremy Cole 2013 The basics of InnoDB space file layout
Annamalai Gurusami MySQL Blog Archive 2014 Externally Stored Fields in InnoDB
Heikki Tuuri. Calvin Sun. 2009-04 InnoDB Internals: InnoDB File Formats and Source Code Structure
Neoreminder 2020 从MySQL InnoDB物理文件格式深入理解索引
Yungyu 2020 InnoDB — 行记录格式

延伸讨论：

各种数据类型的序列与反序列化，以及对应的效率考虑

B+Tree、B+-Tree 均指B⁺-Tree
一般的，B-Tree指狭义的、经典的B-Tree，该结构主要参考：了解 InnoDB 的索引结构：B-Tree 基础
有时候，B-Tree也会指代B⁺-Tree或其他B-Tree变种；这种用法也是非常广泛的，例如，在MySQL/InnoDB的文档中，仅使用B-Tree，而更为准确的说是B+-Tree
“节点”（Node）、“页面”（Page）、“数据块”、“块”(Block)等均指存储B-Tree或B⁺-Tree的节点，即树结构的节点，内部可以存储多个键值。在不同的语境下，大家会用不同的词，例如通常在算法课程/书籍中，会更多的使用“节点”（Node）；而在数据库实现中，则更喜欢用“页面”（Page）或“块”(Block)；更为细节的，如果在内存中，则更多的时候用“页面”（Page），在磁盘上，则更多的“块”(Block)。各种情况下混用的也很多，并没有什么问题。
“记录”（record）、“行”（row）、tuple都是表示表中的一行记录，通常包含多个字段数据。
索引入口（Entry）等是指完整的“键值对”，在叶子节点中，通常包括\( (k_i, a_i) \)；在非叶子节点中可能的形式是：\( (k_i,p_i, a_i) \) 或 \( (k_i, p_i) \)
TAOCP 是 “The Art of Computer Programming”的缩写

orczhou.com