MySQLのインデックスについて整理する

# インデックスとは

- 値を検索/取得するようなカラムに対してあらかじめインデックスを指定しておくことで、処理を高速化させることができる仕組み
- 本の索引(インデックス)を想像すると分かりやすい
- インデックスが設定されていない場合、レコードの検索にテーブルの先頭行から1つずつチェックする必要がある(フルテーブルスキャン)
- ただし、インデックスが適切に設定されていない場合、かえって通常よりもパフォーマンスが低下する可能性もあるため注意が必要

# 前準備

```bash
# 確認用にDBを作成
mysql> create database test_database;
Query OK, 1 row affected (0.02 sec)

# DBが作成されたことを確認
mysql> show databases;
+--------------------+
| Database           |
+--------------------+
| information_schema |
| mysql              |
| performance_schema |
| sys                |
| test               |
| test_database      |
+--------------------+
6 rows in set (0.01 sec)

# 使用するDBの変更
mysql> use test_database;
Database changed

# 確認用にテーブルを作成
mysql> create table test_table (id int, name varchar(10));
Query OK, 0 rows affected (0.05 sec)

# テーブルが作成されたことを確認
mysql> show tables;
+-------------------------+
| Tables_in_test_database |
+-------------------------+
| test_table              |
+-------------------------+
1 row in set (0.01 sec)

```

# インデックスの操作

### インデックスの確認

```bash
# インデックスが作成されていないことが分かる
mysql> show index from test_table;
Empty set (0.00 sec)

```

### インデックスの作成

```bash
# `name_index`という名前で`name`カラムに対してインデックスを作成
mysql> alter table test_table add index name_index(name);
Query OK, 0 rows affected (0.16 sec)
Records: 0  Duplicates: 0  Warnings: 0

# インデックスが作成されたことが分かる
mysql> show index from test_table;
+------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| Table      | Non_unique | Key_name   | Seq_in_index | Column_name | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment | Index_comment |
+------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
| test_table |          1 | name_index |            1 | name        | A         |        NULL |     NULL | NULL   | YES  | BTREE      |         |               |
+------------+------------+------------+--------------+-------------+-----------+-------------+----------+--------+------+------------+---------+---------------+
1 row in set (0.04 sec)

```

### インデックスの削除

```bash
# インデックスの削除
mysql> alter table test_table drop index name_index;
Query OK, 0 rows affected (0.09 sec)
Records: 0  Duplicates: 0  Warnings: 0

# インデックスが削除されたことが分かる
mysql> show index from test_table;
Empty set (0.01 sec)

```

# インデックスの種類

- MySQLでは以下の5(+2)種類のインデックスが設定可能

### PRIMARY

- 指定したカラムの情報が一意の場合に限って設定可能
- 1つのテーブル上に1つしか保持できない
- プライマリキーを指定すると自動で設定される
- カラムをまたがって設定することができる

### UNIQUE

- 指定したカラムの情報が一意の場合に限って設定可能
- 1つのテーブル上に複数設定可能
- ユニークキー、外部キー用

### INDEX

- 一般的なインデックス
- 値が重複している場合でも設定可能
- SELECT文のLIKE句等を使用して情報を取得する際に効果を発揮する

### FULLTEXT

- 全文検索(文章中の単語を見つけるような場合)で効果を発揮する
- インデックスのサイズが大きくなるという欠点がある

### SPATIAL

- 位置情報を格納するカラムにインデックスを設定する場合に効果を発揮する

### プレフィックスインデックス

- 文字列のカラムにおいて、先頭n文字を対象とするようなインデックス
- インデックスのサイズを小さくすることができる
- `alter table test_table add index name_index(name(5));`のように指定する(n = 5)

### 複合インデックス

- マルチカラムインデックスとも呼ばれる
- 複数のカラムを対象に作成するインデックス
- `alter table test_table add index foo_bar_index(foo, bar);`のように指定する
- インデックス作成時に指定したカラムが左から順に検索条件に含まれている場合、インデックスが使用される

# インデックスの作成基準

### 作成すべき基準

- カーディナリティが高い
    - カーディナリティは多重度とも呼ばれる
    - カラムに設定されるデータの種類がどれだけあるのかということ
- レコード数が多く、その中から少量のレコードを検索する場合
- NULL値の多いカラムからNULL値以外のレコードを検索する場合
    - インデックスにNULL値は含まれないため

### 作成しないべき基準

- データの挿入時や更新時の処理がボトルネックになる場合
    - インデックスを作成すると、どうしてもデータの挿入時や更新時の処理が重くなるため
- データ容量の逼迫が問題となる場合
    - インデックスを作成するとそのぶんだけデータ容量を使用するため

# インデックスの適用条件

- 実際に発行したクエリに対してインデックスが適用されているかどうかは実行計画(EXPLAIN)を確認して判断すべき

### 適用される条件(抜粋)

- 定数との比較をする場合
- 範囲検索する場合(`>`, `<`, `>=`, `<=`)
- JOINする場合
- LIKE句(例外あり)、BETWEEN句、IN句を使用する場合
- MIN関数、MAX関数を使用する場合
- ORDER BY句(例外あり)、GROUP BY句を使用する場合

### 適用されない条件(抜粋)

- LIKE句の先頭にワイルドカードが使用された場合
- MySQLがフルテーブルスキャンを実行したほうが速いと判断した場合
- ORDER BY句で指定したカラムの一部にインデックスが貼られていない場合
- WHERE句とORDER BY句の両方を使用する場合は工夫が必要

# インデックスの方式

- 内部的にどのようなデータ構造によってインデックスが実現されているかという話

### 二分探索木

<img src="https://upload.wikimedia.org/wikipedia/commons/d/da/Binary_search_tree.svg" width="300">

- 実際にインデックスのアルゴリズムとして使用されることはないが、ベースとなる構造のためまとめておく
- 「左の子ノードの値 <= 親ノードの値 <= 右の子ノードの値」という制約を持った二分木であり、最も基本的な探索木
- 線形探索した場合、計算量は`O(n)`となるが、二部探索木を構築して二部探索を行った場合、計算量は`O(log n)`となる

### AVL木

<img src="https://upload.wikimedia.org/wikipedia/commons/0/06/AVLtreef.svg" width="300">

- こちらも実際にインデックスのアルゴリズムとして使用されることはないが、ベースとなる構造のためまとめておく
- 「どのノードの左右部分木の高さの差も1以下」という制約を持った二分探索木、平衡木
- ノードの追加や削除時に回転と呼ばれる操作を行うことで、平衡を維持する
- 二分探索木における、データの順番によって木の構成が変化するため探索効率が安定しない(最悪の場合計算量は`O(n)`となる)といったデメリットを解消することができる

### B-tree

<img src="https://upload.wikimedia.org/wikipedia/commons/6/68/B-tree_example.svg" width="500">

- インデックスのアルゴリズムとしても多用される
- 1つの親ノードがm個(m >= 2)の子ノードを保持できる平衡木
- 計算量は`O(log n / log m)`
- AVL木における、メモリ等に比べて速度の遅い補助記憶装置においてパフォーマンスが劣化してしまうといったデメリットを解消することができる

### B+tree

- MySQLのインデックスのアルゴリズムとして採用されている
- B-treeの亜種の1つ
- B-treeと異なり、リーフノードが全てのデータを保持しており、範囲検索に強いというメリットがある

### ビットマップインデックス

- テーブル

|ID|名前|血液型|
|:--|:--|:--|
|1|マイケル|A|
|2|ジェシカ|B|
|3|クリストファー|O|
|4|アシュリー|AB|
|5|マシュー|A|

- ビットマップ

|ID|A|B|O|AB|
|:--|:--|:--|:--|:--|
|1|1|0|0|0|
|2|0|1|0|0|
|3|0|0|1|0|
|4|0|0|0|1|
|5|1|0|0|0|

- テーブルと対になるビットマップと呼ばれるデータ構造を持ち、これを利用して行を特定する
- カーディナリティが低い場合に有効

### ハッシュインデックス

- データとハッシュ関数から求めたハッシュ値を使用し、レコードの格納位置を決定する
- 一意な値の検索を得意とするが、範囲検索やワイルドカードを使用した検索に弱い
- ハッシュが衝突した場合にはレコードの格納位置を一意に決定できない場合があり、その対策としてオープンハッシュ法やハッシュチェイン法等の手法がある