あの“津崎さん”も保有する難関資格「データベーススペシャリスト」。本企画では、データベーススペシャリスト試験 午前/午後試験対策のための「基礎知識」を抜粋してお届けします。今回は「インデックス」の基礎を解説します。
書籍の中から有用な技術情報をピックアップして紹介する本シリーズ。今回は、秀和システム発行の書籍ポケットスタディ データベーススペシャリスト [第2版](2015年12月22日発行)』からの抜粋です。
ご注意:本稿は、著者及び出版社の許可を得て、そのまま転載したものです。このため用字用語の統一ルールなどは@ITのそれとは一致しません。あらかじめご了承ください。
※編集部注:前回記事「耐久性を確保する「障害回復機能」を理解する」はこちら
出題頻度 午前II:●●- 午後I:--- 午後II:---
●--:過去14年間での過去問出題数が1〜9回
●●-:過去14年間での過去問出題数が10〜19回
●●●:過去14年間での過去問出題数が20回以上
●B木、B+木、ビットマップインデックス、ハッシュインデックス
インデックス(索引)は、データベースの性能を向上させる方法の一つです。インデックスは「探すレコードを識別するデータの項目」「対象レコードの格納位置を示すポインタ」で構成されており、これを利用してデータの格納位置を特定し、その位置を直接アクセスする事で、表の検索速度を上げることができます。インデックスが設定されていない場合の検索では、テーブルの最初から順番に1件ずつ探すため、時間がかかります。
但し、インデックス設定により検索対象の表の更新速度が下がる等のデメリットがあります。また、インデックスを設定しても性能が上らないケースもあるため、一般的には次のような場合にインデックスを設定します。
インデックス設定が適しているケース | 適している理由 | |
---|---|---|
検索対象表の行数が多い | インデックスによる性能向上が見込める | |
検索対象表において、検索項目の属性値 (キー値)に重複・偏りが少ない |
||
検索対象の表の更新が少ない | 検索対象表の更新速度低下が少ない | |
検索対象の表の追加・削除が少ない | インデックスの性能低下が起きにくい | |
インデックスには検索に特化した様々なデータ構造がありますが、検索対象のデータ特性に合ったデータ構造を選ぶ必要があります。代表的なインデックスのデータ構造として以下があります。
<1>B木
B木は木構造のデータを構成し、検索を逐次ではなく、木構造の根(root)からたどる事で高速化します。後述のB+木と共に、多くのDBMSで利用されます。幅広く多くの検索で用いられ、BETWEEN等を用いた範囲指定検索において有効ですが、ANDやOR操作だけで行う検索やNOTを用いた否定検索は、後述のビットマップインデックスの方が有効です。
<2>B+木
キーの値の順による順次処理に向かないB木に対し、データを最下層(葉)に配置し、最下層の末尾のデータにポインタを設定することでB木の検索速度を生かしつつ順次処理も高速化したのがB+木です。
<3>ビットマップインデックス
テーブルと対になるビットマップというデータ構造を持ち、これを利用して行を特定します。検索対象表のキー値に重複が多い場合に有効です。
<4>ハッシュインデックス
ハッシュインデックスでは、キー値からハッシュ関数で求めた値を使い、レコードの格納位置を決めます。
ハッシュインデックスは一意な値を検索するのに向いていますが、不等号による範囲検索、ワイルドカード検索などのその他の検索についてはB木インデックスの方が向いています。また、ハッシュインデックスの欠点として、ハッシュ関数の演算結果の値が重複した場合(検索項目81203と89080などいずれも7877で割ると2433)データの格納先を一意に特定できない場合があり、これをシノニムと呼びます。その解決方法として以下があります。
オープンハッシュ法 | あいている番地にデータを格納 |
---|---|
ハッシュチェイン法 | 事前に用意してある「あふれ領域」にデータを格納 |
本試験過去問題による類題演習 | |
---|---|
□H16 午前問42 | ハッシュインデックスの特徴 |
□H15 午前問43 | ハッシュアクセス手法の説明 |
等頻度で検索される表において、平均検索速度が最も向上する表を選ぶ問題がよく出題されます。この場合、以下の計算式を利用します。
「インデックスの特定行へのアクセス時間+テーブルの特定行へのアクセス時間」=nとすると、以下A表、B表について次のようになります。
解答 演習25-1 エ
*囲み内をクリックすると解答を表示します(表示後ページをリロードすると、再び非表示になります)
特徴的な問題ですので、一度問題を解いた後に解答を覚えてしまうことをお勧めします。
本試験過去問題による類題演習 | |
---|---|
□H18 午前問40 | B+木インデックスの格納レコード件数と平均アクセス時間 |
B+木インデックスとビットマップインデックスを比較した説明のうち、適切なものはどれか。
ア ANDやOR操作だけで行えるB+木インデックスの方が有効である。
イ BETWEENを用いた範囲指定検索はビットマップインデックスの方が有効である。
ウ NOTを用いた否定検索はB+木インデックスの方が有効である。
エ 少数の異なる値をもつ列への検索はビットマップインデックスの方が有効である。
(H27春DB午前II問15)
解答 演習25-2 エ
*囲み内をクリックすると解答を表示します(表示後ページをリロードすると、再び非表示になります)
一つの表に大量のデータを格納するとき、並列処理のために異なったディスクにデータを分割格納することがある。このような方式のうちキーレンジ分割方式に関する説明はどれか。
(H17春DB午前問45)
ア 主キーと外部キーの参照関係を保持し、関数従属性に従って異なった表に分割格納する。
イ データの発生した順に格納するディスクを変え、ディスクごとのデータ量が均等になるように分割格納する。
ウ 分割に使用するキーの値にハッシュ関数を適用し、その値に割り当てられたディスクに分割格納する。
エ 分割に使用するキーの値をあらかじめ決めておき、その値に割り当てられたディスクに分割格納する。
解答 Point check エ
*囲み内をクリックすると解答を表示します(表示後ページをリロードすると、再び非表示になります)
Copyright © ITmedia, Inc. All Rights Reserved.