MySQLのインデックスの仕組み

「インデックスとは」 をざっくりと

インデックスを作成することで検索が早くなる。

例えば、英和辞書で考えてみる。
普通の英和辞書だと親切にA→Zの順で単語が並んでいると思うが、これが何の規則もなくバラバラに並んでいるとする。

この不便な辞書から「search」を探したい時、何もない状態だと1ページから順番に探していく必要があり、「search」が記載してあるページによっては検索に膨大時間がかかるかもしれない。
これが実際AからZの順番で並んでいたり、あるいは索引があることで私達は簡単に「search」にたどり着くことができる。

このように、検索が容易になるものがインデックス。
ただし、これは作りすぎてもデメリットがあるので、ただ作ればいいというものでもない（後ほど解説）。

インデックスの作り方

テーブル作成時には下記のように、KEY index_name (column_name)を指定すれば、インデックスが作成される。
また、複数のカラムにインデックスをはる複合インデックスの場合もインデックスを貼るカラムを複数指定すれば作成される。

-- userテーブル作成時にnameカラムにインデックスを作成し、
-- nameカラムとstatusカラムに複合インデックスを作成する
mysql> CREATE TABLE(
    ->   `id` INT UNSIGNED NOT NULL AUTO INCREMENT COMMENT 'id',
    ->   `name` VARCHAR(20) NOT NULL COMMENT '名前',
    ->   `status` ENUM('registered', 'resigned', 'deleted') NOT NULL COMMENT 'ステータス',
    ->   `created_at` datetime NOT NULL COMMENT '作成日時',
    ->   `updated_at` datetime NOT NULL COMMENT '更新日時',
    ->   PRIMARY KEY (`id`),
    ->   KEY `idx_user_name` (`name`),
    ->   KEY `idx_user_name_status` (`name`, `status`)
    -> ) ENGINE=InnoDB DEFAULT CHARSET=utf8mb4 COMMENT='ユーザ';

その他、既に存在するテーブルに対してインデックスの操作を行う時のクエリ

-- userテーブルにインデックスを追加する
mysql> ALTER TABLE user ADD INDEX `index_name`(column_name);

-- userテーブルに複合インデックスを追加する
mysql> ALTER TABLE user ADD INDEX `index_name`(column_name1, column_name2,...);

-- userテーブルにインデックスを削除する
mysql> ALTER TABLE user DROP INDEX `index_name`;

-- userテーブルのインデックスを確認する
mysql> SHOW INDEX user;

インデックスの決め方

どのカラムにインデックスを貼るか、どうやって決定するのか。
それは、そのテーブルにどのようなクエリが走るのか次第。
テーブル設計の段階で想定クリを洗い出し、
そのクエリのパフォーマンスが出るようにインデックスを考える。
さらに実際にパフォーマンスを見たりインデックスが使われているか確認(EXPLAIN)しながらチューニングする
という流れになる。

EXPLAIN？

EXPLAINは、そのクエリについての実行計画を知ることができる。
このインデックスを使うよ〜
こんな方法で実行するよ〜
といったパフォーマンスに関する情報が分かるため、パフォーマンスチューニングには必須。
詳細については過去にEXPLAINについて書いたのでそれを参照。
https://qiita.com/chii-08/items/e6a3ff51129ef1167ab6

ここから本題

ざっくりとインデックスの説明をしたので、もう少し深い説明にうつる。

B+treeインデックス

ここではMySQLのInnoDBで使われているB+treeインデックスについて説明する。
まずB+treeとは、データ構造の一つで
1つのノードが2つ以上の子ノードをもつことができる平衡木構造のこと。

B+treeインデックスは、
以下のようにルートノード、子ノード (ブランチノード)、リーフノードの3つのノードで構成されている。

データへのポインタをもつのはリーフノードだけ。

このインデックスを使ってarticle.user_idを検索する際は
1. ルートノードから出発
2. 検索値以上のポインタが見つかったら、その左下のポインタに紐付いたブランチノードに移動。検索値以上のポインタが見つからない場合、キーの最大値の右下のポインタに紐付いたブランチノードに移動する。
3. ブランチノードでも同様に2を繰り返し、最終的にリーフノードへたどり着く or 検索値のデータが存在しない。

例えば上の図でarticle.user_id=10のデータにたどり着く場合は、以下の赤いポインタを辿ってキー値10のデータにたどり着く。

インデックス≠テーブルのデータ

上で説明した通り、B+treeインデックスの各リーフノードはテーブルのデータへのポインタを保持しているだけであり、テーブルのデータ自体を保持しているわけではない。
ただのテーブルの参照情報なので、インデックス自体を保持するためにディスク領域が必要だし、テーブルのデータに変更が入ることでインデックスに変更が入ったりする。

英和辞書の索引も、索引専用のページが必要なように、インデックスもそれ専用のディスク領域が必要ということ。
英和辞書に新しい単語が追加されれば、索引にもそれが追加されるということ。
ただの参照情報。

インデックスの作成

インデックスを作成する際は、
インデックスで指定したカラムでレコードを並び替え、その結果をリーフノードに記録していく。

レコードの追加・削除・更新

レコードが追加された際、
テーブルにデータを追加するだけではなく、テーブルの全てのインデックスに対して新しいデータ情報を追加する必要がある。
そして各インデックスのどのリーフノードに書き込むかを探し、必要であれば既存の構造を変える必要が出てきたりする。
（この辺りの詳細については後日追記したい）

レコードが削除された場合、
レコード追加のときと同様、全てのインデックスから対象データを削除する必要がある。
各インデックスから削除するデータを検索する。ただし実際にデータを物理削除するわけではなく、削除されたことを示す削除表示が追加される。

レコードが更新された場合、
レコード削除→追加が行われる。
各インデックスから更新するデータを検索しそれを削除（論理削除）し、更新後のデータを新たに追加する。

以上のように、テーブルにレコードが追加・削除・更新されるとそのテーブルに貼られているインデックス分変更が発生することになり、インデックスの数が多いほどこの操作に時間がかかる。
冒頭に「インデックスは作りすぎてもデメリットがある」と書いたのはこれが理由。
折角検索を早くするためにインデックスを貼ったとしても、やりすぎると結局パフォーマンスが悪くなる。

まとめ

結局インデックスとは、検索を早くするためにデータを並び替えた結果の参照情報のこと。
こうやって内部構造を理解すると、なんでパフォーマンスが出ないのかとか、意図したインデックスが効かないかとか分かるようになった。

参考

8.3.1 MySQL のインデックスの使用の仕組み
B-treeインデックス入門
USE THE INDEX, LUKE!
MySQL with InnoDB のインデックスの基礎知識とありがちな間違い