dip Engineer Blog

Engineer Blog
ディップ株式会社のエンジニアによる技術ブログです。
弊社はバイトル・はたらこねっとなど様々なサービスを運営しています。

【MySQL】インデックスの仕組みについて

はじめに

こんにちは、PHPで求人系サービスの開発や社内向けツールの開発を行なっている @taku-0728 です。
今回は遅いクエリのパフォーマンス改善によく使われるインデックスについて、具体的にどういう仕組みで早くなるのかを自分なりにまとめますので、これからインデックスを貼ろうと思っている方は参考にしていただければと思います。
本記事はあくまで自分の考えの整理も兼ねてまとめている部分があり、誤った解釈をしている可能性もありますのでその際は遠慮なくご指摘いただければ幸いです。
私が業務で使っているRDBがMySQLであるためこの記事ではMySQLを例に説明します。

この記事でわかること

  • MySQLで使われるインデックスの仕組み(B-treeインデックスについて)
  • なぜインデックスを貼ると検索速度が向上する(場合がある)のか
  • インデックスを貼ると検索速度が向上するカラム、向上しにくいカラム
  • インデックスを貼るデメリット

この記事の注意点

  • インデックスとは何か、といった初歩的な内容は割愛します

MySQLで使われるインデックスの仕組み

一口にインデックスと言ってもRDBなどによって種類はいくつかわかれますが、本記事ではMySQLで使われるB-treeインデックスについて紹介します。

B-treeインデックスとは

探索系のアルゴリズム二分探索木とAVL木を応用した B-tree を変形した B+ tree を用いた検索方法のことです。
B+ tree について説明するために、二分探索木から順番に説明していきます。

二分探索木

二分探索木とは「検索したい値が中央値より小さい場合は左に進み、大きい場合は右に進みながら検索していくアルゴリズム」のことです。下記出典元の画像がわかりやすいと思います。

二分探索木
出典:4geek.net - 4geek リソースおよび情報

二分探索木は検索に強いアルゴリズムですが、データの挿入や削除によって木の高さが 変わった場合、検索したい値によって検索回数や速度が変わってくる可能性があります。
その問題に対応したのがAVL木です。

AVL木

AVL木とは木の高さに変更があった場合、二分探索木に回転という操作を行うことで木の高さを一定にするデータ構造のことです。回転とは二分探索木の各ノードが持つ値の大小関係の条件を満たしたまま木を変形する操作を意味します。
回転には右回転、左回転があり、右回転の場合は

  • 左にある部分木は、位置が1段高くなる
  • 真ん中にある部分木は、親が変わり、縦の位置は変わらない
  • 右にある部分木は、位置が1段低くなる

という特徴があります。左回転の場合はその逆です。
こちらも下記出典元の画像がわかりやすいと思います。

AVL木
出典:B-treeインデックス入門 #MySQL - Qiita

このAVL木を用いたのが B-tree(B木) です。

B-tree

B-tree とは AVL木と同様なバランス木の一種です。AVL木では各節点にキーがあり、そのキーに対する大小で左右への振り分けを行っていくというルールでした。B木では、節点に複数のキーを格納できます。新たな要素は、それぞれのキーに対して大きいのか、あるいは小さいのかを比較して子の節点へ振り分けられていきます。より詳細に知りたい方はこちらのサイトが参考になると思います。

B+ tree

B+ tree はMySQLで採用されているアルゴリズムです。
ほとんど B tree と同じですが、2点ほど違いがあります。

  • リーフノードとリーフノードを結ぶポインタがある
  • データはリーフノードのみに保持する

言葉で話すと難しいかもしれませんが、こちらのサイトで画像つきで解説されてるのでこちらを参照されるとよりわかりやすいかと思います。

B-treeとB+treeの違い
出典:What are the differences between B trees and B+ trees?

データはリーフノードに持つので、途中の子ノードとリーフノードで同じキーがあることが分かります。また、末端のリーフノードたちはポインタで結ばれています。
B-treeと B+ tree のメリットを下記にまとめます。

  • B-tree
    • 子ノードもデータを持つので、探索途中でヒットすればレスポンスが早い。つまり等価条件の探索が向いている。
  • B+ tree
    • リーフノードがポインタでつながっているので、範囲検索に強い。

MySQLではこの「B+ tree」が採用されています。 以上がMySQLで使われるインデックスの仕組みです。

なぜインデックスを貼ると検索速度が向上する(場合がある)のか

上記でインデックスの仕組みを説明しましたが、ここまでこればなぜインデックスを貼ると検索速度が向上する(場合がある)のかはもうわかると思います。
もしインデックスを貼らなければ先頭から順番に値を探していく必要がありますが、インデックスを貼ることによって B+ tree を使ってより効率的に検索していくため検索速度が向上する(場合がある)ということです。

インデックスを貼ると検索速度が向上するカラム、向上しにくいカラム

上記でインデックスを貼ることで検索速度が向上する(場合がある)と説明しましたが、必ず検索速度が向上するわけではなく誤った貼り方をすれば検索速度は向上どころか劣化する可能性もあります。

インデックスを貼ると検索速度が向上するカラム

  • 検索条件で等価条件が使われるカラム
  • 前方一致でlike検索しているカラム

like検索はインデックスが効かないと思われがちですが、前方一致かつ、検索条件がある程度設定されていればちゃんと効きます。

where name like 'hoge%'

インデックスを貼っても検索速度が向上しにくいカラム

  • 検索条件で範囲検索が使われるカラム
  • 中間一致や後方一致でlike検索しているカラム
  • データの種類が少ないカラム

範囲検索でインデックスが効かない理由はこちらのサイトに詳しくかいてあるので、詳しく知りたい方はリンク先の記事を読まれるといいと思います。
また、like検索でも中間一致や後方一致の場合はインデックスは効きません。
データの種類が少ないカラムは前から順番に検索してもインデックスを貼ってもあまり検索速度に違いはないと思います。具体的に何件以上あれば効果があるのかというのは検索条件にもよって変わるので一概にいうのは難しいですが、検索速度の劣化が見受けられたらインデックスを貼ることを検討すればいいかと思います。

インデックスを貼るデメリット

ここまでインデックスの仕組みと検索速度の向上について説明してきました。「インデックスを貼れば速度が向上する可能性があるんだからとりあえず全カラムに貼っておけばいいじゃん」と思う方ももしかしたらいらっしゃるかもしれませんが、インデックスを貼ることはデメリットがないわけではありません。場合によってはデメリットが生じる可能性もあります。
「インデックスの仕組み」で紹介した通りインデックスとは全データをみて探索木を作成するアルゴリズムですが、insertやupdateなどでデータ構造が変わった場合、探索木を作り直す必要があります。そのため不必要にインデックスを貼ることはinsertやupdateなどデータ構造の変更する際の速度低下につながるので注意が必要です。

まとめ

ここまでインデックスの仕組みからインデックスを貼るデメリットまで説明させていただきました。「インデックスを貼りたい時は必要最低限のカラムにのみ貼る」ことを意識すればいいかと思います。
最初にも申し上げましたが、本記事はあくまで自分の考えの整理も兼ねてまとめている部分があり、誤った解釈をしている可能性もありますのでその際は遠慮なくご指摘いただければ幸いです。
最後までお付き合いいただきありがとうございました。

参考

筆者

https://dippeople.dip-net.jp/6818/dippeople.dip-net.jp (写真右)