ビットマップインデックス VS ハッシュインデックス

MySQLで利用される「ビットマップインデックス」と「ハッシュインデックス」の長所と短所について解説します。 B-treeインデックス以外にも、データベースには特定の用途で高いパフォーマンスを発揮するインデックスが存在します。 それぞれの特徴を理解し、使い分けることが重要です。

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

MySQLの標準的なストレージエンジン（InnoDBやMyISAM）では、ユーザーが明示的にビットマップインデックスを作成することはできません。 これは主に、データウェアハウス（DWH）製品でよく利用される特殊なインデックスです。 ビットマップインデックスは、カラムの各値に対して、その値を持つ行を示すビットのマップ（0と1の羅列）を作成します。

例：性別カラム（'男性', '女性'）

この場合、以下のようなビットマップが作成されます。

• 男性のビットマップ: 1001
• 女性のビットマップ: 0110

長所

• カーディナリティの低いカラムに非常に強い: 性別、血液型、都道府県など、値の種類（カーディナリティ）が非常に少ないカラムの検索が高速です。
• 複雑な検索条件に強い: 複数のビットマップを組み合わせたAND、OR、NOTといった論理演算が非常に高速です。例えば、「東京都に住む男性」のような検索は、それぞれのビットマップを掛け合わせるだけですぐに結果がわかります。
• ストレージ効率が良い: データが少ない場合は、B-treeインデックスよりも少ないディスク領域で済みます。

短所

• 更新処理に非常に弱い: 1行でもデータの追加・更新・削除（INSERT/UPDATE/DELETE）が発生すると、多くのビットマップをロックして再計算する必要があり、コストが非常に高くなります。そのため、頻繁にデータが更新されるシステム（OLTP）には全く向いていません。
• カーディナリティの高いカラムには不向き: ユーザーIDのように値の種類が多い（カーディナリティが高い）カラムでは、ビットマップの種類が膨大になり、逆に非効率になります。
• 同時実行性が低い: 更新時のロック範囲が広くなるため、多くのユーザーが同時に書き込みを行うようなシステムでは性能が著しく低下します。

ハッシュインデックス

ハッシュインデックスは、キー値をハッシュ関数に通して得られたハッシュ値と、データ行へのポインタをペアで格納します。 MySQLでは、MEMORYストレージエンジンで明示的に作成できます。 また、InnoDBには アダプティブハッシュインデックス（AHI） という、内部で自動的に作成・管理されるハッシュインデックスの仕組みがあります。

長所

等価検索（= や IN）が非常に高速: ハッシュ値から直接データを探し当てるため、B-treeインデックスのようにツリーをたどる必要がなく、計算量がO(1)（定数時間）となります。 データ量に関わらず、ほぼ一定の速度で検索できます。

短所

• 範囲検索や順序付けができない: ハッシュ値は元の値の大小関係を保持していないため、>、<、BETWEENといった範囲検索や、ORDER BYによるソートには利用できません。これらの操作では、結局テーブル全体をスキャンする必要があります。
• 部分一致検索ができない: LIKE 'A%' のような前方一致検索などには利用できません。キー全体が完全に一致している必要があります。
• ハッシュの衝突（コリジョン）: 異なるキー値から同じハッシュ値が生成されること（衝突）があります。衝突が多発すると、同じハッシュ値を持つデータを線形探索する必要があるため、パフォーマンスが低下します。

まとめ

このように、それぞれのインデックスには得意・不得意があります。MySQLではほとんどの場合、B-treeインデックスが最適ですが、特定の状況下では他のインデックスの概念が役立つこともあります。 特にInnoDBのアダプティブハッシュインデックスは、MySQLが内部でクエリを高速化してくれている良い例と言えます。