はじめに
今まで業務で幾度となくデータベースを触ってきましたが、インデックスについては見よう見まねとか、経験則でなんとなくやってきた感が強かったです。
そこで、最近インデックスに触れる機会があったので、これを機にインデックスについてまとめようと思いました
「インデックス」って何?
直訳すれば「(本などの)索引」(データベースでの場合)
ちょうど本の索引(=目次)のように、「探しているデータを素早く見つけるための指標」と考えると分かりやすいかもしれないです。
例えば基本(応用)情報技術者試験の参考書の場合、
- 第1章 基礎理論
- 第2章 アルゴリズムとプログラミング
- 第3章 ハードウェアとコンピュータ構成要素
みたいな索引が付けられていて、実際に自分が勉強したい項目のページを素早く探し出せますが、これと同じことを行うのがインデックスです。
また、自分は「DynamoDBにおける、パーティションのパーティションキーみたいなもの」という認識を持っています。(ある程度何のデータかを絞り込むための情報)
B木とB+木
MySQLの検索には、「B+木(=baranced plus tree)」というアルゴリズムが採用されています。
これは「B木(=baranced tree)」の改良版で、下記のような木構造です。(実データは少し簡素化しています)
ちなみに、検索の経路はこんな感じです。
例えば、「19」を検索する場合、こんな感じです。
- 最上段では、19は11以上20以下なので、真ん中の経路を進む
- 2段目では、19は17より大きいので、右端の経路を進む
- 最下段で、18から20を順に探査し、19が見つかる
そして、B+木(B木もだけど)の何が重要かというと、「しきい値(≒インデックス)の値の設定が重要」ということです。
例えば同じデータ数でも、下図の左と右では、どう考えても左の方が検索効率がいいことが分かります。
こういう、検索効率がよくなるインデックスというのを考慮する必要があります。
カーディナリティ
カーディナリティとは?
インデックスを作成する上で欠かせないのが「カーディナリティ」です。
カーディナリティは「同一フィールドに含まれる異なる値の数」のことで、よく「多重度」などど表現されます。
もっと端的にいえば、distinct
やGROUP BY
をした際に取得できる値の個数です。
たとえば、あるテーブルに10レコードがあり、そのname
フィールドが下記だったとします。
name |
---|
Kagekiyo |
Kagekiyo |
Kagekiyo |
Kagekiyo |
Yoshitsune |
Yoshitsune |
Yoshitsune |
Benkei |
Benkei |
Yoritomo |
この場合、name
フィールドのカーディナリティは4(Kagekiyo, Yoshitsune, Benkei, Yoritomo)です。
そして、インデックスを貼る際、カーディナリティが高い(=数値が大きい)フィールドから順に貼っていくというのが基本になります。(もちろん「基本」なだけで、該当しないケースもあります)
データの割合
もう一つ注意しなければらならないのが、データの割合です。
例えば、先程のname
フィールドについて、全100レコードあり、カーディナリティは同じく4だったとします。
しかし、例えば下図の左のグラフのように、ほぼ均等に分散されているのと、右グラフのように1データに極端に集中しているのとでは、下記理由より明らかに前者の方が早く検索できます。
- 後者は、ほぼ全文検索しないといけない
- データの割合的にも、後者では検索されるのは極端にデータが多い「Kagekiyo」である可能性が高い
したがって、「カーディナリティが高い」だけでなく、均等にデータが分散されているフィールドにインデックスを貼る のが重要です。
ただ実際はそうそううまくは均等にならないでしょうし、予測も難しいケースもあるでしょうから、「極端に偏りがないフィールドに貼る」でもOKだと思います。
カーディナリティが高ければ、それだけデータが分散される可能性が高いため、「カーディナリティが高いフィールドからインデックスを貼る」のが一般的、というわけです。
インデックスの貼り方&確認方法
実際にSQLインデックスを貼る方法ですが、下記の通りです
# インデックスの作成 ALTER TABLE テーブル名 ADD INDEX インデックス名(カラム名); # 例 ALTER TABLE test_table ADD INDEX idx1(name); # インデックスの確認 SHOW INDEX FROM テーブル名; # 例 SHOW INDEX FROM test_table; # クエリのインデックス効果を確認する(詳細は次回に説明します) EXPLAIN 実際のクエリ # 例 EXPLAIN SELECT * FROM test_table where name = 'hoge'; # インデックスの削除 ALTER TABLE テーブル名 DROP INDEX インデックス名; # 例 ALTER TABLE test_table DROP INDEX idx1;
次回は
次回は、インデックスについて「効くケース・効かないケース」などについて説明したいと思います。
それでは、今回はこの辺で。