インデックス、B-treeインデックス、Ｂ+木、ハッシュインデックス、ハッシュ関数、ビットマップインデックス
インデックスとは索引のこと、紙の図書での巻末にある索引のようなものです。あるレコードの格納場所（ポインタ）をそのレコードのキー項目の値を対応させておきます。それがインデックス付けです。
あるキー項目の値（検索値）を与えれば、簡単にその検索値に合致したレコードを取り出せます。また、索引が５０音順などにソートされていれば、その順にレコードを高速に取り出すことができます。それで、インデックスを付けることにより、ファイルが物理的にソートされていなくても、ソートされているのと同様な処理ができるのです。
ここではＲＤＢＭＳを対象にします。インデックスは，原理的には「Ｋ→Ｐ」の対応表
Ｋ：キー項目値
Ｐ：列Ｃの値がＫである行へのポインタ
があり、検索とは、ある検索値Ｘを与えられたとき、ＫがＸである対応表に対応するポインタＰを得る仕組みです。
なお、キー項目値Ｋの個数をカージナリティといいます。
「売上表」の列Ｃ「顧客コード」にインデックスをつけることを例にします。顧客コードには「１２３」や「５４３」などがあり、顧客コードが「１２３」である行（売上データ）は、売上表の、５０番目、６７番目、…にあるものとします（ここでは、５０、６７、…をポインタＰだとします）。
下図は、Ｘ＝１２３のときにｐ＝５０、６７、…を得る処理を示しています。
「Ｋ→Ｐ」の対応表
キー項目値Ｋ ポインタＰ
（列Ｃの値） （行の位置）
検索値Ｘ ┬ ┌───┐ ┌──┬──┬──┐
１２３ ↑ │ … ├→┤… │… │… │
│ │ ├───┤ ├──┼──┼──┤
└───→│１２３├→┤５０│６７│… │
│ ├───┤ ├──┼──┼──┤
│ │ … ├→┤… │… │… │
カージ ├───┤ ├──┼──┼──┤
ナリティ│５４３├→┤… │… │… │
│ ├───┤ ├──┼──┼──┤
↓ │ … ├→┤… │… │… │
┴ └───┘ └──┴──┴──┘
インデックスがないと、表の先頭の行から順に、列Ｃの値とＸを比較する必要があります。平均比較回数は行数／２回になるので、行数が大きいときには、非常に時間がかかります。
列Ｃにインデックスがあれば、上図のように、サイズがカージナリティＮの配列から探せばよいので、比較回数はかなり減少します。
インデックスの要点は、検索値Ｘ＝キー項目値Ｋとなる位置を効率よく探すことにあります。
上のような対応表を用いたのでは、Ｋを探すための効率が悪いので、後述する「B-treeインデックス」や「ハッシュインデックス」のような工夫が使われます。
一つの表に複数のインデックスを定義できます。また複数の列を結合したものをインデックスにできます。例えば、売上表に顧客コードのインデックス、商品コードのインデックス、さらには、商品コードと顧客コードを一つの仮想コードとして、それにインデックスを付けることができます。
ＳＱＬでは、CREATE INDEX文によりインデックスを定義・登録します。インデックスはＲＤＢＭＳにより管理されます。
列Ｃにインデックスを設定すれば、列Ｃを対象にした検索処理効率は向上します。しかし、行の挿入，削除，変更などを伴う更新処理では、表の更新だけでなく、この表に関するすべてのインデックスを更新するので、処理効率が低下します。そのため、インデックスは検索頻度の大きいものだけに絞るのが適切です。
インデックスには、次の性質が望まれます。このような性質をもつものが「優れたインデックス」だといえます。
ＲＤＢＭＳではいくつかのインデックス方式が使えますが、ここでは次の３つを説明します。
Ｂ+木という木構造を使ったインデックスです。厳密ではありませんが、およそ次のようなものです。
木構造の節および葉の値は、表の列Ｃの値であり、それに該当する行のポインタが対応しています。
完全二分木のように、根から各葉までの高さが等しいか差が１段階だけの構造（平衡木）になっています。完全二分木では、節葉の個数（カージナリティ）Ｎと階層Ｍの間には、
Ｎ＝２Ｍ＋１ Ｍ＝log2（Ｎ＋１)－１
の関係があり、探索に要する計算量のオーダーは、Ｏ(log2Ｎ) になります。挿入や削除に要する計算量も同じです。
Ｂ+木は、完全二分木とは異なり、節は最大２ｋ＋１個（ｋ＝１，２、…）の枝をもちます。また、各節はサイズ２ｋの配列（パケットという）があり、その各要素は葉と同様なものであり、昇順にソートされています。キー項目値が与えられると、根節のパケット要素を調べます。２つの要素の間であれば、そこから子の枝による節で同様に検索を行います。
このような構造ですので、B-treeインデックスでは、上のＭの値はさらに小さくなり、計算量も（オーダーは同じですが）小さくなります。
上述の「望まれる性質」を検討すると、B-treeインデックスはすべての性質で、まあまあの成績になります。そのため、特別な状況でない限り、ＲＤＢＭＳではB-treeインデックスを用いるのが適切です。
ハッシュ関数を使用して検索値Ｘとキー項目値Ｋを直接関連つける方式です。ハッシュ関数をｆとすれば、Ｋ＝ｆ(Ｘ) で表現できます。
１回の計算で検索できるので、Ｂ+木インデックスより高速に検索ができます。
書物の索引を考えましょう。見出し語はＡ，Ｂ，Ｃ、…のような区分で探したほうが効率的ですね。このとき、見出語に相当するのが列Ｃの値（キー項目値Ｋ）で、ページに相当するのが行へのポインタＰです。Ａ，Ｂ，Ｃ、…に相当するのがハッシュ関数による計算値＝ハッシュ値です。
ハッシュインデックスでは、検索値をハッシュ関数でハッシュ値（Ａ，Ｂ，Ｃ、…）を求め、そのポインタＰ（ページ）を得ることになります。
ハッシュ値（Ａ，Ｂ，Ｃ、…）はキー項目値（見出し語）よりも個数（カージナリティ）が少なくなります。そのため、同じハッシュ値（Ａ）であっても異なるキー項目値（見出し語）が存在します。それをシノニム（同音異義語）といい、シノニムが発生することを衝突（collision ）といいます。シノニムが発生することがハッシュインデックスの特徴です。
ここで重要なのは「どのようなハッシュ関数にすればよいか」です。「よいハッシュ関数」とは、次のような性質をもつハッシュ関数です。
非常に優れたハッシュ関数であれば、目的のポインタを探索するのに、１回のハッシュ関数の計算と１回の衝突リストの検索で済みます。したがって、計算量のオーダーはＯ(1)になります。
しかし、そのようなハッシュ関数を設定するのは困難ですし、キー項目値の特徴により異なります。そのため、ＲＤＢＭＳでは標準的なハッシュ関数をもっていますが、場合によっては自作することもあります。
ハッシュインデックスは、B-treeインデックスと比較して、等号検索効率性では優れ（失敗もある）、増加対応性、インデックス更新効率性はほぼ同等、不等号検索効率性は劣っています（使えないのです）。
すなわち、ハッシュインデックスは、等値条件（＝）での検索には優れています。しかし、キー項目値の大小関係は一切考慮していません。そのため、不等号での条件には使えませんし、ソートもできません。
キー項目値のカージナリティが性別のように極端に小さいときに優れたインデックスです。
イメージ的な説明をします。
インデックスを付けるキー項目が「性別」だとします。キー項目値は「男」と「女」の２種類（カージナリティ＝２）です。
行数と同じサイズの配列「男配列」を作ります。ｉ番目の要素にはｉ番目の行が対応します。その行が「男」であれば、男配列[ｉ]＝１とし、そうでなければ０とします。検索値Ｘが「男」であれば、男配列[ｉ]＝１である表のｉ番目の列を取り出せばよいのです。
「女」についても同様にします。
キー項目が「曜日」だとしたら、７個の配列を作ればよいのです。
ビットマップインデックスの特徴を列挙します。
ビットマップの分割
ここまでの説明では、「全行を一つの配列」にしていました。実際には、行数が多いとき（配列が大きいとき）の検索やインデックス更新処理の高速化のために、行をいくつかのブロックに分割することが行われています。
ここまでのインデックスは、レコード（行）を対象とするインデックスですが、転置インデックスは文書の索引などに用いるインデックスです。紙の図書では巻末に索引があり、検索語からそれが記述されているページがわかるようになっています。それと同じに、検索エンジンでは検索語からＷｅｂページを知ることができます。そのような用途に有効なインデックスです。
非常に単純な例を示します。
ＷｅｂページＡ、Ｂ、Ｃをスキャンして、次のキーワードのリストができました（何をキーワードとするかが問題ですが、ここでは省略します）。
Ａ：データベース、インデックス、ビット、ハッシュ、Ｗｅｂページ
Ｂ：インターネット、Ｗｅｂページ、電子メール、ビット、ハッシュ
Ｃ：サーチ、バイナリ、ハッシュ、インデックス
これから「ビット」を検索語として、それをもつＷｅｂページを知るには、このリストを全文検索することになります。実際には対象となるＷｅｂページは膨大なので、リストも大量になり非効率的です。
それで、左下のような表にします。縦にキーワード、横にＷｅｂページ、存在すれば１、しなければ０とします。上のリストと比較すると、縦と横が逆（転置）になっています。
しかし、これでは０の部分が多く（実際にはほとんどが０でしょう）無駄です。それで右下のようにまとめます。これが転置インデックスです。キーワードを５０音順にソートしておけば、検索語「ビット」の列は簡単に見つけられ、存在するＷｅｂページがＡとＢであることがわかります。
Ａ Ｂ Ｃ
Ｗｅｂページ １ １ ０ Ｗｅｂページ Ａ，Ｂ
インターネット ０ １ ０ インターネット Ｂ
インデックス １ ０ １ インデックス Ａ，Ｃ
サーチ ０ ０ １ サーチ Ｃ
データベース １ ０ ０ データベース Ａ
バイナリ ０ ０ １ バイナリ Ｃ
ハッシュ １ １ １ ハッシュ Ａ，Ｂ．Ｃ
ビット １ １ ０ ビット Ａ，Ｂ
電子メール ０ １ ０ 電子メール Ｂ
転置表 転置インデックス