応用情報技術者 2017年 春期 午前2 問28

B+木インデックスの範囲走査【午前2解説】

正解の理由

解法ステップ

1. B+木インデックスの性質を確認する：葉ノードは順次連結され、等価検索と連続範囲検索（区間検索）を高速に処理できる。
2. 各選択肢のクエリを「連続レンジか」「除外か」「多くの行にヒットするか」で分類する。
3. 高選択性（対象行が少ない）かつ連続した範囲であればインデックスが有効、除外条件や広範囲・高ヒット率ならインデックス効果が薄いと判断する。
4. 問題の前提（値が多数かつ均等分布、NULLはごく少数）を踏まえ、最も効率的なのは連続範囲検索であると結論付ける。

選択肢別の誤答解説

• ア: メーカコードが1001以外の部品を検索する。
  「1001以外」は除外条件であり、B+木では理論上は「<1001」と「>1001」の2つの連続範囲の走査に分かれます。つまり2つの範囲走査を行う必要があり、除外対象が単一値でも結果はほとんど全表を対象にする可能性が高い（選択性が低い）ため効率は悪くなりがちです。従ってウに比べて性能改善効果は小さいです。
• イ: メーカコードが1001でも4001でもない部品を検索する。
  これはさらに「特定の値を除く」条件で、実際にはほぼ全行が対象になる（全体から極めて少数を除く）ため、インデックスを使っても多数のエントリ走査が必要になり効率が悪い。除外値が少数ならなおさらインデックスでの利益は乏しいです。
• ウ: メーカコードが4001以上、4003以下の部品を検索する。
  連続した小さな区間を指定しており、B+木の葉ノード連結を活かせる典型的な範囲検索です。連続範囲なので最初のキー位置まで移動してから隣接リーフを順次読めば良く、ディスクアクセスが少なくて済みます（このため最も効果が高い）。
• エ: メーカコードがNULL以外の部品を検索する。
  「IS NOT NULL」は対象行が大多数になる可能性が高く、インデックスを使ってもほぼ全行を走査する結果となります。またデータベースによってはNULL値をインデックスに含めない場合があり、その場合はインデックスでNULL以外を取り出す方法が制限されることもあります。いずれにせよ選択性が低い検索です。

よくある誤解

1. 「除外条件はインデックスでは一切使えない」
   誤りです。B+木は両側の範囲（例：<1001 と >1001）を個別に範囲走査できますが、除外条件は通常2つ以上の非連続範囲に分かれるため、範囲走査が複数回必要になり効率が落ちやすい点が問題です。
2. 「インデックスがあれば常に高速」
   インデックス効率は選択性（対象行割合）やアクセスパターンに依存します。ヒット行が表全体の大半を占める場合、フルスキャンの方が高速になることもあります。
3. 「NULLは必ずインデックスに含まれる」
   DBMSによって異なります。NULLを索引に含めない実装があり、その場合は IS NOT NULL の処理が特殊になります。

補足コラム

-- ウ：範囲検索（インデックスが有効）
SELECT * FROM 部品 WHERE メーカコード BETWEEN 4001 AND 4003;

-- ア：除外（2つの範囲走査）
SELECT * FROM 部品 WHERE メーカコード <> 1001;

-- エ：IS NOT NULL（選択性次第）
SELECT * FROM 部品 WHERE メーカコード IS NOT NULL;

FAQ