JPS6261118A - 木構造インデクスの検索方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、電子計算機システムにおけるデータ検索方式
に関し、特に木構造のインデクスを持つデータの効率的
な検索方式を提供するものである。

〔発明の従来技術と問題点〕

従来より、複数の属性により識別されるデータの検索キ
ーとして、それら各属性のコード名を繋げて検索キーと
し、一方、各データと検索キーとの関係を木構造のイン
デクスとして設け、与えられた検索キーをもとにインデ
クスを辿って目的とするデータを見付ける方法は公知で
ある。

しかし、従来のインデクスの構造及びその検索方式は、
必ずしも効率的とはいえず、特に所謂ワイルド・カード
（ｗｉｌｄ　ｃａｒｄ　）検索には不便な点が多かった
。

ここで、ワイルド・カード検索について説明すると、例
えば（Ａ、Ｂ、ＦＯＲＴ）なるキーを持つデータと、（
Ａ、Ｃ，ＦＯＲＴ）なるキーを持つデータと、（Ａ、Ｄ
、ＦＯＲＴ）なるキーを持つデータとがあるとき、検索
キーとして（Ａ、＊。

Ｆ　ＯＲＴ）を指定すると上記３つのデータがすべて検
索されるような方式をいう。つまり、検索項目としてド
ント・ケア（ｄｏｎ’　ｔ　ｃａｒｅ）な部分を持つ検
索キーを使用できるもので、非常に便利な機能である。

尚、このドント・ケア部分の指定記号には次の３種類が
ある。

？　−一１文字（英数字及び記号） ＊　−−１〜８文字からなる１属性コ一ド％　−一任意
の数の属性コード 尚、尿性コードは１〜８文字であり、各属性コード間は
ピリオドで区切るものとする。従って属性コードにはピ
リオドは使用できず、上記？、＊、にもピリオドは含ま
れない。

〔発明の目的〕

本発明は、上記ワイルド・カード検索が効率よ（検索で
きるようなインデクス構造、及びその検索方式を提供す
ることを目的とする。以下図面により詳述する。

〔発明の実施例〕

第１図は本発明の一実施例によるワイルド・カード検索
方式の説明図であり、１はインデクス・テーブル、２は
リファレンス・テーブル、３はスタック・テーブル、４
．５．６は夫々各テーブルの参照位置を示すポインタで
あり、夫々■ポインタ、Ｒポインタ、Ｓポインタと略称
する。これらはすべてデータ処理システムの主記憶装置
上に設けられる。また第２図は木構造インデクスの例を
示す図である。

第２図（ａｌにおいて、各技の分岐点にある文字は１つ
の属性コードを示しく以下ノード名という）、最上位の
ノード名から最下位のノード名までのノード名の連鎖が
、ある１つのデータに対する検索キーとなる。例えば、
右端のデータは （Ａ、Ｍ、ＰＬｌ、Ｑ）という検索キーにより検索され
るべきデータである。

また図中Ｔなる添字はそのノードがタイプノードである
ことを示し、タイプノードより下位のレベルは高々１つ
しかないものとする。

第２図（ｂ）は同図（ａｌを横書きにし、且つ同一レベ
ル内ではアルファベット順となるように並べ変えたもの
である。

第１図のインデクス・テーブル１は■欄がノード名、■
欄がレベル番号、■欄がタイプノードであることを示す
フラグ、■欄が次ポインタで、第２図（ｂ）から容易に
作成される。次ポインタは、自ノードと同一レベル又は
より高レベルのノードであって、此のテーブル上で次に
現れるものの位置を示す。但し図示例では、自ノードか
らの距離でその位置を示している。テーブルの右側に図
示された矢印は次ポインタの説明のためのものである。

またインデクス・テーブル上での順番は、同一レベルの
ノードがアルファベット順など一定の順序に従うように
される。

このようなインデクス・テーブルを用いて例えば（Ａ、
Ｍ、ＰＬＩ、Ｑ）なる検索キーを持つデータを検索する
一般的方法を説明する。

イ）まず、ルベル目のＡについては特に問題はない。

口）次の２レベル目のＭを検索するため、ルベル目のＡ
の次のノードを見る。

このノードのノード名はＤで、Ｍとは一致しない。そこ
で、次ポインタに従って４つ先のノードを見るとこれも
ＤＡＴＡで一致しない。更にその次ポインタに従って２
つ先のノードを見ると、ノード名がＭで一致し目的の２
レベル目のノードが見つかったなる。

ハ）次に３レベル目のＰＬｌを探すために、ノードＭの
次のノードＯＢＪから上記口）と同様の検索を行なう。

今度はＯＢＪのポインタの指す２つ先のノードがＰＬＩ
でありすぐ見つかる。

二）ノードＰＬＩはタイプノードである。タイプノード
に達したときは、そのタイプノードの次ポインタが指す
次のタイプノードまでの範囲を二分検索法で検索すれば
よい。

今の例ではすぐにＱが見つかる。

このように、インデクス・テーブルにレベル番号と、同
一レベルの次のノードを指すポインタとを設け、また必
要により各種のフラグを付加することにより、効率的に
検索が行なえる。

次に上記第１図にそってワイルド・カード検索の方式を
述べる。尚、リファレンス・テーブル２及びスタック・
テーブル３には、ノード名及びそのレベル番号の欄が設
けである。

まず、＊によるワイルド・カード検索について説明する
。

ａ）まず第１図のリファレンス・テーブル２には検索キ
ー（Ａ、＊、ＦＯＲＴ）の各ノード名及びそのレベル番
号がセントされる。スタック・テーブル３は最初クリア
されている。また各ポインタ４．５．６はすべて初期値
１となって、第１エントリを指している。

ｂ）この状態で、まずリファレンス・テーブル２のＲポ
インタ５の指すエントリの内容とインデクス・テーブル
１の■ポインタ４の指すエントリの内容とを比較する。

この例ではともに（Ａ）であり、且つレベル番号も一致
するので、その内容（Ａ）及びレベル番号をスタック・
テーブル３のＳポインタ６の指すエントリに書き込む。

しかるのち各ポインタ４．５．６を１歩進して次レベル
の検索に移る。

Ｃ）もし比較の結果一致しないときは、■ポインタ４に
次ポインタの値を加算して、同一レベルの次のノードを
みる。一致していれば上記と同様にスタック・テーブル
３に書き込んで、各ポインタ４．５．６を歩進して次レ
ベルの検索に移る。尚■ポインタ４は当該見つかったエ
ントリの位置から１歩進させる。

尚、それでも見つからなければ、この検索キーに該当す
るデータは無いということになる。

ｄ）リファレンス・テーブル３のＲポインタ５の指すエ
ントリが＊であるときは、レベル番号のみを比較して一
致するノード名があればそれをスタック・テーブル３に
書き込み、各ポインタ４．５．６を歩進して次レベルの
検索に移る。

ｅ）Ｒポインタ５の指示が、当該検索キーのノード数（
これは与えられた検索キーを見れば判るので予めＲポイ
ンタ５の上限値として保持しておく）を越えたとき、ス
タック・テーブル３中には１つの見つかったキーが完成
していることになる。従って、スタック・テーブル３の
内容を出力するか、または最下位レベルのノードに付加
されているデータ・アドレスを出力する。

ｆ）尚、このときＩポインタ４がインデクス・テーブル
１の最後に到達していない場合は、それ以降に別の該当
キーが存在する可能性がある。

そこで、さらにＩポインタ４を順次歩進して、当該エン
トリのレベル番号に応じてＲポインタ５及びＳポインタ
６を同一レベルに合せ、インデクス・テーブルｌの内容
とリファレンス・テーブル２の内容とを比較していく。

一旦１つのキーが見つかったときは、■ポインタは最下
位レベルのエントリを指している筈であり、その次のエ
ントリはより上位のレベルの筈である。従って、リファ
レンス・テーブル２において、Ｒポインタ５が上限値に
達するたびに、新たなキーが見つかったことになる。

ｇ）■ポインタ４がインデクス・テーブルｌの最終値に
一致すれば、検索終了したことになる。

ｈ）尚、＊が複数箇所に存在する検索キーの場合も、上
記と全く同様にして検索できる。何れの場合もインデク
ス・テーブルｌ上では一回のみ走査すれば検索は終了で
ある。

次に？によるワイルド・カード検索について説明する。

？は１つのノード名のなかの１文字についてドント・ケ
ア扱いにするものである。よって上記＊による検索にお
けるノード名比較の際に、？部分に対応する位置の文字
をマスクして比較すればよく、あとは上記ａ）〜ｈ）と
同様である。

次に、％によるワイルド・カード検索方式について述べ
る。この場合は上記とは若干具なる検索手順となる。

ｉ）初期状態は上記ａ）と同じである。また％が出現す
るまでは上記ｂ）ｃ）と同じである。

ｊ）リファレンス・テーブル２上で％が出現したら、イ
ンデクス・テーブルｌ上の当該レベルから最下位レベル
までの一連のノード名をスタック・テーブル３上に展開
し、リファレンス・テーブル２と各ノード名を比較して
、最下位レベルまで一致すれば正解として出力する。

ｋ）他の正解を検索するため、上記％が出現したレベル
のインデクス・テーブルエの次ポインタを利用して、同
一レベルで別のノード名が無いか否かを調べる。もし有
れば上記ｊ）と同様の処理をする。もしインデクス・テ
ーブル１の最後まで達すれば、検索は終了である。

■）上記ｊ）の比較照合における途中に％が出現した場
合には、より下位のレベルの％の位置について上記ｋ）
の処理を行ない、それを順次上位のレベルの％の位置に
ついて、再帰的に行なえばよい。

以上の如くにして、ワイルド・カード検索が可能である
。

又、インデクス・テーブルが大きくなると、それを複数
のブロックに分割して各ブロック毎に取り扱うことが行
なわれるが、この分割に際しても従来の分割方法はワイ
ルド・カード検索には不便であった。

従来はインデクス・テーブルを複数のブロックに分割し
たとき、補助インデクス・テーブルを設け、その中に各
ブロックを代表するキーとして、各フロックの最大キー
（第１図のインデクス・テーブル１でいえば一番下のエ
ントリに記載されたノードに対応するキー）を使用して
いた。しかし例えばｎブロック目の最大キーが（Ａ、Ｂ
、Ｃ）ｎ＋ｌブロック目の最小キーが（Ａ、Ｄ、Ｂ）の
とき、新たに（Ａ、Ｂ、Ｅ）なるキーのデータを登録し
ようとすると、これはｎブロック目の最大キーより大き
いので、ｎ＋ｌブロック目に挿入しなければならない。

（もしｎブロック目に挿入せんとすると、ｎブロックの
代表キーを変更せねばならなくなる。）その結果、（Ａ
、Ｂ、＊）のようなワイルド・カード検索の際にはｎ、
ｎ＋１の両ブロックを参照する必要が生じ、検索処理が
複雑となる。

そこで本発明では、補助インデクス・テーブルに登録す
るキーとして、対応ブロックの最大キーではなく、その
次のブロックの最小キーを登録しておく。そして新デー
タの挿入に際しては、そのデータのキーより大きい補助
インデクス・キーを持つブロックに挿入するようにする
。

第３図は本発明の一実施例による分割インデクス・テー
ブル１１．１２．１３と補助インデクス・テーブル１４
を示している。この場合、例えば（Ａ、Ｍ、ＯＢＪ、Ｐ
）なる挿入キーはブロック１２に挿入されることとなり
、且つ補助インデクス・キーの変更も不要である。そし
て（Ａ、　Ｍ。

ＯＢＪ、＊）なるワイルド・カード検索はブロック１２
についてのみの処理で可能となる。

〔発明の効果〕

以上の如く、本発明のインデクス・テーブルを用いるこ
とにより、ワイルド・カード検索が簡単なアルゴリズム
で簡単なテーブルを用いて実現出来る。

【図面の簡単な説明】

第１図は本発明の一実施例の説明図、 第２図は木構造インデクスの一例を示す図、第３図は複
数ブロックに分割したインデクスの一実施例を示す図で
あり、 図中、１はインデクス・テーブル、２はリファレンス・
テーブル、３はスタック・テーブル、４．５．６は書く
テーブルのポインタである。 第　１ｙＡ 第２１） 第２図（ｂ） 第３図

Claims (3)

【特許請求の範囲】
1. （１）複数の属性コードの連鎖を検索キーとするデータ
   の検索を、該検索キーと各データとの関係を示す木構造
   のインデクスを用いて検索する方式において、 上記インデクスを格納するインデクス・テーブル（１）
   として各エントリに、少なくとも上記属性コードに相当
   するノード名と該ノード名のレベル番号と該レベル番号
   と同一又はより上位のレベル番号であって該テーブル上
   で次に現れるエントリを指すポインタとを格納したイン
   デクス・テーブルを設け、また、 与えられる検索キーのノード名とレベル番号とにもとづ
   き、上記インデクス・テーブルを辿って目的のデータを
   検索する手段を設けたことを特徴とする木構造インデク
   スの検索方式。
2. （２）上記検索手段には、検索キーを各ノード名とレベ
   ル番号との対として格納するリファレンス・テーブル（
   ２）と、該リファレンス・テーブルの各ノード名及びレ
   ベル番号と上記インデクス・テーブルの各ノード名及び
   レベル番号とを比較照合する手段と、比較した結果一致
   したノード名及びレベル番号を順次組み立てるスタック
   ・テーブル（３）とを含むことを特徴とする特許請求の
   範囲第（１）項記載の木構造インデクスの検索方式。
3. （３）上記インデクス・テーブル（１）は複数のブロッ
   ク（１１、１２、１３）と、各ブロックの代表キーを格
   納した補助インデクス・テーブル（１４）とから成り、
   且つ補助インデクス・テーブルの各代表キーとしては該
   当するブロックの次のブロックにおける最小のキーを格
   納してあることを特徴とする特許請求の範囲第（１）項
   または第（２）項記載の木構造インデクスの検索方式。