InnoDB におけるページとインデックスの物理的な構成について
この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 9日目の記事です。
はじめに
どうも、最近このアドカレが本当に終わるのかどうなのか心配になってきているけんつです。
今回は DBMS のストレージ構造を考えていたらインデックスを物理的に保存する場合の構造ってどうなってるんだろうなぁと思ったので InnoDB の内部構造とその物理的な形式を追っていく。
あんまり深く追ってしまうと本当にキリが無いので自分の理解が足りない部分をメモしていく感じになる
参考にしたサイト
InnoDB のスペースファイルレイアウト
InnoDB のデータストレージモデルは MySQL のドキュメントではテーブルスペースと呼ばれているが InnoDB 自体ではファイルスペースと呼ばれている。
スペースは ibdata1, ibdata2, ... などで複数の物理ファイルで構成されるが単一の論理ファイルとして扱われる。
InnoDB の書くスペースには 32bit のスペースIDが与えられる。このIDを元に DBMS やストレージはスペースを参照する。
またこの ID は 0 から始まり、ID が 0 のものはシステムスペースと言われる。このシステムスペースはストレージに関する内部的な情報を保持する。
ページ構成
各スペースは 16 KB*1 毎に 32 bit のID が割り当てられページに分割される。
このページ ID はスペースの先頭からのオフセットに過ぎない。
実際にページは次のようなレイアウトを取る。
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 というフィールドが存在するように、ページは前後のページに対するポインタを保持している。
これによりページは双方向リストとして扱うことができる。インデックスの構築はこの特性を利用した上で全てのページをリンクすることを目的としている。
スペースファイル
スペースファイルは多くのページの連続体となっている。ただ連続しているわけではなく、効率的に管理するためにページは64個で１グループと見なされエクステントという単位で管理されるされている。このエクステントを連続して保持しているのがスペースファイルとなる。
そのためは次のような構造を取る。
おわりに
インデックス全然わからない。
