基礎から理解するデータベースのしくみ（9）

データの格納方法を知ろう(4)

RDBMSが備えるさまざまな高速化手法

　RDBMSは，ここまで説明してきた基本的なデータの格納のしかたや操作方法に加え，高速化のための手法をいろいろ用意しています。Part2の最後に，これらの手法をざっと紹介しておきましょう。

●ハッシュ・インデックス

　キャッシュ・バッファのサイズや使われ方にもよりますが，一般にBツリー・インデックスを使って巨大なデータベースにアクセスする際には，ルート・ノードだけがキャッシュ・バッファにあるのが普通です。そのため，レコードにたどりつくまでにブランチ・ノード，リーフ・ノード，データベース・レコードと何回もディスクにアクセスしなければなりません。これを1回のアクセスでレコードを取得できるようにしよう，というのがハッシュ・インデックスです。

　ハッシュ・インデックスでは，ハッシュ関数と呼ぶ関数を使って，検索に使用するキーとレコードを含むページを直接関係付けます（図9[拡大表示]）。例えば，従業員番号をキーとする場合，従業員番号を適当な数で割った余りを返すような関数をハッシュ関数として選び，関数の戻り値（ハッシュ値といいます）が指すページにそのキーを持つレコードを格納しておきます。こうしておけば，ある従業員番号を持つレコードを検索する際には，ハッシュ関数で特定したページを読み込むだけで済むようになります。

　ただし，Bツリーの場合と違って，範囲検索には利用できません。したがって，キーの順番にレコードをシーケンシャル（逐次的）に読み込んでいくような検索には向いていません。

　加えて，Bツリーではインデックスの作成，削除をテーブルの作成とは独立にできるのに対し，ハッシュ・インデックスではハッシュ関数の選び方がテーブルの構造に影響します。したがって，テーブル作成の時点で，どのようなハッシュ関数を使ってインデックスを作成するかを決めておく必要があります。

　さらに，通常のテーブルでは，レコードの追加できる空き領域がない場合にはエクステントを追加して割り当ていきますが，ハッシュ・インデックスを使う場合はこうしたことはしません。ハッシュ値に対応するページにレコードを格納するだけの空き領域がない場合は，新たにオーバーフロー用のページを割り当ててレコードを格納します。この場合は，ページのチェーン（連鎖）が発生するために読み出しに複数回のディスク入出力が必要になり，パフォーマンスが低下します。

　したがってハッシュ・インデックスを使う場合には，あらかじめレコードの数を見積もり，データをロードする前に十分なエクステントを割り当てておく必要があります。したがって，扱うデータ量がある程度決まっているOLTP＊23システムなどに向いています。逆に，格納するデータの量が決まっていないような場合には向きません。

　ハッシュ・インデックスを使う場合，レコードは事前に割り当てたページのうち，ハッシュ関数によって定められる場所に直接ロードされます。異なるキーの値が同じハッシュ値を返す場合は，それらのレコードは同じページに格納します。ページのサイズはすべて同じですから，各ページに格納されるレコードの数はなるべく均一になるようにしたほうがディスクの領域を節約できるわけです。

　そのため，大規模なデータベースの場合は特に，多量のキーをすべてのページになるべく均一に割り振るようなハッシュ関数を見つけることが重要になります。キーの性質があらかじめわかっている場合は，RDBMSが備えている内部ハッシュ関数を使うよりも，自前でハッシュ関数を用意したほうが均一な分布を得られることもあります。

●レコード・クラスタリング

　特定のキーに対するハッシュ値にしたがって複数のテーブルのレコードを同一ページに格納することで，さらに効率の良いアクセスが可能になることもあります。これをレコード・クラスタリングと呼びます。

　（図10[拡大表示]）はレコード・クラスタリングの例です。従業員テーブル（emp）は従業員番号（eno）が主キーなので，各enoに対してレコードが1件だけ存在します。対して，従業員の経歴を記録するテーブル（emp_hist）ではenoは外部キー＊24なので，同じenoを持つレコードが複数存在する可能性があります。レコード・クラスタリングでは，emp，emp_histテーブルの両方に対して，enoに同一ハッシュ関数を適用してレコードを格納するページを決めます。したがって，同じenoを持つ複数テーブルのレコードが一つのページに存在することになります。

　このとき例えば

SELECT * FROM emp, emp_hist
WHERE emp.eno=emp_hist.eno AND
emp.eno=125;

というSQL文を実行したとしましょう。まずemp.eno＝125の条件によってempテーブルを含むページを検索して，データを読み込みます。次に，emp.eno＝emp_hit.enoによりemp_histのレコードが読み込まれます。このページはさきほどの検索ですでにキャッシュ・バッファ上に読み込んでいるため，emp_histテーブルをアクセスする際に新たなディスク・アクセスは発生しません。

　ちなみに，レコード・クラスタリングはハッシュ・インデックスに特有の方法というわけではありません。Bツリー・インデックスでも使えます。この場合は，キーの値ごとにレコードをまとめて格納することになります。ただし，Bツリーでは複数回のディスク入出力が必要になるため，検索速度は低下します。

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

　ビットマップ・インデックスはデータ・ウエアハウス＊25などで，取り得る値の数が少ない＊26フィールドに対して複雑な検索を行う場合に適しているインデックスの手法です。OracleをはじめいくつかのRDBMSに実装されています。

　ビットマップ・インデックスは，キーの取り得る値の一つひとつに対してビットマップ（ビット列）を用意します。例として，市販の音楽用CDの情報を格納するテーブルがあり，そのフィールドの一つに「ジャンル」があったとしましょう。ジャンルは「クラシック」「ロック」「ジャズ」のいずれかの値をとるものとします。この場合，クラシック，ロック，ジャズのそれぞれについてビットマップを用意します（図11[拡大表示]）。

　ビットマップの各ビットは，レコードの位置（ROWID）に対応し，そのビットがオンなら対応するレコードのフィールドがその値であることを示します。例えば図11の場合，クラシックのビットマップを見ると，m番目とn番目のビットがオンになっているので，ジャンル・フィールドの値がクラシックであるのはm番目とn番目のレコードであることがわかります。

　ビットマップ・インデックスの特徴は，WHERE句にANDやORなどが含まれる検索を高速に実行できることです。例えば，音楽用CDのテーブル（cd）から，ジャンルを表すフィールド（genre）の値がクラシックかロックであるレコードを取り出す，

SELECT * FROM cd
WHERE genre = 'クラシック'
OR genre = 'ロック'

のような検索なら，クラシックのビットマップとロックのビットマップで，ビット単位のORをとるだけで求めるレコードの集合を得ることができます。ビットマップの各ビットが直接ROWIDに対応するため，Bツリーのようにノードをたどっていく必要もありません。

　複数のフィールドに対してビットマップ・インデックスを定義することも可能です。例えば「顧客」テーブルの「性別」「職業」「趣味」の各フィールドにビットマップ・インデックスを作成しておけば，「男性の会社員で趣味がドライブであるレコードを取り出す」といった検索も簡単に実行できます。このほか，1レコードが各キーに対して1ビットしかディスクを占有しないため，インデックスに必要なディスク容量が少なくてすむのもメリットと言えるでしょう。

　半面，ビットマップ・インデックスはレコードの追加，削除，更新に時間がかかるという欠点があります。このため，更新の多いOLTP（オンライン・トランザクション処理）系のシステムには向いていません。データ・ウエアハウスなどのデータが頻繁に更新されないシステムで，テーブルを作成してデータをロードした後でビットマップ・インデックスを作るようにするのが基本です。

加藤 比呂武（かとうひろむ）

コメント ITproブックマーク 印刷

関連キーワード