以前にB-treeインデックスを調べていたが、どんな概念なのかまでは掘り下げでなく、分かった気のまま分かってなかったのでまた調べた
基本概念
B-tree は1972年に Rudolf Bayer と Edward McCreight によって発明された 自己平衡木構造
「B」の由来は諸説あり、Balanced、Bayer、Boeing（開発された場所）などが挙げられるが、公式な説明はない
特徴
| 特性 | 説明 |
|---|---|
| 自己平衡 | 挿入・削除時に自動的にバランスを維持 |
| 多分岐 | 二分木と異なり、1ノードが複数の子を持つ |
| ディスク最適化 | ディスクI/Oを最小化する設計 |
| 計算量 | 検索・挿入・削除すべて O(log n) |
B-tree の構造
基本構成
[Root Node]
[ 30 | 70 | 90 ]
/ | \ \
/ | \ \
[10|20] [40|50|60] [75|80] [95|100]
↓ ↓ ↓ ↓
[Data] [Data] [Data] [Data]
構成要素
| 要素 | 説明 |
|---|---|
| ルートノード | 木の最上位。検索の起点 |
| 内部ノード（ブランチ） | キーと子ノードへのポインタを格納 |
| リーフノード | 実際のデータまたはデータへのポインタを格納 |
| キー | ソートされた値。検索・比較に使用 |
B-tree の規則
次数 m の B-tree は以下の規則に従う：
- すべてのリーフノードは同じ深さ（高さが均一）
- ルート以外の各ノードは最低
⌈m/2⌉個の子を持つ - 各ノードは最大
m個の子を持つ - ノード内のキーは常にソートされている
検索の仕組み
検索アルゴリズム
email = 'user@example.com' を検索する場合：
1. ルートノードから開始 2. ノード内のキーと比較 - 一致 → 発見 - 小さい → 左の子ノードへ - 大きい → 右の子ノードへ 3. リーフノードに到達するまで繰り返し
具体例：値 45 を検索
Step 1: ルート [30 | 70 | 90]
→ 45 は 30 < 45 < 70 なので2番目の子へ
Step 2: 内部ノード [40 | 50 | 60]
→ 45 は 40 < 45 < 50 なので2番目の子へ
Step 3: リーフノード到達、データ取得
わずか3回のノードアクセスで目的のデータに到達
なぜ B-tree はディスクに最適なのか
ディスクI/Oのコスト
| 操作 | 速度 |
|---|---|
| メモリアクセス | ~100 ナノ秒 |
| SSD ランダムリード | ~100 マイクロ秒（1,000倍遅い） |
| HDD ランダムリード | ~10 ミリ秒（100,000倍遅い） |
ディスクアクセスは圧倒的に遅い
最小化することで性能を向上させる
B-tree の最適化ポイント
ノードサイズ = ディスクページサイズ
- 一般的に 4KB〜16KB
- 1回のI/Oで多くのキーを読み込める
高いファンアウト（分岐数）
- 1ノードに数百〜数千のキーを格納可能
- 木の高さを低く保てる
低い木の高さ
- 100万件でも高さは3〜4程度
- I/O回数 = 木の高さ
計算例
ノードサイズ 16KB、キーサイズ 8バイト、ポインタ 8バイトの場合：
1ノードあたりのキー数 ≈ 16KB / 16バイト ≈ 1,000個 高さ2: 1,000 × 1,000 = 100万件 高さ3: 1,000 × 1,000 × 1,000 = 10億件
10億件のデータでも 最大3回のディスクアクセス で検索可能
B-tree と B+tree の違い
この２つあるの知らなかった
実際のデータベースでは B-tree の変種である B+tree がよく使われるらしい
構造の違い
| 特性 | B-tree | B+tree |
|---|---|---|
| データ格納場所 | 全ノード | リーフノードのみ |
| リーフの連結 | なし | リンクリストで連結 |
| 内部ノード | キー + データ | キーのみ |
B+tree の構造
[Root Node]
[ 30 | 70 | 90 ]
/ | \ \
/ | \ \
[10|20] [40|50|60] [75|80] [95|100]
↓ ↓ ↓ ↓
[Data] ←→ [Data] ←→ [Data] ←→[Data]
リンクリストで連結
B+tree のメリット
内部ノードにデータがない
- より多くのキーを格納可能
- 木の高さがさらに低くなる
リーフノードの連結
- 範囲検索が高速
WHERE age BETWEEN 20 AND 30などで威力を発揮
シーケンシャルアクセス
- ORDER BY が効率的
- フルスキャンもリーフを順番に辿るだけ
インデックスの種類と B-tree
RDBMSでの使用例
| RDBMS | デフォルトインデックス | 備考 |
|---|---|---|
| MySQL (InnoDB) | B+tree | クラスタインデックスを採用 |
| PostgreSQL | B-tree | GiST、GIN など他も選択可能 |
| SQLite | B-tree | テーブル自体も B-tree で格納 |
| Oracle | B-tree | B*tree（変種）を使用 |
クラスタインデックス vs セカンダリインデックス
クラスタインデックス（主キー）
B+tree のリーフノード = 実際の行データ
セカンダリインデックス（その他のインデックス）
B+tree のリーフノード = 主キーへの参照 → 主キーのB+treeを再度検索（二重検索）
B-tree が得意なクエリ
完全一致検索
SELECT * FROM users WHERE id = 12345; -- O(log n) で高速
範囲検索
SELECT * FROM orders WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'; -- リーフノードの連結リストを活用
プレフィックス検索
SELECT * FROM products WHERE name LIKE 'iPhone%'; -- 前方一致は B-tree で対応可能
ソート
SELECT * FROM users ORDER BY created_at DESC LIMIT 10; -- インデックス順 = ソート順なので追加のソート不要
B-tree が苦手なクエリ
後方一致・中間一致
SELECT * FROM users WHERE email LIKE '%@gmail.com'; -- フルスキャンが必要 -- 対策: 全文検索インデックス、または逆順カラムを追加
否定条件
SELECT * FROM users WHERE status != 'deleted'; -- インデックスが効きにくい
関数・演算を含む条件
SELECT * FROM users WHERE YEAR(created_at) = 2024; -- インデックスが使われない -- 対策: WHERE created_at >= '2024-01-01' AND created_at < '2025-01-01'
カーディナリティが低いカラム
SELECT * FROM users WHERE gender = 'male'; -- 値の種類が少ない（true/false、性別など）カラムは効果が薄い
インデックス設計のベストプラクティス
1. 複合インデックスの順序
-- クエリ SELECT * FROM orders WHERE user_id = 123 AND status = 'shipped' ORDER BY created_at DESC; -- 効果的なインデックス CREATE INDEX idx_orders ON orders(user_id, status, created_at);
原則: 等価条件 → 範囲条件 → ソートの順
2. カバリングインデックス
-- クエリ SELECT id, name FROM users WHERE email = 'user@example.com'; -- インデックスだけで完結（テーブルアクセス不要） CREATE INDEX idx_users_email ON users(email, id, name);
3. インデックスの過剰作成を避ける
- INSERT/UPDATE/DELETE のたびにインデックスも更新
- インデックスが多いとストレージ消費も増加
- 本当に必要なインデックスを見極める
実行計画で確認の仕方
PostgreSQL
EXPLAIN ANALYZE SELECT * FROM users WHERE email = 'user@example.com';
Index Scan using idx_users_email on users (cost=0.42..8.44 rows=1 width=...) Index Cond: (email = 'user@example.com'::text) Actual time: 0.025..0.026 rows=1 loops=1
