インデックス<データベース<情報技術の基礎<Web教材<木暮

Web教材一覧データベース

インデックス

キーワード

インデックス、B-treeインデックス、B+木、ハッシュインデックス、ハッシュ関数、ビットマップインデックス


インデックスの概念

インデックスのイメージ

インデックスとは索引のこと、紙の図書での巻末にある索引のようなものです。あるレコードの格納場所(ポインタ)をそのレコードのキー項目の値を対応させておきます。それがインデックス付けです。
 あるキー項目の値(検索値)を与えれば、簡単にその検索値に合致したレコードを取り出せます。また、索引が50音順などにソートされていれば、その順にレコードを高速に取り出すことができます。それで、インデックスを付けることにより、ファイルが物理的にソートされていなくても、ソートされているのと同様な処理ができるのです。

ここではRDBMSを対象にします。インデックスは,原理的には「K→P」の対応表
  K:キー項目値
  P:列Cの値がKである行へのポインタ
があり、検索とは、ある検索値Xを与えられたとき、KがXである対応表に対応するポインタPを得る仕組みです。
 なお、キー項目値Kの個数をカージナリティといいます。

「売上表」の列C「顧客コード」にインデックスをつけることを例にします。顧客コードには「123」や「543」などがあり、顧客コードが「123」である行(売上データ)は、売上表の、50番目、67番目、…にあるものとします(ここでは、50、67、…をポインタPだとします)。
 下図は、X=123のときにp=50、67、…を得る処理を示しています。

            「K→P」の対応表
            キー項目値K    ポインタP
          (列Cの値)   (行の位置)
   検索値X ┬ ┌───┐ ┌──┬──┬──┐
    123 ↑ │ … ├→┤… │… │… │
     │  │ ├───┤ ├──┼──┼──┤
     └───→│123├→┤50│67│… │
        │ ├───┤ ├──┼──┼──┤
        │ │ … ├→┤… │… │… │
      カージ ├───┤ ├──┼──┼──┤
      ナリティ│543├→┤… │… │… │
        │ ├───┤ ├──┼──┼──┤
        ↓ │ … ├→┤… │… │… │
        ┴ └───┘ └──┴──┴──┘

インデックスがないと、表の先頭の行から順に、列Cの値とXを比較する必要があります。平均比較回数は行数/2回になるので、行数が大きいときには、非常に時間がかかります。
 列Cにインデックスがあれば、上図のように、サイズがカージナリティNの配列から探せばよいので、比較回数はかなり減少します。
 インデックスの要点は、検索値X=キー項目値Kとなる位置を効率よく探すことにあります。
 上のような対応表を用いたのでは、Kを探すための効率が悪いので、後述する「B-treeインデックス」や「ハッシュインデックス」のような工夫が使われます。

インデックスをつけることの利失

一つの表に複数のインデックスを定義できます。また複数の列を結合したものをインデックスにできます。例えば、売上表に顧客コードのインデックス、商品コードのインデックス、さらには、商品コードと顧客コードを一つの仮想コードとして、それにインデックスを付けることができます。
 SQLでは、CREATE INDEX文によりインデックスを定義・登録します。インデックスはRDBMSにより管理されます。

列Cにインデックスを設定すれば、列Cを対象にした検索処理効率は向上します。しかし、行の挿入,削除,変更などを伴う更新処理では、表の更新だけでなく、この表に関するすべてのインデックスを更新するので、処理効率が低下します。そのため、インデックスは検索頻度の大きいものだけに絞るのが適切です。

インデックスに求められる性質

インデックスには、次の性質が望まれます。このような性質をもつものが「優れたインデックス」だといえます。

インデックスの種類

RDBMSではいくつかのインデックス方式が使えますが、ここでは次の3つを説明します。

B-treeインデックス

B+木という木構造を使ったインデックスです。厳密ではありませんが、およそ次のようなものです。
 木構造の節および葉の値は、表の列Cの値であり、それに該当する行のポインタが対応しています。

完全二分木のように、根から各葉までの高さが等しいか差が1段階だけの構造(平衡木)になっています。完全二分木では、節葉の個数(カージナリティ)Nと階層Mの間には、
   N=2M+1   M=log2(N+1)-1
の関係があり、探索に要する計算量のオーダーは、O(log2N) になります。挿入や削除に要する計算量も同じです。
 B+木は、完全二分木とは異なり、節は最大2k+1個(k=1,2、…)の枝をもちます。また、各節はサイズ2kの配列(パケットという)があり、その各要素は葉と同様なものであり、昇順にソートされています。キー項目値が与えられると、根節のパケット要素を調べます。2つの要素の間であれば、そこから子の枝による節で同様に検索を行います。

このような構造ですので、B-treeインデックスでは、上のMの値はさらに小さくなり、計算量も(オーダーは同じですが)小さくなります。

上述の「望まれる性質」を検討すると、B-treeインデックスはすべての性質で、まあまあの成績になります。そのため、特別な状況でない限り、RDBMSではB-treeインデックスを用いるのが適切です。

ハッシュインデックス

ハッシュ関数を使用して検索値Xとキー項目値Kを直接関連つける方式です。ハッシュ関数をfとすれば、K=f(X) で表現できます。
 1回の計算で検索できるので、B+木インデックスより高速に検索ができます。

書物の索引を考えましょう。見出し語はA,B,C、…のような区分で探したほうが効率的ですね。このとき、見出語に相当するのが列Cの値(キー項目値K)で、ページに相当するのが行へのポインタPです。A,B,C、…に相当するのがハッシュ関数による計算値=ハッシュ値です。
 ハッシュインデックスでは、検索値をハッシュ関数でハッシュ値(A,B,C、…)を求め、そのポインタP(ページ)を得ることになります。

ハッシュ値(A,B,C、…)はキー項目値(見出し語)よりも個数(カージナリティ)が少なくなります。そのため、同じハッシュ値(A)であっても異なるキー項目値(見出し語)が存在します。それをシノニム(同音異義語)といい、シノニムが発生することを衝突(collision )といいます。シノニムが発生することがハッシュインデックスの特徴です。

ここで重要なのは「どのようなハッシュ関数にすればよいか」です。「よいハッシュ関数」とは、次のような性質をもつハッシュ関数です。

非常に優れたハッシュ関数であれば、目的のポインタを探索するのに、1回のハッシュ関数の計算と1回の衝突リストの検索で済みます。したがって、計算量のオーダーはO(1)になります。
 しかし、そのようなハッシュ関数を設定するのは困難ですし、キー項目値の特徴により異なります。そのため、RDBMSでは標準的なハッシュ関数をもっていますが、場合によっては自作することもあります。

ハッシュインデックスは、B-treeインデックスと比較して、等号検索効率性では優れ(失敗もある)、増加対応性、インデックス更新効率性はほぼ同等、不等号検索効率性は劣っています(使えないのです)。
 すなわち、ハッシュインデックスは、等値条件(=)での検索には優れています。しかし、キー項目値の大小関係は一切考慮していません。そのため、不等号での条件には使えませんし、ソートもできません。

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

キー項目値のカージナリティが性別のように極端に小さいときに優れたインデックスです。

イメージ的な説明をします。
 インデックスを付けるキー項目が「性別」だとします。キー項目値は「男」と「女」の2種類(カージナリティ=2)です。
 行数と同じサイズの配列「男配列」を作ります。i番目の要素にはi番目の行が対応します。その行が「男」であれば、男配列[i]=1とし、そうでなければ0とします。検索値Xが「男」であれば、男配列[i]=1である表のi番目の列を取り出せばよいのです。
 「女」についても同様にします。
 キー項目が「曜日」だとしたら、7個の配列を作ればよいのです。

ビットマップインデックスの特徴を列挙します。

ビットマップの分割
ここまでの説明では、「全行を一つの配列」にしていました。実際には、行数が多いとき(配列が大きいとき)の検索やインデックス更新処理の高速化のために、行をいくつかのブロックに分割することが行われています。

(補)転置インデックス(Inverted index)

ここまでのインデックスは、レコード(行)を対象とするインデックスですが、転置インデックスは文書の索引などに用いるインデックスです。紙の図書では巻末に索引があり、検索語からそれが記述されているページがわかるようになっています。それと同じに、検索エンジンでは検索語からWebページを知ることができます。そのような用途に有効なインデックスです。

非常に単純な例を示します。
 WebページA、B、Cをスキャンして、次のキーワードのリストができました(何をキーワードとするかが問題ですが、ここでは省略します)。
    A:データベース、インデックス、ビット、ハッシュ、Webページ
    B:インターネット、Webページ、電子メール、ビット、ハッシュ
    C:サーチ、バイナリ、ハッシュ、インデックス
 これから「ビット」を検索語として、それをもつWebページを知るには、このリストを全文検索することになります。実際には対象となるWebページは膨大なので、リストも大量になり非効率的です。

それで、左下のような表にします。縦にキーワード、横にWebページ、存在すれば1、しなければ0とします。上のリストと比較すると、縦と横が逆(転置)になっています。
 しかし、これでは0の部分が多く(実際にはほとんどが0でしょう)無駄です。それで右下のようにまとめます。これが転置インデックスです。キーワードを50音順にソートしておけば、検索語「ビット」の列は簡単に見つけられ、存在するWebページがAとBであることがわかります。

            A B C
    Webページ  1 1 0     Webページ  A,B
    インターネット 0 1 0     インターネット B
    インデックス  1 0 1     インデックス  A,C
    サーチ     0 0 1     サーチ     C
    データベース  1 0 0     データベース  A
    バイナリ    0 0 1     バイナリ    C
    ハッシュ    1 1 1     ハッシュ    A,B.C
    ビット     1 1 0     ビット     A,B
    電子メール   0 1 0     電子メール   B
        転置表             転置インデックス


本シリーズの目次へ