MySQLのB+treeインデックスの復習

MySQL SQL

最近、とあるプロダクトの性能改善をおこなっており、その中で特にMySQLのチューニングを担当しています。 RDBのチューニングといえばまずはインデックスですが、「インデックスを貼れば早くなる！」というのは感覚的にはわかっているのですが、インデックスがどんな仕組みになっているのか? について少しだけ踏み込んで理解したいと思ったため、勉強してみました。

お題

例えば以下のようなuserテーブルで、『誕生日が 10/15 の人はだれですか?』を検索する場合を考えてみます。

id name class birthday
1 佐藤 A 04/29
2 鈴木 B 06/27
3 高橋 B 04/11
4 田中 A 08/12
5 伊藤 B 10/15
6 渡辺 C 10/28
7 山本 A 03/31
8 中村 B 02/11
9 小林 C 01/24
10 加藤 A 05/08
11 吉田 B 05/30
12 山田 C 07/11
13 佐々木 A 05/03
14 山口 B 12/19
15 松本 C 04/26
16 井上 A 01/08
17 木村 B 11/26
18 林 C 11/16

検索SQL

SELECT name
  FROM user
  WHERE birthday = '12/19'

作成するインデックス

この検索が早くなるようにインデックスを貼るとすると、birthday列に対してインデックスを貼ることになります。

CREATE INDEX idx_user_birthday ON user(birthday)

インデックスをB+treeで表現

B+treeインデックス自体の説明は他にいくらでも記事があると思うので省略します。

上の図は、今回の例をB+treeインデックスで表現したものです。

各ノードの中身は、それぞれ1つ下のノードの最大値となります。

上の図は、左側のブランチノードとリーフノードを抜粋したものです。 例えば一番左のリーフノードの最大値は02/11なので、ブランチノードの最初の要素も02/11になります。 ここではブランチノードとリーフノードのみを例に挙げていますが、ルートノードだとうと同じ仕組みです。

インデックスの走査の仕組み

インデックスの走査は、一番上のルートノードから始まります。そしてノード内の左の要素から順番に、検索する値以上であるかをチェックします。要素が検索する値以上であれば、その要素に対応するブランチノードへのポイントを辿ります。これをリーフノードに達するまで繰り返します。

上の図は、『誕生日が10/15の人』を検索した際に、インデックスをどのように辿るかを表現したものです。

この例だと、以下のようにインデックスを辿ることになります。

  1. 10/15 =< 05/06 は偽なので次の要素に
  2. 10/15 =< 12/19 は真なので 12/19に対応するブランチノードに移動
  3. 10/15 =< 12/19 は偽なので次の要素に
  4. 10/15 =< 10/28 は真なので 10/28に対応するブランチノードに移動
  5. 10/15 =< 08/12 は偽なので次の要素に
  6. 10/15を発見！

これぐらいのデータ量だとありがたみがわかりづらいですが、B+ツリーの走査は非常に効率的な処理です。巨大なデータセットに対してもほとんど一瞬で処理できます。