検索
連載

データベース性能を向上させる「インデックス」を理解する「データベーススペシャリスト試験」戦略的学習のススメ(26)

あの“津崎さん”も保有する難関資格「データベーススペシャリスト」。本企画では、データベーススペシャリスト試験 午前/午後試験対策のための「基礎知識」を抜粋してお届けします。今回は「インデックス」の基礎を解説します。

Share
Tweet
LINE
Hatena

連載目次

ポケットスタディ データベーススペシャリスト [第2版]

書籍の中から有用な技術情報をピックアップして紹介する本シリーズ。今回は、秀和システム発行の書籍ポケットスタディ データベーススペシャリスト [第2版](2015年12月22日発行)』からの抜粋です。

ご注意:本稿は、著者及び出版社の許可を得て、そのまま転載したものです。このため用字用語の統一ルールなどは@ITのそれとは一致しません。あらかじめご了承ください。


※編集部注:前回記事「耐久性を確保する「障害回復機能」を理解する」はこちら

インデックスによる性能向上

出題頻度 午前II:●●- 午後I:--- 午後II:---


 ●--:過去14年間での過去問出題数が1〜9回
 ●●-:過去14年間での過去問出題数が10〜19回
 ●●●:過去14年間での過去問出題数が20回以上


Key Word

B木、B+木、ビットマップインデックス、ハッシュインデックス


インデックスとは

 インデックス(索引)は、データベースの性能を向上させる方法の一つです。インデックスは「探すレコードを識別するデータの項目」「対象レコードの格納位置を示すポインタ」で構成されており、これを利用してデータの格納位置を特定し、その位置を直接アクセスする事で、表の検索速度を上げることができます。インデックスが設定されていない場合の検索では、テーブルの最初から順番に1件ずつ探すため、時間がかかります。

インデックスによる性能向上のイメージ

 但し、インデックス設定により検索対象の表の更新速度が下がる等のデメリットがあります。また、インデックスを設定しても性能が上らないケースもあるため、一般的には次のような場合にインデックスを設定します。

インデックス設定が適しているケース 適している理由
検索対象表の行数が多い インデックスによる性能向上が見込める
検索対象表において、検索項目の属性値
(キー値)に重複・偏りが少ない
検索対象の表の更新が少ない 検索対象表の更新速度低下が少ない
検索対象の表の追加・削除が少ない インデックスの性能低下が起きにくい

インデックスのデータ構造

 インデックスには検索に特化した様々なデータ構造がありますが、検索対象のデータ特性に合ったデータ構造を選ぶ必要があります。代表的なインデックスのデータ構造として以下があります。

<1>B木

 B木は木構造のデータを構成し、検索を逐次ではなく、木構造の根(root)からたどる事で高速化します。後述のB+木と共に、多くのDBMSで利用されます。幅広く多くの検索で用いられ、BETWEEN等を用いた範囲指定検索において有効ですが、ANDやOR操作だけで行う検索やNOTを用いた否定検索は、後述のビットマップインデックスの方が有効です。

B木のイメージ(8を探す場合のシーケンス)

<2>B+

 キーの値の順による順次処理に向かないB木に対し、データを最下層(葉)に配置し、最下層の末尾のデータにポインタを設定することでB木の検索速度を生かしつつ順次処理も高速化したのがB+です。

B+木のイメージ(8に続く値を探す場合のシーケンス)

<3>ビットマップインデックス

 テーブルと対になるビットマップというデータ構造を持ち、これを利用して行を特定します。検索対象表のキー値に重複が多い場合に有効です。

ビットマップインデックスのイメージ(答えがアのレコードを特定するシーケンス)

<4>ハッシュインデックス

 ハッシュインデックスでは、キー値からハッシュ関数で求めた値を使い、レコードの格納位置を決めます。

ハッシュインデックスのイメージ(を特定するシーケンス)

 ハッシュインデックスは一意な値を検索するのに向いていますが、不等号による範囲検索、ワイルドカード検索などのその他の検索についてはB木インデックスの方が向いています。また、ハッシュインデックスの欠点として、ハッシュ関数の演算結果の値が重複した場合(検索項目81203と89080などいずれも7877で割ると2433)データの格納先を一意に特定できない場合があり、これをシノニムと呼びます。その解決方法として以下があります。

オープンハッシュ法 あいている番地にデータを格納
ハッシュチェイン法 事前に用意してある「あふれ領域」にデータを格納

本試験過去問題による類題演習
□H16 午前問42 ハッシュインデックスの特徴
□H15 午前問43 ハッシュアクセス手法の説明

データベースの平均検索時間

 等頻度で検索される表において、平均検索速度が最も向上する表を選ぶ問題がよく出題されます。この場合、以下の計算式を利用します。

計算式

 「インデックスの特定行へのアクセス時間+テーブルの特定行へのアクセス時間」=nとすると、以下A表、B表について次のようになります。

計算式

Chance問題

演習25-1

 関係データベースの表において、検索速度を向上させるために、列Zにインデックスを付与する。ア〜エは、列Zの値が等しい行の数を示したものである。インデックスを付与することによって、1行当たりの平均検索速度が最も向上するものはどれか。ここで、各行は等頻度で検索されるものとする。

演習25-1

(H21春DB午前II問10)


解答 演習25-1 

 *囲み内をクリックすると解答を表示します(表示後ページをリロードすると、再び非表示になります)

 特徴的な問題ですので、一度問題を解いた後に解答を覚えてしまうことをお勧めします。

本試験過去問題による類題演習
□H18 午前問40 B木インデックスの格納レコード件数と平均アクセス時間

Chance問題

演習25-2

 B木インデックスとビットマップインデックスを比較した説明のうち、適切なものはどれか。

ア ANDやOR操作だけで行えるB木インデックスの方が有効である。

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

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

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

(H27春DB午前II問15)


解答 演習25-2 

 *囲み内をクリックすると解答を表示します(表示後ページをリロードすると、再び非表示になります)

Chance問題

Point check

一つの表に大量のデータを格納するとき、並列処理のために異なったディスクにデータを分割格納することがある。このような方式のうちキーレンジ分割方式に関する説明はどれか。

(H17春DB午前問45)


 主キーと外部キーの参照関係を保持し、関数従属性に従って異なった表に分割格納する。

 データの発生した順に格納するディスクを変え、ディスクごとのデータ量が均等になるように分割格納する。

 分割に使用するキーの値にハッシュ関数を適用し、その値に割り当てられたディスクに分割格納する。

 分割に使用するキーの値をあらかじめ決めておき、その値に割り当てられたディスクに分割格納する。


解答 Point check 

 *囲み内をクリックすると解答を表示します(表示後ページをリロードすると、再び非表示になります)

書籍紹介

ポケットスタディ データベーススペシャリスト [第2版]

ポケットスタディ データベーススペシャリスト [第2版]

具志堅融、河科湊著
秀和システム 1,500円

データベーススペシャリスト試験は同じパターンの出題が多いため、過去問をたくさん解くことが合格の早道です。しかし、難易度の高い過去問を解くには、勉強が必要であり、多くの時間と労力を必要とします。本書は、プロの講師が推奨する、テキストを少し読み→該当する過去問を解き→理解を深めるというアジャイル的学習法で、驚くほど短時間で合格するツボとコツを解説します。"すき間時間"を活用して効果的な学習ができます!


注文ページへ

Copyright © ITmedia, Inc. All Rights Reserved.

ページトップに戻る