Extended outer memory module
for my poor native memory.
Posts:
2022/02/13 クラビスの CTO になりました
2020/09/28 gendoc という YAML からドキュメントを生成するコマンドを作った
2020/09/13 ISUCON10 の予選を 7 位で通過した
2019/12/01 Puma の内部構造やアーキテクチャを追う
2019/05/27 Golang の正規表現ライブラリの処理の流れをざっくり掴む
2019/04/29 InnoDB の B+Tree Index について
2019/04/29 InnoDB における index page のデータ構造
2019/04/28 InnoDB はどうやってファイルにデータを保持するのか
2019/01/06 Designing Data-Intensive Applications を読んでいる
2019/01/03 年末年始に読んだ本について、など
2019/01/01 Ruby から ffi を使って Rust を呼ぶ
2018/11/10 ブラウザにおける状態の持ち方
2018/07/01 Rust で web アプリ、 或いは Rust における並列処理
2018/05/14 なぜテストを書くのか
2018/05/13 Rust で wasm 使って lifegame 書いた時のメモ
2018/03/12 qemu で raspbian のエミュレート(環境構築メモ)
2018/03/12 qemu で xv6 のエミュレート(環境構築メモ)
2018/03/03 Ruby の eval をちゃんと知る
2018/02/11 Web のコンセプト
2018/02/03 Rspec のまとめ
2018/02/03 Ruby を関数型っぽく扱う
一つ前の記事に引き続き、今回は index page のデータ構造について。
InnoDB は B+Tree を利用した index を基本構造としており、またデータの保持を行う際には cluster index というデータ構造を採用している。
仮に CREATE TABLE 文が発行されたタイミングで PRIMARY KEY が指定されていなかった場合には、最初に出てきた 非 NULL で UNIQUE なカラム をベースに cluster index が構築される。
それも存在しなかった場合には暗黙的に 48-bit の Row ID というカラムが cluster index のベースキーとして作成される。
16 KB(= 16384 bytes) で構成される page のうち、先頭 38 bytes と末尾 8 bytes は前回の記事で紹介した通り FIL Header, FIL Trailer と呼ばれるヘッダとトレイラが置かれている。この部分で前後の index page へのポインタを保持する。
それらも含めて構造を記載すると以下のようになる。
36 bytes の構成は以下。
全ての index page は infimum と supremum と呼ばれる 2 つの system record を保持している。
infimum はその index page に存在するどの record よりも低く最大の key 値を持ち、next record として user record 内で最小の key 値の record を持つ。 supremum は対照的にどの record よりも高く最小の key 値を持つ。
これによって page 全体を走査しなくてもスキップする page というのを特定することができるっぽい。