关于mysql:InnoDB数据页存储施洪宝

一. 简介

1. Mysql 是目前最为风行的关系型数据库管理系统, 具备体积小、速度快、开放源码等劣势。InnoDB 是 Mysql 应用最宽泛的存储引擎, InnoDB 进行了行锁设计, 反对 MVCC, 提供一致性非锁定读。学习 InnoDB 数据页存储, 可能让咱们更加深刻的了解 InnoDB 的一些个性。
2. 程序 = 数据结构 + 算法, 对于 Mysql 而言也是如此。因为数据长久化的须要, Mysql 的数据不仅存储在内存中, 也会长久化到文件中, 存储构造如下图,

• 从磁盘中, 咱们能够很容易的看到长久化的各个文件。
• 磁盘中的文件须要加载到内存中能力被程序应用, 很显著, 不可能将所有磁盘文件都加载到内存, 当内存中的数据产生更改后, 也须要刷新到磁盘文件中, 什么时候刷新, 怎么刷新, 这些都是 Mysql 须要思考的问题, 然而这些内容不是本文的重点, 咱们这里稍加理解即可。
• 本文的重点是学习数据页的存储, 这些数据页可能存在与零碎表空间, 独立表空间或者长期表空间。能够看到, 这些只是图中的一小部分。

1. 学习之前, 咱们先思考几个问题,

• 无论是内存存储还是磁盘存储, 都离不开内存治理, InnoDB 是如何划分内存以及如何治理内存的?
• InnoDB 应用 B + 树存储咱们表中的数据, B+ 树索引节点以及叶子节点应该须要存储哪些数据? 又是怎么存储的?
• 咱们在应用时, 创立了数据库, 数据表, 这些元数据是如何存储的, 查问某个表时, 如何依据元数据找到表的索引, 如何抉择索引, 抉择索引后, 如何定位到索引的根节点(root page)? 找到跟节点后, 又是如何一步步找到某个具体数据的?

1. 阐明

• Mysql 版本: 8.0.12-debug
• 存储引擎应用 InnoDB
• 咱们会用到 xxd 命令, 应用 xxd(或者 hexdump)能够以十六进制的形式查看文件。

二. InnoDB 存储构造

InnoDB 存储结构图如下所示, 咱们这里只做简要的介绍, 更多细节咱们将在后续的文章中再进行具体论述,

1. 表空间 (tablespace) 能够认为是 InnoDB 存储引擎存储构造的最高层, 所有数据都在表空间中, 除了共享表空间外, 每个表能够创立独立表空间, 具体参数是由 innodb_file_per_table 参数决定, 表空间由各种段组成。
2. 常见的段 (segment) 有数据段, 回滚段, 索引段。innodb 中数据段就是 B + 树的叶子节点, 索引段就是 B + 树中的非叶子节点。
3. 段是由区 (extent) 组成, 默认状况下区的大小是 1MB, InnoDB 默认页大小为 16KB, 所以 1 个区是由 16 个间断页组成。
4. innodb 默认页 (page) 大小是 16KB, 也能够通过 innodb_page_size 进行管制。
5. innodb 存储是面向行 (row) 的, 行的存储格局次要有 compact、redundant、compressed、dynamic。

三. 数据页存储

3.1 独立表空间

通过 innodb_file_per_table 参数, 咱们能够为每个表都创立一个表空间, 这个就是这个表的独立表空间, 这个表的索引段, 数据段都会存储在这个独立表空间中, 然而 Redo log, Undo log 依然在各自的表空间中, 表空间存储如下图,

1. 表空间的 page 0 是表空间的第一页, 存储了表空间的信息，同时也用于治理前 256 个 extent。page 16384 类型为 FIL_PAGE_TYPE_XDES 也用于治理之后的 256 个 extent, 以此类推, 每隔 16384 个页面都会须要一个 FIL_PAGE_TYPE_XDES 页面。
2. page 1 类型是 FIL_PAGE_IBUF_BITMAP, 用于治理每个 page(前 256 个 extent 的 16384 个页面)的 change buffer(change buffer 相干内容不是本文的重点, 感兴趣的读者能够查找相干材料)。与 FIL_PAGE_TYPE_XDES 相似, 每隔 16384 个页面都须要一个 FIL_PAGE_IBUF_BITMAP 页面。
3. page 2 类型为 FIL_PAGE_INODE, 用于治理 segment。
4. page 3 类型为 FIL_PAGE_SDI, 存储 Serialized Dictionary Information(SDI, 词典序列化信息), 存储了这个表空间的一些数据字典 (Data Dictionary) 信息。
5. page 4 个别就是这个表主键索引的 root page。

3.2 页存储

InnoDB 的页存储构造如下, 每页都是由 3 局部组成, File Header(38 字节)、File Body、File Trailer(8 字节), 不同页的 File Body 存储的内容不同,

1. File Header

1. File Type

3.3 数据页

看完 InnoDB 页构造后, 咱们看下数据页的存储,

1. Page Header

1. Infimun & Supermum

虚构记录, Infimum 为 13 字节, Supermum 也是 13 字节。具体存储内容, 咱们会在上面进行介绍。

1. Page Directory

• 页目录, 因为行记录在数据页中以链表的模式链接, 然而在查找记录时, 链表查找速度很慢, 为了减速记录查找, 创立页目录, 页目录能够用于二分查找。每个目录项占用 2 个字节, 从页尾部开始, 倒序存储。
• 为了便于了解 Page Directory, 咱们这里举一个例子, 如果表中存储了 200 条数据, 数据通过链表的形式进行链接, 咱们在查问时, 须要遍历整个链表能力找到数据, 这样无疑比较慢。咱们能够通过建设索引的形式, 放慢查找速度, 咱们能够将这 200 条记录的主键依照程序进行存储, InnoDB 的 Page Directory 就是这个思路, 然而并不是存储了主键的值, 而是存储了对应记录的地位, 并且不是将每个行记录都存储在 Page Directory 中, 只是建设一个稠密索引。

3.4 innodb 行存储

限于篇幅, 咱们这里次要介绍 compact 格局的行记录存储, 存储格局如下图,

1. 从图中能够看出, 每个记录行至多占有 5 字节(记录头) + 主键长度 + 6 字节(事务 ID) + 7 字节(回滚指针)
2. 咱们须要留神记录头中的 next_record 字段, 这个字段占有 16bit, 也就是 2 个字节, 通过这个字段, InnoDB 将一个页中的所有记录以链表的形式链接到一起。

四. 实例解说

为了便于大家了解, 这部分咱们给出一些实例,

1. 本节举例说明 InnoDB 的一个表是如何存储的, 次要介绍两种状况, 一种状况是表中数据很少, 另一种状况是表中数据比拟多, 一页曾经存储不了的状况。
2. 表构造定义,

create table `t` (`id` int not null, primary key(`id`)) engine=InnoDB ROW_FORMAT=Compact;

• 为了更容易了解, 咱们这里只创立了一个非常简单的表, 也只有一个主键索引。主键类型为 int, 占用 4 个字节。
• 创立表后, 能够在相应的目录下看到 t.ibd 文件, 这里我是在 test 数据库下创立的这个表, 所以也就在 test 目录下。
• 从磁盘文件中, 咱们能够看到, t.ibd 文件大小为 112KB, 也就是 7 *16KB, 也就是 7 个 page, 也就意味着, 创立表后, InnoDB 默认初始化了 7 个 page。
• 咱们的表中没有变长字段, 主键长度为 4 字节, 所以单个记录的长度为 5(记录头) + 4(主键 ID) + 6(事务 ID) + 7(回滚指针) = 22 字节

1. B+ 树示例

InnoDB 数据存储是通过 B + 树组织的, 一个很简略的 B + 树如下所示,

• B+ 树的性质有很多, 其增删查改操作较惯例的二叉树更简单一些, 感兴趣的能够查问相干材料, 这里有个基本概念即可。

1. 后续如果没有非凡阐明, 表空间第一个页是 page 0, 第二页是 page 1, 以此类推。

4.1 单页存储

咱们首先看下当表中数据很少的时候, 数据是如何组织的, 具体操作步骤如下,

1. 咱们向表中插入 2 条记录,

insert into t values (2);
insert into t values (1);

• 这里留神咱们先插入主键值为 2 的行记录, 再插入主键值为 1 的行记录。

1. 通过 xxd 将 t.ibd 以 16 进制示意, 执行命令 xxd t.idb t.txt, 也能够应用 hexdump 命令查看。
2. 查看 t.txt 中的内容, 这里咱们查看 page 4 的数据

0010000: a76e 6043 0000 0004 ffff ffff ffff ffff  .n`C............
0010010: 0000 0000 012e 6d9d 45bf 0000 0000 0000  ......m.E.......
0010020: 0000 0000 0005 0002 00a4 8004 0000 0000  ................
0010030: 0093 0001 0001 0002 0000 0000 0000 0000  ................
0010040: 0000 0000 0000 0000 0091 0000 0005 0000  ................
0010050: 0002 0272 0000 0005 0000 0002 01b2 0100  ...r............
0010060: 0200 3069 6e66 696d 756d 0003 000b 0000  ..0infimum......
0010070: 7375 7072 656d 756d 0000 10ff f380 0000  supremum........
0010080: 0200 0000 001c 0481 0000 00fa 0110 0000  ................
0010090: 18ff ea80 0000 0100 0000 001c 0582 0000  ................
00100a0: 012c 0110 0000 0000 0000 0000 0000 0000  .,..............
00100b0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
......
......
0013fe0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0013ff0: 0000 0000 0070 0063 a76e 6043 012e 6d9d  .....p.c.n`C..m.

• 前 38 字节是文件头[0010000,0010026]
• 之后 56 字节是数据页头部[0010027,001005d]
• 之后的 26 字节是最小记录[001005e, 001006a], 最大记录[001006b, 0010077], 这里能够看到最小记录的 n_owns 值为 1(只有本身 1 条记录), 最大记录的 n_owns 值为 3(除了本身外, 还有咱们插入的两条记录)
• 紧接着是第 1 条插入记录[0010078, 001008d]

0010070: .... .... .... .... 0000 10ff f380 0000
0010080: 0200 0000 001c 0481 0000 00fa 0110 ....

• 最初是方才插入的第 2 条记录[001008e, 00100a3]
• 对于 int 类型, innodb 存储形式与惯例的形式不同, [0x00000000, 0x7fffffff]代表 [-2147483648, -1], [0x80000000, 0xffffffff] 代表[0, 21473647]。

1. 存储构造如下图

1. 这里示例下如何从最小记录查找到最大记录

• 首先定位到最小记录的地位, 最小记录占有 5 字节(记录头) + 8 字节(内容) = 13 字节, 最小记录所在的地位为 001005e, 依据最小记录的记录头信息, 能够计算出下一个记录所在位置 001005e + 0030 = 001008e
• 001008e 是主键为 1 的记录所在位置, 接着计算下一个记录的地位 001008e + ffea = 0010078, 这里须要留神的是, 加法运算时, 只保留前面 4 位的后果, 能够看到这个地位就是咱们第一次插入的主键为 2 的记录
• 之后, 持续计算下一个记录所在位置, 0010078 + fff3 = 1006b, 这个就是最大记录所在的地位
• 在查找某个具体的行记录时, 能够先利用 page directory 进行近似的二分查找, 之后再进行链表查找。

1. page directory

• 页尾部蕴含两个 slots

0013ff0: 0000 0000 0070 0063 .... .... .... ....

• 0063 是第 1 个 slot 的地位, 相应的记录所在位置为 0010063, 也就是最小记录。[001005e, 0010062]这个是最小记录的记录头, [0010063, 001006a]是最小记录的内容。
• 0070 是第 2 个 slot 的地位, 相应的记录所在位置为 0010070, 这个是最大记录所在的内容开始地位。

1. 小结

• 能够看到, 从最小记录开始, 到最大记录完结, 数据依照主键程序以链表的形式进行链接。
• 行数据的存储是依照插入的顺序存储的, 不是依照主键顺序存储, 数据删除后, 开释的空间能够复用, 对于复用局部的细节, 后续文章再进行具体介绍。

4.2 多页存储

在 4.1 的根底上, 咱们持续插入数据, 操作步骤如下,

1. 咱们通过脚本向表中持续插入数据

<?php
$servername = "localhost:8083";
$username = "root";
$password = "password";
$dbname = "test";

try {$conn = new PDO("mysql:host=$servername;dbname=$dbname", $username, $password);
    $conn->setAttribute(PDO::ATTR_ERRMODE, PDO::ERRMODE_EXCEPTION);
    for($i = 3; $i < 1000; $i++){$sql = "INSERT INTO t VALUES (" . strval($i) . ")";
        $conn->exec($sql);
    }
}
catch(PDOException $e){echo $sql . "<br>" . $e->getMessage();
}
$conn = null;
?>

• 之前表中曾经插入 2 条记录, 这里又插入 997 条记录, 所以表中当初一共 999 条记录, 主键 id 从 1 到 999。
• 单条记录须要占用 22 字节, 能够晓得, 此时, 单个数据页不能存储全副数据。

1. 以 16 进制查看此时的 t.ibd 文件: xxd t.ibd t.txt
2. 查看 t.txt 内容, 首先查看 page 4 的内容

0010000: df67 193d 0000 0004 ffff ffff ffff ffff  .g.=............
0010010: 0000 0000 0132 5500 45bf 0000 0000 0000  .....2U.E.......
0010020: 0000 0000 0005 0002 0092 8004 0000 0000  ................
0010030: 008a 0002 0001 0002 0000 0000 0000 0000  ................
0010040: 0001 0000 0000 0000 0091 0000 0005 0000  ................
0010050: 0002 0272 0000 0005 0000 0002 01b2 0100  ...r............
0010060: 0200 1a69 6e66 696d 756d 0003 000b 0000  ...infimum......
0010070: 7375 7072 656d 756d 1000 1100 0d80 0000  supremum........
0010080: 0100 0000 0500 0019 ffe6 8000 0153 0000  .............S..
0010090: 0006 0000 0000 0000 0000 0000 0000 0000  ................
.......
.......
0013fe0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0013ff0: 0000 0000 0070 0063 df67 193d 0132 5500  .....p.c.g.=.2U.

• 能够看到, 第 5 页, 目前只有大量内容, 因为此时第 5 页是索引页, 是 B + 树的根, 没有存储具体的数据, 只存储了主键索引。
• File Header, Page Header, Infimum & Supremum 跟之前根本相似, 这里就不再具体介绍。
• 单个索引须要占用 5 字节(记录头) + 4 字节(主键) + 4 字节(记录所在页) = 13 字节。
• 第 1 个索引信息

0010070: .... .... .... .... 1000 1100 0d80 0000
0010080: 0100 0000 05.. .... .... .... .... ....

主键 id 为 0x80000001, 也就是 1, page no 为 0x00000005, 也就是page 5

• 第 2 个索引信息

0010080: .... .... ..00 0019 ffe6 8000 0153 0000
0010090: 0006 .... .... .... .... .... .... ....

主键 id 为 0x80000153, 也就是 339, page no 为 0x00000006, 也就是page 6

• 通过这两个索引信息, 能够晓得, page 5存储着主键 id 从 1 到 338 的数据, page 6存储着主键 id 从 339 到 999 的数据

1. 查看page 5

0014000: e1c0 bb7a 0000 0005 ffff ffff 0000 0006  ...z............
0014010: 0000 0000 0132 5500 45bf 0000 0000 0000  .....2U.E.......
0014020: 0000 0000 0005 0056 3a90 82a6 1d89 1d0c  .......V:.......
0014030: 0000 0005 0000 0152 0000 0000 0000 0000  .......R........
0014040: 0000 0000 0000 0000 0091 0000 0000 0000  ................
0014050: 0000 0000 0000 0000 0000 0000 0000 0100  ................
0014060: 0200 1a69 6e66 696d 756d 0003 000b 0000  ...infimum......
0014070: 7375 7072 656d 756d 0000 1000 1680 0000  supremum........
0014080: 0100 0000 001c 0582 0000 012c 0110 0000  ...........,....
0014090: 1800 1680 0000 0200 0000 001c 0481 0000  ................
00140a0: 00fa 0110 0000 2000 1680 0000 0300 0000  ...... .........
.......
.......
0017e90: 0000 0000 0000 0000 0000 0000 0000 0000  ................
0017ea0: 0000 0000 0070 3a27 39cf 3977 391f 38c7  .....p:'9.9w9.8.
0017eb0: 386f 3817 37bf 3767 370f 36b7 365f 3607  8o8.7.7g7.6.6_6.
0017ec0: 35af 3557 34ff 34a7 344f 33f7 339f 3347  5.5W4.4.4O3.3.3G
0017ed0: 32ef 3297 323f 31e7 318f 3137 30df 3087  2.2.2?1.1.170.0.
0017ee0: 302f 2fd7 2f7f 2f27 2ecf 2e77 2e1f 2dc7  0//././'...w..-.
0017ef0: 2d6f 2d17 2cbf 2c67 2c0f 2bb7 2b5f 2b07  -o-.,.,g,.+.+_+.
0017f00: 2aaf 2a57 29ff 29a7 294f 28f7 289f 2847  *.*W).).)O(.(.(G
0017f10: 27ef 2797 273f 26e7 268f 2637 25df 2587  '.'.'?&.&.&7%.%.
0017f20: 252f 24d7 247f 2427 23cf 2377 231f 22c7  %/$.$.$'#.#w#.".
0017f30: 226f 2217 21bf 2167 210f 20b7 205f 2007  "o".!.!g!. . _ .
0017f40: 1faf 1f57 1eff 1ea7 1e4f 1df7 0070 1d47  ...W.....O...p.G
0017f50: 1cef 1c97 1c3f 1be7 1b8f 1b37 1adf 1a87  .....?.....7....
0017f60: 1a2f 19d7 197f 1927 18cf 1877 181f 17c7  ./.....'...w....
0017f70: 176f 1717 16bf 1667 160f 15b7 155f 1507  .o.....g....._..
0017f80: 14af 1457 13ff 13a7 134f 12f7 129f 1247  ...W.....O.....G
0017f90: 11ef 1197 113f 10e7 108f 1037 0fdf 0f87  .....?.....7....
0017fa0: 0f2f 0ed7 0e7f 0e27 0dcf 0d77 0d1f 0cc7  ./.....'...w....
0017fb0: 0c6f 0c17 0bbf 0b67 0b0f 0ab7 0a5f 0a07  .o.....g....._..
0017fc0: 09af 0957 08ff 08a7 084f 07f7 079f 0747  ...W.....O.....G
0017fd0: 06ef 0697 063f 05e7 058f 0537 04df 0487  .....?.....7....
0017fe0: 042f 03d7 037f 0327 02cf 0277 021f 01c7  ./.....'...w....
0017ff0: 016f 0117 00bf 0063 e1c0 bb7a 0132 5500  .o.....c...z.2U.

• 留神页尾部蕴含 page directory, slots 的个数能够从 page header 中读取
• File Header 中的 FIL_PAGE_NEXT 字段, 值为 0x00000006, 也就是 page no 为 6 的页。

1. 查看page 6

0018000: 2ddb 788c 0000 0006 0000 0005 ffff ffff  -.x.............
0018010: 0000 0000 0133 f431 45bf 0000 0000 0000  .....3.1E.......
0018020: 0000 0000 0005 00a6 3946 8297 0000 0000  ........9F......
0018030: 3935 0002 0142 0295 0000 0000 0000 0000  95...B..........
0018040: 0000 0000 0000 0000 0091 0000 0000 0000  ................
0018050: 0000 0000 0000 0000 0000 0000 0000 0100  ................
0018060: 0200 1a69 6e66 696d 756d 0006 000b 0000  ...infimum......
0018070: 7375 7072 656d 756d 0000 1000 1680 0001  supremum........
0018080: 5300 0000 001d 6d81 0000 00a3 0110 0000  S.....m.........
.......
.......
001bea0: 0000 0000 0000 0000 0000 0000 0070 38c7  .............p8.
001beb0: 386f 3817 37bf 3767 370f 36b7 365f 3607  8o8.7.7g7.6.6_6.
001bec0: 35af 3557 34ff 34a7 344f 33f7 339f 3347  5.5W4.4.4O3.3.3G
001bed0: 32ef 3297 323f 31e7 318f 3137 30df 3087  2.2.2?1.1.170.0.
001bee0: 302f 2fd7 2f7f 2f27 2ecf 2e77 2e1f 2dc7  0//././'...w..-.
001bef0: 2d6f 2d17 2cbf 2c67 2c0f 2bb7 2b5f 2b07  -o-.,.,g,.+.+_+.
001bf00: 2aaf 2a57 29ff 29a7 294f 28f7 289f 2847  *.*W).).)O(.(.(G
001bf10: 27ef 2797 273f 26e7 268f 2637 25df 2587  '.'.'?&.&.&7%.%.
001bf20: 252f 24d7 247f 2427 23cf 2377 231f 22c7  %/$.$.$'#.#w#.".
001bf30: 226f 2217 21bf 2167 210f 20b7 205f 2007  "o".!.!g!. . _ .
001bf40: 1faf 1f57 1eff 1ea7 1e4f 1df7 1d9f 1d47  ...W.....O.....G
001bf50: 1cef 1c97 1c3f 1be7 1b8f 1b37 1adf 1a87  .....?.....7....
001bf60: 1a2f 19d7 197f 1927 18cf 1877 181f 17c7  ./.....'...w....
001bf70: 176f 1717 16bf 1667 160f 15b7 155f 1507  .o.....g....._..
001bf80: 14af 1457 13ff 13a7 134f 12f7 129f 1247  ...W.....O.....G
001bf90: 11ef 1197 113f 10e7 108f 1037 0fdf 0f87  .....?.....7....
001bfa0: 0f2f 0ed7 0e7f 0e27 0dcf 0d77 0d1f 0cc7  ./.....'...w....
001bfb0: 0c6f 0c17 0bbf 0b67 0b0f 0ab7 0a5f 0a07  .o.....g....._..
001bfc0: 09af 0957 08ff 08a7 084f 07f7 079f 0747  ...W.....O.....G
001bfd0: 06ef 0697 063f 05e7 058f 0537 04df 0487  .....?.....7....
001bfe0: 042f 03d7 037f 0327 02cf 0277 021f 01c7  ./.....'...w....
001bff0: 016f 0117 00bf 0063 2ddb 788c 0133 f431  .o.....c-.x..3.1

• 留神 File Header 中的 FIL_PAGE_PREV 字段, 值为 0x00000005, 也就是 page no 为 5 的页。
• 联合 page 5 能够看出, 叶子节点的两个页通过链表进行链接, 每个页内的数据通过记录头中的 next_record 字段进行链接。

1. 存储结构图如下,

1. 小结

• 对于单页存储不了的状况, 须要进行页决裂, 此时 B + 树会有多层构造, 最低层为叶子节点, 存储了具体的数据, 下面是索引节点, 只存储主键以及下一层节点所在的页信息

五. 总结与思考

本文介绍了 innodb 的数据页存储, 以实例的形式解说了 innodb 存储引擎如何存储一个表中数据的。然而咱们依然有很多问题没有给出答案,

1. 查找行记录时, 须要找到某个索引的 root page, 这个信息是存储在哪里的?
2. 咱们没有介绍段和区的相干内容, 这些在 InnoDB 数据存储时是如何应用的?
3. 咱们查看数据时, 都是间接查看磁盘文件, 内存中的页与磁盘中的页有何区别, 内存中的脏页又是如何刷新到磁盘的?

InnoDB 存储引擎较为简单, 不可能一次性将全部内容学会, 咱们无妨每次带入一个问题, 深刻寻找这个问题的答案, 对于这些问题, 我会在后续文章中再逐渐介绍。

六. 参考

1. <<Mysql 技术底细 InnoDB 存储引擎 >>
2. 淘宝数据库内核月报