応用情報技術者 2010年 春期 午前2 問30

インデックス方式のうち、キー値を基に算出して格納位置を求めるとき、異なったキー値でも同一の算出結果となる可能性があるものはどれか【午前2 解説】

要点まとめ

• 結論：異なるキー値が同じ算出結果になる可能性があるのはハッシュインデックスです。
• 根拠：ハッシュ関数はキー値を固定長のハッシュ値に変換し、衝突（コリジョン）が起こることがあるためです。
• 差がつくポイント：B+木やビットマップは衝突を前提とせず、転置インデックスは全文検索用で衝突の概念が異なります。

正解の理由

よくある誤解

解法ステップ

1. インデックス方式の特徴を整理する。
2. ハッシュインデックスはキー値をハッシュ関数で変換し、衝突が起こる可能性があることを確認。
3. B+木はキー値を順序付けて格納し、衝突がないことを理解。
4. 転置インデックスは全文検索用で衝突の概念が異なることを把握。
5. ビットマップインデックスは属性の有無をビットで表現し、衝突の概念がないことを確認。
6. 以上から、衝突が起こる可能性があるのはハッシュインデックスであると判断する。

選択肢別の誤答解説

• ア: B+木インデックス
  キー値を順序付けて格納し、衝突は発生しません。
• イ: 転置インデックス
  文書検索用で、キー値の衝突という概念は適用されません。
• ウ: ハッシュインデックス
  ハッシュ関数の性質上、異なるキー値が同じハッシュ値になる衝突が起こり得ます。
• エ: ビットマップインデックス
  属性の有無をビットで表現し、衝突の概念はありません。

補足コラム

FAQ