JPH01279318A - 索引検索方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は索引検索方式に関し、特にデータベース管理シ
ステムにおいて二次記憶装置上に構築された複数レベル
の索引ブロックから構成される階層的な木構造の索引を
用いてレコードの検索を行う方式に関するものである。

〔従来の技術〕

データベースのレコードを検索する方式として、Ｂツリ
ー等の複数レベルの索引ブロックから構成される階層的
な木構造の索引をデータベースと同様に二次記憶装置上
に構築しておき、その索引を用いて検索を行うものが一
般に知られている。また、この方式を更に細分すれば、
従来、■全ての検索要求に対して最上位の索引ブロック
から順次検索を行うもの ■ｎ回前までの検索で使用された最下位索引ブロックを
主記憶装置上に退避させておき、今回の検索要求に対し
て可能ならばこの索引ブロックを使い、それ以外は最上
位の索引ブロックから順次検索を行うもの とがある。

しかして、■の方式にあっては、二次記憶装置より最上
位から順次に索引ブロックを読み出し、検索要求に含ま
れる索引キー値との同一性を判断して順次下位の索引ブ
ロックへと辿って行き、該当する索引ブロックを見つけ
出すものである。

また、■の方式も基本的には■と同様であるが、先行す
る検索で既に使用して主記憶装置上に退避された索引ブ
ロックが使用可能な場合、最上位の索引ブロックからそ
の索引ブロックまでの検索が省略できる点で効率的にな
っている。

〔発明が解決しようとする課題〕

ところで、この種の二次記憶装置上に構築した索引を使
用する検索方式にあっては、処理の高速化を図る上で索
引ブロックの参照回数の削減は重要な課題であり、索引
ブロックへの参照を１つ減らすだけで検索時間が大幅に
短縮できるものであった。すなわち、索引検索システム
において主たる動作を行う中央処理装置の処理速度に比
較して二次記憶装置への入出力動作の処理速度は極めて
遅いため、索引ブロックを参照するために二次記憶装置
からその索引ブロックを読み込んでくるための入出力動
作に要するオーバーヘッド・タイムが無視できないため
である。

このような観点より、前述した従来の検索方式には次の
ような問題点があった。

（１）従来の方式■では、常に最上位の索引ブロックか
ら検索を開始するため、直前の検索で同じ索引キー値を
使っているような場合であっても前回の検索過程で得ら
れた情報を利用することはできず、結果として索引ブロ
ックの参照回数が非常に多くなり、検索時間が長くなる
。

（２）従来の方式■では、従来の方式のの問題点を解決
するため、ｎ回前までの検索で使用された最下位索引ブ
ロックを再利用することを可能としているが、全ての検
索で主記憶装置上に退避された索引ブロックが使用でき
るとは限らず、索引ブロックの参照回数を有効に減らす
ことはできない。なお、退避させる索引ブロックの数ｎ
を増やすことによりこの問題はある程度解決できるが、
記憶に多くの領域を必要とする索引ブロックを数多く主
記憶装置上に退避させることとなることから、高価な主
記憶装置の有効利用という観点から問題がある。

本発明は上記の点に鑑み提案されたものであり、その目
的とするところは、主記憶装置を無駄に使用することな
く索引ブロックの参照回数を減らして検索時間の短縮化
を図れる索引検索方式を提供することにある。

〔課題を解決するための手段〕

本発明は上記の目的を達成するため、二次記憶装置上に
構築され複数レベルの索引ブロックから構成される階層
的な木構造の索引を用いてデータベースのレコードを検
索する方式において、索引を構成する全ての索引ブロッ
クのブロック番号と各索引ブロックの親ブロックのブロ
ック番号とを記憶する親ブロックテーブルと、以前に検
索された索引キー値とその検索で参照された最下位索引
ブロックのブロック番号とを記憶するキャッシュ索引と
を設け、検索要求に対し、キャッシュ索引に記憶された
索引キー値と最下位索引ブロックのブロック番号とを参
照し、索引で定められた索引キー値の順序関係に従って
検索要求の索引キー値の直前に位置する索引キー値に対
応する第１のブロック番号と検索要求の索引キー値の直
後に位置する索引キー値に対応する第２のブロック番号
とを獲得し、親ブロックテーブルを参照して第１および
第２のブロック番号自身あるいは第１および第２のブロ
ック番号を有する索引ブロックの上位の索引ブロックの
ブロック番号を順次獲得し、それらのブロック番号が一
致するか、あるいはいずれか一方が最上位の索引ブロッ
クのブロック番号に一致するまで参照を継続し、一致し
たブロック番号の索引ブロックから検索を行うようにし
ている。

〔作用〕

本発明の索引検索方式にあっては、検索要求に対し、キ
ャッシュ索引に記憶された索引キー値とその索引キー値
に対応する以前の検索における最下位索引ブロックのブ
ロック番号とが参照され、索引で定められた索引キー値
の順序関係に従って検索要求の索引キー値の直前に位置
する索引キー値に対応する第１のブロック番号と検索要
求の索引キー値の直後に位置する索引キー値に対応する
第２のブロック番号とが獲得され、親ブロックテーブル
が参照されて第１および第２のブロック番号自身あるい
は第１および第２のブロック番号を有する索引ブロック
の上位の索引ブロックのブロック番号が順次獲得され、
それらのブロック番号が一致するか、あるいはいずれか
一方が最上位の索引ブロックのブロック番号に一致する
まで参照が継続され、一致したブロック番号の索引ブロ
ックから検索が行われる。

上記の検索が開始される索引ブロックは、索引キー値の
順序関係に従い検索要求の索引キー値の前後に最も近く
位置する既に検索された結果である最下位索引ブロック
から後戻りして見つけ出された分岐点であるため、その
分岐点における最下位索引ブロックから下位に検索を行
うことで検索要求の索引キー値に対する検索が達成され
る。

〔実施例〕

以下、本発明の実施例につき図面を参照して詳細に説明
する。

第１図は本発明の索引検索方式の一実施例である索引検
索システムの構成図である。第１図において、１は通常
のデータベース管理システムで見られるデータベース２
および索引３を格納しである二次記憶装置であり、この
二次記憶装置１と親ブロックテーブル４とキャッシュ索
引５と索引検索手段６と検索開始ブロック決定手段７と
により索引検索システムが構成されている。ここで、二
次記憶装置１に格納された索引３は階層的な木構造を持
ち、複数レベルの索引ブロックから構成され、各索引ブ
ロックは正の整数の一意なブロック番号を持つものであ
る。また、親ブロックテーブル４は索引３を構成する全
ての索引ブロックのブロック番号と各索引ブロックの親
ブロックのブロック番号とを記憶しておくものであり、
キャッシュ索引５は以前に検索された索引キー値とその
検索で参照された最下位索引ブロックのブロック番号と
を記憶しておくものである。なお、親ブロックテーブル
４とキャッシュ索引５の内容は当初は二次記憶装置１に
格納されており、システム起動時に二次記憶装置１から
索引検索システムの主記憶装置に読み込まれて形成され
るものである。

一方、索引検索手段６は利用者から与えられる検索要求
８を解析し、検索要求８に含まれる索引キー値を指定し
て検索開始ブロック決定手段７を呼び出し、検索開始ブ
ロック決定手段７が返すブロック番号を持つ索引ブロッ
クから索引３の検索を開始し、この検索で使われた索引
キー値と、最下位索引ブロックのブロック番号とをキャ
ッシュ索引５に登録する機能を有するものである。また
、検索開始ブロック決定手段７は索引検索手段６に呼び
出された際に起動するものであり、親ブロックテーブル
４とキャッシュ索引５とを参照し、指定された索引キー
値を検索すべく、検索を開始すべき索引ブロックのブロ
ック番号を決定して呼び出し元である索引検索手段６に
返す機能を有するものである。

第２図は親ブロックテーブル４の論理的構成を示した図
であり、親ブロックテーブル４は、索引３を構成する全
ての索引ブロックのブロック番号と、その索引ブロック
の索引３におけるレベルを示すレベル識別子と、その索
引ブロックの親ブロックのブロック番号とを含んでいる
。なお、最上位の索引ブロックのレベル識別子には１を
設定し、以下の索引ブロックでは、索引におけるレヘル
が１つ下がるごとに１を加算するものとする。また、最
上位の索引ブロックに親ブロックは存在しないため、そ
のブロック番号には負の整数（無効なブロック番号）が
設定される。なお、実際の親プロンクチープル４の構成
法としては、例えば、ハ。

シング技法等の高速化のための既知の技法を応用するこ
とができる。

次いで、第３図はキャッシュ索引５の論理的構成を示し
た図であり、キャッシュ索引５はｎ個のエントリから構
成され、各エントリには索引キー値とその索引キー値の
検索で参照された最下位索引ブロックのブロック番号と
が格納されるようになっている。なお、実際のキャッシ
ュ索引５は、それに含まれるエントリに関し、上記の親
ブロックテーブル４と同様に高速化のための既知の技法
や、先入れ先出し制御のために例えば両方向チエインに
よる連結等の既知の技法を応用して構成することができ
る。

第４図は索引検索手段６の処理の流れを示すフローチャ
ートであり、以下、第４図を参照して第１図の実施例の
概略動作を説明する。

利用者から検索要求８が与えられると、索引検索手段６
はその検索要求８を解析して要求された索引キー値を得
る（ステップ６１）。次いで、この索引キー値を指定し
て検索開始ブロック決定手段７を呼び出しくステップ６
２）、それが返すブロック番号を持つ索引ブロックから
検索を実行する（ステップ６３）。次いで、最も長い間
参照されなかったエントリをキャッシュ索引５から削除
しくステップ６４）、今回の検索に使用された索引キー
値と今回の検索で参照された最下位索引ブロックのブロ
ック番号とから構成されるエントリをキャッシュ索引５
に追加する（ステップ６５）。

そして、検索結果９を要求元に返しくステップ６６）、
処理を終了する。

第５図は検索開始ブロック決定手段７の処理の流れを示
すフローチャートであり、以下、第５図に沿って検索を
開始する索引ブロックのブロック番号の決定にかかる動
作を説明する。

検索開始ブロック決定手段７が起動されると、検索開始
ブロック決定手段７は変数Ｂえ、Ｂ、のそれぞれに最上
位の索引ブロックのブロック番号すなわち「１」を設定
する（ステップ７０１）。

次いで、索引検索手段６によって指定された索引キー値
よりも小さい索引キー値を持つエントリをキャッシュ索
引５の索引キー値から捜し出し、その中で最も大きい索
引キー値を持つエントリの索引ブロックのブロック番号
を変数Ｂ、に設定する（ステップ７０２）。同様に、索
引検索手段６によって指定された索引キー値よりも大き
い索引キー値を持つエントリをキャッシュ索引５の索引
キー値から捜し出し、その中で最も小さい索引キー値を
持つエントリの索引ブロックのブロック番号を変数Ｂ、
に設定する（ステップ７０３）。上記の処理でどちらの
場合も該当する値がない場合は、変数Ｂ、、Ｂ、は最上
位の索引ブロックのブロック番号「１」に設定されたま
まである。

次に、親ブロックテーブル４から変数Ｂ、のレベル識別
子と変数Ｂ、のレベル識別子とを参照して比較しくステ
ップ７０．４　）　、変数Ｂ、Ｉのレベル識別子と変数
Ｂ、のレベル識別子が一致した場合、処理はステップ７
０８に移行する。一方、変数Ｂ。

のレベル識別子と変数Ｂ、のレベル識別子が異なる場合
には、それらの大小関係を比較しくステップ７０５）、
変数Ｂ、のレベル識別子が変数Ｂ。

のレベル識別子よりも小さい場合には親ブロックテーブ
ル４を参照してブロック番号Ｂ、を持つ索引ブロックの
親ブロックのブロック番号を変数Ｂアに設定しくステッ
プ７０７）、変数Ｂイのレベル識別子が変数Ｂ、のレベ
ル識別子よりも大きい場合には親ブロックテーブル４を
参照してブロック番号Ｂ、を持つ索引ブロックの親ブロ
ックのブロック番号を変数Ｂ、に設定しくステップ７０
６）、ステップ７０４に戻って同様の処理を繰り返す。

一方、ステップ７０８では変数８８と変数Ｂ。

とを比較し、変数Ｂ、と変数Ｂ、とが等しければ索引検
索手段６に変数Ｂ、を返しくステップ７０９）、処理を
終了する。また、変数８３と変数Ｂ。

とが異なる場合は変数Ｂ、と変数Ｂｙをそれぞれ最上位
の索引ブロックのブロック番号「１」と比較しくステッ
プ７１０）、どちらか一方が最上位の索引ブロックのブ
ロック番号と等しければ最上位の索引ブロックのブロッ
ク番号を索引検索手段６に返しくステップ７１１）、処
理を終了する。

それ以外の場合には親ブロックテーブル４を参照し、変
数Ｂヶにはブロック番号Ｂ、を持つ索引ブロックの親ブ
ロックのブロック番号を、変数Ｂ。

にはブロック番号Ｂ、を持つ索引ブロックの親ブロック
のブロック番号をそれぞれ設定しくステップ７１２）、
ステップ７０８に戻って処理を繰り返す。

上記の処理により最上位の索引ブロックからステップ７
０２．７０３で獲得された索引ブロックへ至る経路の分
岐点が見つけ出され、検索要求の索引キー値はそれ以下
の索引ブロックを検索することにより見つけ出される。

〔発明の効果〕

以上説明したように、本発明の索引検索方式にあっては
、最上位の索引ブロック以下の索引プロ７りから検索を
開始するため、検索の際に参照する必要のある索引ブロ
ックの故を削減することができ、二次記憶装置の入出力
動作を減らして検索時間を大幅に短縮することができる
効果がある。

また、親ブロックテーブルとキャッシュ索引が必要とす
る主記憶装置上の領域は、従来の索引ブロック全体を主
記憶装置上に退避する場合に比較して極めて少ないため
、窩価な主記憶装置を有効利用することができるもので
ある。

なお、本発明の索引検索方式はＢツリ一方式の検索にお
いて検索される索引キー値が特定の値域に集中している
ような場合に特にを効であるが、他の方式の索引であっ
ても、キャッシュ索引に最低２つのエントリが登録され
ていれば以前の検索過程の情報を有効に再利用すること
ができるので、広範囲の値を検索するような場合にも充
分効果がある。

【図面の簡単な説明】

第１図は本発明の索引検索方式の一実施例である索引検
索システムの構成を示す図、 第２図は親ブロックテーブルの論理的構成を示す図、 第３図はキャッシュ索引の論理的構成を示す図、第４図
は索引検索手段の処理の流れを示すフローチャートおよ
び、 第５図は検索開始ブロック決定手段の処理の流れを示す
フローチャートである。 図において、１・・・二次記憶装置、２・・・データベ
ース、３・・・索引、４・・・親ブロックテーブル、５
・・・キャッシュ索引、６・・・索引検索手段、７・・
・検索開始ブロック決定手段、８・・−検索要求、９・
・・検索結果。

Claims (1)

1. 【特許請求の範囲】 二次記憶装置上に構築され複数レベルの索引ブロックか
   ら構成される階層的な木構造の索引を用いてデータベー
   スのレコードを検索する方式において、 索引を構成する全ての索引ブロックのブロック番号と各
   索引ブロックの親ブロックのブロック番号とを記憶する
   親ブロックテーブルと、以前に検索された索引キー値と
   その検索で参照された最下位索引ブロックのブロック番
   号とを記憶するキャッシュ索引とを設け、 検索要求に対し、キャッシュ索引に記憶された索引キー
   値と最下位索引ブロックのブロック番号とを参照し、索
   引で定められた索引キー値の順序関係に従って検索要求
   の索引キー値の直前に位置する索引キー値に対応する第
   １のブロック番号と検索要求の索引キー値の直後に位置
   する索引キー値に対応する第２のブロック番号とを獲得
   し、親ブロックテーブルを参照して第１および第２のブ
   ロック番号自身あるいは第１および第２のブロック番号
   を有する索引ブロックの上位の索引ブロックのブロック
   番号を順次獲得し、それらのブロック番号が一致するか
   、あるいはいずれか一方が最上位の索引ブロックのブロ
   ック番号に一致するまで参照を継続し、 一致したブロック番号の索引ブロックから検索を行うこ
   とを特徴とする索引検索方式。