ハッシュインデックス

ハッシュインデックスは、検索キーへハッシュ関数を適用してバケット位置を求め、同じ値かを比較して該当行へ到達する索引です。主に完全一致検索に適します。

■ 試験で押さえるポイント

• キー分布が均等でバケット数が適切なら、平均的には少ない回数で等価検索できます。ハッシュ値が同じ異なるキーは衝突するため、バケット内で元キーを比較します。

• ハッシュ値はキーの大小順を保たないため、<、>、BETWEEN、最小値、ORDER BY、前方一致などの範囲・順序処理には通常利用できません。

• 特定値へ偏ると一バケットが長くなり性能が下がり、件数増加時にはバケット分割や再ハッシュが必要です。最悪計算量は常に$O(1)$ではありません。

• B-treeは一致と範囲の双方へ汎用的に使え、ハッシュは等価条件へ特化します。DBMSごとに永続性、同時実行、対応演算の実装差があります。

■ 選択肢での判断ポイント

WHERE キー=値ならハッシュが候補、BETWEENやORDER BYならB-treeが候補です。ハッシュ値衝突が絶対にないという説明を除きます。

例: 社員番号=12345はhash(12345)で求めたバケットだけを調べられますが、社員番号10000～19999は連続バケットにならないため範囲走査できません。