応用情報技術者 2011年 秋期 午前2 問32

B+木インデックス【午前2解説】

正解の理由

解法ステップ

1. インデックス（B+木）の特徴を思い出す：順序付けられたキー、葉ノードの連結、範囲走査が得意。
2. 各選択肢を「点検索（＝特定値）」「否定条件（＝〜以外）」「範囲検索」「NULL判定」のどれかに分類する。
3. B+木が最も効果を発揮するのは「範囲検索」であると判断する。
4. NULLの扱いについてはDBMS差があることを念頭に置き、問題条件（ごく少数のNULL）と照らして影響が小さいことを確認する。
5. よって範囲を指定する選択肢（ウに該当するもの）が正解であると結論付ける。

選択肢別の誤答解説

• ア（特定の値を除外する検索）: 「特定の値以外」を選ぶ条件は除外条件（NOT 等）になり、該当行が多数になる可能性が高い。インデックスで該当行を１つずつ拾っていくよりもテーブル全体の走査（フルスキャン）が効率的になることが多い。
• イ（複数の特定値を除外する検索）: 複数値を排除する否定条件も同様に広範囲を対象にするためインデックス効果は小さい。インデックスの有無にかかわらず多数の行を読む必要がある。
• ウ（メーカコードの連続範囲を指定する検索）: B+木の葉ノードは順次アクセスできるため、範囲の先頭を特定してから隣接する葉を順に辿るだけで済む。ランダムI/Oを最小化でき、明確に有利。
• エ（NULL以外を検索）: NULL以外を選ぶ条件は「ほとんどすべての行」を選ぶことになりがちで、インデックスで多数のエントリを走査するとかえって効率が悪い。さらに、NULL の索引への含有は DBMS により異なるため動作が変わる点にも注意（ただし本問では NULL はごく少数なので全体影響は小さい）。

よくある誤解

• 誤解1: 「インデックスは常に検索を高速化する」
  → インデックスは選択性（検索結果が少ないこと）が高い場合に有効。対象が多数ある否定条件や「ほぼ全部」を選ぶクエリではフルスキャンの方が速いことがある。
• 誤解2: 「NULLはどのDBでもインデックスに含まれない」
  → DBMS によって扱いが異なる（例: Oracle は全て NULL のキーを索引化しないことがあるが、MySQL/PostgreSQL は NULL を含む場合がある）。少数の NULL であれば性能影響は小さい。

補足コラム

• B+木とハッシュインデックスの比較：ハッシュは等価検索（＝特定の値を探す）では非常に速いが、範囲検索には対応できない。一方 B+木は等価検索にも範囲検索にも向いているため汎用性が高い。
• カバリングインデックス：検索に必要な列がすべてインデックスに含まれていればテーブル本体アクセスが不要となりさらに高速化する。今回のようにインデックスが対象列だけで、かつ行全体が必要なら追加のテーブルアクセス（ルックアップ）が発生する点に注意。

FAQ