【SQL】B-Treeインデックス・複合インデックス・カーディナリティのおさらい

### はじめに

SQLパフォーマンスを左右する大きな要素として「インデックスの貼り方と使い方」があります。
しかし、「インデックスを貼れば速くなる」と思ってむやみに貼ってしまうと、逆にパフォーマンスを落とすことも…。
本記事では以下の3つのキーワードを軸に、インデックスについて整理します。
1. B-Treeインデックス
2. 複合インデックス
3. カーディナリティ

それぞれの概念を理解し、上手に活用することで効率的なデータ検索と、不要なインデックスによる性能低下を防ぎましょう。

### 1. B-Treeインデックスとは

#### 1.1 B-Treeの構造
- B-Tree（Balanced Tree, もしくはB+Treeなど）とは、データを木構造（ツリー構造）で管理するアルゴリズムの一つです。
- 木の高さができるだけ均一になるようにバランスを保つことで、データの検索・挿入・削除を**対数時間（O(log n))**に近いスピードで行うことができます。

(実際のRDBMS実装はB+Treeなどの派生形が多いですが、本質的には似た構造です)

#### 1.2 B-Treeインデックスのメリット
1. 大抵のRDBMSのデフォルト
   - Oracle, MySQL(InnoDB), PostgreSQL, SQL Serverなど、多くの主要RDBMSで標準的に利用されるインデックス構造がB-Treeです。
2. 範囲検索に強い
   - 連続した値を扱う場合（例: 日付、数値）でも、高速に範囲検索が可能。
3. 等価検索にも強い
   - =演算子（またはIN演算子）にも効果が高いです。

#### 1.3 B-Treeインデックスが有効なパターン
- 主キーやユニークキー: 独自性を保証し、高速検索が必要な場合。
- 範囲検索: BETWEEN, >=, <= などをよく使うカラム。
- ソートやGROUP BY: インデックスが並び順を保証してくれるため、クエリによってはソート不要で高速化できる。

### 2. 複合インデックス（コンポジットインデックス）

#### 2.1 複合インデックスとは
- 2つ以上のカラムを組み合わせて、1つのインデックスキーとして管理するインデックス。
- 例: (first_name, last_name), (prefecture, city, address), (order_date, customer_id)など。

#### 2.2 メリット
1. 複数カラムの組み合わせで検索するケースが多い場合に有効
   - 例えば「姓＋名」で検索することが多いとか、「都道府県＋市区町村」で住所検索するような場面で威力を発揮します。
2. WHERE句の順序によっては単体カラムインデックスを複数使うよりも高速
   - DBのオプティマイザが、複合インデックスを使って一気に絞り込んだほうが早いと判断してくれるケースが多い。

#### 2.3 注意点：「左端一致」の原則（B-Treeの場合）
- B-Treeの複合インデックスは先頭のカラムから順に検索条件に含まれているときに効果を発揮します。
- 例: (colA, colB, colC)という複合インデックスがある場合、
  - WHERE colA = X はインデックス利用OK（先頭カラムだけでも可）。
  - WHERE colA = X AND colB = Y もインデックス利用OK。
  - WHERE colB = Y だけだと、先頭のcolAを飛ばしているのでインデックスが効かないケースが多い（DB次第で部分的に使うこともありますが、基本的には左端要素が重要）。

#### 2.4 作りすぎには要注意
- 複合インデックスを複数の組み合わせパターンで乱立させると、更新系の負荷が増大します。
- データ挿入/更新/削除のたびに複数インデックスをすべてメンテナンスしなければならないため。
- 複合インデックスを作るときは「どの順番でWHERE句に書かれるか」をよく考慮し、必要最小限に留めるのがポイントです。

### 3. カーディナリティ（Cardinality）とは

#### 3.1 カーディナリティの定義
- カーディナリティとは、カラムやテーブルにおける異なる値（ユニークな値）の数を指します。
- 「選択度（selectivity）」という用語で呼ばれることもあります。
- カーディナリティが高い = 重複する値が少ない (ほとんどユニーク)
- カーディナリティが低い = 同じ値がたくさんある (重複が多い)

#### 3.2 なぜカーディナリティが重要か
- RDBMSのオプティマイザは、**「ある条件でどれくらいの行数が返ってくるか」**を予測して実行計画を立てます。
- インデックスが効果を発揮するかどうかは、絞り込みの効き具合に左右されるので、カーディナリティが高いカラムほどインデックス利用のメリットが大きいと言えます。
- 例: gender (男性 / 女性) のように2,3パターンしかないカラムはカーディナリティが低く、インデックスを貼ってもほとんど絞り込みできない → フルスキャンが早い場合が多い。
- email(全て固有)のように重複がほとんどないカラムはカーディナリティが高く、WHERE email = '...'のときにインデックスが非常に有効。

#### 3.3 カーディナリティと統計情報
- 多くのRDBMSではカラムごとの統計情報（distinct数や分布など）を保持しており、オプティマイザがこれを参照して実行計画を決めます。
- カーディナリティが古いままだと、誤った実行計画を選んでしまうことがあるため、定期的にANALYZE(PostgreSQLやMySQLならANALYZEコマンド、OracleならDBMS_STATS.GATHER_*_STATSなど)が重要です。

### 4. まとめと運用上のポイント

#### 4.1 B-Treeインデックスの基本
- 等価検索・範囲検索が得意
- ほぼ全てのRDBMSで標準的に使われるインデックス構造

#### 4.2 複合インデックスの活用
- 複数カラムを同時に検索する場面で有効
- 左端カラムから検索条件に含まれているかが重要
- 作りすぎると更新コストが上がるので要注意

#### 4.3 カーディナリティの意識
- 重複が少ない（＝カーディナリティが高い）カラムはインデックス効果が高い
- カーディナリティが低いカラムにインデックスを貼っても、絞り込み効果が低くてフルスキャンになる可能性大
- 統計情報を定期的に更新し、オプティマイザが正確なカーディナリティを把握できるようにする



### 5. おまけ: インデックスの作成時にチェックしたいこと
2. クエリパターン（WHERE句）を洗い出しているか？
   - 複合インデックスを作るなら、どのカラム順が最もよく使われるかを把握する
3. カーディナリティは十分高いか？
   - データ分布を確認して、重複率が高すぎないかチェック
4. 実行計画(EXPLAIN)でインデックスが使われているか？
   - 作ったはいいが結局使われていないなら意味がない
5. 統計情報のメンテナンスはできているか？
   - 定期的にANALYZEやDBMS_STATSなどで統計を更新

### 終わりに

B-Treeインデックスは最もベーシックかつ汎用的ですが、貼りどころを誤るとパフォーマンスが向上しないどころか更新系の足を引っ張る原因になります。
また、複合インデックスは便利な一方で、左端カラムや順番の考慮が欠かせません。
そして、カーディナリティは**「どのくらい検索条件で絞り込めるか」**を知るための重要な指標です。
適切にインデックスを設計し、定期的な統計情報更新を行うことで、SQLのパフォーマンスを最適化しましょう。

以上、「B-Treeインデックス」「複合インデックス」「カーディナリティ」についてのまとめでした。質問や補足があればぜひコメントでお寄せください！