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

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

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

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

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

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

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

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

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

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

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

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

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

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

つづく

【カテゴリ】データベース

プロフィール

愛知県名古屋市にあるジャスウィルで働く社員です。

ジャスウィルは大学事業に特化したシステムを提案しています。『大学向け事務・教務統合パッケージ―TriR Campus』を開発しています。


Facebookページでは、イベントや普段の社員の様子を公開中♪
ぜひご覧ください☆

過去一年の月別記事 全て表示