平成27年度 秋期 午前 問26

✓ これが正解ウハッシュインデックス

解説

ハッシュ方式は違うキーが同じ位置に写ることがあります。

インデックスにはいくつかの方式があり、それぞれ格納位置の決め方が違います。設問はキーの値をもとにして格納位置を計算する方式で、異なる値でも同じ位置になり得るものを探しています。ここで問われている性質は衝突と呼ばれ、値を短い範囲の数へ写す関数を通す方式にだけ現れます。写す先の空間は元のキーの空間より狭いので、原理的に異なる値が同じ位置に写る場合があるためです。見分けるときの軸は二つです。一つ目は、位置決めが計算で行われるのか、木構造の探索で行われるのか、単語ごとの逆引き表で行われるのかという方式の違いです。二つ目は、その方式で衝突が起こり得るかどうかという性質です。二つを重ねると、計算方式で衝突が起こり得るものが一つに絞られ、それが正解にあたります。

ほかの選択肢はなぜ違うのか

• アB+木インデックス：B＋木インデックスは、木構造をたどってキーの位置を探し当てる方式です。同じキーは同じ場所に置かれますが、異なるキーが同一の格納位置に写ることは仕組み上ありません。範囲検索を効率よく扱えるのが利点です。
• イ転置インデックス：転置インデックスは、文書に含まれる単語ごとに、その単語が出現する文書の一覧を持つ形の索引です。キー値から格納位置を算出する方式ではないので、この設問の性質そのものが当てはまりません。
• エビットマップインデックス：ビットマップインデックスは、キーの取り得る値ごとに、その値をもつ行の位置を1と0の並びで表す方式です。異なるキー値ごとに独立した並びを持つため、同一の算出結果に写ることは起こりません。