はじめに
こんにちは。ディップ株式会社の福岡拠点でエンジニアとして働いている佐藤です。
アドベントカレンダーの7日目を担当させていただきます！
今回の記事の内容は、DBのインデックスの「仕組み」がどうなっているのか についてです。
インデックスが高速に検索できる仕組みである 「B-tree / B+Tree」の構造を、図を用いてできるだけわかりやすく解説します。
きっかけ
業務中にマイグレーションを適用して「ちゃんとインデックスがはられているかな？」とDBMSで確認したところindex_algorithmのプルダウンに
- BTree
- HASH
- FULLTEXT
- SPATIAL
など、複数のアルゴリズムが選択できることに気づきました。
「自分はいままでインデックス＝効率が良くなり検索スピードが上がるもの、くらいの理解だったな」 と思い、インデックスの仕組みを調べてみることにしました。
インデックスの正体
まず気になったのが、
「インデックスって、テーブルみたいに中身を覗けるのか？」
という点でした。
インデックスは ページという単位のバイナリデータ として保存されているため
人がそのまま目で見ても全く理解できません。
インデックスが効いているかどうかは EXPLAIN 文で確認できますが
実体そのものを見られない という点が理解を難しくしているなと感じました。
インデックスは、基本的に（キー, 値）のペアで構成されています。
値には、ポインタ（行の位置）かデータそのものが配置されます。
このキーをいかに効率よく見つけるかが鍵となるわけです。（キーだけに
）
今回は、 多くのDBMSで一般的に採用されている B-tree 系データ構造（B-tree / B+Tree） を中心にその仕組みを順番に整理していきますが
B+Tree の仕組みを説明する前に、その元となった B-tree、さらにその前提となる 2分探索木を順に整理していきたいと思います。
2分探索木
「1,3,4,6,7,8,9」といった値を2分探索木のルールに従って配置すると、下の図のようになります。
- ○ が 節（ノード）
- ノードをつなぐ線が 枝
- 一番上のノードが 根
- 一番下のノードが葉
という構成になっています。
検索時のルールは
- 検索対象 < ノードの値 → 左へ
- 検索対象 > ノードの値 → 右へ
と進み、繰り返すことで目的の値に辿り着きます。
例）検索対象が「7」であった場合
- 6と7を比較 → 右へ
- 8と7を比較 → 左へ
なので比較回数としては、2回で目的の値に辿り着くことができます。
値の先頭から目的のものを探す（フルテーブルスキャン）より、明らかに比較回数が少なく済みます。
ただし、2分探索木には
- ノードは1つの値しか持つことができない
- 子は最大で2つ
という制約があるため、データが増えると木の高さが深くなりやすいという課題があります。この 木が深くなる問題を解決するために考案されたのが B-tree です。
B-Tree
2分探索木と比較したB-Treeの特徴として
- ノードに複数のキー（値も含む）を持つことができます
- 複数の子ノードを持つことができます
- データの登録や削除が行われても、高さを一定に保つように、常に木全体でバランスをとります
これらの特性により
2分探索木のように木が深くなりすぎず、木の高さを低く保つことができ、検索の効率が大きく向上します。
※ B-tree では、内部ノード（葉以外のノード）に
キーと、対応する子ノードへのポインタ を持っており
葉ノードには キーとデータへのポインタ（またはデータそのもの） が格納されます。
図では構造を分かりやすくするため、ポインタ部分を省略し、キー（数値）のみを表記しています。
B+Tree
B-Treeと比較したB+Treeの特徴として
- 内部ノード（葉以外のノード）には、キーのみを持ちます
- 葉ノードにデータ（またはデータへのポインタ）が集約されています
- 葉ノード同士が連結リストになっています
これらの特性により
- 内部ノードのデータ量が少なくなり、よりたくさんのキーを持つことができます
- 連結されていることによって、一度検索開始位置が見つかれば、あとは葉ノードを横方向に順にスキャンするだけなので範囲検索を高速に処理できます
DBによっての違い
DBMSによって同じ B+Tree 系インデックスでも表記が異なることもあります。
PostgreSQLでは「B-tree」と表記されており、これは B-tree 系データ構造の総称で、 実装としては B+Tree に近い構造が用いられています。そのため、表記が「B-tree」であっても実体は B+Tree の性質を持つと考えて問題ない場合がほとんどです。
まとめ
2分探索木 → B-Tree → B+Tree の順に見てきました。
調べる前までは、「検索を速くする仕組みだけど、実態が不明な何か」という印象でしたが
今回改めて調べてみることで、1歩深く理解できた気がします。
インデックスの仕組みを理解するきっかけになれば幸いです。
参考文献
- https://gihyo.jp/dev/serial/01/sql_academy2/000701#sec2_h2
- https://planetscale.com/blog/btrees-and-database-indexes?utm_source=chatgpt.com
- https://it-biz.online/it-skills/b-tree/?utm_source=chatgpt.com#toc3
- https://www.momoyama-usagi.com/entry/info-algo-tree?utm_source=chatgpt.com
- https://www.postgresql.jp/docs/14/btree-implementation.html