B-Treeインデックスの仕組み

データベースのパフォーマンス向上において、インデックスは欠かせない技術です。中でもB-Treeインデックスは最も広く使われており、その効率性の秘密を理解することで、より良いデータベース設計が可能になります。

B-Treeインデックスとは

B-Treeは「Balanced Tree（平衡木）」の略で、データを階層的な木構造で管理するインデックス技術です。本の索引のように、大量のデータから目的の情報を素早く見つけるための「地図」として機能します。

例として、社員テーブルの年齢データ [22, 25, 26, 28, 29, 30, 31, 35] にB-Treeインデックスを作成すると、以下のような構造になります：

          [28]           ← ルートノード
         /    \
    [25]      [30]       ← 中間ノード
   /  \      /   \
[22] [26]  [29] [31,35]  ← リーフノード

驚異的な検索効率

B-Treeの真価は検索効率にあります。1000万件のデータがある場合：

• 線形検索: 平均500万回の比較
• B-Tree検索: 平均23回の比較

この劇的な差は、B-Treeが O(log n) の計算量で動作するためです。

等価検索の例

「年齢30歳」を検索する場合：

1. ルートノード[28]をチェック → 30 > 28なので右へ
2. 中間ノード[30]で発見 → 該当データを直接取得

わずか2ステップで目的のデータに到達できます。

範囲検索の威力

B-Treeのリーフノードは連結リストのように繋がっているため、範囲検索も高効率です。「年齢25-30歳」を検索する場合：

1. 開始点（25歳）をB-Tree検索で発見
2. リーフレベルで順次移動：[25] → [26] → [28] → [29] → [30]
3. 該当するすべてのデータを連続取得

B-Tree構築の秘密：ルートノードはこうして決まる

多くの人が「ルートノードは平均値？」と考えがちですが、実際は分割過程での中央値昇格によって決まります。

データを順次挿入する過程を見てみましょう（各ノードの最大容量を3個と仮定）：

ステップ1: [22, 25, 26] → まだ1ノードで収まる

ステップ2: 28を挿入 → [22, 25, 26, 28] → 容量オーバー！

分割発生:

      [26]        ← 中央値が昇格してルートに
     /    \
  [22,25] [28]    ← 左右に分割

この過程を繰り返すことで、最終的なB-Tree構造が決定されます。重要なのは、ルートノードの値はデータの平均値ではなく、分割時の中央値だということです。

バランスが生む安定性

B-Treeの「Balanced（平衡）」という名前は、すべてのリーフノードが同じ深さにあることを意味します。これにより：

• どのデータを検索しても、ほぼ同じステップ数で到達
• 挿入・削除操作でも構造が崩れない
• 安定したパフォーマンスを維持

実践での活用

-- よく検索される列にB-Treeインデックスを作成
CREATE INDEX idx_employee_age ON employees(age);

-- 範囲検索が高速化
SELECT * FROM employees WHERE age BETWEEN 25 AND 30;

-- ソート処理も最適化
SELECT * FROM employees ORDER BY age;

まとめ

B-Treeインデックスは、木構造の階層性と連結リストの連続性を併せ持つ優れた技術です。その効率性は数学的な計算量の削減だけでなく、実際のディスクI/O最適化にも寄与しています。

データベースの心臓部とも言えるB-Treeの仕組みを理解することで、より効果的なインデックス戦略を立てることができるでしょう。大量データを扱うシステムにおいて、B-Treeは今後も重要な役割を果たし続けるはずです。