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 を関数型っぽく扱う
やっと B+Tree Index まできた…。
InnoDB の B+Tree Index はディスクからの読み出しに対して最適化された構造になっている。
root page, leaf page, non-leaf page(internal page) で構成される。
root page は必ず一つ。そこから leaf page もしくは internal page への参照を持つ。
全ての leaf page は同じ level に存在し、その level を 0 として扱う。
leaf page では infimum レコードから始まって supremum レコードまで次のレコードへの参照が続く single-linked list の構造を持っている。そして infimum と supremum レコードの間の user record は index を構成する key 値と value 値を持つ。
internal page では leaf page 同様に infimum から始まり supremum まで続く single-linked list 構造だが、子供となる internal/leaf page の最小の key 値とその pgae へのポインタを持つ。
同じ level に属する page 同士はそれぞれ次の page と前の page へのポインタも持っている。