B-Tree インデックス (B-Tree Index)
オラクルのインデックス、すなわち、デフォルト時のインデックスは B-Tree インデックス(※1) になる。
B-Tree インデックスとはバランスド・ツリーインデックスの略である(1969 年頃に既に考案されている)。プログラミングを始めたときにソートアルゴリズムやデータ構造で勉強したであろうと思う二分木 (Binary-Tree) の進化版みたいなものである。
一部のブランチが異常に成長しないように平衡を保つように再編成(バランス)する仕組みによって、常にインデックスによる検索性能を高い状態に保つことができる(※2)。
RDBMS によっては色々な種類のインデックスが存在しているが、現在においても B-Tree インデックスが多くのケースで優れたパフォーマンスを出していることには変わりないようである。
(※1) B-Tree には B-Tree から派生した B+ Tree(B+-Tree) と B* Tree(B*-Tree) などの改良型があり、B-Tree の考案者が UB-Tree という新しい方式を提唱*1するなど現在でも改良が加えられている古くて新しいアルゴリズムである。
オラクルでは B*-Tree 型の B-Tree インデックスが使われているらしいがマニュアル上では B-Tree で統一されており B*Tree の表記は見つけられなかった。技術資料では B*Tree と書かれているものが結構存在する。
(※2) 数回のマルチブロックリードで全レコードを読み取り終わるような 小規模表 にインデックスを付与しても、ほとんど意味がない。
B-Tree インデックスと NULL
B-Tree インデックスは、テーブルの格納領域とは別の索引セグメントに NULL を除いたデータを格納する。
テーブル構造に比べて余分なデータの無い、この小さな構造体でデータを読み、比較、抽出することで検索結果を即座に得ることが可能になる。
B-Tree はルート、ブランチとリーフから構成される。ルートはブランチを兼用することがある。
- ブランチブロックには、検索キーとブロックアドレス(※1)
- リーフブロックには、検索キーと ROWID をもつ。
隣接するリーフブロック同士は、レンジアクセスやインデックスへのフルスキャンのために双方向でリンクしている。
このような構造により、イコールでの検索には、ルートノードからの探索。範囲検索の場合には、さらにリンクを辿って順方向、逆方向に検索が継続される(のだと思う)。
インデックスの重要な格納ルールに、ブランチ、リーフには必ず昇順(降順)に検索キー(※2)を格納するという掟がある。
この掟によってブロック分割が発生し、ツリーの階層が深くなることがある。階層が深くなると検索時のパフォーマンスが徐々に低下する。
また、インデックスの内部が、いびつな形で空洞化が進むとレンジスキャン時に大幅にレスポンスが低下する(※3)ので注意が必要である。
(※1) ブロックアドレスとは、ブランチブロック、または、リーフブロックへのポインタ。
(※2) 複合キー(複合主キー)の場合には、第一キーから順番にソートされる。全てデータが同じ場合は ROWID でソートされる。
(※3) 正確にはデータの件数が大幅に減っても、早くなるはずの応答時間が変化しない。
複合インデックス (コンポジット・インデックス) の並び順と検索速度
複合インデックス(※)や複合主キーの場合、その並び順によって検索時のコストは大きく異なる。
(※) 以前は連結インデックス(Concatenate Index) 略してコンカチ・インデックスと呼ばれていたような記憶もある。
例えば、あるテーブルの項目 colA と colB の範囲検索の場合。
そのテーブルには、colA、colB の順で複合インデックスが作成されているとする。
次の２つの SQL について考える。
SELECT colA FROM tbl WHERE colA >= 30 AND colA < 50 … (1)
SELECT colB FROM tbl WHERE colB >= 30 AND colB < 50 … (2)
このとき複合インデックスのリーフブロックには、以下のようなイメージで colA、colB の昇順にデータが格納されている。
それぞれの SQL では探索方法と検索しなければいけない範囲が異なる。
この場合には、(1) の SQL の方が検索時間をかなり短縮できている。これはインデックスが並び替えてから格納するというルールによって得られる効果である。
| colA | colB | (1) | (2) |
| 10 | 20 | - | 探索開始:miss |
| 10 | 30 | - | hit |
| 20 | 10 | - | miss |
| 20 | 20 | - | miss |
| 30 | 40 | 探索開始:hit | hit |
| 30 | 50 | hit | miss |
| 40 | 10 | hit | miss |
| 40 | 50 | 探索終了:hit | miss |
| 50 | 20 | miss | hit |
| 50 | 30 | - | 探索終了:hit |
このように複合インデックスの場合、その定義する順番は非常に重要である。
また、並び替えにおいてもインデックスが使用されることがある。
B-Tree インデックスが不得意なデータ分布
B-Tree インデックスの苦手とするのは、カーディナリティ度（選択度)の低いデータの場合である。
およその目安であるが、全レコードの 10% 以上が検索条件に適合する条件の場合には B-Tree インデックスによる優位性を体感できないように思う。インデックスをメンテナンスするオラクルがくたびれ損で容量も無駄になる
（ビットマップ・インデックスも、ほぼ同様でインデックスがマージできない条件下ではインデックス自体に意味がない）
データの分布にバラつきがある場合には、テーブルのカラム統計(ヒストグラム)の収集を検討する。
⇒ テーブル・カラム・インデックス統計情報
一般的に最初からカーディナリティが少ない場合、検索に限ればビットマップ・インデックスの方が高速に処理できる。
しかし、ビットマップ・インデックスは B-Tree と比べて更新処理内容がコスト高のために更新頻度が低いテーブルに向いているといえる。
インデックス関連事項
