非叶b 树节点在 innodb 中是如何物理表示的？
回想一下，b-tree（更具体地说是 b+tree）具有叶节点和非叶节点。在 b+tree 中，所有叶节点都位于非叶或“内部”节点树的下方，并指向实际包含行数据的页面。
我知道非叶节点存储在非叶节点段中，并使用类似于数据页的页面。我找到了有关如何物理存储数据页的大量文档，但是我无法找到有关非叶索引页的外观的任何内容。
问问题
2181 次
1 回答
1
在 On learning InnoDB: A Journey to the core 中，我介绍了 innodb_diagrams 项目来记录 InnoDB 内部结构，它提供了本文中使用的图表。稍后在 innodb_ruby 的快速介绍中，我介绍了 innodb_space 命令行工具的安装和一些快速演示。
InnoDB 索引页的物理结构在 InnoDB 索引页的物理结构中描述。我们现在将使用一些实际示例来研究 InnoDB 如何在逻辑上构建其索引。
术语旁白：B+Tree、root、leaf 和 level InnoDB 使用 B+Tree 结构作为其索引。当数据不适合内存并且必须从磁盘读取时，B+Tree 特别有效，因为它确保仅基于树的深度访问任何请求的数据需要固定的最大读取次数，可以很好地扩展。
索引树从“根”页开始，其位置是固定的（并永久存储在 InnoDB 的数据字典中）作为访问树的起点。树可以小到单个根页面，也可以大到多级树中的数百万个页面。
页面被称为“叶子”页面或“非叶子”页面（在某些情况下也称为“内部”或“节点”页面）。叶页包含实际的行数据。非叶子页面仅包含指向其他非叶子页面或叶子页面的指针。树是平衡的，因此树的所有分支具有相同的深度。
InnoDB 为树中的每个页面分配一个“级别”：叶页面被分配级别 0，并且级别在树上递增。根页面级别基于树的深度。如果区分很重要，所有既不是叶页也不是根页的页面也可以称为“内部”页面。
叶页和非叶页 对于叶页和非叶页，每条记录（包括下确界和上确界系统记录）都包含一个“下一条记录”指针，它存储到下一条记录的偏移量（在页内）。链表从 infimum 开始，按 key 升序链接所有记录，到 supremum 终止。记录在页面内没有物理排序（它们占用插入时可用的任何空间）；他们唯一的顺序来自他们在链表中的位置。
叶页面包含非键值作为每个记录中包含的“数据”的一部分：
非叶子页面具有相同的结构，但它们的“数据”不是非键字段，而是子页面的页码，而不是确切的键，它们代表它们指向的子页面上的最小键：
同一级别的页面 大多数索引包含多个页面，因此多个页面按升序和降序链接在一起：
每个页面都包含“上一页”和“下一页”的指针（在 FIL 标题中），对于 INDEX 页面，这些指针用于形成同一级别的页面的双向链接列表（例如，叶子页面，在级别 0 形成一个列表，第 1 级页面形成单独的列表等）。
单页表详解 让我们看一下单索引页中大部分B+Tree相关的内容：
创建和填充表 可以创建和填充上图中使用的测试表（确保您使用的是 innodb_file_per_table 并使用梭子鱼文件格式）：
CREATE TABLE t_btree (
i INT NOT NULL,
s CHAR(10) NOT NULL,
PRIMARY KEY(i)
) ENGINE=InnoDB;
INSERT INTO t_btree (i, s)
VALUES (0, "A"), (1, "B"), (2, "C");
虽然这个表很小而且不现实，但它确实很好地展示了记录和记录遍历是如何工作的。
验证空间文件的基本结构 该表应该与我们之前检查过的相匹配，三个标准开销页（FSP_HDR、IBUF_BITMAP 和 INODE）后跟一个索引根的单个 INDEX 页，在这种情况下两个未使用的 ALLOCATED 页。
$ innodb_space -f t_btree.ibd 空间页面类型区域
start end count type
0 0 1 FSP_HDR
1 1 1 IBUF_BITMAP
2 2 1 INODE
3 3 1 INDEX
4 5 2 FREE (ALLOCATED)
space-index-pages-summary 模式将为我们提供每页中的记录计数，并显示预期的 3 条记录：
$ innodb_space -f t_btree.ibd 空间索引页面摘要
page index level data free records
3 18 0 96 16156 3
4 0 0 0 16384 0
5 0 0 0 16384 0
（请注意，space-index-pages-summary 还将空的 ALLOCATED 页面显示为具有零记录的空页面，因为这通常是您对绘图感兴趣的内容。）
space-indexes 模式将显示有关我们的 PRIMARY KEY 索引的统计信息，该索引正在其内部文件段上消耗一个页面：
$ innodb_space -f t_btree.ibd 空间索引
id root fseg used allocated fill_factor
18 3 internal 1 1 100.00%
18 3 leaf 0 0 0.00%
设置记录描述 器 为了让 innodb_ruby 解析记录的内容，我们需要提供一个记录描述器，它只是一个 Ruby 类，提供了一个返回索引描述的方法：
类 SimpleTBTreeDescriber < Innodb::RecordDescriber type :clustered key "i", :INT, :NOT_NULL row "s", "CHAR(10)", :NOT_NULL end
我们需要注意这是聚集键，提供键的列描述，以及非键（“行”）字段的列描述。有必要要求 innodb_space 使用以下附加参数加载此类：
-r -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber
查看记录内容 本示例中的根页面（即叶子页面）可以使用 page-dump 模式进行转储，并提供根页面的页码：
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d
SimpleTBTreeDescriber -p 3 页面转储
除了我们之前看过的该输出的某些部分之外，它现在将打印一个“记录：”部分，每条记录具有以下结构：
{:format=>:compact,
:offset=>125,
:header=>
{:next=>157,
:type=>:conventional,
:heap_number=>2,
:n_owned=>0,
:min_rec=>false,
:deleted=>false,
:field_nulls=>nil,
:field_lengths=>[0, 0, 0, 0],
:field_externs=>[false, false, false, false]},
:next=>157,
:type=>:clustered,
:key=>[{:name=>"i", :type=>"INT", :value=>0, :extern=>nil}],
:transaction_id=>"0000000f4745",
:roll_pointer=>
{:is_insert=>true, :rseg_id=>8, :undo_log=>{:page=>312, :offset=>272}},
:row=>[{:name=>"s", :type=>"CHAR(10)", :value=>"A", :extern=>nil}]}
这应该与上面的详细说明完全一致，因为我已经从这个示例中复制了大部分信息以确保准确性。注意以下几个方面：
:format 是 :compact 表示记录是梭子鱼格式表中的新“紧凑”格式（与羚羊表中的“冗余”相反）。输出中列出的 :key 是索引的关键字段数组， :row 是非关键字段数组。:transaction_id 和 :roll_pointer 字段是包含在每个记录中的 MVCC 的内部字段，因为这是一个集群键（PRIMARY KEY）。:header 散列中的 :next 字段是一个相对偏移量 (32)，必须将其添加到当前记录偏移量 (125) 以产生下一条记录 (157) 的实际偏移量。为方便起见，计算出的偏移量包含在记录哈希中的 :next 中。递归索引 使用 index-recurse 模式可以实现递归整个索引的简单输出，但由于这仍然是单页索引，
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d
SimpleTBTreeDescriber -p 3 索引递归
ROOT NODE #3: 3 records, 96 bytes
RECORD: (i=0) -> (s=A)
RECORD: (i=1) -> (s=B)
RECORD: (i=2) -> (s=C)
构建非平凡的索引树 InnoDB 中的多级索引树（过于简化）如下所示：
如前所述，每个级别的所有页面都相互双链接，并且在每个页面内，记录按升序单链接。非叶子页面包含“指针”（包含子页码）而不是非键行数据。
如果我们使用在快速介绍 innodb_ruby 中创建了 100 万行的更简单的表模式，那么树结构看起来会更有趣一些：
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 3 索引递归
ROOT NODE #3: 2 records, 26 bytes
NODE POINTER RECORD >= (i=252) -> #36
INTERNAL NODE #36: 1117 records, 14521 bytes
NODE POINTER RECORD >= (i=252) -> #4
LEAF NODE #4: 446 records, 9812 bytes
RECORD: (i=1) -> ()
RECORD: (i=2) -> ()
RECORD: (i=3) -> ()
RECORD: (i=4) -> ()
NODE POINTER RECORD >= (i=447) -> #1676
LEAF NODE #1676: 444 records, 9768 bytes
RECORD: (i=447) -> ()
RECORD: (i=448) -> ()
RECORD: (i=449) -> ()
RECORD: (i=450) -> ()
NODE POINTER RECORD >= (i=891) -> #771
LEAF NODE #771: 512 records, 11264 bytes
RECORD: (i=891) -> ()
RECORD: (i=892) -> ()
RECORD: (i=893) -> ()
RECORD: (i=894) -> ()
这是一个三级索引树，可以通过上面的 ROOT、INTERNAL、LEAF 行看到。我们可以看到有些页面已满，有 468 条记录消耗了 16 KiB 页面中的近 15 KiB。
使用 page-dump 模式查看非叶子页面（第 36 页，在上面的输出中），记录看起来与之前显示的叶子页面略有不同：
$ innodb_space -f t.ibd -r ./simple_t_describer.rb -d SimpleTDescriber -p 36 页面转储
{:format=>:compact,
:offset=>125,
:header=>
{:next=>11877,
:type=>:node_pointer,
:heap_number=>2,
:n_owned=>0,
:min_rec=>true,
:deleted=>false,
:field_nulls=>nil,
:field_lengths=>[0],
:field_externs=>[false]},
:next=>11877,
:type=>:clustered,
:key=>[{:name=>"i", :type=>"INT UNSIGNED", :value=>252, :extern=>nil}],
:child_page_number=>4}
存在 :key 数组，尽管它表示最小键而不是精确键，并且没有 :row 存在，因为 :child_page_number 代替了它。
根页有点特殊 由于根页是在第一次创建索引时分配的，并且该页码存储在数据字典中，因此根页永远不能重定位或删除。一旦根页面填满，就需要拆分，形成一个根页面加上两个叶子页面的小树。
但是，根页面本身实际上不能被拆分，因为它不能被重新定位。相反，分配了一个新的空页面，将根中的记录移动到那里（根被“提升”了一个级别），并且该新页面被分成两部分。然后根页面不需要再次拆分，直到其下一级有足够的页面使根充满子页面指针（称为“节点指针”），这在实践中通常意味着几百到一千多个。
B+Tree 级别和增加树深度 作为 B+Tree 索引效率的一个示例，假设完美的记录打包（每个页面都已满，这在实践中永远不会发生，但对讨论很有用）。上面示例中简单表的 InnoDB 中的 B+Tree 索引将能够存储每个叶页 468 条记录，或每个非叶页 1203 条记录。在给定的树高度，索引树可以是以下大小的最大值：
Height Non-leaf pages Leaf pages Rows Size in bytes
1 0 1 468 16.0 KiB
2 1 1203 > 563 thousand 18.8 MiB
3 1204 1447209 > 677 million 22.1 GiB
4 1448413 1740992427 > 814 billion 25.9 TiB
可以想象，大多数具有合理 PRIMARY KEY 定义的表都是 2-3 级，有些达到 4 级。然而，使用过大的 PRIMARY KEY 会导致 B+Tree 的效率大大降低，因为主键值必须存储在非叶页中。这会极大地增加非叶子页面中记录的大小，这意味着每个非叶子页面中的记录要少得多，从而使整个结构的效率降低。
于 2018-06-01T08:11:47.573 回答