データベースインデックスの仕組み — B+木とLSM-Treeの内部構造

なぜインデックスが必要なのか

テーブルのフルスキャン（全行走査）では、$O(n)$ 行を調べます。行はページにまとめて格納され、1ページに数百行が入るとすると、100万行のテーブルは数千ページになります。1行を探すだけでも、この数千ページを読んで全行を確認します。

適切なインデックスがあれば、検索は $O(\log n)$ で済みます。B+木インデックスは1つのノードから分かれる子の数（分岐数、fan-out）が大きいので、100万行のテーブルでも3〜4回のディスクアクセスで目的の行に届きます。

インデックスの中核となるデータ構造には、読取りに強いB+木と、書込みに強いLSM-Treeがあります。どちらが適しているかは、読取りと書込みのどちらが多いか、範囲検索をどれだけ使うかで変わります。

B+木（B+ Tree）の基礎

B木からB+木へ

B木（B-Tree）は、Rudolf BayerとEdward McCreightが1970年に発表した自己平衡探索木です。各ノードが複数のキーを持つので、1回のディスク読取りで多くのキーを比較でき、ディスク上のデータの探索に向いています。

B+木は、B木に次の2つの変更を加えた構造です。

1. データはリーフノードにのみ格納される — 内部ノードはキー（ルーティング情報）のみを持つ
2. リーフノード同士が連結リストで接続されている — 範囲検索が効率的になる

B+木の性質

次数（order）$m$ のB+木は、次の性質を持ちます。

• 各内部ノードは最大 $m$ 個の子ノードを持つ
• 各内部ノードは最低 $\lceil m/2 \rceil$ 個の子ノードを持つ（ルートを除く）
• $k$ 個のキーを持つ内部ノードは $k+1$ 個の子ノードを持つ
• リーフノードは最大 $m-1$ 個のキーを持つ
• リーフノードは最低 $\lceil (m-1)/2 \rceil$ 個のキーを持つ
• すべてのリーフは同じ深さにある（完全平衡）

検索アルゴリズム

検索では、ルートからリーフに向かって木を下ります。

Search(node, key):
  if node is leaf:
    return binary_search(node.keys, key)
  
  // 内部ノード: 適切な子ノードを選ぶ
  i = 0
  while i < len(node.keys) and key >= node.keys[i]:
    i += 1
  return Search(node.children[i], key)

各ノードのキーはソートされているので、二分探索を使えば $O(\log m)$ で次にたどる子ノードを特定できます。木の高さは $O(\log_m n)$ なので、全体の計算量は $O(\log_m n \cdot \log_2 m) = O(\log n)$ です。

実際の $m$ は数百程度（ノードサイズはディスクページと同じ4KB〜16KB）なので、100万行のテーブルでも木の高さは3〜4程度です。

挿入と分割

挿入は次の手順で進みます。

1. 検索アルゴリズムで挿入先のリーフノードを特定する
2. リーフにキーを挿入する（ソート順を維持）
3. リーフが溢れた場合（キー数 > $m-1$）は、分割（split）する：
   • リーフを2つに分ける
   • 区切りキー（リーフ分割では新しい右リーフの先頭キー）を親ノードにコピーする
   • 親も溢れた場合は、親も分割する（分割が再帰的に上へ伝播する）
4. ルートを分割した場合は、新しいルートを作る（木の高さが1段増える）

次のデモでは、この過程を1ステップずつ実行できます。

分割の擬似コードは次のとおりです。

Insert(tree, key, value):
  leaf = find_leaf(tree.root, key)
  insert_into_leaf(leaf, key, value)
  
  if leaf.num_keys > MAX_KEYS:
    split_leaf(leaf)
 
SplitLeaf(leaf):
  mid = ceil(leaf.num_keys / 2)
  new_leaf = new LeafNode()
  
  // 後半のキーを新リーフに移動
  new_leaf.keys = leaf.keys[mid:]
  leaf.keys = leaf.keys[:mid]
  
  // 連結リストを更新
  new_leaf.next = leaf.next
  leaf.next = new_leaf
  
  // 区切りキーを親にコピー
  promote_key = new_leaf.keys[0]
  insert_into_parent(leaf.parent, promote_key, new_leaf)

範囲検索の効率性

B+木の最大の強みは範囲検索です。リーフノードが連結リストでつながっているので、範囲の開始点を見つけたら、あとはリーフを順にたどるだけです。

RangeScan(tree, low, high):
  leaf = find_leaf(tree.root, low)
  results = []
  
  while leaf != null:
    for key in leaf.keys:
      if key > high:
        return results
      if key >= low:
        results.append(leaf.data[key])
    leaf = leaf.next
  
  return results

リーフノードはディスク上で連続して配置されることが多いので、この走査ではシーケンシャルリードを使えます。

削除とマージ

削除でリーフのキー数が最小値（$\lceil (m-1)/2 \rceil$）を下回ると、再分配（redistribution）かマージ（merge）を行います。

1. 再分配：隣接する兄弟ノードからキーを借りる
2. マージ：兄弟ノードと合体し、親から区切りキーを削除する

マージが親に伝播すると、最悪の場合ルートまで到達し、木の高さが1段減ります。

クラスタードインデックスと非クラスタードインデックス

クラスタードインデックス

クラスタードインデックスでは、テーブルの行データ自体がB+木のリーフノードに格納されます。インデックスの順序が、そのまま行の格納順序になります。

MySQLのInnoDBはこの方式です。主キー（Primary Key）がクラスタードインデックスになり、テーブル全体がこのB+木として格納されます。

-- InnoDBでは、この主キーがクラスタードインデックスになる
CREATE TABLE users (
  id INT PRIMARY KEY,      -- B+木のキー
  name VARCHAR(100),        -- リーフノードに格納されるデータ
  email VARCHAR(200),       -- 同上
  KEY idx_email (email)     -- セカンダリインデックス
);

セカンダリインデックス（主キー以外のインデックス）のリーフには、主キーの値が入っています。そのため、セカンダリインデックスでの検索は2段階になります。

1. セカンダリインデックスのB+木で主キー値を取得
2. クラスタードインデックス（主キーのB+木）で実際の行データを取得

非クラスタードインデックス

PostgreSQLでは、テーブルの行をヒープ（行を順不同に並べたページの列）に格納します。デフォルトのB-treeインデックスはB+木に近い構造で、リーフのエントリーがヒープ内の行ポインター（TID: タプルID）を持ちます。

PostgreSQLのインデックス構造:
  B+木のリーフ: [key → TID (block_number, offset)]
  ヒープページ:  [行データがページ内に格納]

この方式では、ヒープの行を読みに行くたびに、ランダムI/Oが発生し得ます。そのため、インデックスだけで応答するIndex-Only Scanを使えるかどうかが性能に大きく影響します。

ディスクI/Oとページ構造

なぜノードサイズ = ページサイズなのか

ディスクI/Oの最小単位はページ（ブロック）です。B+木のノードサイズをページサイズ（通常4KB〜16KB）に合わせると、1回のI/Oで1ノード分のキーをすべて読み込め、読み込んだデータに無駄が出ません。

ページサイズ = 16KB, キーサイズ = 8B, ポインタサイズ = 8B の場合:
  1ノードに格納できるキー数 ≈ 16384 / (8 + 8) ≈ 1000
  → 分岐数（fan-out）≈ 1000
 
高さ3のB+木が格納できるキー数:
  1000 × 1000 × 1000 = 10億
  → 10億行のテーブルでもわずか3回のディスクアクセスで検索可能

バッファープール

データベースは、頻繁にアクセスするページをメモリー上のバッファープールにキャッシュします。ルートノードや上位の内部ノードはほぼ常にキャッシュにあるので、ディスクアクセスはリーフまでの1〜2回で済むことが多くなります。

LSM-Tree — 書込最適化のアプローチ

B+木の書込コスト問題

B+木は読取りに優れますが、書込みのコストが大きくなります。1つのキーを挿入するだけでも、ディスク上のランダムな位置にあるページを読み取り、変更して書き戻す（Read-Modify-Write：1回の読取りと1回の書込み）必要があります。分割が起きれば、複数のページを更新します。その結果、論理的な変更量に比べて実際に書き込む量が大きくなります。これを書込増幅（Write Amplification）と呼びます。

LSM-Treeの設計思想

LSM-Tree（Log-Structured Merge-Tree）は1996年にPatrick O'Neilらが提案したデータ構造です。すべての書込みをシーケンシャル書込みに変換することで、書込みスループットを高めます。

書込パス

1. WAL（Write-Ahead Log）に書込みを追記する（クラッシュ時の復旧用）
2. Memtable（メモリー上のソート済み構造、通常はスキップリストや赤黒木）にキーを挿入する
3. Memtableが一定サイズに達したら、ディスクにフラッシュしてSSTable（Sorted String Table）として書き出す。SSTableはソート済みのキーバリューペアを格納するファイルで、書き出した後は変更しない（イミュータブル）

読取パス

読取りでは、新しいデータから順に複数のレベルを探します。

Read(key):
  // 1. まずMemtableを検索（最新データ）
  result = memtable.get(key)
  if result != null: return result
  
  // 2. L0のSSTableを新しい順に検索
  for sstable in L0_tables (newest first):
    result = sstable.get(key)  // Bloom filter + binary search
    if result != null: return result
  
  // 3. L1以降を順に検索
  for level in [L1, L2, ...]:
    result = level.get(key)    // 各レベルはソート済みなので二分探索
    if result != null: return result
  
  return NOT_FOUND

各SSTableにはブルームフィルターがあり、キーがそのファイルに存在しないことを、データを読まずに判定できます。存在すると誤って判定する確率（偽陽性率）は、通常1%以下に設定します。

コンパクション

SSTableが増えると、1回の読取りで調べるファイルも増えて性能が落ちます。そこで定期的にコンパクション（compaction）を実行し、SSTableをマージします。

Compaction(level_n, level_n1):
  // level_n のSSTableとlevel_n+1の重複範囲をマージ
  for sstable in level_n.tables:
    overlapping = find_overlapping(level_n1, sstable.key_range)
    merged = merge_sort(sstable, overlapping)
    // 新しいSSTableとしてlevel_n+1に書き出す
    write_new_sstables(level_n1, merged)
    // 古いSSTableを削除
    delete(sstable, overlapping)

代表的なコンパクション戦略は次の2つです。

LSM-TreeとB+木の書込増幅

LSM-Treeでは、コンパクションが書込増幅の原因になります。Leveledコンパクションでは、データを下のレベルへ移すたびに、範囲が重なる下のレベルの既存データもまとめて書き直します。下のレベルは上のレベルの $T$ 倍（サイズ比）の大きさがあるので、書き直す量は移すデータのおよそ $T$ 倍です。これがレベルごとに繰り返されるので、書込増幅はレベル数 $L$ とサイズ比 $T$ に応じて増え、最悪ケースの目安として $O(L \times T)$ と表されます。サイズ比10、4レベルなら、最悪の場合は数十回規模の書き直しになります。

B+木の書込増幅は、小さな論理変更でもページ単位で更新することから生じます。100Bだけの変更でも、16KBのページ全体を書き戻すことがあります。ただし実際の増幅率は、WALの形式、ページの書き出し方、グループコミット、バッファープールでのバッチ化に左右され、ワークロードによって変わります。

B+木 vs LSM-Tree — いつどちらを使うか

次の表の「高速」「遅い」などは、同じ操作をB+木とLSM-Treeで比べたときの相対的な評価です。

選択の指針

• 読取りが多い・範囲検索が多い → B+木 / B-tree系インデックス（MySQL/InnoDB、PostgreSQLのデフォルトのB-tree）
• 書込みが多い・ログやイベントデータ → LSM-Tree（RocksDB、Cassandra）
• 混在ワークロード → チューニングやハイブリッド構成を検討

実際のデータベースでの採用状況

MySQL（InnoDB）

InnoDBでは主キーのB+木がテーブルそのものなので、セカンダリインデックスで行を探すと、取得した主キー値でクラスタードインデックスを引き直します。EXPLAINの出力では次のようになります。

-- EXPLAIN で実行計画を確認
EXPLAIN SELECT * FROM users WHERE email = 'test@example.com';
-- type: ref, key: idx_email → セカンダリインデックスを使用
-- SELECT * は idx_email だけではカバーできないため、InnoDB は主キーでクラスタードレコードを引き直す

PostgreSQL

PostgreSQLはヒープテーブルとB-treeインデックスの構成です。HOT（Heap-Only Tuples）最適化により、インデックス対象のカラムが変わらず、新しいタプルバージョンが同じヒープページに収まる更新では、インデックスを更新せずに済みます。

デフォルトのB-tree以外に、GiST（Generalized Search Tree）、GIN（Generalized Inverted Index）、BRIN（Block Range Index）などのインデックスタイプもあります。

RocksDB

RocksDBは、Meta（Facebook）が開発したLSM-Treeベースのストレージエンジンです。LevelDBからフォークし、本番環境向けの最適化を加えています。

• Leveledコンパクションがデフォルト
• Column Familiesで論理的にデータを分離
• ブルームフィルターで読取パスを最適化

TiKV（TiDB）やMyRocksなどが、内部のストレージエンジンとしてRocksDBを使っています。CockroachDBも以前はRocksDBを使っていましたが、現在はRocksDBを参考にGoで実装したPebbleに移行しています。

SQLite

SQLiteは内部で2種類のB木を使います。テーブルの格納に使うテーブルB木は、データをリーフノードにだけ格納するB+木に近い構造です。インデックスに使うインデックスB木は、内部ノードにもキーを持つ、従来のB木に近い構造です。WITHOUT ROWIDテーブルは行をインデックスB木に格納し、主キーをクラスタードインデックスとして使います。

発展的なトピック

書込最適化B木（Bε-Tree）

B+木とLSM-Treeの中間に位置する構造として、Bε-Tree（B-epsilon Tree）があります。各内部ノードにバッファーを持ち、書込みをまとめて下位へ送ることで、読取り性能を保ちながらB+木より書込みを速くします。TokuDB（かつてPercona Server for MySQLで提供されていたが、現在は削除済み）で使われていました。

Learned Index

2018年にTim Kraskaらが提案したLearned Indexは、B+木の内部ノードが担う経路選択を、機械学習モデル（線形回帰やニューラルネットワーク）で置き換える手法です。データの分布を予測しやすい場合は、B+木より高速で、メモリー使用量も少ないインデックスを実現できる可能性があります。ただし実用化にはまだ課題が多く、主に研究段階にあります。

ALEX（Adaptive Learned Index）

ALEXは、動的な挿入・削除に対応し、データ分布の変化に合わせてモデルを更新することで、Learned Indexを実用に近づけたデータ構造です。

まとめ

B+木もLSM-Treeも、ディスクI/Oの特性に合わせて設計されたデータ構造です。

• B+木は、大きな分岐数でランダムリードの回数を減らし、リーフの連結リストで範囲検索を速くする。読取り中心のOLTPワークロードに向いている
• LSM-Treeは、すべての書込みをシーケンシャルI/Oに変換し、書込みスループットを高める。ログや時系列データの蓄積に向いている
• 読取りと書込みのどちらが多いか、範囲検索をどれだけ使うかによって、適した構造が変わる

次にEXPLAINで実行計画を見るとき、その裏側でB+木がどのように検索パスを決定しているか、想像できるようになっていれば幸いです。