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

NO IMAGE

今回は、最もポピュラーであり、ほとんどのリレーショナルデータベースで使用することができるB-Treeインデックスを掘り下げてみます。

※ORACLE,MySql等でデフォルトのインデックス。
※B-Treeとは「バランスツリー」のことで検索アルゴリズムの一つとしても有名です。

図で簡単に表現すると、下記のようになります。
（カメルーンを検索する場合）
WS000002.jpg

最上位のヘッダブロックから検索していき、
最下位のリーフブロックにて実表の物理位置(ROWID)をゲットします。

この階層が浅ければ浅いほど検索の速度があがりますが、
B-Treeの特徴としてデータ量が10倍、20倍になっても、
階層の深さはさほど変わりません。

そのため、データ量に関わらず一定の速度を保つことが可能になります。

その他、B-Treeインデックスの特徴として
　・範囲検索の高速化
　・ソートの高速化
の2点についても、パフォーマンスに良い結果を得ることができます。

範囲検索の高速化については、最下位のリーフブロックに前後のデータのポインタを
各データにもっているので、前後のデータを連続して検索することができるためです。

ソートの高速化については、B-Treeインデックス内のデータは既にソートされているため、
ソート処理の必要がないためです。

なお、複数の列を使用した複合インデックス(主キーに多い）の場合は注意が必要です。

複合インデックスの一部だけを使った検索では、条件によってインデックス検索がされず
思うような速度が出ない場合があります。

複数列で１つの一意性を保つため、インデックスではデータを特定できないためです。

※oracleの場合はオプティマイザの判断によりインデックス検索されることもある。
※一部のみでも、カーディナリティが高い場合など。

つづく