【データベース】ハッシュインデックスとビットマップインデックスを理解する

Posted at 2024-09-11

はじめに

今回は「達人に学ぶDB設計徹底指南書第2版」の6章の演習問題でビットマップインデックス、ハッシュインデックス」について調べたことをまとめていきます！

B-treeインデックスについてはこちら

ビットマップインデックスは、検索対象のカラムに対して、その値に対応するビットマップを使用してレコードを特定するインデックス。
主にデータウェアハウス環境で使用される

製品の在庫状態と配送地域
オンラインショップのデータベースで、製品の「在庫状態」と「配送地域」に対してビットマップインデックスを使用して、レコードを特定する場合。
カラムには「在庫状態」（在庫あり／在庫なし）と「配送地域」（国内／海外）が含まれる。

以下のような製品データがあるとする(あんまり在庫ありとか、国内とかベタ書きで入れないと思いますが、わかりやすくするためそうしてます笑)

このデータに対して、「在庫状態」と「配送地域」に基づくビットマップインデックスを作成する

例1: 国内配送または在庫ありの製品を検索

「在庫あり」と「国内配送」のビットマップをOR演算
- 在庫あり = 1 0 1 0 1
- 国内配送 = 1 0 1 1 0
- OR演算結果 = 1 0 1 1 1
- → 結果: 製品ID 1、3、4、5 が該当

カーディナリティの低いカラムに対して有効
取りうる値の種類が少ないカラム（今回の在庫状態や性別、血液型など）に対して高速に機能する。
カーディナリティの低い　= 取りうる値の種類が少ない
OR演算子や否定系の検索にも対応
OR 演算子や NOT 演算子を使ったクエリでも、インデックスが適用され、効率的な検索が可能。(B-treeではインデックスが効かない)
IS NULLにも対応
B-treeインデックスと異なり、ビットマップインデックスは IS NULL に対してもインデックスを利用できる。(インデックス内にNULLも保持するため)
ビットデータはサイズが小さいため、インデックスのサイズが小さくなる

データの更新、削除、追加に時間がかかる
更新頻度の高いシステムでは、ビットマップインデックスのパフォーマンスが低下する。
テーブルのデータが更新されるたびに、インデックスのビット値も更新する処理を行わなければならないため、更新時の性能が悪い。
そのため、頻繁にデータ更新が行われるタイプのシステム(OLTP)で利用するには性能的なリスクが大きい

ハッシュインデックスは、ハッシュ関数を使用して検索対象のキーと、レコードが格納されているページを直接結びつけるインデックス。
たとえば、従業員番号などをハッシュ関数に入力し、ハッシュ値によって該当するページにアクセスしてレコードを取得する。

従業員番号をハッシュ関数にかけたとき、その戻り値がページの参照先となり、データがそのページ(ページについては下記に記載)に格納される。検索する際には、キーを使って同じハッシュ関数で戻り値を計算し、その戻り値が示すページにアクセスして、該当するレコードを探す。

特定のキーによる検索(等値検索)が非常に高速
大量のデータから特定のキーを使ってデータを検索する場合、ディスクアクセスを最小限にすることで非常に高速にデータを取得できる。

オーバーフローページの発生
ハッシュインデックスでページがいっぱいになった場合、新しいページ（オーバーフローページ）が作成され、チェーン状にリンクされる。これにより、ディスクアクセスが増え、パフォーマンスが低下する。
例
ページAがいっぱいの場合、ページBを作成してデータを格納し、ページAにはページBへの参照を保持する。
結果として、複数のページを辿る必要があり、ディスクI/Oが増加する。
ハッシュ関数の選択が重要
均一にページを割り振るためには、適切なハッシュ関数を選ぶ必要がある。データの量や構造に合わないハッシュ関数を選ぶと、パフォーマンスが低下する。(選び方までは、調べられてないので不明)
データ量の予測が難しい環境には不向き
ハッシュ関数を選択するにはデータ量を予測する必要がある。そのため予測が難しい場合は向いていない。
等値検索以外ではインデックスが利用できない
ハッシュ関数で変換されたハッシュ値は、元の値の順序関係を維持していないため。

ページは、データベースがディスク上でデータを格納・管理するための基本的な単位。データベースではデータをページ単位で管理し、効率的にデータの保存やアクセスを行う。

データベースは、ディスク上のデータをページ単位で保存・管理する。特定のページに空きがない場合は、他のページにデータを格納し、そのページに参照情報を保持する。これにより、データが分散され、複数ページにわたって格納されることになる。