JPH04195588A - データベースの後方一致検索処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明はデータベースの後方一致検索処理方式％式％ 〔従来の技術〕 データベースの分野において、データベースファイルに
格納されている多数のレコードから特定の条件を満足す
るレコードを検索する処理は「問い合わせ」と呼ばれて
いる。

ところで、この問い合わせは、一般に、レコードの特定
のフィールドに含まれる文字列を指定し、それが一致す
るか否かによって行われることが多い。

なお、一致の形態に応じて検索方式も次のように３通り
ある。

・前方一致検索 ・後方一致検索 ・中間一致検索 ここで、前方一致検索とは指定した文字列がフィールド
の前方で一致することを条件とするものであり、後方一
致検索とは指定した文字列がフィールドの後方で一致す
ることを条件とするものであり、中間一致検索とは指定
した文字列がフィールドの任意の位置で一致することを
条件とするものである。

一方、問い合わせを高速に行うための手法として、レコ
ード内の所定のフィールドの値を索引キー値としてキー
値順に並べた索引が従来から用いられている。

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

上述したように、問い合わせにおける検索方式としては
３通りあり、高速化の手法として索引が設けられている
ものであるが、一致を見るフィールドに関して索引が存
在しない場合はいずれの検索方式でも全てのレコードを
読み込んで一致を判断しなければならないのは当然とし
て、索引が設けられている場合であっても、後方一致検
索と中間一致検索にあっては前方一致検索のような飛躍
的な効果は望めないという欠点があった。すなわち、一
般に文字列を対象とする索引は先頭の文字のキー値から
序列を定めているため、前方一致検索では索引から該当
するレコードを即座に検索することができるが、後方一
致検索や中間一致検索では索引の順序が意味をなさない
ため、全ての索引キーレコードを読み込んで一致を判断
しなければならないからである。

本発明は上記の点に鑑み提案されたものであり、後方一
致検索を高速に行えるようにした処理方式を提供するこ
とを目的とするものである。なお、中間一致検索につい
ては対象としていない。

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

本発明は上記の目的を達成するため、レコードの所定の
フィールドの値を降順にした降順索引キー値と対応する
レコードへのポインタ値とを有する降順索引キーレコー
ドをキー値順に格納した最下位ブロックと、最下位ブロ
ック内の最大の降順索引キー値とその最下位ブロックへ
のポインタ値とを有する上位降順索引キーレコードをキ
ー値順に格納した上位ブロックとで階層的に形成された
降順索引と、 検索要求において指定された条件を降順に変換する条件
変換手段と、 変換された条件を降順索引キー値として降順索引の降順
索引キーレコードを検索する降順索引キーレコード検索
手段と、 検索された降順索引キーレコードのポインタ値から目的
のレコードを検索するレコード検索手段とを備えるよう
にしている。

〔作用〕

本発明のデータヘースの後方一致検索処理方式にあって
は、条件変換手段が検索要求において指定された条件を
降順に変換し、降順索引キーレコード検索手段が変換さ
れた条件を降順索引キー値として降順索引の降順索引キ
ーレコードを検索し、レコード検索手段が検索された降
順索引キーレコードのポインタ値から目的のレコードを
検索する。

〔実施例〕

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

第１図は本発明のデータヘースの後方一致検索処理方式
の一実施例を示す構成図である。

第１図において、本実施例は、機能部として、降順索引
定義手段１とレコード登録手段２と降順索引キー値生成
手段３と降順索引キーレコード登録手段４と条件変換手
段５と降順索引キーレコード検索手段６とレコード検索
手段７とを備えている。また、記憶領域ないしは格納情
報として、デ−タヘース８とレコード９と降順索引１０
と上位ブロック１１と最下位ブロック１２と上位降順索
引キーレコード１３と降順索引キーレコード１４とを備
えている。なお、各部の機能等については、重複を避け
るため、以下の動作を通して説明することとする。

以下、上記の実施例の動作を場合を分けて説明する。

（１）レコードの登録 レコードの登録に先立ち、降順索引定義手段１が、登録
すべきレコード９内の任意のフィールドを降順索引の生
成の対象として定義する。

第２図はレコード９として書籍レコードのフィールドの
例を示したものであり、書名、著者、出版社等のフィー
ルドを有している。降順索引定義手段１は、例えば、書
名のフィールドを降順索引の生成の対象として定義する
。

第１図において、その後、登録すべきレコード９が与え
られると、レコード登録手段２は、レコード９を格納す
るデータベース８上のアドレスを決定し、データベース
８内に登録する。

レコード登録手段２によるデータヘース８へのレコード
９の登録と前後して、降順索引キー値生成手段３は、降
順索引定義手段１によって定義されたフィールドに基づ
き、登録したレコード９の当該フィールドの値を降順に
して降順索引キー値を生成する。

第３図は書籍レコードにつき書名のフィールドが降順索
引の生成の対象として定義されている場合に生成される
降順索引キー値の具体例を示したものであり、降順索引
キー値生成手段３は、書名の文字列を逆にした文字列を
降順索引キー値として生成する。

次いで、第１図において、降順索引キーレコード登録手
段４は、降順索引キー値生成手段３によって生成された
降順索引キー値とレコード登録手段２によって登録され
たレコード９のデータベース８上のアドレスであるポイ
ンタ値とから構成される降順索引キーレコード１４を、
降順索引１０の最下位ブロック１２上に登録する。なお
、降順索引キーレコード１４については、最下位プロ。

り１２上で降順索引キー値の順に格納する。

また、降順索引キーレコード１４が最下位ブロック１２
上でいっばいになった場合、降順索引キーレコード登録
手段４は、最下位ブロック１２上に含まれる降順索引キ
ーレコード１４の最大の降順索引キー値を降順索引キー
値とする上位降順索引キーレコード１３を上位ブロック
１１上に作成し、その上位降順索引キーレコード１３の
ポインタ値に最下位ブロック１２のアドレスを持たせて
最下位ブロック１２をポイントするようにさせる。

その後に降順索引キーレコード１４を新たに登録する場
合は別の最下位ブロック１２に格納し、その最下位ブロ
ック１２上に含まれる降順索引キーレコード１４の最大
の降順索引キー値を降順索引キー値とすると共にその最
下位ブロック１２のアドレスをポインタ値とする上位降
順索引キーレコード１３を上位ブロック１１上に作成す
る。

同様に、上位ブロック１１の上位降順索引キーレコード
１３がいっばいになった場合にも、更に上位の上位ブロ
ックを作成し、階層的に降順索引ｉｏを形成して行く。

以上の処理をレコード９を登録する毎に行う。

第４図は第３図の書籍レコードを全て登録した後のデー
タヘース８の状態を示したものであり、上位ブロック１
１の上位降順索引キーレコード１３１〜１３３と、最下
位プロ、り１２１，１２２゜１２３の降順索引キーレコ
ード１４０１〜１４１２と、レコード９０１〜９１２と
から構成され、ポインタにより階層的に関係付けられて
いる。

（２）レコードの検索 レコード９の検索要求は、既に降順索引定義手段１によ
って定義されたフィールドについて、ある文字列を条件
として指定し、その文字列が後方一致するレコード９を
検索すべきものとして与えられるものとする。

例えば、第４図のデータヘース８に対して「書名が“殺
人事件“で終わる書籍を検索せよ、」といった旨の検索
要求が行われる。

第１図において、レコード９の検索要求に対し、条件変
換手段５は、指定された条件の文字列を降順に変換し、
降順索引゛キー値を生成する。

例えば、上記の「書名が°殺人事件”で絆わる書籍を検
索せよ。」といった旨の検索要求が行われると、条件変
換手段５は、条件の文字列“殺人事件”をｖｌｌｌｌ［
にし、“件事大殺′を降順索引キー値として生成する。

降順索引キーレコード検索手段６は、条件変換手段５に
よって生成された降順索引キー値を基にデータベース８
の降順索引１０の降順索引キーレコード１４を検索する
。すなわち、検索は、先ず、上位ブロック１１を読み、
上位ブロック１１内で検索要求があった降順索引キー値
に最も近くて大きい降順索引キー値を有するか等しい降
順索引キー値を有する上位降順索引キーレコード１３を
求め、そのポインタ値から最下位ブロック１２を辿り、
該当する降順索引キーレコード１４を得る。

前述の降順索引キー値“件事大殺”を例にとると、降順
索引キーレコード検索手段６は、第４図において、先ず
上位ブロック１１を参照し、上位降順索引キーレコード
１３１を得る。そして、上位ｌ順索引キーレコード１３
１のポインタ値から最下位ブロック１２１を辿り、“件
事大殺”で前方一致する降順索引キーレコード１４０４
および続く最下位ブロック１．２２，１２３の降順索引
キーレコード１４０５〜１４０９を取得する。

第１図において、レコード検索手段７は、降順索引キー
レコード検索手段６によって検索された降順索引キーレ
コード１４のポインタ値を基に、データベース８からレ
コード９を取得する。

前述の例では、レコード検索手段７は、第４図において
、取得された降順索引キーレコード１４０４〜１４０９
のポインタ値に基づき、レコード９０３．９１１．９０
９．９０１．９０５，９０７を取得する。

以上説明したように、後方−敗の検索が極めて高速に行
えるものである。

具体的な数値をもって示せば、例えば、レコード総数を
１００万件、レコードのブロッキングファクタ（１個の
ブロックに入るレコード数）を１０、索引のブロックの
ブロッキングファクタを２００と過程した場合、求める
レコード総数件であるとすると、従来の索引が定義され
ていない場合にはレコードの全てのブロックを検索する
ため１０万回のｌ１０（入出力処理）が必要となり、索
引が定義されている場合には索引の全てのプロ・ツクを
検索するため５千回のＩｌｏとなるが、本発明では、降
順索引１０で最上位ブロックから上位ブロックと最下位
ブロックとを順次に辿るためのＩｌｏが２回で、レコー
ドの格納されたプロ、りに対するＩｌｏが１回の計３回
で済むことになり、飛躍的な高速化を図ることができる
。

〔発明の効果〕

以上説明したように、本発明のデータベースの後方一致
検索処理方式にあっては、降順索引を持つことにより、
後方一致検索が高速に行え、問い合わせに対するサービ
スを向上できるという効果がある。

【図面の簡単な説明】

第１図は本発明のデータベースの後方一致検索処理方式
の一実施例を示す構成図、 第２図はレコードの論理的構成の例を示す図、第３図は
降順索引キー値の具体例を示す図および、 第４図はデータベースの具体例を示す図である。 図において、 １・・・・・・降順索引定義手段 ２・・・・・・レコード登録手段 ３・・・・・・降順索引キー値生成手段４・・・・・・
降順索引キーレコード登録手段５・・・・・・条件変換
手段 ６・・・・・・降順索引キーレコード検索手段７・・・
・・・レコード検索手段 ８・・・・・・データベース ９・・・・・・レコード １０・・・降順索引 １１・・・上位ブロック １２・・・最下位ブロック １３・・・上位降順索引キーレコード １４・・・降順索引キーレコード

Claims (2)

【特許請求の範囲】
1. （１）レコードの所定のフィールドの値を降順にした降
   順索引キー値と対応するレコードへのポインタ値とを有
   する降順索引キーレコードをキー値順に格納した最下位
   ブロックと、最下位ブロック内の最大の降順索引キー値
   とその最下位ブロックへのポインタ値とを有する上位降
   順索引キーレコードをキー値順に格納した上位ブロック
   とで階層的に形成された降順索引と、 検索要求において指定された条件を降順に変換する条件
   変換手段と、 変換された条件を降順索引キー値として降順索引の降順
   索引キーレコードを検索する降順索引キーレコード検索
   手段と、 検索された降順索引キーレコードのポインタ値から目的
   のレコードを検索するレコード検索手段とを備えたこと
   を特徴とするデータベースの後方一致検索処理方式。
2. （２）レコード内の任意のフィールドを降順索引の生成
   の対象として定義する降順索引定義手段と、レコードを
   データベースに登録するレコード登録手段と、 レコード登録時に降順索引定義手段で定義されたフィー
   ルドの値を降順にして降順索引キー値を生成する降順索
   引キー値生成手段と、 生成された降順索引キー値を含ませた降順索引キーレコ
   ードを降順索引に登録する降順索引キーレコード登録手
   段とを備えたことを特徴とする請求項１記載のデータベ
   ースの後方一致検索処理方式。