基本情報 平成26年度 秋期 問27｜テクノロジ系に関する問題

答えは d「利用者IDが‘1001’の売上を検索する。＜利用者ID＞」 です。

「ハッシュインデックス」はピンポイントで値を当てに行く検索が得意。

• ハッシュインデックス向き：「ID＝1001の人を探して！」のような完全一致検索
• B⁺木インデックス向き：「○○円以上、今月分、‘DB’で始まる」のような範囲・前方一致検索

👉 覚え方：「ハッシュ＝一発検索／B⁺木＝範囲探し」。

ほかの選択肢：a 1万円以上（範囲）／b 今月（範囲）／c ‘DB’で始まる（前方一致）は、どれも値の大小や並び順を使う検索なのでB⁺木が向く。

なぜこれが正解か

正解は d（利用者IDが‘1001’の売上を検索する＝完全一致検索）。

• ハッシュインデックス: キーをハッシュ関数で計算しバケットを特定→等価検索（=）に強くO(1)
• B+木インデックス: ノードを比較しながら辿る→範囲検索・前方一致・ソート・等価検索に強くO(log n)

「利用者ID = 1001」のような完全一致検索はハッシュインデックス向き。一方「以上/以下」「期間検索」「LIKE 'DB%'」はB+木向き。

各選択肢の解説

• a 売上金額1万円以上：範囲検索→B+木向き。
• b 売上年月日が今月：範囲検索→B+木向き。
• c 商品名DB始まり：前方一致→B+木向き。
• d 利用者ID=1001：完全一致→ハッシュインデックス向き（正解）。

覚え方・ひっかけ注意

「ハッシュ＝等価のみ最速、B+木＝範囲・順序・前方一致まで万能だが等価はO(log n)」。ハッシュインデックスは順序を保持しないため `ORDER BY` の支援にならず、`<`/`>`/`BETWEEN`/`LIKE`では使えない。MySQLのMEMORY/InnoDBやPostgreSQLでハッシュインデックスが利用可能。ただしB+木の方が汎用性が高く実務ではB+木が主流。

理論的背景

データベースのインデックス構造は主に3系統:

• B+木（B+ Tree）: 平衡多分木、葉ノードが線形リンクで連結。範囲検索・順序走査・等価検索全てに対応、O(log n)。RDBMSのデフォルトインデックス。
• ハッシュ（Hash）: ハッシュ関数で直接バケット位置を計算、O(1)。等価検索特化、衝突時はチェーン法/オープンアドレス法。
• ビットマップ: 各値の存在を1ビットで表現、低カーディナリティ（性別・状態フラグ等）に最適、ANDオペレーションが高速。DWHで使用。
• 他: 全文検索インデックス（転置インデックス、N-gram）、GiST/GIN（PostgreSQL）、R-tree（空間データ）、LSM-Tree（NoSQL/書込み多）等。

ハッシュインデックスの理論的計算量はO(1)だが、衝突によるバケット内チェーン走査・リハッシュコストがあり、実効性能はB+木のO(log n)と僅差な場合もある。

実務での使われ方

Oracle/PostgreSQLでは標準的にB+木を使い、ハッシュインデックスは限定的用途。MySQL InnoDBはAdaptive Hash Indexで頻繁にアクセスされるB+木の一部を自動的にハッシュ化する最適化を持つ。SAP HANAやインメモリDB（Redis、Memcached）はハッシュテーブルが中心構造。

クエリオプティマイザは統計情報（カーディナリティ、ヒストグラム、相関）に基づきインデックス選択を決定。カーディナリティが高い（=値の種類が多い）列ほどB+木/ハッシュインデックスの選択性（selectivity）が高く有効。逆に低カーディナリティ列（性別、Yes/No）はビットマップインデックスが効率的。

ハッシュインデックスの弱点: ①順序保持なし→ORDER BY/範囲検索NG、②ハッシュ衝突時の性能劣化、③インデックスサイズが固定的でテーブル拡張時にリハッシュ必要、④部分一致LIKE使用不可。これらの理由でB+木が汎用デフォルトとなっている。

試験での位置づけ

FE/AP/DBスペシャリストのデータベース分野で頻出。①インデックス構造の比較、②選択性とカーディナリティ、③クエリオプティマイザの動作、④インデックスの設計とメンテナンス（再編成、断片化）、が主要論点。本問はB+木とハッシュの使い分けを問う基本問題。

選択肢の発展補足

LSM-Tree（Log-Structured Merge Tree）はLevelDB、RocksDB、Cassandra、HBase、ScyllaDB等で採用される書込み最適化構造。順次書込み→定期マージで構築され、書込み多のNoSQL/分散DB向き。読込み時はBloom Filterで存在判定を高速化。

ハッシュインデックスは分散KVS（Redis、DynamoDB、Cassandra）でパーティション/シャーディングのキー決定にも使われる。Consistent Hashing（一貫性ハッシュ）はノード追加削除時のリハッシュコストを最小化する手法で、メモリキャッシュやP2Pシステムで広く使われる。本問のような「インデックス選択」問題は、クエリパターンと構造特性のマッチングを問うものだが、実務ではEXPLAIN/EXPLAIN ANALYZEで実行計画を確認しつつ調整するのが定石。