基本情報技術者 2014年 秋期 午前（科目A） 問27

売上表の検索でハッシュインデックスが適切なのはどれか【午前2 解説】

要点まとめ

• 結論: 等価検索（特定の利用者ID＝'1001'）にはハッシュインデックスが最も適しており高速化しやすいです。
• 根拠: ハッシュは等価比較を定数時間で解決し、B+木は順序や範囲検索に強くレンジ／前方一致に適します。
• 差がつくポイント: 前方一致・範囲・順序が必要か、列の選択性（ユニーク性）やDB実装のサポート状況で最適解が変わります。

正解の理由

よくある誤解

• ハッシュは常に速い：等価検索では有利だが、レンジや前方一致、順序付けが必要な検索では無力です。
• 等価検索＝ハッシュが最適とは限らない：低選択性（値の重複が多い）やインデックスのみでの処理（カバリング）の可否でB+木が有利な場合があります。
• 前方一致にもハッシュが使えると思う：ハッシュは文字列の接頭辞検索をサポートせず、前方一致はB+木（文字列順序の範囲検索）で処理します。

解法ステップ

1. クエリの検索条件の種類を判定する（等価比較、範囲比較、前方一致、順序付けなど）。
2. 必要な機能で照合：等価 → ハッシュが候補、範囲・前方一致・ORDER BY → B+木が候補。
3. 列の選択性（ユニークか多重か）とアクセス頻度を確認する。選択性が高ければハッシュのメリットが大きい。
4. DB実装（使用するRDBMS）がハッシュインデックスをどの程度最適化しているか確認する。
5. 必要なら実測（実行計画・コスト比較）で最終判断する。

選択肢別の誤答解説

• ア: 売上金額が1万円以上の売上を検索する。<売上金額>
  → 不適切。条件が「以上」といった不等号・範囲検索なので、B+木のレンジ検索が得意。ハッシュでは範囲を表現できません。
• イ: 売上年月日が今月の売上を検索する。<売上年月日>
  → 不適切。今月分は日付の範囲（開始日〜終了日）検索に相当するため、B+木が適切です。
• ウ: 商品名が‘DB’で始まる売上を検索する。<商品名>
  → 不適切。前方一致（プレフィックス検索）は文字列の順序に基づく区間検索であり、B+木で効率的です。ハッシュは前方一致をサポートしません。
• エ: 利用者IDが‘1001’の売上を検索する。<利用者ID>
  → 適切。これは典型的な等価検索で、ハッシュインデックスが高速に答えを返せます。選択性が低すぎない限り有利です。

補足コラム

• 実際のRDBMS事情：MySQL InnoDBでは主にB+木が使われます。ハッシュインデックスは一部エンジン（MEMORY）や特定状況で提供されます。PostgreSQLにもハッシュインデックスはありますが、実運用ではB-treeが標準的かつ安定していることが多いです。
• 複合インデックス：等価かつ範囲が混在する条件では、先頭列が等価で続く列が範囲ならB+木複合索引で有利になる場合があります。ハッシュは通常、複合キーでも等価の組合せのみを高速化します。
• 選択性の重要性：列の値がほとんど同じ（低選択性）なら、ハッシュでもメリットが小さい。統計情報を見て判断しましょう。

FAQ