【データベース】B-treeインデックスの基礎を理解する

# はじめに
今回は、データベースのパフォーマンスに最も関係するインデックスについて学んだことをまとめていきます。

## データベースのパフォーマンスを決める主な要因
- **ディスクI/Oの分散**（RAID）
- **インデックス**　⇦ **【この記事の対象箇所】**
- **統計情報**
- **SQLにおける結合**（正規化）

---

## インデックスとは？
> データベースにおけるインデックスとは、目的のレコードを効率よく取得するための「索引」のことです。テーブル内の特定の列を識別できる値（キー値）と、キー値によって特定された列のデータが格納されている位置を示すポインタで構成されています。インデックスを参照することで目的のデータが格納されている位置に直接アクセスすることができ、検索を高速化することができます。

https://products.sint.co.jp/siob/blog/index


### インデックスがパフォーマンス改善のため利用される理由
1. **アプリケーションに影響を与えない**（アプリケーション透過的）
2. **テーブルのデータに影響を与えない**（データ透過的）
3. 上記の2つを満たし、かつ、**性能改善の効果が大きい**

#### アプリケーション透過的とは？
インデックスを使用するかどうかは、DBMSが自動的に判断するため、アプリケーションに変更を加える必要がない。

#### データ透過的とは？
インデックスを作成しても、テーブルに格納されるデータには影響を与えず、テーブルの構造も変化しない。

#### 透過的（透過性）とは？
「存在を意識しなくてよい」という性質のこと。つまり、インデックスはアプリケーションやテーブルから見て存在を意識しなくても動作する。

---

### 様々なインデックス
- **B-treeインデックス**（最もよく使用される）
- ビットマップインデックス
- ハッシュインデックス
この記事では、B-treeインデックスに絞り、まとめていく。

ビットマップとハッシュについては下記の記事にまとめています。

https://qiita.com/rgj0830/items/5976d80b06beb04c0b9c

### B-treeの構造
- **木構造**でデータを保持。最下層のリーフノードが実データの場所を示すポインタを保持する
- データベースは、最上位のルートノードから順番に辿ってリーフノードにアクセスし、実データに到達する

### B-treeインデックスの特徴
- **均一性**: 各キー値の間で検索速度にばらつきが少ない
- **持続性**: データ量の増加に対してパフォーマンス低下が比較的緩やか
- **処理汎用性**: 検索、挿入、削除、更新処理のいずれの処理もそこそこ速い
- **非等値性対応**: 不等号（<, >, <=, >=）などを使った範囲検索もそこそこ速い
他のインデックスに比べて突出した点などはないが平均点が高いのが特徴
#### 1. 均一性
B-treeは**平衡木**（balanced tree）と呼ばれ、どのリーフノード（実データのポインタを持つノード）もルートノードからの距離が同じになる。このため、どんなキー値でも同じ速度で結果を得られる。
**注意点**
ただ、B-treeでは、長期間の運用で、削除、更新、挿入処理など繰り返されることで、インデックスの構造が崩れ、非平衡木になってしまうケースがある。自動で修復を行う機能が備わっているが、更新が重なれば、バランスが悪くなり、検索時間にばらつきが生まれる。

#### 2.範囲検索の高速化
B-treeは、キー値をソートして保持しているため、範囲検索でも検索範囲を絞ることが可能。
等号(=))だけでなく不等号(<、>、<=、>=)や BET WEEN などの範囲検索条件に対しても高速化ができる。

#### 3.効果が薄れるケース
B-treeインデックスは否定条件（`!=`、`<>` など）では効果がない。これらの条件は特定のノード以外すべてを対象にするため、絞り込み効果が失われ、フルスキャンになりやすいです。

#### 4.ソート処理の高速化
SQLで以下の処理を行った場合、DBMS 内でソートが行われる
- 集約関数(COUNT、SUM、AVG、MAX、MIN)
- ORDER BY 句
- 集合演算(UNION、INTERESCT、EXCEPT)
- OLAP 関数(RANK、ROW_NUMBER など)
DBMS内部ではソート専用のメモリ領域が割り当てられている。
ソート処理を行う時は、そのメモリ領域に一時的にデータを保持して行う。
大量のデータのソートが必要な場合、メモリに乗り切らずに溢れてしまうことがある。
その時、DBMSは一時的にディスクへデータを書き出す。
ディスクへの書き込みなどの I/O はとても時間がかかる、コストの高い処理なので、パフォーマンスが著しく低下する。SQL を記述する際は、極力、大きなソートを避けることがパフォーマンス上、望ましい。
B-treeインデックスはソートされた状態でキー値を保持するため、**ORDER BY句**などで同じ順序を指定すれば、ソート処理をスキップできる。これはパフォーマンスの大幅な改善に繋がる。


---

## B-treeインデックスの設計方針

### 1. 大規模なテーブルに対して作成
少数のレコードに対しては、インデックスを使うよりもフルスキャンの方が速いことが多いため、**大規模なテーブル**に対して作成することが推奨される。
少数のレコードの基準、閾値は、ストレージやサーバの性能など環境によって変わるが、目安としてレコード数が1万以下の場合、ほぼ効果がないと言われている。

### 2. カーディナリティの高い列に作成
**カーディナリティ**とは、特定の列の値の種類の多さを示す概念。
カーディナリティが高い列は、効率的な絞り込みが可能なので、インデックス作成に向いている。

- **例1**: 口座番号のような多数の異なる値を持つ列（カーディナリティが高い）
- **例2**: 性別のような少数の異なる値を持つ列(カーディナリティが低い)
#### カーディナリティの注意点
- 複合列に対してのインデックスを作成する場合は、その複合列の組み合わせてカーディナリティを考える。
- カーディナリティが高くても、特定の値にデータが集中している列には向いていない
  **例**:1~100 までの値をとる列で、全体の 90%が 8 と言う値をとる列

### 3. SQLのWHERE句や結合条件に使用される列に作成
インデックスは、SQLの検索条件や結合条件に指定される列に作成しないと意味を成さない


---
## B-treeインデックスの注意点

### インデックスが効かなくなるケースがある
- インデックス列に対して演算や関数が適用される場合
- 否定条件（`!=` や `<>`）を使用する場合
- **OR**句を使う場合（`IN`句に書き換えることで回避可能）
- 後方一致や中間一致の **LIKE**句
- 暗黙的な型変換が発生している場合

### 主キーや一意制約の列にはインデックス作成不要
主キーや一意制約を設定すると、DBMSが自動でB-treeインデックスを作成する(重複チェック等行う時に使用するため)ため、手動で作成する必要はない。検索条件に指定すると、その時に作成されたインデックスが使用される。

---

## インデックスのメンテナンス

長期間にわたってデータの更新が続くと、インデックスの構造が崩れることがある。このため、定期的にインデックスの再構築などのメンテナンスを行い、性能を維持することが重要。

## まとめ
今回はB-treeインデックスについて学んだことをまとめました。
恥ずかしながらインデックスが効かなくなるケースをあまり把握していなかったため、学びになりました。(否定条件とかORとか普通に使ってしまっていた)
何事もメリット、デメリットを知った上で選択できる力が大切だなとい改めて実感しました。
引き続き基礎を固めていきたいです。

## 参考書籍

https://www.shoeisha.co.jp/book/detail/9784798186627