II-22-2. インデックスの種類と特徴

バイナリツリー(B木)、索引構成表、ビットマップ・インデックス、逆キー・インデックス、ハッシュ・クラスタ(ハッシュ・インデックス)など、様々なインデックスの種類を紹介し、それぞれの特徴と利点・欠点について解説する。

【学習の要点】

* B木インデックスは、木構造のページ群にアドレス情報を格納し、インデックス値を比較しながら二分検索法で該当する行の検索を行う。

* ハッシュ・インデックスはハッシュ関数を使って直接アドレス計算を行って該当する行検索を行う。

* ビットマップ・インデックスは1行に1ビットを割り当てたビットマップデータの相対位置から該当する行検索を行う。

図II-22-2. B+木インデックス

【解説】

1) インデックスの種類

インデックスには様々な種類があり、それぞれ利点と欠点を持っている。B+木インデックスが、RDBMSのインデックスで最も多く使われる木構造といわれている。

* 二分木インデックス

木構造は木のように広がっていく構造をもつ。二分木は木構造のなかで最も基本的なもので、ノード(節)の下にある子のノードが最高で2つであるという構造を持つ。

検索方法は、検索したい値をルート(根)から分岐(枝)へたどっていき、目的のキー値がノードのキー値よりも小さければその前の枝へ向かい、大きければその次の枝へ向かう。その次のノードでもその動作を繰り返す。等しいときに完了となる。

データの追加により二分木のバランスが崩れ片側だけに集中するようになると、パフォーマンスが低下するという欠点がある。

* B木インデックス

B木(バランス木)は、二分木インデックスの欠点を解消するために考えられたもので、バランス木の名前の通り、データの分岐の先がすべて同一の階層に属した多分木の構造を持つ。ノード内にもソートされた複数のキーが含まれる。

検索方法は、ノード内のキーを検索し、目的のキーが、ノードのキー値よりも小さければその前の枝へ向かい、大きければその次の枝へ向かい、その次のノードでもその動作を繰り返す。リーフノードにキーがあったときに完了となる。

利点は、レコード追加後の検索性能が保たれること、欠点は、レコード削除での検索性能が低下することである。

* B+木インデックス

B木はノードにもデータを記録するが、B+木ではデータは木の最下層にあるノード(葉ノード、リーフレベルのノード)に格納され、内部ノードにはキーのみが記録される。

また隣のノード同士をポインタで結合してシーケンシャルアクセスの性能向上が図られている。

B木インデックスとB+木インデックスともに区別なくB木インデックスと呼ぶこともある。

* ハッシュインデックス

B木インデックスを使った場合には、目的のレコードのアドレスを得るためには、数回のアクセスが必要になることがある。これをハッシュ関数と呼ばれるものを使って、一回で目的のレコードのアドレスを取得できるようにしたものである。

B木とは異なり、BETWEENなどの範囲検索には利用できない欠点がある。

* ビットマップインデックス

キーとなる値をビット列で用意するものである。ビット列はキーの値の数だけ用意される。

利点は、通常ではインデックスの設定に不向きとされる、カーディナリティが低い場合に検索性能が高く、インデックスの容量を少なくできる。欠点は、キーの値の数が多い場合にはビット列が増えるため不向きであることと、レコード追加がある場合に性能の低下が大きいことである。

* 逆キーインデックス

キーの値を逆にしてインデックスを格納する方式で、連番(シーケンス番号)などに付加する索引では同じノードに更新が集中するのを避け更新を分散させることができる。範囲検索ができない欠点がある。

OSS Course Naviのコンテンツは IPA OSS モデルカリキュラムを基としています。