リーフ以外のb ツリー ノードは innodb で物理的にどのように表されますか?
b-tree (より具体的には b+tree) には葉ノードと非葉ノードの両方があることを思い出してください。b+tree では、すべてのリーフ ノードが非リーフ ノードまたは「内部」ノードのツリーの下にあり、実際に行データを含むページを指します。
非リーフ ノードは非リーフ ノード セグメントに格納され、データ ページのようなページを使用することがわかっています。データ ページが物理的にどのように格納されているかについては十分なドキュメントを見つけましたが、非リーフ インデックス ページがどのように見えるかについては何も見つけることができませんでした。
InnoDB の学習: コアへの旅で、innodb_diagrams プロジェクトを紹介して、この投稿で使用される図を提供する InnoDB の内部を文書化しました。後の「innodb_ruby の簡単な紹介」では、innodb_space コマンドライン ツールのインストールといくつかの簡単なデモについて説明しました。
InnoDB の INDEX ページの物理構造は、InnoDB インデックス ページの物理構造で説明されています。次に、いくつかの実用的な例を使用して、InnoDB がそのインデックスを論理的に構造化する方法を調べます。
用語の余談: B+Tree、ルート、リーフ、およびレベル InnoDB は、そのインデックスに B+Tree 構造を使用します。B+Tree は、データがメモリに収まらず、ディスクから読み取る必要がある場合に特に効率的です。これは、ツリーの深さのみに基づいて、要求されたデータにアクセスするために一定の最大読み取り回数が必要になることを保証するためです。 、うまくスケーリングします。
インデックス ツリーは、ツリーにアクセスするための開始点として、場所が固定されている (そして InnoDB のデータ ディクショナリに永続的に格納されている) 「ルート」ページから始まります。ツリーは、単一のルート ページほど小さい場合もあれば、マルチレベル ツリーの数百万ページほど大きい場合もあります。
ページは、「リーフ」ページまたは「非リーフ」ページ (一部のコンテキストでは「内部」ページまたは「ノード」ページとも呼ばれます) と呼ばれます。リーフ ページには、実際の行データが含まれます。非リーフ ページには、他の非リーフ ページまたはリーフ ページへのポインタのみが含まれます。木はバランスが取れているため、木の枝はすべて同じ深さになります。
InnoDB は、ツリー内の各ページに「レベル」を割り当てます。リーフ ページにはレベル 0 が割り当てられ、レベルはツリーの上方に向かって増加します。ルート ページ レベルは、ツリーの深さに基づいています。区別が重要な場合、リーフ ページでもルート ページでもないすべてのページを「内部」ページと呼ぶこともできます。
リーフ ページと非リーフ ページ リーフ ページと非リーフ ページ の両方について、各レコード (最小システム レコードと上限システム レコードを含む) には、次のレコードへのオフセット (ページ内) を格納する「次のレコード」ポインターが含まれています。リンクされたリストは infimum から始まり、すべてのレコードをキーの昇順でリンクし、supremum で終了します。レコードはページ内で物理的に順序付けられているわけではありません (挿入時に使用可能なスペースを使用します)。それらの唯一の順序は、リンクされたリスト内の位置から来ます。
リーフ ページには、各レコードに含まれる「データ」の一部として非キー値が含まれます。
非リーフ ページは同じ構造を持ちますが、非キー フィールドの代わりに、それらの「データ」は子ページのページ番号であり、正確なキーの代わりに、それらが指す子ページの最小キーを表します。
同じレベルのページ ほとんどのインデックスには複数のページが含まれているため、複数のページは昇順および降順でリンクされています。
各ページには、「前のページ」と「次のページ」のポインターが (FIL ヘッダーに) 含まれており、INDEX ページでは、同じレベルのページの二重リンク リストを形成するために使用されます (たとえば、レベル 0 のリーフ ページは 1 を形成します)。リスト、レベル 1 ページは別のリストを形成するなど）。
単一ページのテーブルの詳細 単一のインデックス ページで B+Tree に関連するもののほとんどを見てみましょう。
テーブルを作成して入力する 上 の図で使用されているテスト テーブルを作成して入力することができます (innodb_file_per_table を使用し、Barracuda ファイル形式を使用していることを確認してください)。
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");
この表は非常に小さく現実的ではありませんが、レコードとレコード トラバーサルがどのように機能するかをうまく示しています。
スペース ファイルの基本構造を確認します 。テーブルは、3 つの標準オーバーヘッド ページ (FSP_HDR、IBUF_BITMAP、および INODE) の後に、インデックスのルート用の 1 つの INDEX ページが続く、以前に調べたものと一致する必要があります。 2 つの未使用の ALLOCATED ページ。
$ innodb_space -f t_btree.ibd space-page-type-regions
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 space-index-pages-summary
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 モードでは、内部ファイル セグメントで 1 ページを消費している PRIMARY KEY インデックスに関する統計が表示されます。
$ innodb_space -f t_btree.ibd space-indexes
id root fseg used allocated fill_factor
18 3 internal 1 1 100.00%
18 3 leaf 0 0 0.00%
レコード 記述子をセットアップする innodb_ruby がレコードの内容を解析するためには、インデックスの説明を返すメソッドを提供する Ruby クラスであるレコード記述子を提供する必要があります。
class SimpleTBTreeDescriber < Innodb::RecordDescriber タイプ :クラスター化されたキー "i", :INT, :NOT_NULL 行 "s", "CHAR(10)", :NOT_NULL end
これはクラスター化されたキーであり、キーの列の説明と非キー (「行」) フィールドの列の説明を提供する必要があることに注意する必要があります。次の追加の引数を使用して、このクラスをロードするように innodb_space に要求する必要があります。
-r -r ./simple_t_btree_describer.rb -d SimpleTBTreeDescriber
レコードの内容を見てください 。この例のルート ページ (リーフ ページ) は、ページ ダンプ モードを使用してダンプでき、ルート ページのページ番号を指定できます。
$ innodb_space -f t_btree.ibd -r ./simple_t_btree_describer.rb -d
SimpleTBTreeDescriber -p 3 ページダンプ
以前に見たこの出力の一部とは別に、レコードごとに次の構造を持つ「records:」セクションが出力されます。
{: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 であることは、レコードが Barracuda フォーマット テーブルの新しい「コンパクト」フォーマットであることを示します (Antelope テーブルの「冗長」ではなく)。出力に表示される :key はインデックスのキー フィールドの配列であり、:row は非キー フィールドの配列です。:transaction_id および :roll_pointer フィールドは、クラスター化されたキー (PRIMARY KEY) であるため、各レコードに含まれる MVCC の内部フィールドです。:header ハッシュ内の :next フィールドは、次のレコードの実際のオフセット (157) を生成するために、現在のレコード オフセット (125) に追加する必要がある相対オフセット (32) です。便宜上、この計算されたオフセットは、レコード ハッシュに :next として含まれます。インデックスを再帰する インデックス再帰モードを使用すると、インデックス全体を再帰する優れた単純な出力を実現できますが、これはまだ単一ページのインデックスであるため、
$ 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 index-recurse
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 行で確認できる 3 レベルのインデックス ツリーです。一部のページが完全にいっぱいで、468 レコードが 16 KiB ページのほぼ 15 KiB を消費していることがわかります。
ページ ダンプ モードを使用して非リーフ ページ (上記の出力の 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 がその代わりになるためです。
ルート ページは少し特殊です ルート ページはインデックスが最初に作成されたときに割り当てられ、そのページ番号はデータ ディクショナリに格納されるため、ルート ページを再配置または削除することはできません。ルート ページがいっぱいになったら、それを分割して、ルート ページと 2 つのリーフ ページの小さなツリーを形成する必要があります。
ただし、ルート ページ自体は再配置できないため、実際には分割できません。代わりに、新しい空のページが割り当てられ、ルート内のレコードがそこに移動され (ルートが 1 レベル上げられます)、その新しいページが 2 つに分割されます。ルートページは、すぐ下のレベルに十分なページがあり、ルートが子ページポインター (「ノードポインター」と呼ばれる) でいっぱいになるまで、再度分割する必要はありません。
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 の効率が大幅に低下する可能性があります。これにより、非リーフ ページのレコードのサイズが大幅に増加する可能性があります。つまり、各非リーフ ページに収まるレコードが大幅に少なくなり、構造全体の効率が低下します。