それが僕には楽しかったんです。

ミドルウェアとかやってます

InnoDB におけるページとインデックスの物理的な構成について

この記事は「 けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 9日目の記事です。

はじめに

どうも、最近このアドカレが本当に終わるのかどうなのか心配になってきているけんつです。
今回は DBMS のストレージ構造を考えていたらインデックスを物理的に保存する場合の構造ってどうなってるんだろうなぁと思ったので InnoDB の内部構造とその物理的な形式を追っていく。
あんまり深く追ってしまうと本当にキリが無いので自分の理解が足りない部分をメモしていく感じになる

参考にしたサイト


blog.jcole.us
blog.jcole.us

InnoDB のスペースファイルレイアウト

InnoDB のデータストレージモデルは MySQL のドキュメントではテーブルスペースと呼ばれているが InnoDB 自体ではファイルスペースと呼ばれている。
スペースは ibdata1, ibdata2, ... などで複数の物理ファイルで構成されるが単一の論理ファイルとして扱われる。

InnoDB の書くスペースには 32bit のスペースIDが与えられる。このIDを元に DBMS やストレージはスペースを参照する。
またこの ID は 0 から始まり、ID が 0 のものはシステムスペースと言われる。このシステムスペースはストレージに関する内部的な情報を保持する。

ページ構成

各スペースは 16 KB*1 毎に 32 bit のID が割り当てられページに分割される。
このページ ID はスペースの先頭からのオフセットに過ぎない。

実際にページは次のようなレイアウトを取る。

https://i0.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/Basic_Page_Overview.png
https://i2.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/FIL_Header_and_Trailer.png


FIL Header *2というものが 38 byte あり、ボディに相当する部分が 16338 KB ある。
そして末尾に FIL Trailer というものが 8 byte ある。
Header はページの種類を示すために使用される。

FIL Header
name length
Checksum 4 byte
Offset (Page Number) 4 byte
Previous Page 4 byte
Next Page 4 byte
LSN for last page modification 8 byte
Page Type 2 byte
Flush LSN (0 except space 0 page 0) 8 byte
Space ID 4 byte
FIL Trailer
name length
Old-Style Checksum 4 byte
Low 32 bits of LSN 4 byte

Header, Trailer の構造的特徴

まずページタイプはヘッダーに保存される。このヘッダーには後に続くページデータを解析するために必要な情報が入っている。またスペースIDもヘッダーに直接保存されている。
ページは初期化される段階でページIDをヘッダーに保存する。そして、フィールドから読み取られたページIDがファイルへのオフセットに基づいていることを確認する。

また Previous Page と Next Page というフィールドが存在するように、ページは前後のページに対するポインタを保持している。
これによりページは双方向リストとして扱うことができる。インデックスの構築はこの特性を利用した上で全てのページをリンクすることを目的としている。

LSN*3 についてはまだ CMU の講義で Database Recovery まで進んでいないので触れない。

スペースファイル

スペースファイルは多くのページの連続体となっている。ただ連続しているわけではなく、効率的に管理するためにページは64個で1グループと見なされエクステントという単位で管理されるされている。このエクステントを連続して保持しているのがスペースファイルとなる。
そのためは次のような構造を取る。

https://i2.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/Space_File_Overview.png

FSP_HDR, IBUF_BITMAP, INODE*4 が続いたあとはエクステントと言われる領域が連続する。

テーブル毎のスペース

InnoDB は FIle_per_tablespace がデフォルトで有効になっているためテーブルごとにスペースファイルを作成する。
ibd ファイルというものがそれに該当するが次のような構造を取る。

https://i2.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/IBD_File_Overview.png

この構造で注目したいのはインデックスに関する情報を保持しているという点。
ルートページに関するインデックスや、インデックスにおいてノードページとリーフページと情報を保持している。

これが物理的なインデックス情報の保持に関わってくる。

おわりに

インデックス全然わからない。

*1:デフォルトでは 16 KB となっているが変更可能

*2:FIL というのは File の短縮形らしい

*3:ログシーケンス番号というもの。リカバリの際に使用することがあるらしい。

*4:Index のノード情報を持つ