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