JPH02230464A - レコード検索方法及びデータベース・システム - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ．産業」二の利用分野 本発明は、コンピュータによるデータ処理、より具体的
には、データを表現する符号化された署名を用いてデー
タを記憶及びザーチする方法及び構造に関する。

Ｂ．従来技術 まり高速なサーチを可能にするデータの符号化及び構成
法は、情報システムにとって重要である。

署名符号化は１つのそのような方法である。本発明によ
り解決される問題点を理解するために署名生成又は符号
化のプロセスについての説明から始める。ここでは、「
レコード」という用語は、データベース・レコード又は
文書内のテキスｌ・断片等の一般的なデータ・オブジェ
クｌ・を示ずために使用する。

実際の符号化プロセスは、各レコード毎に１とＯとだけ
を含む短い署名Ｓ１を計算する事より成る。これらの署
名を生成するためには種々の公知の「ハッシング」技術
を使用する事ができ、これについては詳細は説明しない
。各レコードごとに得られる署名は通常、本来のレコー
ドよりは遥かに小さい。署名及びレコードの識別子（Ｔ
ｌ１つと呼ばれる）は、後に検索するために「ページ」
」二に記憶される。ペーシとは、キー及び署名データを
含む事ができ、メモリ又はディスク上に存在しうる固定
サイズの記憶域の単位である。

１つ以上の値を含んでいるレコード又はテキスト断片の
位置を特定するために、同の右号化プロセスを用いる事
によって探索項目から署名が計算される。次に、この「
照会」署名は、記憶されている署名と比較される。照会
署名中の「１」ビットが存在する各位置において、記憶
された署名が「１」ビットを含んでいれば、署名に関連
するレコードは照会を満足している可能性があると識別
される。次に、署名と共に記憶されているＴＩＤがレコ
ードを検索するために使用される。レコード中のデータ
・フィールド（又はテキス１〜断片中のワード）は、一
致が生したが否かを決定する通常のストリング比較アル
ゴリズムを用いて、探索値に対して正ＨＥに照合される
。次に、正確な照合条件を満足するレコードがユーザー
に返される。

４一 多数のレコードを扱うために、レコードの「グループ」
に関して「親」署名が計算される。より高位のレベル（
祖父母）の署名は、同様に、下位レベルの署名のグルー
プに関して槽成される。次いで、これらの署名は階層的
な（多レベルの）ファイル構造の形に構成できる。新し
い親署名を計算する１つの周知の方法は、個々の署名の
グループの重畳又は「ビットＯＲ．Ｊである。照会署名
は、個々の署名と比較する前に、最初に、この親署名と
比較される。もし照会署名のどこかの位置で１のビット
が生じ且つ親署名中に対応する１が存在しなければ、下
位レベル（子）の署名及びそれらに関連するレコードの
グループの全体は、それ以上調査のためにアクセスする
必要がない。このプロセスは、多数の不一致の署名及び
レコードを親署名がフィルタ・アウトする事を可能にす
る。

不幸な事に、この技術が使われる時、飽和と組合せエラ
ーの両方の問題が起きる。より多くの署名が親署名に重
ねあわされる程、より多くのビットが１にセットされる
ようになる。ある時点で、飽和が起き、親署名は全て１
を含むようになる。

この時、親署名はどの照会・“：名とも照合一致しどの
照会署名も拒絶されな＜　ノ．，　１、ので、親署名は
役に立たなくなる。この飽和の問題を制御する幾つかの
方法が知られているので、それは詳細には説明しない。

第２の問題は、署名のビットは複数の元のレコードのフ
ィールドを表しているので、親署名は全ての存在してい
る個々のレコードだけでなく、親により表されるグルー
プ中のレコードから得られた値を絹合せることによって
形成されるデータを含むように見える存在しない「仮想
」レコードも表す事である。これらの仮想レコードはデ
ータ中に存在しないが、親署名によって存在しているよ
うに誤って示される。例えば、単に、姓と肩書のフィー
ルド対を含むレコード（Ｇｈａｎｇ，　Ｅｎｇｉｎｅｅ
ｒ），（Ｓｃｈｅｋ，　Ｓｃｉｅｎｔｉｓｔ）．　（Ｙ
ｏｓｔ，　Ｍａｎａｇｅｒ）及び（Ｌｅｈｍａｎ，　Ｓ
ｃｉｅｎｔｉｓｔ）を想定する。これらに関する署名は
、例えば（Ｏ○１．　１，　１０１．０）．　（０１１
１０　１　００），　（１　０　１　１　００００）及
び（０　１　０　］．　０１００）である。これら４つ
の署名のビツｌ−　Ｏ　Ｒにより形成される親署名（］
．　］．　］−　１　］Ｊ−　］．　Ｏ）は」二記レコ
ードの存在を正しく示すが、存在しない仮想レコード（
ｃｈａｎｇ，　Ｓｃｉｅｎｔｉｓｔ），　　（Ｓｃｈｅ
ｋ，Ｍａｎａｇｅｒ），　　（Ｙｏｓｔ，　Ｅｎｇｉｎ
ｅｅｒ）等の存在も示す。

グループ化署名の重ね合わせ方法を用いる事による飽和
と組合せエラーの効果は、レコードが不必要にアクセス
される事である。レコードの不必要なアクセスは、「デ
ータ偽ドロップ（ｆａｌｓｅｄｒｏｐ）　Ｊとも呼ばれ
る。親署名が原因となって１組の子署名が不必要にアク
セスされる時、これは「署名偽ドロップ」と呼ばれる。

親署名は、正確なテス１・が実行されなければならない
レコードのスーパーセッ１・を示す。理想的には、この
集合のサイズは、正しい（即ち偽ドロップを含まない）
解答集合のサイズに一致すべきである。ハッシングの不
完全性により、並びに種々の飽和及び組合せ効果により
、実際はそのようにならない。従って、データ及び署名
偽ドロップの数は、照合一致しないレコードをそれ以上
考慮しない時の符号化方式の有効性の決定的な指標であ
る。これらの問題を解決するするために、いくつかの異
なった多レベル署名構成法が、Ｒｏｂｅｒｔｓ（１９７
９），　　ＰｆａｌＬｚ　　（１９８０），　　Ｄｃｐ
ｐｉｓｃｈ　　（１９８６），Ｓａｃｋｓ−Ｄａｖｉｓ
　（１９８７）他により既に研究されている。

ＰＴａｌｔｚ　ｅｔ　　ａｌ．，　　”Ｐａｒｔｉａｌ
　　ｆＪａｔ．ｃｈ　　Ｒｅｔｒｉｅｖａｌ１１ｓｉｎ
ｇ　　　　Ｉｎｄｅｘｅｄ　　　Ｄｅｓｃｒｉｐｔｏｒ
　　　Ｆｉｌｅｓ”，Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ　
ｏｆｔｈｅ　ＡＣＭ．　Ｓｅｐｔ．　　］９８０，　　
Ｖｏｌ．２３．　Ｎｏ．　９，　ｐ．　５２２−５２８
はスパース署名符号化方式を用いた多レベル署名構成を
開示している。

Ｏに対する１の比率が低い署名は、ビットＯＲされてグ
ループ署名を形成する。これは飽和の問題の助けになる
が、組合せエラーはそのままである。

同じグループからのレコード値の組合せより成る照会は
、不必要なレコード署名のアクセスを生じる。この組合
せエラーに加えて、スパース符号化方式は、署名空間を
非効率的に使用する。

Ｒｏｂｅｒｔｓ，　　”Ｐａｒｔｉａｌ　Ｍａｔｃｈ　
Ｒｅｔｒｉｅｖａｌ　ｖｉａ　ｔｈｅＭｅｔｈｏｄ　ｏ
ｆ　Ｓｕｐｅｒ−Ｉｍｐｏｓｅｄ　Ｃｏｄｅｓ”，　Ｐ
ｒｏｃｅｅｄｉｎｇｓｏｆ　ｔｈｅ　ＩＥＨＥ，　Ｖｏ
ｌ．　６７，　Ｎｏ．　１２，　Ｄｅｃｅｍｂｅｒ　１
，９７９，ｐ．　１．６２４−］６４２はビット・スラ
イス・アーキテクチャを使用する事によって組合せエラ
ーの効果を最小化した署名記憶方法を最初に提案し実施
した。

この方式では、署名は論理的には行列の行を形成し、物
理的にはビット列毎に記憶される。照会が処理される時
、照会署名中の１が生じる位置は、行列中のどの列がア
クセスされ調査されるべきかを示す。この方法の主な欠
点は、更新及び削除のコストが高い事である。各ビット
列に関する記憶域は行の総数によって決定されるので、
各列に関する記憶域と更新の要求は膨大なものになる。

Ｓａｃｋｓ−Ｄａｖｉｓ　　　ｅｔ　　　ａｌ．．　　
　”Ｍｕｌｔｉｋｅｙ　　　八ｃｃｅｓｓＭｅｔｈｏｄ
ｓ　　Ｂａｓｅｄ　　ｏｎ　　Ｓｕｐｅｒｉｍｐｏｓｅ
ｄ　　　ＣｏｄｉｎｇＴｅｃｔ＋ｎ　ｉｑｕｅｓ　　，
　　　八〇Ｍ　　Ｔｒａｎｓａｃａｃｔｉｏｎｓ　　ｏ
ｆ　　ＤａｔａｂａｓｅＳｙａｔｅｍｓ，　　Ｖｏｌ．
　　１２＋　Ｎｏ−　４，　Ｄｅｃｅｍｂｅｒ　１，９
８７，　　ｐ．６５５−６９６は、Ｒｏｂｅｒｔｓによ
って最初に提案されたビットースライス・アーキテクチ
ャを改良する多レベル・ブロック方式を工夫している。

この方式では、ビット・スライスの親「ブロック」署名
が飽和を減少させるために使われている。しかじながら
、組合せエラーの問題は解決されていない。

さらに、更新が頻繁であるような環境では、この方式の
更新のコストは、■署名挿入当り、数十から１００以上
のページ・アクセスになり、許容できない程度に高い。

Ｄｅｐｐｉｓｃｈ，　　”Ｓ−ｔｒｅｅ　　：　　Ａ　
　Ｄｙｎａｍｉｃ　　ＢａｌａｎｃｅｄＳｉｇｎａｔｕ
ｒｅ　　Ｉｎｄｅｘ　　ｆｏｒ　　Ｏｆｆｉａａ　　Ｒ
ｅｔｒｉｅｖａｌ”，ｐｒｏｃｅｅｄｉｎｇｓ　　ｏｆ
　　ｔｈｅ　　１９８６　　ＡＣＭ　　Ｃｏｎｆａｒｅ
ｎｃａ．Ｓｅｐｔ．　８−１０．　１９８６は、葉署名
がビット・パターンの類似性によりクラスタ化された多
レベル方式を開発している。かなり大きなデータ及び照
会署名の使用により茗名は組合せエラーに対して少し敏
感でなくなっている。この方法は２つの顕著な欠点を有
している。第１に、より大きな署名に関して、より大き
な記憶空間が要求される。第２に、クラスタリングーア
ルゴリズムに関してがなり多くの計算が必要である。

Ｃ．発明が解決しようとする課題 本発明の課題は、データを効率的に探索する手段を提供
する事である。

Ｄ．課題を解決するための手段 本発明は、２以上のデータ項目のレコードを表わす署名
を符号化する方法を含む。その第１のステップは、好ま
しくはバッシングにより、レコードのデータ項口の少な
くとも２つを表わすヘース署名を計算する。次に、ベー
ス署名よりも多くのビットを有する組合せ署名が初期化
される。組合せ署名のビットは、ベース署名の２以」−
のビットの集合の各々に対応ずる。最終ステップは、組
合せ署名のビットに対して、それに対応するベース署名
の」二記各集合のビツ１・に関する１以−１二の論理演
算に基ずいて、値を割当てる。

本発明は、さらに、組合せ署名が記憶される改良された
階層的データ構造、及びそのようなデータ構造を探索す
る改良された方法を含む。この方法は、データのグルー
プの各々の組合せ署名がグループのどのデータも探索基
準に一致しない事を示す場合にそのようなデータを読取
る事なくデータのグループを拒絶するステップを含む。

Ｅ．実施例 Ｅ−１．概略 本発明の中心的アイデアは、レコードからの中一の値で
はなく値の組合せを符号化する、即ち元のレコードの署
名からの複数ビットのある組合せに基ずいて新しい署名
を計算する、新規な署名関数を使用する事である。最低
レベルの署名は「ベース署名」又はＢ木の用語では「葉
署名」と呼ばれる。より高いレベルの署名は「親署名」
又は「非葉著名」と呼ばれる。任意のデータ・レコード
に関して、Ｓ１はベース又は葉署名を示し、ＣＳ１は対
応する第１レベルの組合せ署名を示ず。

ＣＳ２、ＣＳ３、及びＣＳ４は、第２、第３、及び第４
のレベルに関するより高いレヘルの組合せ署名を示す。

各葉ページは、８１葉茗名のグループを保持する。これ
らのレコードに関する第１レベルの組合せ署名ＣＳ１は
、第２レベルの組合せ的親署名ＣＳ２を形成する必要が
あるときに計算されるが、記憶はされない。各非葉ペー
ジは、これらの親組合せ署名の組を保持する。非葉ペー
ジ自身の上の第２レヘルの組合せ茗名ＣＳ２は、グルー
プを形成し、正確に１つの親彰名、第３レベルの組合せ
署名ＣＳ３を有する。第３レベルの署名は同様にグルー
プ化され、このプロセスは全ての葉署名を包含するのに
必要なレベルまで継続する。

この新規な型の組合せ署名は、非葉レベルで使用される
時、他の方式よりも緩やかに飽和し、より多くの下位レ
ベルのグループがより少ないページ・アクセスを生じる
の事をなくす。再び、第１レベルの組合せ署名ＣＳＩは
、計算され、ビットＯＲ演算を用いて高位レベルの組合
せ署名中に蓄積されるだけであって、永久的に記憶され
ることはない。第１レベルの組合せ署名（以下、単に「
組合せ署名」と呼ぶ）ＣＳＩを計算するために、葉署名
Ｓ１が、ｌｌａｒｒｉｓｏｎ，　”Ｉｍｐｌｅｍｅｎｔ
ａｔｉｏｎ　ｏｆ　ｔｈｅＳｕｂｓｔｒｉｎｇ　Ｔｅｓ
ｔ　ｂｙ　ｆｌａｓｈｉｎｇ　＋　　Ｃｏｍｍｕｎｉｃ
ａｔｉｏｎｓｏｆ　ｔｈｅ　ＡＧＭ．　Ｖｏｌ．１４，
　Ｎｏ．１２，　Ｄｅｃｅｍｂｅｒ　１９７］，　ｐ．
’１１７−７７９等のハッシュ・アルゴリズム又は他の
標準的な方法を用いて各レコードに関して計算される。

葉署名Ｓ１に関する長さ及びハツシュ関数を見つけるた
めの技術は周知であり、例えばＦａｌｏｕＬｓｏｓ　　
　　ｅｌ　　　　ａｌ．＋　　　　　”ＯｐＬｉｃａｌ
　　　　　ＳｉｇｎａＬｏｒｃｌＥｘＬｒａｃ［．ｉｏ
ｎａｎｄｌｍｆｏｒｍａＬｉｏｎＬｏｓｓ，ＡＣＭＴｒ
ａｎｓａｃｔｉｏｎｓ　ｏｎ　Ｄａｔａｂａｓｅ　Ｓｙ
ｓｔｅｍｓ，　　Ｖｏｌ．］２，Ｎｏ．３，　Ｓｅｐｔ
．　１９８７，　ｐ．　３９５　−４２８に示されてい
る。

各葉署名Ｓ１に関して、新しいより大きな組合せ署名Ｃ
ＳＩが計算される。組合せ茗名ＣＳＩは葉署名Ｓ１より
も多くのビットを有しており、そのビットは全てＯにセ
ットされている。次に、組合せ署名ＣＳＩの各ビットが
、葉署名のビッ］・の特定の各サブセットの中の全ての
ビットが１に等しい時は、１にセットされる。これはビ
ットＡ．　Ｎ　Ｄとして知られる論理演算である。組合
せ署名ＣＳ１の各ビッ１〜に関して、Ｓｌ中のビットの
異なったザブセットを選択する。葉署名Ｓ１のグループ
に関する第２レベルの親組合せ署名ＣＳ２（以下、「第
２レベルの署名」と呼ぶ）を形成するために、グループ
の組合せ署名ＣＳＩの全てが共に重ね合わされる（ビッ
トＯＲされる）。

この署名方法は、Ｂ木、ＡＶＬ木、又はＫ　−　Ｄ木を
含む任意の数の多レベル・アクセス構造中に組込む小が
できる。これらのアクセス方法のうち最も一般的な、１
３木インデックスを川いて多レベル署名ファイルを構成
するだめの一般的な構成を以下説明する。この方法を用
いると、Ｂ木内の各葉のインデックス・キー項口に単一
の葉署名Ｓ１が挿入され、第２レベルの組合せ署名ＣＳ
２が計算され各非葉Ｂ木のインデックス・キー項目に中
に挿入される。内部の（非葉の）Ｂ木ページ中の高位レ
ベルの組合せ署名項目ＣＳ２、ＣＳ３、ＣＳ４等は下位
１ノベルの署名のグループ全体を拒絶するのに役立つが
、一方葉ページ中の葉署名Ｓ１は特定のデータ・レコー
ドを拒絶する。

本発明は既存の署名方法を」二回るいくつかの利点を提
供する。組合せ署名がＢ木ファイル中に組込まれる時、
それらは他の多レベル署名構造よりも遥かに少ない保守
管理しか必要としない。あるインデックス・キー値の範
囲にわたる普通の照会に関して、及び正確なキー値の探
索に関して、インデックスを普通に使用できる。しかし
ながら、照会がインデックス・キー値以外の探索項１」
（探索基準）を含む時、１３木は多レベル署名アクセス
法を用いて探索できる。事前順序Ｉ・ラバース（拒絶さ
れた下位レベルのペーシをスギップする）を実行し、葉
ページで署名をテス１〜する事により、データを迅速に
探索し探索基準との合致をテス１・する事ができる。こ
の探索方法はそのような改良された性能を提供する。そ
の性能は典型的にはりレーション走査を単独で用いた時
に可能であるよりも１桁良い。これは主に署名中の組合
せエラーにより生しる偽ドロップを大幅に減少させた事
による。

Ｅ−２．良好な実施例の詳細な説明 良好な実施例は、従来のデータベース管理システム（Ｄ
ＢＭＳ）のコンポーネン１・を用いて実現される。それ
は、テキス１・・データの探索を可能にする事によって
、基礎を成すＤＢＭＳの探索能力を拡張し、且つ照会中
で多数の探索項目が共にＡＮＤされる時にレコード走査
又は複数Ｂ木インデックス法に代わるものをＤＢＭＳに
提供する。最初に、使用するハッシュ法を説明する。次
に、異なった署名を計算するためのス１・ラテシーを提
供する。最後に、Ｂ木データ構造に関して署名をいかに
使用するかを述べる。

Ｅ−３．ハッシュ・アルゴリズム 良好な実施例で使用するハッシュ関数は、レコード・フ
ィールド又はテキス１〜・ワードの部分文字列を、特定
範囲内の単一の数値に符号化する手段を提供する。ハッ
シュ関数によって計算される数字は、１にセットすべき
葉署名Ｓ１中のビッ］・位置を識別する。他の適当なハ
ッシュ関数を使用しても良いが、ここではＭ．　Ｃ．　
Ｉｌａｒｒｉｓｏｎ，”Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ
　ｏｒ　ｊＪ＋ｅ　ＳｕｂｓＬｒｉｎｇ　Ｔｅｓｔ　ｂ
ｙ１１ａｓｈｉｎｇ　　．　　Ｃｏｍｍｕｎｉｃａｔｉ
ｏｎｓ　　ｏｒ　　Ｌｉｆｅ　　ＡＣＭ，　　Ｖｏｌ．
１４，Ｎｏ．２１，　Ｄｅｃｅｍｂｅｒ　１．９７１で
最初に開示されたハッシュ関数を使用する。

Ｅ−４．署名の生成 このハッシコ技術を用いて葉署名が形成されると、組合
せ署名ＣＳＩを計算するために使用する組にそのビット
をグループ分けずる方法を決定するだめの異なったスト
ラテジーが可能になる。それらのス］・ラテジーはラン
ダム方式と系統的方式のいずれかに分類される。各グル
ープに関するビットの数及びグループの総数は解析的又
は実験的に変更する事ができる。

ｍは葉署名Ｓ１の畏さを表わし、ｃｍは組合せ署名ＣＳ
Ｉの長さを表わすものと仮定する。系統的な方式では、
Ｓ１中のビット・パターンの２ｍ個の可能な組合せの全
て又は一部からビット・グループが選択される。組合せ
署名ＣＳＩの実際の長さｃｍは、葉署名Ｓ１がら必要な
組の数によって決定される。

系統的ストラテジーを用いる時は、葉署名ｓ１中の全て
の可能なビット対を識別する。これらの対の各々のビッ
トはビットＡＮＤされ、各々の結果は組合せ署名ＣＳＩ
中の特定のビット位置に写像される。これが系統的に行
なわれる時、葉君名Ｓ１のｍビットが、組合せ署名ＣＳ
Ｉのｍ−１のビット区画を形成する。第１の区画はｍ−
１ビットの畏さであり、第２の区画はｍ−２の長さであ
り、以下同様である。組合せ署名ＣＳ］のビット１は葉
署名Ｓ１のビット１及び２をビットＡＮＤする事によっ
てセッ１・される。ＣＳＩのビット２はＳ１のビットＪ
及び３をビットＡ　Ｎ　ｆ）する事によってセットされ
る。このプロセスは全てのビット対が符号化されるまで
継続する。

この系統的方法を用いると、組合せ署名ＣＳＩに必要な
ビッｌ・の総数は次式に等しい。

（ｍ−ＩＮ−（ｍ−２）＋（ｍ　　３）十・・・＋１又
は、 ｃｍ　＝　ｍ　（ｍ−１）／２ これを説明するために、各組は正確に２ビッ｝・から成
っており、葉署名Ｓ１は８ビットの長さである（ｍ＝８
）と仮定する。葉署名Ｓｌ中の全ての可能なビット対を
表わす組合せ署名ＣＳ１は２８（７＋６＋５＋４＋３＋
２＋１）ビットの長さである。

組合せエラーを伴う照会が行なわれる時に何が起きるか
を考察する事によって、この方式がどのように働くかを
説明する。照会署名ＱＳは、デー夕・レコードのフィー
ルドから葉署名Ｓ１が計算されるのと同ｂ方法で探索項
口のフィールドから計算される。次に組合せ照会署名Ｑ
ＣＳが、葉茗名Ｓ１から組合せ署名ＣＳ１を計算するた
めに使用するのと同じ技術を用いて照会署名ＱＳから生
成される。親組合せ署名ＣＳ２、ＣＳ３等に関して、候
補者としての資格を与えるために、組合せ照会署名ＱＣ
Ｓ中の各セット・ビットは親署名中のセット・ビットに
対応しなければならない。この条件に適合しない組合せ
署名ＣＳ２、ＣＳ３、ＣＳ４等は無視する事ができ、従
って、これらの署名で表現されるデータのグループ全体
も無視する事ができる。従って、組合せ署名は多数の下
位レベルの署名を検査しないで済ます事を可能にする。

Ｅ−５．８木の説明 最初にＢ木がキー及び”ＦＩＤの組をどのように組織化
するかを説明し、次に署名値がレコード・フィールドか
らどのようにして形成されるかを説明する。テキストは
１組の可変長レコード・フィ−ルドとして取扱う事がで
きるので、テギスト・オブジェクトについて別個の説明
は行なわない。

計算された署名が標準的なＩ３木のキーにどのようにし
て付加され、どのまうにして（キー、署名、Ｔ　Ｉ　Ｄ
）の項目がＢ木インデックス構造中で挿入され、削除さ
れ且つ探索されるかを説明する。

Ｂ木はデータベース・システムにおいて普通に見られる
ものであって、各レコード毎に１つ以上のキーと共に記
憶されたＴＩＤによりレコードを容易に検索する事を可
能にする。キーは（氏名等の）フィールド値であり、Ｔ
ＩＤはレコード識別子である。（キー、Ｔ　Ｉ　Ｄ）の
項目はページ上に順に記憶される。（キー、Ｔ　Ｉ　Ｄ
）項目の集合全体は、キー項目を含む葉ページを整列す
る事により、常にソートされたキー順に保持される。こ
れらの葉ページ上のキー値の位置及び範囲は、親ページ
上に記憶された１組の親（キー、ページＩＤ）項目によ
って保持される。親ページにより指し示されるページは
子ページと呼ばれる。葉ページに関する親キーは、葉ペ
ージ上の最大のキーよりも大きいが次の葉ページの最小
のキー値よりも小さいか又はそれに等しいキー値である
。親キーもソートされ、親ページ中に（親キー、子ペー
ジＩＩ））項口として保持されている。親ページ」二の
項目は、正しい葉ページへの探索を管理するのに役立つ
。

新しい（キー、Ｔ　Ｉ　Ｄ）項目が付加される時、正し
い葉ページの位置が特定され、そのページにキーが付加
される。もしページにそれ以上のスペースが存在しなけ
れば、それは２つのページに分割される。項目の半分は
元のペーシに留り、他の半分は第２のページに移動する
。親ページに関するページのオーバーフローは、葉ペー
ジと同様しこ管理される。

葉署名Ｓ１は、Ｂ木の葉ページ中に記憶され、組合せ親
署名ＣＳ２、ＣＳ３等は非葉ページ中に記憶される。こ
の結果、葉のＢ木ページに関して（キー、Ｓ１、ＴＩＤ
）の項目が、又非葉ページに関して（親キー、ＣＳ２／
ＣＳ３／・・・、子ページＩＤ）の項目が形成される。

Ｂ木の最上位レベルの組合せ署名は、照会に関係のない
部分木全体を拒絶又はフィルタ・アウ１・するのに役立
つ。

Ｅ−６．葉署名Ｓ１の形成 葉署名Ｓ１は、フィールドの部分文字列にハッシュ関数
が適用された後で指定されたビッ！・をセットずる事に
よって形成される。フィールド部分文字列はレコード中
のフィールド値又はワードの連結３文字の系列より成る
。例えば、第１図のレコード２０のフィールド２２の値
’Ｃｈａｎｇ」は３文字部分文字列の系列「Ｃｈａ」、
「ｈａｎ」、’ａｎｇＪより成っている。

ｌｌａｒｒｉｓｏｎのハツシュ・アルゴリズムは、各文
字の重みイ＝Ｊけられた値を加算する事によって各３文
字系列に基すき、数字を計算する。大文字、小文字の区
別は無視され、値Ｏ〜２５が次のように割当てられる。

即ち、ａ＝ｏ．ｂ＝１．，ｃ＝２，・・・ｚ＝２５ｏ重
み２５６°が、系列の最後の文字に与えられる。重み２
５６１が、最後の次の文字に与えられ、そして重み２５
６２が、各３文字系列の最初の文字に与えられる。文字
の値が重み付けられ加算されると、次にその結果は、葉
署名Ｓ１のビット長ｍよりも小さい最大の素数により除
算される。剰余は、葉署名Ｓ１中のどのビッ１〜位置力
月にセッ１・されるべきかを示す。このプロセスは、レ
コード・フィールド中の全ての３文字部分文字列がハツ
シングされるまで繰返される。表２は、ハッシングの例
を示している。これについては、後で詳述する。

手続きＳＩＧ　　Ｓｌは、入力としてレコードを受けと
り、出力としてレコードの葉署名Ｓｌを形成する。手続
中で、２進文字列は最初に全てＯにセッ１・される。レ
コードのフィールドの各部分文字列が走査される時、ハ
ッシュ関数によりこの文字列の最初と最後のビット位置
の間のビットが選択され、】にセットされる。ハッシン
グ中、異なった部分文字列が同じビットを１にセットす
ることもある。理想的には、特定のハッシュ関数は署名
ビットのほぼ半分を１にセットすべきである。

手続きＳＩＧ　　Ｓｌの疑似コードによる実施が表１に
示されている。この手続きへの入力データは、符号化す
べきレコード又はテギストである。

２４一 出力は、新しい葉君名Ｓ１である。その行１０２〜１．
０６は、走査プロセスが開始する前に行なわれる初期化
ステップである。行１．０８〜１２Ｇはレコード中の全
てのフィールドを処理するだめのループを形成する同じ
ハッシュ関数が、行１．１０で出会う全てのフィールド
部分文字列に関して使用される。行１１２〜１２２は、
フィールド中の各部分文字列にハッシュ関数を適用する
ループを形成している。ハッシュ結果が計算された（行
１１４．）後、それは行１１８で署名ビットをセッ１・
するのに使用される。行１．２０は、現在のフィールド
をレコードの次のフィールドに進める。ＳＩＧ　　Ｓｌ
手続きのＣ言語による実現例は、表８に示されている。

ＳＩＧ　　Ｓｌの正味の結果は、レコード中のデータを
より小さなよりコンパクトな表現に符号化することであ
る。レコードは、レコード中のフィールド値を比較する
代わりに適当に形成された葉署名Ｓ１をテストする事に
よってより効率的に探索する事ができる。

Ｅ−７．組合せ署名ＣＳＩの形成 次に、葉茗名Ｓ１から組合せ署名ＣＳＩを形成する方法
について説明する。手続きＳＴＧ　　ＣＳ１は入力とし
て葉署名Ｓ１を受取り、Ｓ１中の全ての可能なｎビット
−グループ分けを調べる事によって組合せ署名ＣＳＩ計
算する。この実施例では、ｎ＝２であり、従って、ビッ
ト対がＮ１′１べられる。しかしながら、より大きな値
を使用しても良い。従って、３つ組、４つ組等を調べて
もよい。

表２に示されている、ＳＩＧ　　ＣＳＩの疑似コードに
よる実現は、入力葉署名Ｓ１中のビッｌ・・グループを
走査する事によって出力組合せ署名ＣＳ１を形成する。

行２０２〜２０６は組合せ署名ＣＳＩを初期化し、葉署
名Ｓ１を走査するだめのループを準備する。行２０８〜
２５８の間の最初のＤｏ−ＵＮＴＩＬルーブは、現在の
８１ビットから始めて、葉署名Ｓ１中の各新しいビット
・グループを処理する。行２１８のテストは、もし８１
ビットがオフであれば、８１ビット位置をスキップする
。行２２０は、現看のＳ１ビット位置に関する葉署名Ｓ
１の残りのビツ１・を走査するプこめの位置ポインタを
初期化する。８１ビットに対する実際の論理操作は、行
２２２〜２４０の間の内側ＤＯ−ＵＮＴＩ　Ｌルーブ中
で実行される。各連続した８１ビットが行２２４で現在
の８１ビットと比較されるた後、出力ビットが順次セッ
トされる。行２２８〜２３４は、組合せ署名ＣＳ１を、
選択された論理演算の結果にセットする。

良好な実施例では、葉署名８１ビットの各対の中の２つ
のビットが両方１に等しい場合に限って、組合せ署名Ｃ
ＳＩのビツｌ・をセツ１・ずるために、ビット対の単純
な「ビットＡ　Ｎ　Ｄ　Ｊの論理演算が使われている。

行２３６〜２３８は、各々、Ｓ１とＣＳＩのビット位置
ポインタを進める。行２４４〜２５４に示すコードは、
グループ中の開始葉署名Ｓ１ビットがＯの時、内側Ｄｏ
−ＵＮＴＩＬループをスキップする最適化である。論理
演算又は「相関テスト」はビットＡＮＤより成るので、
もしＳ１グループのどれかのメンバーがＯであれば、そ
のグループに関する組合せ署名ＣＳＩビットも０になる
。表３は、葉署名Ｓ１から組合せ署名ＣＳＩがどのよう
にして形成されるかを示しており、後に詳述する。この
Ｓ］ＧＣＳＩ手続きのＣ言語による実現は、表９に示さ
れている。

葉茗名Ｓ】ビットの間の全ての相関を捕えるプロセスが
本発躬に対する鍵である。葉署名Ｓ１中でビットのどの
グループがセットされているかを記録する事によって、
組合せ署名ＣＳＩは、元のレコード中のフィールドが互
いに相関付けられているあり方を符号化する。知られて
いるどのマルチ・レベル署名符号化の発明もこの事を行
なっていないので、他の方法は、同じグループのレコー
ド中の異なったレコードから取り出された値より成る照
会を提示されると、葉署名を拒絶するのに失敗し、従っ
て重大な組合せエラーを被る。

Ｅ−８，高レベル組合せ署名の形成 次に、親署名を形成する方法を説明する。この時点まで
に、葉署名Ｓ１が記憶され、組合せ署名ＣＳＩが計算さ
れている。既存の１３木アクセス方法を使用するために
、（親キー、ＣＳ２、葉ぺ一ジＩＤ）項目に関する第２
レベルの組合せ署名ＣＳ２を計算するのに必要な手続き
を提供する。第２レベルの組合せ署名ＣＳ２は、個々の
組合せ署名ＣＳＩを重ね合せる又は「ビッｈ　Ｏ　Ｒ　
Ｊする事により形成される。この手続きは、種々の第２
レベル、第３レベル、及び高位レベルの署名ＣＳ２、Ｃ
Ｓ３、ＣＳ４等を計算するために他の手続きにより繰り
返し使用される。

ＳＩＧ　　ＯＲ手続きの疑似コードによる実施が表３に
示されている。それは、第２レベルの組合せ署名ＣＳ２
（以下、第２レベル署名ＣＳ２と呼ぶ）を形成するため
に組合せ署名ＣＳＩを重ね合せる。この手続きは、第２
レベルの署名ＣＳ２を加算して第３レベルの署名ＣＳ３
を形成するためにも使用される。入力は組合せ署名であ
る。出力は、最後に出力署名が初期化されて以来の全て
の入力組合せ署名に基づく、次レベルに関する計算され
た親組合せ署名ＣＳ２（又はレベルｉ＋１）である。リ
セッ１・・フラグは出力署名を初期化「クリア」するか
否かを示す。

出力署名は、もし新しいグループが考Ｊ恵されるならば
クリアされる（行３０２）。行３０／’］〜３０６は両
方の署名を走査するためにループを初期化する。行３０
８〜３２８の間のＤｏ−ＵＮＴＴＩ、ループは、第１の
（入力）署名を順次にビツｌ−　Ｏ　Ｒして、第２の（
出力）署名を形成する。バイト、ダブル・バイト、又は
４バイト単位を使用する事により、このループの処理ス
ピードは容易に８、１６、又は３２の因子だけ各々増加
させる事ができる。ＳＩＧ一〇Ｒ手続きのＣ言語による
実施は、表１０に示されている。

ＳＩＧ　　ＯＲ手続きは、Ｂ木中の任意のレベルにおい
て親レベル署名が形成され、１つの首尾一貫した方式で
更新される事を可能にする。更に、署名の重ね合せのビ
ットＯＲ法は、バイト単位が使用される時に非常に効率
的であるという利点を有する。

良好な実施例において使用される論理演算はいくつかの
ビットを共にビットＡＮＤするので、結果として生Ｃる
組合せ署名中でセットされたビツ！・の総数は、他の署
名方法を用いた時４１二りも這かに小さい。従って、組
合せ署名ＣＳＩのグループは、親署名を形成するのに従
来の葉署名を使用する時よりもずっと緩やかにそれらの
親組合せ署名を飽和させる。しかし、実際には、１３木
が充分なレベルを有する時は、」二側のレベルの親組合
せ署名は飽和する。とは言っても、これは非常に緩やか
に、他の署名方法を用いた場合よりもずっと高いレベル
で起きる。

階層的署名システムに関する飽和の正＋ｉ？ｆな割合は
、次のとおりである。

親飽和＝］．　Ｑ　Ｏ　Ｘ　（　］．　　ｅ（Ｎ　ｘ　
Ｉ＋　１１−ＬＤＩ１）但し、Ｎ＝葉署名の数 Ｌ　Ｉ）　＝　１にセットされた全ビットの％１．００
％に飽和した（全てｌの）署名は非常に非選択的である
。例えば、もしＳ１中のビッ１〜が１である確率（Ｓ１
ビット密度と呼ばれる）が１／４であり、そして、たっ
た８個の葉署名Ｓ１がグループ中に置かれている（Ｎ＝
８）とすると、親飽和レベルは９９．９９％である。し
かし、これと比較して、組合せ茗名ＣＳＩのビットは葉
署名Ｓ１ビットのビッｌ−　Ａ　Ｎ　Ｉ）によって形成
されるので、ＣＳＩビットが１になる確率は１．　／４
Ｘ　１．　／４即ち１／１６である。従って、親飽和レ
ベルは４０．３３％であり、これは顕著な改善である。

Ｅ−９，照会署名の生成 レコード署名及び照会署名の形成の両者に、同シ署名生
成アルゴリズムが使用される。従って、ＳＩＧ　　Ｓｔ
及びＳＩＧ　　ＣＳＩ手続きを、照会署名の計算に使用
する事ができる。照会中に与えられる探索値を保持する
ために空レコードが使われる。次に、このレコードはＳ
ＩＧ　　Ｓｌルーチンに対する入力として使われる。生
成された葉署名Ｓ１は照会署名ＱＳと呼ばれる。この照
会署名ＱＳは、組合せ照会署名ＱＣＳを形成ずるために
ＳＩＧ　　ＣＳＩに与えられる。

Ｅ−１０．組合せ照会署名ＱＣＳを用いた比較以下、ど
のようにして照会署名が使用されるがを説明する。記憶
されている親の第２又は高位レベルの組合せ署名ＣＳ２
、ＣＳ３等と組合せ照会署名ＱＣＳとを比『咬ずるため
に、任意の２つの署名を迅速に比較するアルゴリズムを
用いる。署名を比較するために、互いに署名のビットＡ
ＮＤを取り、その結果得られたビット・ストリングを元
の組合せ照会署名ＱＣＳと比較する。もし２つが同一で
あれば、照会署名とデータ署名は適合しており、子署名
又は非照会組合せ署名ＣＳ２、ＯＳ３等により表される
データが調べられなければならない。

このＳＩＧ　　ＡＮＤ手続きの疑似コードによる実現は
、表４に示されている。この手続きへの第１の入力は絹
合せ照会署名ＱＣＳである。第２の入力は、第２又は高
位レベルの組合せ署名ＣＳ２、ＣＳ３、ＣＳ４等のデー
タ署名である。

照会署名及びデータ署名のビットは、全てのビットがテ
ストされるまで一度に１つづつ比較される。行４０２〜
４０４はループ及び結果変数を初期化する。行４　０　
６〜４２２の間のＤｏ−ＵＮＴＩ　Ｌループは、ビット
毎に両署名を処理する。以前と同様に、パイ！・、２バ
イｌ・、４バイｌ・単位を用いれば、ビットＡＮＤ処理
を高速化できる７，比較結果は、行４２４で返される。

同じ手続きが、照会署名ＱＳが葉署名Ｓ１と比較される
時にも使用される。唯一の相違は、葉署名Ｓ１が組合せ
茗名よりも小さい事である。この手続きのＣ言語による
実現（ＳＩＧ　　ＣＯＶＲと呼ばれている）が表１１Ａ
及び１．１Ｂに示されている。ＳＴＧ　　ＣｏＶＲ手続
き（及び下記のＩＸＭ　　ＬＦＩＮ及び■ＸＭ　　ＬＸ
ＤＥ）によって使用される手続きＩＸＭ　　ＳＲＣＨの
Ｃ言語による実現は表１．５Ａ及び１．５Ｂに示されて
いる。

Ｅ−１．１．８木署名探索動作 この章では、照会を処理するために、Ｂ木中に記憶され
ている署名を走査するアルゴリズムが提示される。この
走査プロセスは、探索項目を含む照会が解決されなけれ
ばならない時に使用される。

ＳＩＧ　　ＳＣＡＮは、照会の探索項目を渦足する全て
のレコードを返す。探索は、Ｂ木インデックスの１・ツ
プ・ページ又は根ペーシで開始する。

組合せ照会署名ＱＣＳは、ＳＩＧ　　Ｓｌ及びＳ１Ｇ　
　ＣＳＩ手続きを用いて生成され、１３木内の、照合一
致を生じない下位レベルのベーシ（部分木）へのアクセ
スを消去するために使用される。Ｂ木は、左から右へ、
必要に応じて下位の葉レベルを訪問しながら、走査され
る。この形式の木走査は事前順序（ｐｒｅ−ｏｒｄｅｒ
）　トラバースとしても知られている。この走査アルゴ
リズムは表５の疑似コードに詳細に示されている。この
手続きは、１度だけ呼び出され、照会の探索基準に適合
する全てのデーターオブジェクトを返す。

表５のＳＩＧ　　ＳＣＡＮ手続きは、フィールド値、ワ
ード又は部分文字列がプールＡ．　Ｎ　Ｄ演算子で結合
されたものを含む照会を与えられると、Ｂ木中の署名を
探索する。この手続きは、正確な照合一致を生じる全て
のレコードを返す。「根ポインタ」は、探索すぺきＢ木
インデックスの根ページである。行５０２〜５０４は、
与えられた探索項目から照会署名ＱＳ及び組合せ照会署
名ＱＣＳを計算する。行５０８〜５７２のＤｏ−ＵＮＴ
ＩＬループは、各第３レベルの署名ＣＳ３（根レベル）
の項目をテストする。各第３レヘルの署名ＣＳ３は、行
５１２で、組合せ照会署名ＱＣＳに対してテストされる
。行５１４は、第２レベルの署名ＣＳ２より成る子署名
グループを探索しなければならない事を第３レベルの署
名ＣＳ３が示す時に使用されるテス１〜を含む。行５１
／ｌの署名テストが成功すると、行５１６で、子ページ
ＩＤに関連するＢ木の子ページが検索される。行５３４
はＣＳ２署名の走査を初期化する。

行５２４〜５６６の間のＤＯ−ＵＮＴＩＩ＝ループは、
次レベルの署名の探索に類似した論理を含んでいる。各
第２レベルの署名ＣＳ２が行５２８でテストされる。こ
のテストに成功すると、第２レベルの署名ＣＳ２に関連
する子ページＩＤが、葉署名Ｓ１を含む葉Ｂ木ページを
検索するために使われる。行５４４〜５５４で、もし照
会の照会署名ＱＳが葉署名Ｓｌと照合一致すると、記任
されたＴＩＤを用いて、対応するデータ・レコードが検
索され、標準的な文字列照合アルゴリズムを用いて正確
に調べられる。照会の探索基準がレコ−１ζ中の値によ
って正確゜にｈ１ｋ足される１１、ｙ、レコード（又は
Ｔ　Ｔ　Ｄ）が返される。さもなければ、レコードは偽
ドロップであり、無視される。ＳｉＧＳＣＡＮ手続きの
Ｃ言語による実ｊｊｌＬ例は表１２Ａ〜１２Ｆに示され
ている。

照会がフィールド値の組合せの探索項１］から成る時、
Ｂ木の高位レベルの組合せ署名が下位レベルの署名グル
ープを拒絶する。従って、署名の偽ドロップの割合が減
少する。この拒絶がＢ木の根付近で起きる時、部分木の
全体がアクセス不要になり、ディスク・アクセスの減少
と探索効率の改善を生じる。

Ｅ−１２．　　レコード及び署名の挿入新しい（キー、
Ｓ１、Ｔ　Ｉ　Ｄ）項目がＢ木中に挿入される方式を説
明する。レコード・オブジェクトを符号化し、署名を含
むＢ木に挿入する手続きを提示する事によって、その説
明を行なう。このアルゴリズムは、データベース・テー
ブル中のレコードが付加又は更頷される毎に使用される
。

（キー、Ｓ１、Ｔ　Ｉ　Ｄ）項目を挿入するために、特
定のレコードーギー・フィールドが、正しい葉ペーシの
位置を見出すために使用される。その項目が挿入され、
もしＢ木ベーシに充分な余地が存在しなければ、そのペ
ージは分割される。もし必要ならば、分割はトップ・レ
ベルまで波及し、Ｂ木の全レベル数が増加する。

この挿入プロセスの疑似コードによる実施例ＳＩＧ　　
ＩＮＳＲが表６に示されている。ＳＩＧＩＮＳＲに対す
る入力は、符号化すべきレコード又はテキストである。

ＴＩＤはレコードを検索するために使用される値であり
、根ポインタは１３木インデックスの根ページである。

新しいレコードがデータベース中に挿入される時、レコ
ードのキー・フィールドが抽出され、正規のＢ木インデ
ックスーキーが形成される（行６０２）。次に、葉署名
Ｓ１及び組合せ署名ＣＳＩが計算される（行６０４〜６
０８）。行６　１．　０で、Ｂ木の、根がら出発して下
方への探索が行なわれ、ターゲット葉ページに至る経路
に沿った既存の親レベル署名（例えばＣＳ３、ＣＳ２）
が、新しく計算された組合せ茗名ＣＳＩとビット○Ｉく
される。葉レヘルにおいて、葉ページ探索が行なわれ、
もし充分なスペースがあれば、（キー、Ｓ１、’Ｔ’Ｔ
Ｉ））項目が適当な位置に挿入される（行６２０〜６２
２）。行６２４は、新しい親第２レベル署名ＣＳ２を形
成し、これはＳＩＧ　　ＣＳＩを用いて親ページに送ら
れる。

行６２８で、もしスペース不足の条件に出あうと、標準
的なＢ木の葉ページの分割操作が開始する。この動作中
、葉ページは物理的に半分に分劃され、新しい親の第２
レベル署名ＣＳ２が、一時的に計算された組合せ署名Ｃ
Ｓ］の左半分及び右半分のグループに関して計算される
。次に、（左ギー、ＣＳ２、左子ページＩＤ）の項目が
元の親ページに伝搬され古い親の項目を更新するのに使
われる。他の（右キー、ＣＳ２、右子ページＩＤ）の項
目は、同じ親ページ上に新しい項目として挿入される。

親ページ上にスペースがなければ、同様の分割動作が起
き、新しい右及び左の項目が計算され、次に高位のレベ
ルに伝搬される。根レベルに充分なスペースがない時は
、根の分割によりＢ木にイ・」加的なレベルが生らる．
ＳＩＣ：ｆＮｓＲ手続き（ＩＸＭ　　ＬＦＩＮと呼ばれ
る）のＣ言詔による実現例が表１３Ａ〜１．　３　Ｋに
示されている。

ＩＸＭＬＦ１Ｎ（及び下記のＩＸＭ　　ＬＦＤＩΣ）に
より使用される手続きＩＸＭ　　ＳＲＣＩ−１のＣ言語
による実現例が表１５Ａ及び１５Ｂに示されている。

この手続きは、新しいキー・データが関連の署名ととも
にいかにしてＢ木中に挿入されるかをボしている。この
実現例の利点は、下位レベルのページ上の署名のグルー
プに関する親署名を計算する事により、ページ分割の基
本的Ｂ木スペース管理ス１・ラテジーに変更を加える必
要がない事である。

Ｅ−１３．　レコード及び署名の削除 次に、レコードがＢ木からどのようにして削除されるか
を説明する。キーの削除を取り扱うためにいくつかの異
なったス１・ラテジーが可能である。

各ストラテジーの背後にある一般的な考えを提供４〇一 する。

署名が使用される時、葉の（キー、Ｓ１、ｉ’　ＩＤ）
項目の各々の削除は、親の第２レベルの署名ＣＳ２に反
映されるべきである。２つの一般的なストラテジーの１
つを用いて、削除を取り扱う事ができる。ファジー削除
ストラテジーは必ずしも高位レベルの親署名を更新する
事なしに葉の項目を消去する（これは多くのデータ（ｔ
ｕｐｌｅ）が削除されると共に偽ドロップの割合を増加
させる）。遅延「正確」削除ストラテジーは、葉のグル
ープの削除が、全ての影響を受ける親を変化させる。選
択される具体的なストラテジーは、データベースに対す
る読み取りと書き込みの頻度と混合度に依存し、適当な
間隔で走行するバッチ・モード保守管理ユーティリティ
によって選択され使用されてもよい。普通のインデック
スでは、葉ページ中の要素の数があるしきい値（典型的
には半分）以下に低下しページ併合が試みられるように
なるまで、通常、削除は個々の葉ページに局在化してい
る。

通常インデックス削除は、ページが実際に削除又は併合
されるまでは親ギーに影響を与えない。

「ファジー削除」ス１〜ラテシーの疑似コードによる実
施例は表７に示されている。このＳＩＧＤ　Ｅ　Ｌ　Ｔ
手続きに対する入力は、削除すべきレコード又はテキス
トである。ＴＩＤは、重複キーの場合に項目を一意的に
識別するために使われる値である。ポインタは、Ｂ木イ
ンデックスの根ページである。ターゲットＢ木の項目は
行７０２で構成される。削除すべき項目の位置は標準的
なＢ木探索アルゴリズムを用いて決定される（行７２４
〜７２６）。次に行７２８で項目が削除される。

もしそれが最後の項目ならば、葉ページは空であり、こ
れは次のページと併合される。行７３０のテストは、こ
の条件をテストする。もし真であれば、行７３８で古い
親の項目（親キー、ＣＳ２、子ベージＩＤ）が消去され
る。もしこの親レベル・ページが空になると、このプロ
セスは根レベルに到達するまで反復される（行７４２）
。削除プロセスのＣ言語による実施例（Ｉ　ＸＭ　　Ｌ
ＦＤＥと呼ばれる）は表１４Ａ〜１４Ｊに示されている
。

この削除手続きは、項目が削除される時にＢ木がいかに
保守管理されるかを示している，，挿入手続きと同様に
、署名が包含される時、基本的な１３木のスペース管理
ス１・ラテジーに大きな変更は要求されない。これで、
本発明のＢ木実施例の詳細な説明を終える。

Ｅ−１　４−　．例 良好な実施例の動作を説明するために、８つのレコード
が挿入され照会される例を考察する。各レコードがデー
タペースに挿入される時、（キーＳ１、’Ｉ”ｌＤ）項
目より成る■３木のキーが形成される。葉署名Ｓ１はＳ
ＩＧ　　Ｓｌ手続きを用いて生成される。

８つのデーターレコードは第４図に示されている。最初
のレコード４　０　　（ｃｈａｎｇ，　ＩＥｎｇｉｎｅ
ｅｒ）ば表２に示すように葉署名Ｓ１　３４を形成する
ために使用される。先ずフィールド値をハッシングする
事から始める。Ｃ　＝　２　，　ｈ　＝　７　，　ａ　
＝　０　，　ｎ１３及びｇ＝６とする。最初の部分文字
列「Ｃｈａ　Ｊに関して、文字の値に重みが付けられ加
算されて、１　３２８６４の値が得られる。この結果は
、葉署名Ｓ１のビット長よりも小さな最犬の素数、この
場合は７で除算され、剰余４が、Ｓ１のどのビット位置
が１にセッ１・されるかを示ずｔ＝めに使用される。例
を単純にするために、各フィールドに関して最初の２つ
の３文字系列をのみをハッシングしだ後の結果を示す。

一般には、この技術を用いてフィールド全体をハッシン
グする。

第３図は、Ｃｈａｎｇのレコード４０に関する組合せ署
名ＣＳ１４−２の計算を示す。Ｓ１　３４の最後のビッ
トを除゛く各ビットがＳ１中の各残りのビッ１〜と対を
形成され、組合せ署名ＣＳ］中のビットのグループを形
成する。これが行なわれると、ＣＳＩ／］−２中の各々
のビットのグループ４　／］．　ａ〜ｇが、対応ずる８
１ビットと全ての他の残りの８１ビットとの間に形成で
きる全ての可能な対を表す。８１ビット対の両方のビッ
トが１の時を示すために、ビットＡ．　Ｎ　Ｉ）演算が
使用される。葉署名Ｓ１　３４中のビッ１〜が０の時、
組合せ署名ＣＳ］．４−２中の対応するビット・グルー
プ全体４伺 ４は０である。

（キー、Ｓ１、ＴＩＩ））項目及び組合せ署名Ｃ８１　
４２が組立てられた後、根から正しい葉ページに至るた
めに標準的なＢ木探索が行なわれる。

空のＢ木は特別なケースである。その場合、根ページも
葉ペーシであり、親ペーシ（又は署名）はまだ存在しな
い。通常、絹合せ署名ＣＳ１４−２は葉ページに下降す
る経路に沿って他の組合せ署名とビットＯＲされる。葉
レベルにおいて、（ギーＳ１、ＴＩＤ）項口が挿入され
る。

Ｃｈａｎｇ氏のレコード４０の後、第４図の残りのレコ
ードの組がデータベース及びＢ木に挿入される。実際に
は、レコードは順番に挿入する必要はない。第５図に示
すように、Ｂ木の葉ページは７つだけのレコードを含み
うると仮定する。

第６図に示すように、８番目の項目（Ｙｏｓｔ，１０１
　１００００．’Ｉ’ＩＤ８）４６がＢ木に挿入される
時、根ページは分割され、半分の項目カ月−（左）のペ
ージ４８に残り、残りが下の（右の）べ一ジ５０に移動
される。新しい項目４６が次に挿入される。しかし、親
レベルは形成する必要がない３．親レベルを形成するた
めに、２つの葉ページに関する第２レベルの署名ＣＳ２
　５２、５／′ｌが第７区に示すように計鈴：される。

ＳＩＧ　　．ＣＳＩ手続きが、各葉ペーシ４８、５０」
二の個々の葉署名Ｓ１に適用される。次に、これらの結
果はビットＯＲされ、各葉ページ４８、５０に関する第
２１ノベルの署名ＣＳ２　　５２、５４を形成する。

より多くの項目がＢ木に付加される時、この分割プロセ
スが継続し、現在のトップ・レベルのぺ−シが分割され
る毎に新しいレベルが形成される。

第８図は、３レベルに成長したＢ木を示している。

テキストに説明されているように、ギーの削除は挿入プ
ロセスの逆である。葉ページが、削除される正確に１つ
の項目を右ずる時、標準的なＢ木の併合プロセスが行な
われ、空ページが解放される。

第８図で、探索項目（”Ｓｃｈｅｋ”，　”Ｓｃｉｅｎ
ｔｉｓｔ”）より成る照会が３レベルのＢ木に適用され
る。ＳＩＧ　　Ｓｌを使用して、照会署名ＱＳ　５５が
形成され、それから組合せ照会署名ＱＣＳ　５６が形成
される。１３木の根ベージ５８が最初にアクセスされる
。組合せ照会署名Ｑ．ＣＳ５６は、次に各根ベーシの項
目と比較される。ＳＩＧＡ．ＮＤ比較手続きが、ＱＣＳ
　５６と最初の第３レヘル署名ＣＳ３　　６０とが照合
一致した事を示す。その根ページ項目の子ページ・ポイ
ンタ（］）ｉ″Ｒ）は、その子ページ６２の位置を見出
すために使用される。次に組合せ照会署名ＱＣＳ　　５
６が子ページ」二の各項１」の第２レベルの組合せ署名
ＣＳ２と比較される。署名テス１・は、照会署名中の各
１のビットに対応ずるデータ署名中の１のビットが存在
する時にのみ満足される。組合せ照会署名ＱＣ３５Ｇ中
の１の全ては、子ページ６２の第１の項目の第２レベル
署名ＣＳ２　６４中に、位ｍ　７　（Ｏから数えて）を
除いて１をイイしている。その項目は拒絶されるので、
その下位レベルの葉ページ６６はアクセスされない。

組合せ照会署名ＱＣＳ　５６が、子ページ６２上の第２
の項目の第２レベルの署名ＣＳ２　６／１と比較される
時、ＱＣＳ５６の全ての１は対応する１をイ２エする。

次に葉子ページ６８カ月）゛Ｉ″Ｒ値を用いてアクセス
され、より短い照会署名ＱＳ５５が、葉子ページ６８」
二の各項ｌ」の葉茗名Ｓ１３４と比較される。第２の項
１」に関ずる葉署名Ｓ】　３４のみが、照会署名ＱＳ　
５５の１が存在する全ての位置において１を含んでいる
。その項目中のＴＩＤフィールド（ＴｆＤ６）は次に、
関連レコードを検索するために使用され、照会中の探索
項目と検索されたレコード中のフィールド値との間で正
確なストリング比較が行なわれる。これは正しいレコー
ドなので、それはユーザーに返される。

我々が考察する次の照会は組合せエラーを含むものであ
る。第８図で、第２の照会は探索項目”Ｃｈａｎｇ”及
び゜’ＳｃｉｅｎＬｉｓＬ”より成るものであり、この
組合せは実際のデータには存在しないが、非組合せ親署
名を用れば仮想レコードとして存在するように見えるで
あろう。最初に、照会署名ＱＳ７０が照会に関して計算
される。次に、組合せ照会署名ＱＣＳ　７２が計算され
、根ページ５８の一４８ 各項目に対して比較される。組合せ照会署名ＱＣＳ　７
２は位置２２及び２５に１を含み、根ページの最初の項
目の第３レベルの署名ＣＳ３　６０はそうでないので、
その項目に関連する全ての下位レベルのページが拒絶で
きる。同様に、組合せ照会署名ＱＣＳ　７２は位置２０
、２２、２３及び２５に１を含み、根ページの第２の項
目の第３レベル署名ＣＳ３はそうでないので、その項目
に関する全ての下位レベルのページは同様に拒絶できる
。これは、組合せ（”Ｃｈａｎｇ”，　”Ｓｃｉｅｎｔ
ｉｓｔ”）が存在しない事を正しく反映している。

比較のために、第９図に示すように、２レベル署名ファ
イルを構成するために非組合せ葉署名Ｓ１を使用したと
仮定する。ここで、第２レベルの非組合せ署名７４が根
ページの項目に関して記憶−゛−れている。」二記の例
と同ら照会を用いると、非組，Ｓｉせ署名が使用される
時、ページ・アクセスの数がずっと大きく、従って全体
的性能がずっと悪くなる事が示される。

最初の照会（ＮＡＭＥ＝”Ｓｃｈｅｋ’，　Ｔ　Ｉ　’
Ｔ”ＬＥ”ＳｃｃｉｅｎＬｉｓＬ”）を処理するために
、照会署名ＱＳ５５が計算され、根ページの各項Ｉコに
対して比較される。根ページの第１の項目の非組合せ第
２レベル署名Ｓ２７４に対してテストされた後、照合一
致が示され、その項目に関連する子ページが検索される
。次に、照会署名ＱＳ　　５５が子ぺ一ジ」二の各項目
に対して比較される。照合一致は生じないので、その子
ページ上の全ての項目が署名偽ドロップであり、そのペ
ージに対するアクセスは不用であった。照会署名ＱＳ５
５が根ページの第２の項１目の非組合せ第２レベル署名
Ｓ２と比較される時、もう１つの照合一致が示され、各
千ページが検索される。照会暑名ＱＳ　５５をそのペー
ジの項目の葉署名Ｓ１と比較した後、１つだけが照合一
致を含んでいる。従って、この照会を解決するために、
全ての葉署名Ｓ１が調査された。

組合せエラーを含む照会（Ｎ　Ａ　Ｍ　Ｅ　一”Ｃｈａ
ｎｇ　，Ｔ　Ｉ　Ｔ　Ｌ　Ｅ　＝　”Ｓｃｉｅｎｔｉｓ
ｔ”）の場合、第９図の２レベル署名Ｂ木で照会署名Ｑ
Ｓ　７０が使用される時、根ページの第１の項目の非組
合せ第２レベル署名Ｓ２　７４は照会署名ＱＳと照合一
致を生じる。次に、対応する子ページがアクセスされ、
全ての葉署名Ｓ１がテストされるが、一致は全く生らな
い。ＱＳは、根ページ上の第２の項目の非組合せ第２レ
ベル署名Ｓ２とは一致しないので、その項目の対応する
子ページはスキップされる。この照会を、第７図に示す
等価な２レベル組合せ方式と比較すると、組合せ署名が
性能の大幅な改善を生じている事が分かる。

説明のため、本発明の特定の実施例は上記のように述べ
たが、本発明の技術思想及び範囲から逸脱する事なく種
々の変形が可能である。特に葉署名Ｓ１の生成には、異
なったハッシュ関数を使用するか、又は符号化される部
分文字列の長さを変える等の、代替的な符号化方法が可
能である。さらに、組合せ署名ＣＳＩは、８１ビットの
対の単純な論理的交わり（ＡＮＤ）を用いる以外の方法
で葉署名Ｓ１がら計算する事もできる。例えば、ビット
対だけを考える代りに、８１ビットの、より大きな集合
（３つ組、４つ組等）を使用する事ができる。さらに、
］二記の単純な論理演算を（ＡＮｆ））を、より複雑な
論理的計算で置き換えてもよい。

そのような署名は、上記の例やここで説明した実施例で
用いた単純な照会よりも遥かに７Ｍ雑な照会に関して有
用であろう。最後に、８１ビットのあらゆる集合につい
て同一の論理演算を使用する必要も、又Ｓ１ビットの集
合の各々が同数のメンバーを有している必要もない事を
理解されたい。ハッシュ方法、集合のサイズ及びメンバ
ーシップ、並びに集合に対して行なわれる論理演算の選
択は、提示される可能性の最も高い照会のタイプに照し
て行なわれなければならない。

Ｓｌ中のビットの集合を選択する事に対する代替的方式
は、ＣＳ１中の各ビットに関して事前に選択されたラン
ダムなビットの集合を常に使用する事である。ランダム
方式では、使用する８１ビット・グループの数（典型的
には組合せ署名ＣＳｌ中のビットの数に等しい）を最初
に事前に決定しておく。次に、葉署名Ｓ１からビットを
ランダムに選択して、組合せ署名ＣＳＩ中の各ビットに
対応する８１ビットの集合を形成する。次に、単純な論
理演ＷＡＮＤを用いて、もし集合中の全てのビットが１
に等しければ結果を１にセツ１・シ、そうでなければ結
果をＯにセットする。最後に、ＣＳｌ中の対応するビッ
トを、論理演算の結果に等しくセットする。ランダムな
葉署名８１ビットの集合が各組合せ署名ＣＳ１のビット
に割当てられると、その割当てられた選択は変更なしに
使用するべきである。

最後に、本発明は、種々のデータ構造と共に使用できる
。良好な実施例はＢ木を使用しているが、一般に任意の
階層的データ構造を使用しうる。これは、通常の２進木
、ＡＶＬ木、ｒｔｒｉｅ」構造、及びＫ−Ｄ木を含む。

Ｂ木の場合、Ｂ木における良好な署名性能を維持するた
めに、種々のファジー式の又は正確な削除ストラテジー
が可能である。

上記のファジー式削除技術に対する１つの変形例はＢ木
の上側レベル中で必要な署名を周期的に再計算する遅延
ストラテジーである。この方法は、直接的であり、且つ
標準的なバッチ・モードーインデックス構成ユーティリ
ティを変形する串により実現できる。

一９５一 −Ｕ一 ４３３一 −５３一 一６０一 一６ｌ一 Ｓ工Ｇ　　ＳＩＢ 漬」しん ソース・コード ＰＡＲＴ八 ／大　ＳＩＧ　　ＳＩＢ　　　Ｃ ／★　ｇｅｎｅｒａｔｅ　ｃｏｍｂｉｎａｔｏｒｉａｌ
＃土ｎｃｌｕｄｅ　　＜ｓｙｓ　　ａｏｎｓ．ｈ＞＃ｉ
ｎａｌｕｄｅ　　＜ｔｒａ　ａｔｒｌ。ｈ〉＃土ｎａｌ
ｕｄｅ　　＜ｔｒａ　　ｍａｃ．ｈ＞＃ｉｎｃｌｕｄｅ
　　　＜ｔｒａ　　ｅｒｒｓ．ｈ＞４ｉｎｃｌｕｄｅ　
　＜ｐａｇ　Ｊ：Ｉａｇ．ｈ＞４ｉｎｃｌｕｄｅ　＜ｐ
ａｇ　ｒｅｃ．ｈ＞＃土ｎｃｌｕｄｅ　　＜土ｓｐ　　
ｉｓｐ．ｈ＞４ｉｎｃｌｕｄｅ　　＜ｂｐｍ　ｂｐｍ．
ｈ＞４ｉｎａｌｕｄｅ　　＜ｉｘｍ　ｉｘｍ．ｈ＞４ｉ
ｎｃｌｕｄｅ　　＜土ｘｍ一土ｍ．ｈ＞＃土ｎｃｌｕｄ
ｅ　　＜ｓｉｇ　　ｓｉｇ．ｈ＞ｓｉｇｎａｔｕｒｅ Ｓ１ｂ ｆｏｒ ｉｎｐｒｅａｐ ｒｅｃｏｒｄ Ｓ工ＮＴ ｓｉｇ　ｓ１ｂ（　ｓｉｇｐ，ｓｉｇｌｅｎｚＳ工ＧＮ
ＡＴＵＲＥＰ　ｓｉｇｐ； Ｓ工ＮＴ　　　　　　ｓｉｇｌｅｎ； Ｓ工ＧＮＡＴＵＲＥＰ　ｉｎｐｓｉｇｐ；Ｓ工ＮＴ　　
　　　　ｃｌｅａｒ； ｉｎｐｓｉｇｐ， ｃｌｅａｒ ｛Ｓ工ＮＴ　　ｒｃ； Ｓ工ＮＴ　　ｂａｓｅｂｉｔ； Ｓ工ＮＴ　　ｂｉｔｐｏｓ； ｃｈａｒ　　＊ｆｉｅｌｄ； Ｓ工ＮＴ　　ｉ，ｊ； Ｓ工ＮＴ　　　ｉｉ； Ｓ工ＮＴ　　ｓ１　　ｉ； Ｓ工ＮＴ　　ｔｍｐ； ＲＥＣＯＲＤＰ　ｉｎｐｒｅｃｐ； Ｓ工ＮＴ　　　　ｆｉｅｌｄｎｏ； Ｓ工ＮＴ　　　　ｆｉｅｌｄｌｅｎ； ｃｈａｒ　　　＊ｆａｈａｒｐ； −６’ｌ− −乙ｔー −ｂｂ− 一６クー 表１２Ａ Ｓ工Ｇ　ＳＣＡＮソース・コード ＰＡＲ’Ｉ’　　Ａ ／★Ｓ工Ｇ　ＳＣＡＮ　Ｃ ／★ ★　　　ｉｎｄｅｘ　　ｓｃａｎ　　ｓｉｇ　　−　　
ｒｅａｕｒｓｉｖｅｌｙ　　ｓｃａｎｓ　　ａｌｌ　　
ｃｈｉｌｄ　　ｐａｇｅｓ　　ａｓｓｏｃｉａｔｅｄｗ
ｉｔｈ　　ｔｈｅ　　ｓｐｅｃｉｆｉｅｄ　　ｓｔａｒ
ｔｉｎｇ　　ｐａｇｅ★／ ＃ｉｎａｌｕｄｅ ＃ｉｎｃｌｕｄｅ ＃ｉｎｃｌｕｄｅ ＃ｉｎａｌｕｄｅ ４ｉｎｃｌｕｄｅ ４ｉｎａｌｕｄｅ ＃土ｎａｌｕｄｅ ＃ｉｎａｌｕｄｅ 〃土ｎｃｌｕｄｅ ４ｉｎａｌｕｄｅ ＃ｉｎａｌｕｄｅ ＃ｉｎａｌｕｄｅ 〃土ｎａｌｕｄｅ ４ｉｎｃｌｕｄｅ ＜ｓｙｓ　ａｏｎｓ．ｈ＞ ＜ｐａｑ−ｐａｑ．ｈ＞ ＜ｐａｇ　ｒｅｃ．ｈ＞ ＜ｂｐｍ　ｂｐｍ．ｈ＞ ＜ｉｘｍ　　ｉｘｍ．ｈ＞ ＜ｉｘｍ　　ｉｎ．ｈ＞ ＜ｓｉｇ　　ｓｉｇ．ｈ＞ ＜ｃａｍｓ　　ｃｉｂ．ｈ＞ ＜１００　　１ｏａ．ｈ＞ ＜ｔｒａ　　ｃｔｒｌ．ｈ＞ ＜ｔｒａ　ｍａｃ．ｈ＞ ＜ｔｒａ　　ｅｒｒｓ．ｈ＞ ＜ｖｒｍ　　ｖｓｍ．ｈ＞ ＜ｗｉｎ　ｄｉｓｐ．ｈ＞ ＃ｄｅｆｉｎｅ　　ＢＵＦＦＳ工ＺＥ　　１０２４＃ｄ
ｅｆｉｎｅ　ＰＲＯＪＳ工ＺＥ　５１２４ｄｅｆｉｎｅ
　ＰＦＩＸＳ工ＺＥ　　２５６Ｔ工Ｄ Ｄ工ＳＰＣＢＰ ＲＥＣＦＬＤＳ ｐａｇｅ−土ｄ；　　　／＊ ｄａｂｐ； 大ｒｅｃｆｌｄｓｐ； ｔｈｅ ＴＩＤ　　ｏｆ ｔｈｅ ｒｏｏｔ　ｐａｇｅ ｃｈａｒ ｃｈａｒ ＰＡＧＥＰ ＲＥＣＯＲＤＰ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｔ工Ｄ ｂｕｆｆｅｒ［　ＢＵＦＦＳ工ＺＥ］；ｐｒｅｆｉｘ［
　ＰＦ工ＸＳ工ＺＥ］；ｐａｃｒｅｐｉ ｒｅｃｏｒｄｐ； ｎｆｌｄｓ； ｒｅｃｎｏ； ｔ　ｘ　ｄ　ｏ　ｆ　ｆ　； ｅｎｄｏｆｆ； ｃｐａｇ　ｉｄ；　　　　／★ｔｈｅ ／大　ｗａｒ Ｔ工Ｄ ｃｈｉｌｄ　ｐａｇｅ 一乙ｇ一 議」」翻比 Ｓ工Ｇ　　ＳＣＡＭ ？ＰＭＤＢＳ工Ｄ　ｄｂｓｉｄ； ＢＰＭＤＢＳ工Ｄ　　ｒｅｌｄｂｓｉｄ；ＲＥＣＯＲＤ
Ｐ　　ｆｕｌｌｒｅｃｐ；ＲＥＣＯＲＤＰ　　ｐｒｏｊ
ｒｅｃｐ；Ｓ工ＮＴ　　　　ｉｔ　ｊ　； ｃｈａｒ　　　　＊ｔｉｄｐ； Ｓ工ＧＳＣＡＮＩＤ　　　ｓｉｇｓａａｎｉｄ；Ｓ工Ｇ
ＮＡＴＵＲＥＰ　ｓｉｇ１ｑｐ；Ｓ工ＧＮＡＴＵＲＥＰ
　ｓｉｇ１ｐ； Ｓ工ＧＮＡＴＵＲＥＰ　　ｓｉｇ２ａｐ；ＳＩＧＮＡＴ
ＵＲＥＰ　ｓｉｇ２ｂｐ；Ｓ工ＧＮＡＴＵ旺Ｐ　ｓｉｇ
ｑｌｐ； Ｓ工ＧＮＡＴＵＲＥＰ　ｓｉｇｑ２ａｐ；Ｓ工ＧＮＡＴ
ＵＲＥＰ　ｓｉｇｑ２ｂｐ；ＶＳＭＤＥＳＣＰ　　　ｓ
ｔｍｄｅｓｃｐ；Ｓ工ＮＴ　　　　　　ｓｉｇ　ｒａｍ
ｐ■；／＊　ｐｒｅｆｉｘ　　ｍａｎａｇｅｍｅｎｔ　
　大／ＲＥＣＯＲＤＰ　　ｐｒｅｖｒｐ； Ｓ工ＮＴ　　　ｐｒｅｖｐｆｉｘ； Ｓ工ＮＴ　　　　ｒｅｃｐｆｉｘ； Ｓ工ＮＴ　　　　ｓ２ａ，　　ｓ２ｂ；ｃｈａｒ　　　
　＊ｒｅｃａｐ； ｃｈａｒ　　　　＊ｐｒｅｖａｐ； 工ＸＭＳＣＡＮ工Ｄ　ｓｃａｎｉｄ； ｒｅｌｅｖａｎｔ ｓｃａｎ ｃｏｎｔｒｏｌ ｂｌｏｃｋ Ｓ工ＮＴ ＳＩＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ ＳＩＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ ｓｉｚｅ； ｑｗ７ ｌｐａｇ； ｐｐａｑ； ｓｉｒ； ｓ２ａｒ； ｓ　２　ｂ　ｒ　ｒ ｓ２ａｂｒ； ｈｉｔｓ； ｆｄｓ； ｔａｓ； ／★ ｓｉｇｎａｔｕｒｅ ｓｔａｔｉｓｔｉｃｓ 一一シ− ｆｄｓ，ｈｉｔｓ，ＯＬ）； ／大：　　ＴＲＡ　　ＥＸＩＴ（ｓ１ｇｒｅｔｕｒｎ（
　ｒｅ　）； ｓｃａｎ，ｒＣ）； ：＊／ 一クｑ一 ４５〇一 ｃｈａｒ ＲＥＣＯＲＤＰ ＲＥＣＯＲＤＰ ＲＥＣＯＲＤＰ ＲＥＣＯＲＤＰ ＩＸＭＩ？ＢＳＤＦ ＩＸＭＰＢＳＤＦ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ ＳＩＮＴ Ｓ１：ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ Ｓ工ＮＴ ＬＳＮ ＬＯＣＮＡＭＥ Ｓ工ＮＴ Ｓ工ＮＴ ｒｂｕｆ［　ＲＥＣ１？Ｆ工Ｘ］； ｐｂｓｄ； ｓｕｃｃｒｅｃ； ｈｉｇｈｋｅｙ； ｓｐｌｉｔｋｅｙ； ｐｂｓｄｆｌｄ； 大ｐｂｓｄｆｌｄｐ； ｐａｒｔｎｏ； ｐａｒｔｒｅａｉｄ； ｒｅｃｎｏ； ｐａｒｔｓｉｚｅ； ｎｅｗｐｆｉｘ； 土ｒｅｓｕｌｔ； ｆｉｅｌｄ； ｒＣ，　　ｒａ１； ｓｕｃｃｐｆｉｘ； ｐｂｓｄｎｆｌｄ； ＳｕＣＯｐｒｅＣｒ 土，ｊ； ｎｐｂｓｄｌｅｎ； ｐａｇ　ｌｓｎ； 工ｎａｍｅ； ｎｕｎｉｑｆｌｄ； ｎｏｒｉｇｆｌｄ； ｒｅｃｏｒｄ　　ｂｕｆｆｅｒ　　大／ｐｒｅｆｉｘ　
ｂｉｎａｒｙ　ｓｅａｒｃｈ　ｄｉｒｅｃｔｏｒｙびｓ
ｕｃａｅｓｓｏｒ　ｏｆ　ｎｅｗ　ｒｅｃｏｒｄ　＊／
ｈｉｇｈｋｅｙ　　ｆｏｒ　　ｒｉｇｈｔｍｏｓｔ　　
ｌｅａｆｐａｇｅ　　大／ｐａｇｅ　ｓｐｌｉｔ　ｋｅ
ｙ　ｒｅｃｏｒｄ　＊／ｐｂｓｄ　　ｓｌｏｔ　　　（
ｓｔａｒｔ　　ｏｆ　　ｐａｒｔｉｔｉｏｎ）　　大／
ｒｅｌａｔｉｖｅ　　ｒｅｃｏｒｄ　　ｎｕｍｂｅｒ　
　ｉｎ　　ｐａｒｔ．　　大／ｃｏｍｐｒｅｓｓｅｄ　
　ｋｅｙ　　ｐａｇｅ　　ｄｉｒ　　ｓｌｏｔ　　大／
ｓｉｚｅ　　ｏｆ　　ｓｅａｒｃｈ　　ｐａｒｔｉｔｉ
ｏｎ　　大／ｓｉｚｅ　　ｏｆ　　ｎｅｗ　　ｐｒｅｆ
ｉｘ　　ａｆｔｅｒ　　ｉｎｓｅｒｔ大／ｉｘｍ　ｃｏ
ｍｐ　ｄｉｆｆｅｒｅｎｃｅ　ｂｅｔｗｅｅｎ　ｔａｒ
ｇｅｔａｎｄ　　ｌａｓｔ　　　＜＝　　ｃｏｍｐｒｅ
ｓｓｅｄ　　ｋｅｙ　　＊／ｆｉｅｌｄ　　ｎｕｍｂｅ
ｒ　　ｗｉｔｈｉｎ　　ｐｂｓｄ　　ｒｅｃｏｒｄ　　
＊／ｒｅｔｕｒｎ　ｃｏｄｅ　＊／ ｐｒｅｆｉｘ　ｌｅｎｇｔｈ　ｏｆ　ｓｕｃｃｅｓｓｏ
ｒ＊／ｗｉｌｌ　　ｈｏｌｄ　　ｐｂｓｄ−＞ＲＥＣｎ
ｆｌｄｓ　　大／ｎｅｘｔ　　ｒｅｃｉｄ（１ｓｔ　　
ｒｅｃｉｄ，ｎｅｘｔ　　ｐａｒｔ）　　＊／ｐｒｅｆ
ｉｘ　　ａｒｒａｙ　　ｉｎｄｅｘ　　大／ｌｅｎｇｔ
ｈ　ｏｆ　ｎｅｗ　ｐｂｓｄ　★／ｐａｇｅ　ｄｏ−１
ｓｎ　ｓｔａｔｅ　＊／ｆｏｒ　　ｂｕｉｌｄｉｎｇ　
　ｔｈｅ　　ｌｏｃｋ　　ｎａｍｅ　　＊／ｕｎｉｑｕ
ｅ　　　　ｆｉｅｌｄｓ　　ｉｎ　　ｋｅｙ　　★／ｏ
ｒｉｇｉｎａｌ　ｆｉｅｌｄｓ　ｉｎ　ｋｅｙ　＊／一
グ乙一 ｔｒａＪＩｕｓｈ　（Ｅ　ＲＥＳ工Ｇｌ，”ｉｘｍｆａ
±ｌｕｒｅ”）； ｇｏｔｏ　ｅｘ１ｔ； ｌｆｉｎ”，１０， Ｌｏｃｋ， ｌａｔｃｈ ｏｒ　ｂｐｍ ｝ 一２θ一 ａｔ　ｔｈｉｓ　ｐｏｉｎｔ，ｋｅｙ　ｈａｓ　ｂｅｅ
ｎ　ｉｎｓｅｒｔｅｄ，ｐｂｓｄ　ｈａｓ　ｂｅｅｎ　
ａｄｊｕｓｔｅｄ．ｎｏｗ　ｎｅｅｄ　　ｔｏ　ｌｏｇ
　　ｔｈｅ　ｉｎｓｅｒｔ　　ａｎｄ　　ｐｏｓｓｉｂ
ｌｙ　ｉｎｖａｌｉｄａｔｅ　　ｉｎｄｅｘ−一−一−
ｌｏｇ　ｄａｔａ−−−−−　　　　−−−−−ｎｅｗ
　ＬＳＮ−−−−−ｒｃ　＝　ｉｘｍ　ｌｏｇｉ（　ｐ
ａｇｅｉｄ，ｂｕｆｐ，　　ｉｎｐｋｅｙ，．．＋，＆
（ｂｕｆｐ−＞ＰＡＧ１ｓｎ）ｒｃ　　＝　　ｉｘｍ　
　ｔｓｃｎ（　　ｐａｇｅｉｄ，　　ｂｕｆｐ，　　　
±ｎｐｋｅｙ，　　ｐａｒｔｎｏ，　　ｒｅａｎｏ，　
　．．．ｉｎｓｐａｒｍ　）； ）； ｕｓｅ　　ｐｈｙｓｉｃａｌ　　ｍａｎａｇｅｒ　　ｔ
ｏ　　ｌｏｇ，　　ｉｘｍ　　ｔｓｃｎ　　ｔｏ　　ｉ
ｎｖａｌｉｄａｔｅ．★／ ｉｆ　　（ｄｂｓｉｄ　＞　　Ｏ　＆＆　ｉｘｍ　ｌｏ
ｇｄ）ｉｆ　　（ｒＣ　＝　　ｉｘｍ　　ｌｏｇｉ（ｄ
ｂｓｉｄ，ｐａｇｅｉｄ，主ｎｐｋｅｙ，ｂｕｆｐ，Ｒ
ＴＹＰｉｘｍ　　ｌｆｉｎ））｛　　ｔｒａ−ｐｕｓｈ
　（Ｅ　　ＲＥＳ工Ｇｌ，”ｉｘｍ　　ｌｆｉｎ”，８
５，”土ｘｍ　　ｌｏｇｉ　　ｆａｉｌｅｄ．”）；ｇ
ｏｔｏ　　ｅｘｉｔ； ｝ 一ＲＩＩ− ＃ｉｎｃｌｕｄｅ ＃！ｉｎａｌｕｄｅ ＃ｉｎａｌｕｄｅ ＃ｉｎｃｌｕｄｅ ４ｉｎｃｌｕｄｅ ＃土ｎｃｌｕｃｉｅ ４ｉｎｃｌｕｄｅ ＃土ｎｃｌｕｄｅ ＃土ｎｃｌｕｄｅ ４ｉｎａｌｕｄｅ ＃ｉｎｃｌｕｄｅ ＃ｉｎａｌｕｄｅ ＃ｉｎａｌｕｄｅ ＃ｉｎｃｌｕｄｅ ＃ｉｎａｌｕｄｅ ＜ｓｙｓ　　ｃｏｎｓ．ｈ＞ ＜ｔ−ｒａ　　ａｔｒｌ．ｈ＞ ＜ｔｒａ　ｍａｃ．ｈ＞ ＜ｔｒａ　　ｅｒｒｓ．ｈ＞ ＜ｐａｑ−ｐａｑ−ｈ＞ ＜ｐａｇ　ｒｅｃ．ｈ＞ ＜ｉｓｐ　ｉｓｐ．ｈ＞ ＜ｂｐｍ　ｂｐｍ．ｈ＞ ＜ｉｘｍ　　ｉｘｍ．ｈ＞ ＜ｉｘｍ　ｉｍ，　ｈ＞ ＜ｌｏｇ　ｒｔｙｐ．ｈ＞ ＜ａｌｇ　ｃｌｇ．ｈ＞ ＜ｌｏａ　　ｌｏｃ．ｈ＞ ＜ｔｒｎ　　ｔｒｎ．ｈ＞ ＜ｅｎｖ　　ｌｏｃ．ｈ＞ ｌｆｄｅ（　ｐａｇｅｉｄ， ｐａｇｅｉｄ； ｂ　ｕ　ｆｐ　； ｉｎｐｋｅｙ； ★○ｕｔｋｅｙ； ｓｃａｎｌｉｓｔ； ＊ｄｕｍｍｙ； Ｓ工ＮＴ　　ｉｘｍ ＴＩＤ ＰＡＧＥＰ ＲＥＣＯＲＤＰ ＲＥＣＯＲＤＰ 工ＸＭＳＣＡＮ工Ｄ ｃｈａｒ ｂｕｆｐ， 主ｎｐｋｅｙ， ｏｕｔｋｅｙ， ｓａａｎｌｉｓｔ， ｄｕｍｍｙ −３ｂ一 表１４Ｊ 工ＸＭ　ＬＦＤＥソース・コード −ＰＡＲＴ　　Ｊ ｅｌｓｅ ｛　ｔｒａ」ｕｓｈ　（Ｅ　ＲＥＳ工Ｇ１，ｆａｉｌｅ
ｄ．”）； ｝ ｇｏｔｏ　ｅｘｉｔ； ｝ ｆＩｅｎｄｉｆ ｝ ｅｘｉｔ： ／大 大　　　ｕｎｆｉｘ　　ｔｈｉｓ　　ｐａｇｅ：　　　
ｒｅｍｅｍｂｅｒ　　ｔｈａｔび ｉｆ　（ｂｐｍ　ｕｆｉｘ（　ｂｕｆｐ，　　ＢＰＭ　
ＮＯＬＶ　））ｔｒａ−ｐｕｓｈ（Ｅ　　ＲＥＳＩＧ１
，”ｉｘｍ　　ｌｆｄｅｌ′，１２０，”Ｃａｎｎｏｔ
　　ｕｎｆｉｘ　　ｐａｇｅ’つ；／★：　　ＴＲＡ　
ＥＸ工Ｔ（ｉｘｍ ｒｅｔｕｒｎ（　ｒＣ）； ｌｆｄｅ，ｒｃ）； ：＊／ −ｔ？，ｔ一 −４７１一 一ｑ７一 一４７３一 Ｆ．発明の効果 本発明を用いると、データベース・システムにおいて効
率的にデータを探索する事が可能になる。

【図面の簡単な説明】

第１図はザンブル・データ・レコードと良好な実施例に
よるハッシュざれた葉署名を示す図、第２図しよ良好な
実施例によるハツシュされた葉署名の計算を示す図、 第３図は良好な実施例による組合せ署名の計算を示す図
、 第４図はサンプル・データ・レコードを示す図、第５図
は第４図の最初の７つのレコードに関する葉署名を含む
単一のＢ木の葉ページを示す図、第６図は第４図の８番
目のレコードの挿入中に第５図の単一の葉ページが２つ
の葉ページに分裂したものを示す図、 第７図は良好な実施例による２レベル組合せＢ木を示す
図、 第８図は良好な実施例による３レベル組合せＢ木を示す
図、 第９図は従来技術による２レベル非組合せ署名Ｂ木を示
す図である。 出願人　インターナショナル・ビジネス・マシーンズ・
コーポレーション

Claims (4)

【特許請求の範囲】
1. （１）２以上のデータ項目を有するレコードを表わす署
   名を符号化する方法であって、 （ａ）レコードのデータ項目の少なくとも２つを表わす
   ベース署名を計算するステップと、 （ｂ）ベース署名よりも多くのビットを有する組合せ署
   名を初期化するステップと、 （ｃ）ベース署名の２以上のビットの各組のビットに対
   する１以上の論理演算に基ずいて組合せ署名のビットに
   値を割当てるステップとを含む方法。
2. （２）特許請求の範囲第１項の方法において、（ｄ）第
   ２のレコードに関する第２の組合せ署名を計算するため
   に上記ステップ（ａ）〜（ｃ）を反復するステップと、 （ｅ）少なくとも第１及び第２の組合せ署名と同じ数の
   ビットを有する第２レベルの組合せ署名を初期化するス
   テップと、 （ｆ）第１及び第２の組合せ署名の対応ビットに対する
   １以上の論理演算に基ずいて第２レベルの組合せ署名の
   ビットに値を割当てるステップとをさらに含む方法。
3. （３）データベース管理システムの階層的インデックス
   において、インデックスがレコードの各データ・ページ
   へのポインタを有する葉ページを含み、特許請求の範囲
   第２項に記載の第２レベル組合せ署名がデータ・ページ
   のレコードを表わし、署名がインデックスのデータ・ペ
   ージの各最下位のレベルの非葉ページに記憶されたイン
   デックス。
4. （４）特許請求の範囲第３項に記載のインデックスを探
   索する方法において、データ・ページのどのレコードも
   探索基準に一致しない事を各々の第２レベルの組合せ署
   名が示すデータ・ページを拒絶するステップを含む方法
   。