解説

$B^+$木インデックスとビットマップインデックスの比較解説

インデックスの特徴

$B^+$木インデックス

• 構造: 平衡木構造で、データは木の葉に連結リストの形で格納される。
• 用途: 範囲検索や、値に基づく順序が必要な場合に適している。
• 操作: 単一値検索や範囲検索（BETWEEN, <, >など）が高速。
• 条件: 一般的に、値の種類が多い列（高カーディナリティ）に有効。

ビットマップインデックス

• 構造: 各異なる値ごとにビットベクトルを持ち、該当する行を1で示す。
• 用途: 少数の異なる値（低カーディナリティ）を持つ列に適している。
• 操作: AND、OR、NOTなどビット演算による複数条件検索が高速。
• 特徴: 大量のデータに対してもビット演算で高速に複雑な条件処理が可能。

選択肢の評価

ア: AND や OR 操作だけで行える検索は$B^+$木インデックスの方が有効である。

• 誤り
  AND や OR といった論理演算による複数条件検索は、ビットマップインデックスが特に有効です。ビットマップはビット演算で高速に処理可能で、一方$B^+$木では複数インデックスの統合処理にコストがかかります。

イ: BETWEEN を用いた範囲指定検索はビットマップインデックスの方が有効である。

• 誤り
  BETWEEN や範囲指定には$B^+$木インデックスが適しています。ビットマップは範囲をビット単位で明示的に表現しにくく、範囲検索には劣ります。

ウ: NOT を用いた否定検索は$B^+$木インデックスの方が有効である。

• 誤り
  否定検索でもビットマップインデックスは有効です。ビット単位のNOT演算で高速に否定条件を計算できます。$B^+$木では否定条件を満たすレコードの検索は困難であり遅くなりがちです。

エ: 少数の異なる値をもつ列への検索はビットマップインデックスの方が有効である。

• 正しい
  低カーディナリティの列ではビットマップインデックスが圧倒的に効率的です。ビットマップのビット数が少なく、かつビット演算による高速な条件検索が可能なためです。

まとめ

数式補足

• 複数条件のAND検索:

• OR検索:

• NOT検索: