【Railsのインデックス入門】B+treeの仕組み・複合インデックス・t.referencesの落とし穴

はじめに

久しぶりにRailsでの開発を行なっており、マイグレーションファイルを作成する際にインデックスを貼ったのだが、インデックスについて正確に理解してなかったのでこれを機にまとめておく。

データベースのインデックスは、目次のようなもので、良い感じにデータをソートしてくれてるんだろうな。くらいにしか思っていなかったのだが、実際にはインデックスは単にデータを並べ替えるだけではなく、二分探索を応用したバランス木（B-treeやB+tree） を利用して効率的な検索を可能にしている。

本記事では、インデックスの仕組みを詳しく解説するとともに、Railsにおけるインデックスの貼り方や、データベース内部でどのように動作するのかについても記載。

インデックスとは？

データベースのインデックスは、検索の高速化を目的としたデータ構造。一般的に B-tree（B+tree） を採用し、二分探索を拡張したバランス木の形でデータを管理する。これにより、データ検索が高速化される一方で、インデックスの更新コストが発生する。

二分探索とは？（計算量O(log n)）

二分探索は、整列されたデータから特定の値を効率的に見つけるアルゴリズムであり、計算量は O(log n) 。

例: 二分探索のイメージ

例えば、1から100までの数字が並んでいるとき、50を探す場合を考える。

1. まず中央の50を見る → 見つかったので終了！（1回の比較）
2. もし検索値が30なら、中央の50と比較して「左側」にあると判断し、1〜49の範囲で再び中央の25を見る。
3. これを繰り返すことで、毎回探索範囲を半分に減らすことができる。

100個のデータに対して最大で約 log2(100) ≈ 7回 の比較で検索が完了する。

ただ、二分探索では各ノードに1つだけのデータを持つので、対象データが多くなるとそれだけ木の高さが高くなり検索が非効率になってしまう。この課題を解決するためにB木（Balanced木＝平衡木）というデータ構造が1970年に発表された。

B-treeの「B」はBalanced（バランスの取れた）を意味し、ツリーの高さを均等に保つ（バランスする）ことで検索の効率を向上させるという特性を表している。そしてB木の中に、B-木とB+木の2種類があり、B+木はB-木をさらに改良したものになっている。

B-treeとB+treeの違いと特徴

B-treeの具体例

B-treeはノードごとに複数のキーを持ち、それぞれのキーの間に子ノードを持つ。B-treeには 内部ノード（検索用のキーとデータを持つ）と リーフノード（実際のデータを持つ）がある。

        [40, 70]   ← 内部ノード（検索用のキーとデータ）
       /    |    \
 [10, 30] [50, 60] [80, 90]  ← 内部ノード（検索用のキーとデータ）
    |       |       |
 [10 20 30] [50 55 60] [80 85 90]  ← リーフノード（実データを保持）

例えば 55 を探す場合:

1. ルートノードの [40, 70] を確認 → 55は40と70の間なので、中央の子ノード [50, 60] に進む。
2. [50, 60] のノードを確認 → 55がリーフノード [50, 55, 60] にあるので、見つかる！

✅ B-treeの特徴:

• 内部ノードもデータを持つ → 検索時に途中のノードでヒットすれば、リーフノードまで降りずに済むため、等価検索が高速。
• 範囲検索にはあまり向かない → リーフノードが連結していないため、範囲検索時に複数のパスをたどる必要がある。

B+treeの具体例

B+treeでは、すべてのデータがリーフノードに格納され、内部ノードには検索用のキーのみを持つ。

        [40, 70]   ← 内部ノード（検索用のキーのみ）
       /    |   　　 \
 [10, 30] [50, 60] 　　　[80, 90]  ← 内部ノード（キーのみ）
    |       |      　　　 |
 [10 20 30] [50 55 60] [80 85 90]  ← リーフノード（実データを保持）

✅ B+treeの利点:

• 範囲検索が高速: 例えば、50〜90のデータを取得する場合、B+treeではリーフノード同士がポインタで連結しているため、50を見つけたら隣へ進むだけで範囲検索が可能。通常のツリー構造では、データを探すたびにルートノードから検索を開始する必要があるが、B+treeではリーフノード同士が直接つながっているため、一度検索したらそのまま次のリーフノードへ移動することができる。リーフノード（[10 20] → [30 40] → [50 55 60] → [70 80 85 90]）がポインタでつながっている のがポイント
• 内部ノードにはデータを格納しない: 内部ノードにはデータを持たずキーのみを格納するため、1つのノードにより多くのキーを収納できる（=Orderが高い）ため、Treeの階層（=ツリーの高さ）が少なくなり計算量が減る
• ディスクI/Oの最適化: B+treeでは、すべてのデータがリーフノードにまとまっているため、ページのキャッシュ効率が向上する。

Railsで使われるデータベースとB-tree

Railsでよく使われるデータベース（PostgreSQL, MySQL, SQLite）では、デフォルトのインデックスとして B+tree が採用されている。

Railsでのインデックスの作成

単一インデックスの作成

Railsでは、マイグレーションファイルで add_index メソッドを使用することで、特定のカラムにインデックスを作成できる。

def change
  add_index :users, :email, unique: true
end

この場合、users テーブルの email カラムに対して 一意制約付きのインデックス が作成される。

複合インデックスの作成と優先順位

複合インデックスを作成すると、単一カラムのインデックスもカバーされる ため、無駄なインデックスを増やさずに済む。

def change
  add_index :orders, [:user_id, :created_at]
end

このインデックスを作成すると、

• WHERE user_id = ? のような検索はこのインデックスを利用可能。
• WHERE user_id = ? AND created_at = ? のような複合条件でも高速検索が可能。
• ただし、created_at単体での検索（WHERE created_at = ?）には利用できない。

複合インデックスの優先順位

• 左側のカラムから優先して検索が行われる。
• できるだけデータを絞り込めるカラムを最初に記述するのが理想。
• 例えば add_index :orders, [:status, :created_at] の場合、status で絞り込んでから created_at の順に検索される。
• 逆に created_at での検索が主な用途であるなら、順番を逆にする方が良い場合がある。

t.references で自動的にインデックスが作成される

Railsのマイグレーションで t.references を使用すると、自動的にインデックスが作成される。

t.references :user, foreign_key: true  # user_id に自動でインデックスが作成される

このとき、意図せず不要なインデックスが作成されることがあるため、不要な場合は index: false を明示的に指定する必要がある。

t.references :user, foreign_key: true, index: false

複合インデックスを作成したのに、t.references により単一インデックスも作成される問題

例えば、以下のマイグレーションを実行すると

def change
　　t.references :user, foreign_key: true
　　add_index :orders, [:user_id, :created_at]
end

この結果、schema.rb には以下のように自動的に意図しない単一インデックスが追加されてしまう。

create_table "orders", force: :cascade do |t|
  t.bigint "user_id"
  t.index ["user_id"], name: "index_orders_on_user_id"
  t.index ["user_id", "created_at"], name: "index_orders_on_user_id_and_created_at"
end

複合インデックスを貼る場合、t.references で 不要な単一インデックスが作成されないように index: false を指定する。

def change
  t.references :user, foreign_key: true, index: false
  add_index :orders, [:user_id, :created_at]
end

最初これに気づかずに、PRレビューで単一インデックスも貼られていることを指摘され、インデックス貼ってないはずなのになんでだろう？となった。

まとめ

• インデックスは検索速度向上に有効だが、更新コストも考慮する必要がある。
• 複合インデックスを作成すると、最初のカラムを使う単一検索もカバーされるが、2つ目のカラム単独では利用できない。
• 複合インデックスのカラムの順番は重要で、最も絞り込めるカラムを最初に指定するのが望ましい。
• t.references で意図しないインデックスが作成されることがあるため、t.referencesを使う場合はindex: false の指定を忘れない。t.referencesでマイグレーションファイルを作成せずに、add_indexで複合インデックスも含めてインデックスを一元管理するのもあり。