IT 技書の森

B-Tree

データベースインデックスの基盤となる自己平衡型の多分岐探索木

データ構造データベース

B-Tree とは

B-Tree は、Rudolf Bayer と Edward McCreight が 1970 年に発表した自己平衡型の多分岐探索木で、RDS (PostgreSQL, MySQL) のインデックスの基盤技術である。ディスク I/O を最小化するために設計されており、検索・挿入・削除が O(log n) で行える。

二分探索木との違い

観点 二分探索木 B-Tree
子ノード数 最大 2 数百〜数千
木の高さ 高い (log₂ n) 低い (log_m n)
ディスク I/O 多い 少ない (1 ノード = 1 ページ)
用途 メモリ内 ディスクベースの DB

構造

         [10 | 20 | 30]           ← ルートノード (3 つのキー)
        /    |     |    \
   [1,5]  [12,15] [22,25] [35,40]  ← リーフノード
  • 各ノードが複数のキーを持つ (ディスクページサイズに合わせる)
  • 全てのリーフが同じ深さ (自己平衡)
  • ノード内のキーはソート済み

B+Tree (データベースで実際に使われる)

B-Tree の変種で、データはリーフノードにのみ格納し、リーフ同士がリンクリストで接続される。

内部ノード: [10 | 20 | 30]  ← キーのみ (データなし)
              ↓
リーフ:    [1,5] → [10,12,15] → [20,22,25] → [30,35,40]
           ↑ データはここにのみ格納、リーフ同士がリンク

範囲検索 (WHERE age BETWEEN 20 AND 30) がリーフのリンクを辿るだけで高速に行える。

LSM ツリーとの比較

観点 B-Tree LSM ツリー
読み取り 高速 (1 回のツリー走査) 中程度 (複数 SSTable)
書き込み 中程度 (ランダム I/O) 高速 (シーケンシャル I/O)
用途 RDS (PostgreSQL, MySQL) DynamoDB, Cassandra

インデックスの仕組み

CREATE INDEX idx_users_email ON users(email);

-- B+Tree インデックスが作成される
-- email でソートされたリーフノードが、テーブルの行へのポインタを持つ

SELECT * FROM users WHERE email = 'alice@example.com';
-- B+Tree を O(log n) で検索 → 行のポインタを取得 → テーブルから行を取得

計算量

操作 計算量
検索 O(log n)
挿入 O(log n)
削除 O(log n)
範囲検索 O(log n + k) (k = 結果数)

B-Tree の関連書籍も参考になる。

関連用語