インデックスってなんだ？？？

わからないことがあり調べるたびに「理解せずに使ったことが恥ずかしい...」の気持ちになる微経験おじさんです。
データベースで使用するインデックスについて、理解を深めるためにまとめました。

# インデックスとは
## 基本的な概念
データを素早く検索するための補助的なデータ構造。本の索引に似た仕組みを持っている。
本の索引ではキーワードと対応するページ番号が記載されており、特定の内容を探すページを1枚ずつめくる必要がない。
同様にデータベースのインデックスもデータの値とその格納場所を対応して記録している。

データベースにおける実際のデータは新しいレコードが追加される順番に保存されていく。
インデックスがない場合、特定のデータを探すとき、すべてのレコードを順番に確認しなければならない。
これを**フルテーブルスキャン**という

インデックスには検索対象となるカラムの値と、そのデータが実際に格納されている場所を示すポインタが含まれている
データベースはこのポインタを使って必要なデータに直接アクセスすることができる

インデックスは常に整列された状態で保持される。これにより効率的にデータの検索が行えるようになる。
新しいデータが追加されたり、既存のデータが更新されたりした場合、インデックスも自動で追加、更新され、正しい順番が維持される。

※インデックスはデータベース内に追加のデータ構造として保存さえれるため、ディスク容量を消費する。
※データの更新のたびにインデックスも更新されるので、更新にかかる時間は増加する

### インデックスの種類の概要
用途や特性に応じて数種類のインデックスが存在する
- 主インデックス
テーブルの主キーに対して自動的に作成されるインデックスで、主キーはテーブルないでレコードを一意に識別するために使用される値であるため、主インデックスは高速な検索を実現するうえで重要な役割を果たす
- 副インデックス
主キー以外のカラムに作成されるインデックス。例えばUserテーブルで名前や電話番号による検索を高速化したい場合、これらのカラムに副インデックスを作成することができる。
- 複合インデックス
複数のカラムを組み合わせて作成される。例えば姓と名の両方を使って検索することが多い場合、姓と名両方のカラムを含む複合インデックスを作成することがでより効率的な検索が可能になる

### インデックスを使用する目的
データベースの検索性能の向上。データベースに格納されているデータ量が増加するにつれて、効率的なデータアクセスは重要性を増してくる
- 検索速度向上
データベースは全てのレコードを確認する必要がなくなり、必要なデータを素早く取得できる
  - 特定の部署に所属する従業員を検索する場合、部署カラムにインデックスがあれば、特定の部署カラムを持っている従業員を取得することができる
- 一意性の保証
主キーに対するインデックスはデータの重複を防ぎ、一意性を保証する役割も果たしている
  - 従業員IDが重複して登録されることを防ぐために、従業員IDカラムに対してインデックスを作成することができる
- 整列順序の管理
データを物理的に並び替えることなく、論理的な順序を維持することができる。データの並び替えに伴う処理コストを削減できる。
- 結合操作の効率化
テーブル間の結合を行い際に、インデックスが存在することで、結合操作の性能が大幅に向上する。
  - 注文テーブルと顧客テーブルを顧客IDで結合する場合、顧客IDにインデックスが作成されていれば、結合処理を効率的に行うことができる

## インデックスの内部構造
### B-tree
[【図解】B-Treeインデックスを理解しよう](https://qiita.com/shibainuu/items/25d4d9c37d8e7ba04afa)
多くのデータベースにおいて、インデックスはB-treeと呼ばれるデータ構造を使用している。B-treeは多分岐の木構造であり、以下の特徴を持っている。
- すべてのリーフノード（末端ノード）は同じ深さに位置する
- 各ノードには複数のキー値と、対応するデータへのポインタが格納されている
- 検索、挿入、削除の操作がすべてlog(n)の時間複雑性で実行できる
- 自己バランス機能により、データの変更後も効率的な構造を維持する

B-treeの構造により、インデックスは大量のデータに対しても効率的な検索を実現できる。例えば、1000万件のレコードを持つテーブルでもB-treeインデックスを使用すれば、通常3〜4回のディスクアクセスで目的のデータを見つけることができる。

## 効果的なインデックス設計
### どのカラムをインデックスにするべきか
- 主キー
自動的にインデックスが作成される。主キーの一意性を保証し、頻繁に検索条件として利用されるため。
- 外部キー
他のテーブルとの結合に使用されるため、インデックスを作成することで結合操作性能が向上する。そのためインデックスを作成することが推奨される。
- 検索条件として頻繁に使用されるインデックス
顧客管理システムで名前による検索が頻繁に行われる場合、名前カラムにインデックスを作成することで検索性能が向上する

:::note warn
ただし以下について慎重に考えてインデックスの作成をするべき
:::

- 更新頻度の高いカラムのインデックス作成
データが頻繁に更新されると、更新のたびにインデックスも更新する必要があり、パフォーマンスが落ちる可能性がある（商品の在庫数など）
- 取りうる値が少ない（選択性が少ない）カラムのインデックス作成
性別を表すカラム（男or女など）にインデックスを作成しても、効果は限定的。反対にメールアドレスなど、ほとんど値が異なるカラムにおいてはインデックスが効果的に機能する

### 複合インデックスの設計方法
複合インデックスを作成する際に最も重要なのは**カラムの順序**

例えば顧客テーブルに対して【都道府県、市町村区、姓、名】の順番で複合インデックスを作成した場合、まず都道府県で整列され、同じ市町村区で整列され、同じ姓で整列されるとなる。

#### 複合インデックスで気をつけること
- 中間カラムを飛ばして利用する場合は効果が低い
複合インデックスは先頭カラムから順番に使用される場合に最も効果を発揮するが、逆に中間のカラムを飛ばして使用する場合、効果は限定的になる。例えば「特定の姓と名を検索する」場合、都道府県、市町村区の指定がない場合。
- 検索の範囲条件
複合インデックスは先頭カラムに対する検索範囲には効果的だが、後続のカラムに対する検索範囲には効果が低下する
  - 【年, 月, 日】の複合インデックスでは「特定の年の、特定の月の、特定の日」を検索する場合には効果的だが、「全ての年の、特定の月の、特定の日」を検索する場合効果的ではない
- 複合インデックスのカラム数
カラム数が増えれば増えるほどインデックスのサイズが大きくなり、更新のコストが高くなる。実際の検索パターンで必要となるカラムのみ含めるのが望ましい

## インデックスのメンテナンスコスト
インデックスは検索性能を向上させる一方で、作成や維持には一定のコストが生じる

- ディスク容量の増加
インデックスの作成には追加のディスク容量が必要になる。インデックスはテーブルとは別に保存され、一般的にインデックスはテーブル容量の20% ~ 40%程度になることが多い。
- データ挿入、更新、削除時のオーバーヘッド
データが変更されるたびにインデックスも更新しなければいけないことから、データ変更の頻度が高いテーブルにインデックスを作成するとパフォーマンスが低下する可能性がある
  - 1秒間に数千回の更新が行われるリアルタイム在庫管理システムで、在庫数カラムに複数のインデックスが作成されていると更新処理が大幅に低下する
- インデックスの断片化
時間の経過とともにデータの挿入や、削除によってインデックス内に空きスペースが生じる。この断片化によりインデックス効率が低下し、検索性能に影響を与える可能性がある。
  - 顧客データベースで頻繁に顧客の追加や、削除が行われると、顧客IDのインデックスは断片化される可能性がある

# 参考記事
ありがとうございました！
https://zenn.dev/farstep/books/learn-database-index-basics
https://zenn.dev/yuki_tu/articles/c0a11385a33e0c
https://engineers.fenrir-inc.com/entry/2024/04/10/185439
https://qiita.com/shibainuu/items/25d4d9c37d8e7ba04afa