Lapis Lazuli

technical blog for web developer

MySQLのB-Treeインデックスを理解する

MySQLのインデックスには一般的にB-Treeインデックスというものが使われています。
BTreeはインデックスのアルゴリズムなのですが、今回は何故これが一般的なのかについてです。

B-Treeとは

インデックスは実テーブルのデータを素早く探す為の索引ですが、アルゴリズムによって大きく仕組みが異なります。
B-Treeは平衡木構造というデータ構造をもっています。
平衡木はバランスドツリーとも言われ、その名の通りツリー構造の高さを可能な限り等しくした形になっています。

二分探索木

平衡木は二分探索木という構造を元にして成り立っています。
二分探索木とは、ルートノードと呼ばれる根本のノードから分岐していくツリー状のデータ構造です。
この構造の特徴はバランスが整った構造になっている場合、計算量が少なくて済みます。
ただ、ちゃんと整っていればの話で、実際に運用してデータの削除や追加などが行われると歪な構造になっていきます。
平均計算量はlog nになりますが、最悪はn回計算しないといけなくなります。
これを解決するために平衡木というツリー構造があります。

平衡木を作るためのアルゴリズム

平衡木は二分探索木を基本として、いかに高さのバランスが均等になるかを考えられたものになります。
その中の一つのAVL木というツリー構造になります。
AVL木はツリーを回転させ高さを揃えるアルゴリズムです。
具体的には、データが葉に挿入されたとき、部分木の高さが2以上なら木を回転させ高さの差が1以内になるように調整されます。
こうすることで計算量がlog nになるようにします。
AVL木を利用し、多分岐の構造を持つのがB-Treeになります。

B-Treeインデックスの仕組み

B-TreeのAVL木の最もたる違いは、2以上の子ノードを持つ事が出来るという点になります。
木の深さを抑えて読み取り回数を減らすような構造にすることで、素早くデータの読み出しが可能になるからです。
ルートノードと中間ノードにはキーと子ノードへのポインタが格納され、実データはリーフノードに格納されるます。そして検索するときにルートからキーによってたどっていくノードを変える仕組みになっています。
つまり、データを各ノードで持たないので効率の良い、高速なデータ検索が可能となるという訳です。

まとめ

今回はB-Treeインデックスについてでした。
MySQLは普段よく使っているけど、インデックスのアルゴリズムなどは意識したことがなかったので、今後はより理解を深めていきたいと思いました。