ハイパフォーマンスMySQLでインデックスについて勉強したことまとめ #MySQL

インデックスの種類

インデックスはサーバーレイヤではなくストレージエンジンレイヤで実装されているため、標準化されていない。
インデックスとは本の目次のようなもので、ストレージエンジンがデータを検索するときにデータ全体をスキャンする必要がなくなるので高速で検索することが可能になる。

MySQLのストレージエンジンでで一般的に使用されているインデックス。
なんの断りもなしに「インデックス」と言われているときはBツリーインデックスを指していることが多い。

ここにわかりやすくまとまっている
B-treeインデックス入門

5は4より大きいので、右側に進みます
5は6より小さいので、左側に進みます
5が見つかりました

検索の具体的な手順はB-treeインデックス入門で開設されている通りの手順。

ストレージエンジンがこのようなツリー構造をあらかじめ作っておき、上の手順を踏むことでデータの高速な検索が可能になっている。

ツリーのノードはソートされているので、高速化された検索と同じようなソートをすることができる。
例えば名前にインデックスがついていたら、名前の検索も高速だが、ソートも高速。

Bツリーインデックスで例えば上のような複合インデックスを貼った場合は、インデックスを貼る順序が大事になっている。
上の図では姓→名の順にインデックスが貼られているとする。

検索がインデックス付きの列の左から始まらないと意味がない。今回の場合は姓が最初のインデックスなので、姓で検索すると高速だが、名で検索しても高速ではない。同様に特定の文字で終わる姓の人の検索にも役たたない。
インデックスで列をスキップすることはできない。つまり名がMakikoで特定の誕生日をもつ人物を検索することはできない。必ず一番最初に貼ったインデックスの値を指定しなくてはいけない。

ハッシュインデックスはハッシュテーブルに基づくインデックス。インデックスのすべての列を使用する正確な検索にのみ役に立つ。
MySQLでこの仕組みをサポートするのはMemoryストレージエンジンだけ。

こんなテーブルがあったとする。
架空のハッシュ関数f()があったとして

f('Arjen') = 2323
f('Baron') = 7437
f('Peter') = 8784
f('Vadim') = 2458

というハッシュが生成されるとする。

このようにハッシュ値とポインタのテーブルを用意して、ここから検索することができる。
インデックス自体は短いハッシュ値を格納するだけなので、ハッシュインデックスは非常にコンパクト。