(57)【要約】【課題】本発明の目的とするところはロジカルロックマネージメント（ｌｏｃｋ  ｍａｎａｇｅｍｅｎｔ）の改善された方法を提供することにある。【解決手段】ユーザのリクエストを含めてダイナミックロックテーブルのメンテナンス保守のステップを有し、ダイナミックロックテーブルでは、複数の内部節点ノードの各々は、（ａ）  親節点に対する参照を有し（ｂ）  キャラクタ比較位置を含む第１データフィールドを有し（ｃ）  比較キャラクタを含む第２データフィールドを有し（ｄ）  可変的な個数の少なくとも２つの後継者ノードへの参照を有し（ｅ）ハッシュ表アレイを有し、さらに所定数のハッシュバケットを有し、データベースへユーザのリクエストを渡す前にデータベースへのユーザに関連するロックテーブルへの問い合わせを実行するステップを有する。【選択図】図１
2006004439.tif 000002
【特許請求の範囲】
【請求項１】
複数のストリングエントリを含むデータベース（１２００）をアクセスするいくつかのユーザのリクエストの衝突検出又は衝突マネージメントのための方法、とりわけ、ロックマネージメント（ｌｏｃｋ  ｍａｎａｇｅｍｅｎｔ）のための方法において、
ユーザのリクエストを含めてダイナミックロックテーブル（１２０２）のメンテナンス保守のステップを有し、前記ダイナミックロックテーブル（１２０２）では、当該リクエストは次のようなインデクシング方法により、インデクシングされるものであり、
前記インデクシング方法は、探索ツリーを使用することにより複数のストリングエントリのインデクシングを行う方法であって、前記の複数のストリングエントリのうちの各１つが複数キャラクタの１つのストリングであるようにした当該のインデクシング方法において、前記探索ツリーは、連結リンクされた節点を有し、前記の連結された節点ノードは、１つの根節点（４）及び複数の内部節点ノード並びに複数のリーフ節点ノード（５ａ，５ｂ，５ｃ，５ｄ）を有し、前記の内部節点ノードは、１つのキャラクタ又はキャラクタのサブストリングに関連付けられており、また前記のリーフ節点ノードは、前記の複数のストリングエントリに関連付けられており、ここで、前記の複数の内部節点ノードの各々は、更に、下記の要素（ａ）〜（ｅ）を有し、すなわち
（ａ）  親節点に対する参照を有し、ここで前記親節点ノードは、前記複数の内部ツリー節点ノードのうちの他の１つのもの又は、前記根節点ノード（４）であり、
（ｂ）  キャラクタ比較位置を含む第１データフィールドを有し、前記キャラクタ比較位置は、前記キャラクタ又は、前記複数の内部節点ノードのうちの前記の１つに関連するキャラクタのサブストリングにおけるキャラクタの数を指示するものであり、
（ｃ）  比較キャラクタを含む第２データフィールドを有し、前記比較キャラクタは、前記キャラクタ又は、前記複数の内部節点ノードのうちの前記の１つに関連するキャラクタのサブストリングにおけるキャラクタが、前記キャラクタ比較位置に関連する前記ストリングエントリの１つのキャラクタ位置にて１つのストリングエントリ内に含まれているか否かを決定するため使用され、
（ｄ）  可変的な個数の少なくとも２つの後継者ノードへの参照を有し、
（ｅ）  ツリーのトラバース走査の間に後継者ノードの中の高速ハッシュ探索を可能にするための相応の親節点ノードの後継者ノードへの参照を有するハッシュ表アレイ（１８）を有し、さらに所定数のハッシュバケット（１８ａ，１８ｂ，１８ｃ，１８ｄ）を有し、
データベース（１２００）へユーザのリクエストを渡す前にデータベース（１２００）へのユーザに関連するロックテーブル（１２０２）への問い合わせを実行するステップを有することを特徴とする、衝突検出又は衝突マネージメントのための方法。
【請求項２】
複数のストリングエントリの各々におけるキャラクタの数が同じであるインデクシング方法によって、リクエストはインデクシングされる、請求項１記載の衝突検出又はマネージメント方法。
【請求項３】
複数の内部ノードのうちの少なくとも１つが、１つのキャラクタ比較位置を有する親節点ノードに対する参照を有し、キャラクタ比較位置は複数の内部ノードのうちの少なくとも１つのキャラクタ比較位置より少なくとも２だけ少ないものであるインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項４】
複数の内部節点ノードの各々が１つのレベルに関連付けられ、更に、このレベルにも関連付けられた複数のリンク連結された節点ノードのうちの少なくとも１つの参照リンクを有するインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項５】
参照リンクのうちの少なくともいくつかが２重リンク結合されたリストを形成するインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項６】
キャラクタのストリングは、アルファニューメトリックキャラクタの１つのストリングであり、複数のエントリのうちの少なくとも１つが１つのワイルドカードキャラクタを有し、該ワイルドカードキャラクタはキャラクタのストリングの任意の可変的な位置に又は複数のストリングエントリのうちの少なくとも１つの任意の可変的な位置に位置決めされるインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項７】
探索ツリーの或１つの探索が、複数の連結リンクされた節点ノードのうちの少なくともいくつかへの連結リンクを有する１つのスタックをマネージするための後入れ先出しメモリマネージャを利用するインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項８】
探索はバックトラッキングを利用するインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項９】
探索はスタックの枝刈り（ｐｒｕｎｉｎｇ）を含むインデクシング方法によって、リクエストはインデクシングされることを特徴とする請求項１記載の衝突検出又はマネージメント方法。
【請求項１０】
複数のストリングの中から、複数のキャラクタから成る所定のストリングを探索する方法であって、前記複数ストリングの各々が複数キャラクタの１つのストリングであるようにした当該の探索方法において、該方法は、下記ステップを有する、すなわち、
請求項１から９までのうちいずれか１項のインデクシング方法により探索ツリーを生成するステップを有し、ここで、前記の複数のストリングは複数のストリングエントリを形成するものであり、
前記の所定のストリングに関連する問い合わせを形成するステップと、
前記の問い合わせを利用して前記探索ツリーをトラバース走査して前記の所定のストリングにマッチングする前記複数ストリングの任意のものに１つのインデックス索引を与えるステップを有することを特徴とする探索方法によって、ロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１１】
前記探索ツリーは、請求項２から９までのうちいずれか１項記載のインデクシング方法により生成されるようにした、請求項１０記載の探索方法によって、ロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１２】
前記の所定のストリングは、複数のアルファニュートリックキャラクタ及び少なくとも１つのワイルドカードから成るようにした、請求項１０又は１１記載の探索方法によって、ロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１３】
前記のトラバース走査プロセスは、前記の複数の連結リンクされた節点ノードのうち少なくともいくつかへの連結ノードを有する１つのスタックをマネージするための後入れ先出しメモリマネージャを利用する、請求項１０から１２までのうちいずれか１項記載の探索方法によって、ロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１４】
前記トラバース走査プロセスは、バックトラキングを利用する、請求項１３記載の探索方法によって、ロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１５】
前記トラバース走査は、前記スタックの枝刈り（ｐｒｕｎｉｎｇ）を利用するようにした、請求項１３又は１４記載の探索方法によってロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１６】
請求項１０から１５までのうちいずれか１項記載の、複数のストリングの中から、複数のキャラクタからなる所定のストリングを探索する方法において、探索ツリーを生成し、前記の所定のストリングに関連する問い合わせを形成するステップは、次の事項上へ実行される、すなわち、ヒューマンリソースマネージメント、ファイナンシャルズ、ロジスティックスビジネスワークフロー、人事マネージメント、組織マネージメント、ペイロールアカウンティング、タイムマネージメント、人事開発又はネットワーク、例えばインターネット又はイントラネット、システム、例えばＲ／３システム上へ実行される、請求項１０から１５までのうちいずれか１項記載の探索方法によって、ロックテーブル（１２０２）の問い合わせが実行される、請求項１〜９記載の衝突検出又はマネージメント方法。
【請求項１７】
複数のインストラクションの記憶されているコンピュータによりリード可能な（ｃｏｍｐｕｔｅｒ―ｒｅａｄａｂｌｅ）媒体において、
前記の複数のインストラクションは、プロセッサにより実行されると、前記プロセッサをして下記のステップを実行させるインストラクションを含む、すなわち、
請求項１により衝突検出又は衝突マネージメントを実行させるステップを有することを特徴とするコンピュータによりリード可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数のストリングエントリを含むデータベースをアクセスするいくつかのユーザのリクエストの衝突検出又は衝突マネージメントのための方法、とりわけ、ロックマネージメントのための方法に関する。
【背景技術】
【０００２】
ここ数１０年コンピュータプログラマ及び科学者が、データベースを保守し、それ等の内容を探索するため新しく、そして、効率的な手法を発見してきている。探索を行うための標準的技術は、リニアな探索、ハッシング及び２進探索ツリーを含む。
【０００３】
リニアな探索技術は、キー、又はストリングを行うための最も基本的な手法である（用語“ストリング”は、アルファニューメリック又は２進キャラクタのグループを記述するため用いられる）。当該の直線的な方法メソッドは、すべての現存のストリングに対してループ動作する。前記のすべての現存のストリングは、通常、アレイ又はリニアなリンク連結リストとして組織化され、各ストリングＫｉをリクエストされるＫと比較する。リニアな探索は、下記の擬似コードにより表現され得る；
ＦＯＲ  ｉ＝１  ＴＯ  ｎ  ＤＯ
ＩＦ  Ｋｉ＝ｒｅｑｕｅｓｔｅｄ  ｓｔｒｉｎｇ  Ｋ  ＴＨＥＮ  ＲＥＴＵＲＮ
Ｉ（Ｋｉ）
ＥＮＤ  ＤＯ
ここで  Ｉ（Ｋ）は、ストリングＫに関連する情報レコードである。
【０００４】
そのような探索の実行時間は、Ｏ−記法（Ｎｏｔａｔｉｏｎ）を使用すると（関数ｆ（ｎ）はＯ（ｇ（ｎ）である）―  すべてのｎ≧ｎＯ  に対して
ｆ（ｎ）≦ｃｏｎｓｔ．ｆａｃｔｏｒ・ｇ（ｎ）  が成立つようなｎＯが存在する場合）、
Ｔｌｉｎｅａｒ（ｎ）＝Ｏ（ｎ）
こうして、リニア探索の実行時間はストリングの数ｎと共に比例的に増大する。
【０００５】
単純性、簡易性のためリニア探索は、より進んだ探索方法より少ないオーバーヘッドを有する。一般的にいえば、リニア探索は、探索すべきストリングのセットが小である場合、他の探索方法により高速である。従ってインプリメンテーションの容易性及びロバストネスのため、ｎ＜１００である際の小規模探索に対してリニアな探索は優先される。
【０００６】
リニア探索の不都合は、エントリ又はストリングの数ｎへのリニアな依存性である。リニア探索方法は、増大するｎに対して、高性能アプリケーション向けに非現実的になる。１０，０００―エントリテーブルを探索することは、１０―エントリテーブルより１，０００倍遅くなる。
【０００７】
探索に対する他の普及している技術はハッシングである。ハッシングは、リニア探索方法におけるようにすべてのストリングをあまり残さず探索しつくすというよりむしろストリングの２進表示から直接、所定ストリングのアドレス又はロケーションを計算するものである。ハッシング探索は、しばしば２段階ステッププロセスであり、ここで、ハッシング関数Ｈは、リニア探索方法を用いて探索されるストリングの小さいリストを参照するインデックス索引をリターンする。ハッシング探索は、擬似コードで次のアルゴリズムにより表現される。
【０００８】
ｉ＝Ｈ（Ｋ）
ＲＥＴＵＲＮ  Ｔ（ｉ）
ここでハッシング関数Ｈは、所定のストリングのインデックス索引、リターンインデックス索引ｉを計算する。インデックスｉはマッチングストリングのみに関与ないし参照し得、又はストリングの１つのリストを参照し得、該ストリングのリストは次いでマッチングストリングに対してリニアに探索されねばならない。
【０００９】
通常使用されるハッシング関数Ｈは下記の式を用いてハッシュ表Ｔ内へのストリングの編成組織化又はインデクシングを行う：
Ｈ（Ｋ）＝（キーストリングＫの総バイトｂ１，…，ｂｍ（ＡＳＣＩＩコード）の和）ｍｏｄｕｌｏ  Ｍ
ここでＭはハッシュ表Ｔのサイズを表す。明らかにハッシュ関数Ｈは、一般に、各ストリングに対して固有―意であることが保証され得ない。２以上のストリングにより、同じハッシュ関数が生じる場合には、（異なるストリングＫｉ≠Ｋｊに関して（Ｈ（Ｋｉ）＝Ｈ（Ｋｊ）が生じる場合には）衝突ケースの発生と称される。衝突ケースに対処する最も普通の手法は、リクエストされたエントリを見出すべく通常リニア探索方法により、衝突リストの探索を要する各々のハッシュ表エントリに対して同一のハッシュ値を有するストリングのリストを維持保持することである。
【００１０】
一般にハッシングの実行時間は、衝突リストの平均長さに依存し、前記の衝突リストの平均長さは、ハッシュ関数Ｈの分布のみならず、ハッシュ表サイズＭにも依存する。ハッシュ関数Ｈがほぼ完全な分布（すなわち、任意のキーストリングＫがインデックスｉ＝Ｈ（Ｋ）へ分散、分布される確率がすべてのｉ＝１…Ｍに対して等しい起こり易さである）を有するものと仮定すると、ハッシングの平均実行時間は次のようになる。
【００１１】
Ｔｈａｓｈ（ｎ）＝Ｏ（ｎ／Ｍ）
その結果は、十分大きなハッシュ表サイズＭ＞ｎ、に対してほぼ一定である実行時間である。
【００１２】
従って、理論上、実行時間は、ほぼｎに無関係であると期待され得る。ここでは完全なハッシュ関数（大多数の実世界アプリケーションにおける非現実的な期待）を使用し得るならばの条件付きである。
【００１３】
ハッシングの欠点は、衝突のケースを分解する固有の必要性により、付加的で、時には長たらしい検索の行われることが要求される。ハッシング技術を利用する平均探索が迅速であるが、探索を完結する実際の時間長さは、所定のストリング分布に対して最も一層より悪くなり得る。最悪のケースでは、すべてのストリングが、同じインデックスにて終わることが起こり得て、探索の総合的性能が、リニアな探索の場合より良好なものとならない。従って実際上、実時間世界アプリケーションに対して効率的なハッシュ関数を見出すことは、困難なタスクであり、インデクシングすべきストリングの実際の確率分布に著しく依存する。
【００１４】
ハッシングのもう１つの欠点は、ワイルドカード探索に役立たないことである。ワイルドカード探索は、そこにて探索ストリングにおける１つ以上のキャラクタがワイルドカードキャラクタであるようなものである（すなわち、他の任意のキャラクタにとって代わり得るキャラクタである）。ワイルドカード探索は、しばしば多重マッチングストリングをリターンする。
【００１５】
探索の他の方法は探索ツリー方法である。その種探索が実行される前に、その上にて探索を実行すべきデータを編成組織化するために探索ツリーを生成しなければならない。探索ツリーインプリメンテーションの種々のものが提案されており、その中で最も基本的なものは、２進探索ツリーであり、この２進探索ツリーは、次のように規定される。
【００１６】
（ツリー節点ノードにより表される）ストリングの１セットＫ１，…，Ｋｎにわたる（２進）ツリーＴは、次の条件が成立つ場合、探索ツリーと称される、すなわち、いずれのサブ節点ノードＴに対しても、そして、Ｔの左のサブツリーにおけるいずれの下降するノードＴ１に対しても、また、右のサブツリーにおけるいずれのＴrに対しても、下記が成立つ場合；
ｖａｌｕｅ（Ｔ１）＜ｖａｌｕｅ（Ｔｒ）、ここで  ｖａｌｕｅ（Ｔ）は、ツリー節点ノードＴに関連するストリング値であって、探索ツリーと称される。
【００１７】
こうして基本的な探索手続きを（再帰的に）擬似コードで次のように定式化できる（通常のように、Ｋは探索されているストリングを表し、そして、非存在のキーのような特別な場合は、簡単化のため省略し得る）：
ＰＲＯＣＥＤＵＲＥ  ＴＲＥＥ―ＳＥＡＲＣＨ（Ｔ，Ｋ）
ＩＦ  Ｋ＝ｖａｌｕｅ（Ｔ）  ＴＨＥＮ
ＲＥＴＵＲＮ  Ｉｎｆｏｒｍａｔｉｏｎ  ａｓｓｏｃｉａｔｅｄ  ｗｉｔｈ  Ｔ
ＥＬＳＥ
ＩＦ  Ｋ＜ｖａｌｕｅ（Ｔ）  ＴＨＥＮ
ＴＲＥＥ−ＳＥＡＲＣＨ（ｌｅｆｔ-ｓｕｂｔｒｅｅ（Ｔ），Ｋ）
ＥＬＳＥ
ＴＲＥＥ−ＳＥＡＲＣＨ（ｒｉｇｈｔ  ｓｕｂｔｒｅｅ（Ｔ），Ｋ）
ＥＮＤＩＦ
ＥＮＤＩＦ
上述の探索ツリーは、―方法メソッドは、深さ優先―ツリー―トラバース走査を実行し、それにより、ツリーの深さに比例して増大する実行時間を生じる。従って、適当にバランスされた探索ツリーの条件下で（すなわち、それのリーフ節点ノードが実質的に均に分布しているツリー）平均実行時間は次の通りである。
【００１８】
Ｔｔｒｅｅ＝Ｏ（ｌｏｇ２ｎ）
こうして，理論上、平均実行時間は、エントリ、又はストリングの数と共に対数的に増大する。このことは、多数のエントリに亘って探索する場合、リニア探索に対しての実質的改善を成す。
【００１９】
探索ツリー方法の１つの欠点は、フィールド条件下で、実行時間は大いに変化し得る、それというのは実際上、探索ツリーはめったにバランスされないからである。ツリーのバランシング特性は、著しく、実際のストリング分布に依存する。前記問題を最小化するため、下記刊行物に記載されている、ＡＶＵ  ツリー（tree）のような複雑な方法が案出されている、すなわち、
Van Wyk， Christopher J., 著述 Data Structures and C. Programms， Addison-wesley Publishing， １９８８年。
しかしながら、そのような方法は、またツリー構造管理のためインプリメンテーション上のオーバーヘッドを増大させる傾向を呈する。実際上、アクチュアルのインプリメンテーションに依存して、ツリーをベースとする探索は、エントリの数が幾１００のブレークイーブンポントを越えないならば、簡単なリニア探作を凌駕することはない。
【非特許文献１】Van Wyk， Christopher J., 著述 Data Structures and C. Programms， Addison-wesley Publishing， １９８８年
【発明の開示】
【発明が解決しようとする課題】
【００２０】
本発明の目的とするところはロジカルロックマネージメント（ｌｏｃｋ  ｍａｎａｇｅｍｅｎｔ）の改善された方法を提供することにある。
【課題を解決するための手段】
【００２１】
本発明によれば、複数のストリングエントリを含むデータベースをアクセスするいくつかのユーザのリクエストの衝突検出又は衝突マネージメントのための方法、とりわけ、ロックマネージメント（ｌｏｃｋ  ｍａｎａｇｅｍｅｎｔ）のための方法において、
ユーザのリクエストを含めてダイナミックロックテーブルのメンテナンス保守のステップを有し、ダイナミックロックテーブルでは、当該リクエストは次のようなインデクシング方法により、インデクシングされるものであり、
インデクシング方法は、探索ツリーを使用することにより複数のストリングエントリのインデクシングを行う方法であって、複数のストリングエントリのうちの各１つが複数キャラクタの１つのストリングであるようにした当該のインデクシング方法において、探索ツリーは、連結リンクされた節点を有し、連結された節点ノードは、１つの根節点及び複数の内部節点ノード並びに複数のリーフ節点ノードを有し、内部節点ノードは、１つのキャラクタ又はキャラクタのサブストリングに関連付けられており、またリーフ節点ノードは、複数のストリングエントリに関連付けられており、ここで、複数の内部節点ノードの各々は、更に、下記の要素（ａ）〜（ｅ）を有し、すなわち
（ａ）  親節点に対する参照を有し、ここで親節点ノードは、複数の内部ツリー節点ノードのうちの他の１つのもの又は、根節点ノードであり、
（ｂ）  キャラクタ比較位置を含む第１データフィールドを有し、キャラクタ比較位置は、キャラクタ又は、複数の内部節点ノードのうちの１つに関連するキャラクタのサブストリングにおけるキャラクタの数を指示するものであり、
（ｃ）  比較キャラクタを含む第２データフィールドを有し、比較キャラクタは、キャラクタ又は、複数の内部節点ノードのうちの１つに関連するキャラクタのサブストリングにおけるキャラクタが、キャラクタ比較位置に関連するストリングエントリの１つのキャラクタ位置にて１つのストリングエントリ内に含まれているか否かを決定するため使用され、
（ｄ）  可変的な個数の少なくとも２つの後継者ノードへの参照を有し、
（ｅ）  ツリーのトラバース走査の間に後継者ノードの中の高速ハッシュ探索を可能にするための相応の親節点ノードの後継者ノードへの参照を有するハッシュ表アレイを有し、さらに所定数のハッシュバケットを有し、
データベースへユーザのリクエストを渡す前にデータベースへのユーザに関連するロックテーブルへの問い合わせを実行するステップを有する。
【発明を実施するための最良の形態】
【００２２】
本発明は、ジュエネリックインデクシング及びパーシャルマッチ問い合わせを支援するアルファニューメリック又は２進ストリングの高速インデクシング及び検索取出のための方法を提供することにより前述の問題を克服する。本発明は特有一義的コンパクトツリーを利用し、ここで、１つの節点ノードが、１つの探索ストリングにて複数のキャラクタをステップ的に走査するため使用され得、そして、基礎となるストリングアルファベット内に存在するキャラクタ（例えば８ビットーベースーキャラクタに対して２５６）と同じ数の後継者サクセッサー節点ノードを有し得る。更にワイルドカード探索中可能な多重マッチングストリングのため複数のサブツリーないしツリーを探索する必要がある場合、本発明はバックトラッキングを使用する。また、本発明はヒューリスティックサブツリー枝刈り（ｐｒｕｎｉｎｇ）すなわち、それによりパーシャルマッチ探索をサブツリー全体の破棄により加速し得る方法を利用する。
【００２３】
本発明は、ストリングを使用したケースに主に適用されるが、そのような探索はデータベース中に記憶されている任意のデジタル情報を探索するため使用し得る。
【００２４】
発明の要約
本発明は、ストリングの形態で記憶されている高速探索及びインデクシング法に関する。この発明は所定の問い合わせストリングにマッチングするようデータベースを迅速に探索するための手段を提供する。開示された実施例では探索方法メソッドは、図解のためアルファニューメリックストリングに関連付けて利用される。
又、本発明によれば複数のストリングの中から、複数のキャラクタから成る所定のストリングを探索する方法であって、前記複数ストリングの各々が複数キャラクタの１つのストリングであるようにした当該の探索方法において、前記方法は、下記ステップを有する、すなわち、
請求項１から９までのうちいずれか１項のインデクシング方法により探索ツリーを生成するステップを有し、ここで、前記の複数のストリングは複数のストリングエントリを形成するものであり、
前記の所定のストリングに関連する問い合わせを形成するステップ
前記の問い合わせを利用して前記探索ツリーをトラバース走査して前記の所定のストリングにマッチングする前記複数ストリングの任意のものに１つのインデックス索引を与えるステップを有するのである。
【００２５】
本発明による所定のストリングを探索する方法を次の事項に関連して使用すれば特に有利である、すなわち、ヒューマンリソースマネージメント、ファイナンシャルズ、ビジネスワークフロー、人事マネージメント、ペイロールアカウンティング、タイムマネージメント、人事開発又はネットワーク、例えば、インターネット又はイントラネット、システムに関連して使用すれば特に有利である。そのようなシステムは、特にドイツ連邦共和国のＳＡＰ、ＷａｌｌｄｏｉｆからのＲ／３システムであり得る。
【００２６】
本発明のいくつかの基本的側面及び有利な実施例は、次のようなものである。
【００２７】
高速のストリングインデクシング方法は、効率的に、コンパクトな探索ツリーを利用して、アルファニューメリック又は２進ツリーを記憶し、探索し、そして除去する。探索ツリーにおけるレベルの数は、可能であれば、１つより多くのキャラクタを表す１つの節点ノードにより最小化される。ツリーの各内部節点ノードは、順次ハッシングに対するハッシュ表アレイを有し、このハッシュ表アレイはまた、１つの所定の節点ノードをトラバースするのに必要とされる時間を最小化する。キャラクタレベルにおけるワイルドカードのようなパーシャルマッチングのため探索を実行し得る。ストリングエントリの同じテーブル上にて、独立的に、且つ、同時に多重のインデクスをオープンし得る。
【実施例】
【００２８】
発明の詳細な説明
本発明は探索を行いデータベースを保持するための改善された方法を開発したものである。本発明は、従来の探索及びインデクシングに比して多くの利点を有する。そのうちの１つは、スピードであり、優れたスピードは主に、３つのファクタに帰せられ得る。エントリ又はキーストリングの数に対するロバストネス、キーストリング分布に対するロバストネス及びキーストリング長さに対するロバストネス。それ等のすべての３つのファクタを以下に詳細に説明する。
【００２９】
Ｋ１＝ｂ１１...ｂ１ｍ，Ｋ２＝ｂ２１...ｂ２ｍ，...,  Ｋｎ＝ｂｎ１...ｂｎｍ  により表されるランダムのｍ―キャラクタキーストリングｎ個の１セットをインデクシングするものとする。
【００３０】
図解目的のため、各キャラクタが８ビットバイトとしてコード化されている通常のケースを仮定し、各キーストリングの長さが２５６バイト（ｍ＝２５６）であると仮定する。
【００３１】
キーストリングの数に対するロバストネスは、ストリングの数ｎが増大するに従って、ＩＮＳＥＲＴ，ＲＥＭＯＶＥ,及びＦＩＮＤの基本動作ｏｐｅｒａｔｉｏｎｓの平均実行時間が固有的に増大するのを制限することに関連する。
【００３２】
本発明において、開示された高速ストリング方法（好適実施例中では“ＦＩ”と称される）は、インデクスツリーをトップからボトムへトラバース走査し（それの構造は、次のことを除いて２進ツリーのそれと類似している、すなわち、内部ノードがそこから直接下降している、単に２というよりむしろ多重のサブツリーを有し得ることを除いて類似する一方、同時に左から右へ探索ストリングをステップ的に走査して進む。探索ツリーの最後のキャラクタに到達すると、プロセスはマッチングを指示する探索ツリーのリーフ節点ノードに到達しているか、又は探索ストリングが現在インデクス中に存在していないことを検出している。こうして、ツリー節点ノード検査の平均総数は、インデクスツリーの平均深さと等しいか、それより小でなければならない。
【００３３】
本発明に関連して利用される探索ツリーの平均深さは次のように計算し得る。探索ツリーの平均ブランチングファクタＫは、任意の内部節点ノードから発する子孫下降サブツリーの平均数として定義付けられ得る。従って、Ｋは、基礎となるアルファベットにおける基礎となるキャラクタの数と等しいか、又はそれより小である（例えば、８ビットに対して２５６）。しかしながら、実際上、平均ブランチングファクタは、当該の数より著しく小である、それというのは、キーストリングの実世界分布は、通常均一分布とは程遠いものであるからである。ランダムな実世界データの大きなセットを用いての実験結果の示すところによれば、リズナブルなブランチングファクタは、４〜９ビットの基礎となるアルファベット及び１６〜５１２のキャラクタのストリング長さに対して  Ｋ＝３…７のレインジ内にある。
【００３４】
内部節点ノードの数はツリーＴの各後続レベルに対してＫのファクタだけ増大するので、最終レベルでの（キーストリングの総数に等しい）リーフ節点ノードｎの総数は、次のように表され得る。
【００３５】
ｎ＝ｋｄｅｐｔｈ（Ｔ）  又は  ｄｅｐｔｈ（Ｔ）＝ｌｏｇＫｎ
更にＦＩ  ｏｐｅｒａｔｉｏｎｓ  ＩＮＳＥＲＴ，  ＲＥＭＯＶＥ  及び  Ｆ  ＩＮＤ  の平均実行時間がツリーの深さに等価であるので次のように表され得る。
【００３６】
ＴＦＩ（ｎ）＝Ｏ（ｌｏｇＫｎ）そして実行時間は、エントリの数の増大と共に対数的にのみ増大する。例えば、Ｋ＝４の場合、キーストリングエントリの数の４倍になるごとに、平均してそれらの考慮されるべき動作ｏｐｅｒａｔｉｏｎｓ  に対して唯もう１つのレベルが加えられるだけである。
【００３７】
キーストリング分布に対するロバストネスは、エントリの所定のセットに対して探索時間の分散偏差を制限することに関連する。換言すれば、１つの任意の所定のエントリに対する探索は、理想的には他の任意のエントリごとに最悪のケースに関してーに対する探索と同じ時間量を取るべきである（すなわち、最悪のケースは平均ケースより遙かに多くの時間をとるべきではない）。しかしながらキーストリングの実世界分布に基づき、１つの２進ツリーがインデクスツリーのトップの近傍でいくつかのリーフ節点ノード及び極度の深さのところで他のリーフ節点ノードを有し得る。最悪のケースにて、２進ツリーは、そこにて、いくつかのエントリに対する探索がリニアリスト探索と同じ時間のかかるポイントへ縮退し得る。ＡＶＬツリーは、２進ツリーより幾らか良好に分布されるが、アルゴリズムのデータ構造を維持するのに劇的に増大する管理オーバーヘッドを代償にして行われるものであり、これにより、総合的な性能が悪化する。ハッシングアルゴリズムはまた、エントリのバランスされていない分布をも来し得る。理想的には、エントリはハッシングテーブルを横切って均一に分布され、そして、衝突リストは、多かれ少なかれ均一の長さである。実際上、或衝突リストは、他のものより長い。最悪のケースでは、すべてのエントリが、同じハッシュスロットにマッピングされ、１つのハッシュ探索は、１つのリニアリスト探索に等価なものとなる。
【００３８】
ＦＩインデクスツリーが概して完全にバランスされたツリーではないけれども、最大縮退の度合いが制限される。それというのは、少なくとも１つのストリングキャラクタが、ツリーを降下する各下降ステップに対して探索ストリングにて、トラバースされるからである。こうして、ツリーＴの総合深さは、キーストリング長さｍにより制限され、このキーストリング長さは、通常エントリｎの総数より対数的に小さい数である。
【００３９】
キーストリング長さに対するロバストネスは、個別のエントリの平均長さｍへの探索時間の依存性を制限することに関連する。このことは、ロジカルロックマネージメント（ｌｏｃｋ  ｍａｎａｇｅｍｅｎｔ）のようなアプリケーションにおいては重要な配慮事項であり、ここでは各キーストリングが、全データベーステーブルラインに相応し得る。それ等のアプリケーションでは、数１０００ではなくとも数１００のキャラクタの長さであるキーストリングをインデクシングし探索することが重要であり得る。従来の探索方法を用いる場合、大きなキーストリング長さは、しばしば、各探索ステップに対して長ったらしいキャラクタごとの比較を必要とする。
【００４０】
ＦＩは、各探索ステップが探索ストリングにて多重キャラクタをカバーし得るようにして、キーストリングをインデクシングし得る能力を有する。実際のストリング長さに無関係に、各探索ごとに唯一の単一のキャラクタ検査しか必要でない。ＦＩインデクスツリーＴの深さが通常ストリング長さｍより遙かに小さいので、ストリングの大部分を、検査する必要がなく、探索プロセス中スキップし得る実験の結果により確認されたところによれば、大抵の実世界アプリケーションにて、ＦＩ性能がキーストリング長さと共に大して変わらない。ＦＩは、誤ったリターンの無いことを検証するのに、探索ストリング及びリーフ節点ノード（又はワイルド探索の場合における節点ノード）の１つのファイナル比較をしさえすればよい。
【００４１】
図示の実施例
ＦＩインデクシングツリー２の有利な実施例の基本構造例が図１に示してある。
【００４２】
当該の図解においてツリーに関連するデータベースは次のよなストリングエントリを有する。“ａｂｃｄ”，“ｃｄａｆ”，“ｃｄｄｈ”，及び“ｇｆｂｅ”．
簡単のため、及び図解目的のためだけにそれのキーストリングに対する基礎となるアルファベットは８つのキャラクタ（３ビット）を有する。注目すべきことには、比較的に小又は大のアルファベット（例えば８ビットに基づく）が大抵のアプリケーションにとって有用である。
【００４３】
インデクスツリー２のトップには根節点ルートノード４が位置付けられ、このルートノード４は、インデクスツリーの初期設定の際生成される第１ノードである。リーフノード５ａ，５ｂ，５ｃ，及び５ｄは、キーストリングフィールド６ａ，６ｂ，６ｃそして６ｄ並びに情報フィールド７ａ，７ｂ，７ｃ，７ｄに関連付けられ、それらのキーストリングフィールドは、インデクシングされるキーストリングを含み、前記情報フィールドは、ユーザがインデクシングされるキーストリングと関連付けたい任意の付加データを含む。注目すべきことには、ユーザは、複数情報フィールドを１つの所定のキーストリングと関連付けたいと願う。例えばキーストリングは、従業員識別番号であり得、別個の情報フィールドは、従業員氏名、アドレス、電話番号等であり得る。
【００４４】
２進ツリーにおけるように、内部節点ノードが存在し、それ等の内部ノード節点ノードは、所定のキーストリング又はユーザ提供の情報に関連付けられているのではなく、比較に関連付けられており、この比較は、所望のリーフノードへ向かっての方向、指示を与えるものである。図１には唯一の内部ノード節点８が示されているが、コンピュータプログラミングの当業者にとって、明らかなようにインデクスツリーがしばしば多数の内部ノードを有する。
【００４５】
内部ノード節点は、いくつかのデータフィールドを含む。親フィールド１０は当該節点の親ノード、ルート、根ノード４を参照する。Ｐｏｓ  ｆｉｅｌｄ  １１は、キャラクタ比較位置（ｐｏｓ）と称されるものについての情報を含む。このフィールドは各内部ノード節点に対して次の条件が充足されるように維持される、すなわち、第１のｐｏｓキャラクタ（すなわち、長さｐｏｓのサブストリング）は、その節点ノードから発するサブツリー内に含まれているリース節点ノードに関連するすべてのキーストリングに対して、同一であるとの条件が充足されるように維持される。キャラクタ比較位置が指示しているところによれば、キャラクタ比較が、共通のサブストリングにつづく後続の節点ノードにて行われるべきであるということである。キャラクタ比較位置は、同一のキャラクタシーケンスをスキップすることにより、インデクスツリーに亘って探索プロセスを加速するため使用される。Ｆ１ツリーの性質によれば、１つの所定のサブツリーのリーフ節点ノードに含まれているすべてのストリングが同じプレフィックスを有する。例えば、リーフ節点ノード５ｂ、５ｄは内部節点ノード８と共に１つのサブツリーを構成し、それぞれキーストリング“ｃｄａｆ”及び“ｃｄｄｈ”に関連付けられる。それ等の２つのサブストリングは、プレフィックス“ｃｄ”を共用する。この例では、内部節点ノード８のｐｏｓフィールドはキャラクタキャラクタ比較位置数２を含むこととなる、というのは、これは、内部節点ノード８から発するサブストリングに含まれるすべてのストリングの長さであるからである。当該のキャラクタ比較位置に関連するキャラクタは、第３キャラクタであり、この第３キャラクタは、２つのサブストリングが共通に有しない第１のキャラクタである。
【００４６】
Ｓｕｃｃフィールド１２は、後継者節点ノードの現在、瞬時番号のトラックをキープする。事例では、内部節点ノード８は、２つの後継者リニア８ｂ及びリーフ節点ノード５ｃを有する。ＳｕｃｃＦｉｒｓｔフィールド１３は、すべての後継者ノード節点ノードの２重にリンクされたＮＵＬＬ−終端されたリスト（時により、サイブリングリストと称される）の第１のノードに対する参照である。事例中内部ノード８のＳｕｃｃＦｉｒｓｔフィールド１３は、リーフ節点ノード５ｂを参照する。ＳｕｃｃＦｉｒｓｔフィールド１３は、他のものの中で、ＲＥＭＯＶＥ機能のために用いられ、これについては以下説明する。
【００４７】
ＣＨフィールド１４は節点ノードの比較キャラクタを有する。比較キャラクタは、或１つの節点ノードをサイブリングノードから区別、識別する第１のキャラクタである（これは他の点では同じストリングを共有する）。
【００４８】
ＳｂｌＰｒｅｖ  フィールド１５は、サイブリングリストの先行（左隣）の節点ノードへの参照リンクである。サイブリングリストの先行節点ノードがない場合、（リファレンス）リンクは、ＮＵＬＬ（零）リファレンスである。同様に、ｓｂｔＮｅｘｔフィールド１６は、サイブリングリストの次の（右隣）ノードへのサイブリングリストの次の節点ノードがない場合、参照リンクは、零参照である。事例では、内部節点ノードへの参照リンクであり、内部節点ノード８のフィールド１６は、リーフ節点ノード５ｄへの参照リンクである。
【００４９】
ローカル後継者ハッシュ表１７は、追従すべき適正な後継者ブランチの探索及び識別に使用される。（すなわち、所定の探索中進行すべきツリーを更に１レベル下る）ローカル後継者ハッシュ表１７は、ハッシュ表アレイ１８及びフィールド１９からなるハッシュ表アレイ１８は、キャラクタ値を表すハッシュバケットの固定数を含む。事例では基礎を成すキーストリングを構成する８つのキャラクタが４つのハッシュバケット１８ａ、１８ｂ，１８ｃ及び１８ｄを横切って均一に分布している。上述のように内部ノード８から発するサブツリーのリファレンス節点ノードに含まれるすべてのキーストリングが同じスタートｐｏｓキャラクタを有するので、これは、事例中２つのキャラクタ“ｃｄ”となる、それ等のｐｏｓストリングに対する後続のキャラクタ、これもまたキャラクタ比較位置キャラクタ、すなわち、それぞれ“ａ”及び“ｄ”はハッシュバケット内に置かれる。事例中キャラクタ“ａ”及び“ｅ”は、ハッシュバケット１８ａ割り当てられており、“ｂ”及び“ｆ”はハッシュバケット１８ｂに、そして、“ｃ”及び“ｇ”は、ハッシュバケット１８ｃに、そして、“ｄ”及び“ｈ２は、ハッシュバケット１８ｄに割り当てられている。こうしてハッシュバケット１８ａは、リーフ節点ノード５ｂへの参照リンクを有し、ハッシュバケット１８ｄは、リーフ節点ノード５ｃへの参照を有する。
【００５０】
ＨａｓｈＮｅｘｔフィールド１９は、ハッシュ衝突リストに対する参照リンクとして用いられる。事例中“ｃ”及び“ｇ”もまた、ルート根節点ノード４のハッシュ表アレイ中に同じハッシュバケットを有するので、そして１つの有利な実施例では各ハッシュバケットが唯一の他のノード節点にのみ参照を有し得るので、後継者ノード節点、ルート根節点ノード―それの比較キャラクタが“ｃ”であるーがそれの比較キャラクタが“ｇ”であるサイブリング節点ノードを参照することが必要である。こうして、内部ノード８のｈａｓｈＮｅｘｔフィールド１９は、リーフ節点ノード５ｄへの参照リンクを有する。
【００５１】
１つのリーフ節点ノードは、リーフ節点ノードであり得、（インデクスツリーが唯一のエントリからなる場合）、又は１つの内部ノードであり得る。事例中リーフ節点ノード４は、１つの内部節点ノードである。こうして、ルート根節点ノード４は、内部節点ノード８と同じフィールドを有しない（こうしてルート根節点ノード４の親フィールドは零ポイント（ＮＵＬＬ  ｐｏｉｎｔｅｒ）リーフ節点ノード５ａ，５ｂ，５ｃを有する）。及び５ｄもまた、いくつかのデータフィールドを含む。図１に関連して述べると、リーフ節点ノード５ｂは、典型的リーフ節点ノードの１例として挙げられている。リーフ節点ノード５ｂの親フィールド２０，ｃｈフィールド２４ｂ、ｓｂｌｐｒｅｖフィールド２５，及びｓｂｌＮｅｘｔフィールド２６は、内部ノード８の親フィールド１０，ｃｈフィールド１４，ｓｂｌｐｒｅｖフィールド１５，及びｓｂｌＮｅｘｔフィールド１６に類似する。Ｐｏｓフィールド２１は、それを１つのリーフ節点ノードとして識別するため“無限”“ｉｎｆｉｎｉｔｅ”、１つの特別な値にセットされる。ｓｕｃｃフィールドの内部は不確実である。リーフ節点ノードは後継者を有しないからである。キーフィールド２７は、キーストリングフィールド６ｂを参照し、一方ｉｎｆｏフィールド２８は、情報フィールド７ｂを参照する。
【００５２】
事例中明らかになることは、キーストリング“ａｂｃｄ”キャラクタ“ａ”でスタートする唯一のキーストリングは、リーフ節点ノード５ａに関連付けられ、ｃｈフィールド２４ａは、キャラクタ“ａ”を含む。同様７に、キーストリングキャラクタ“ｇ”でスタートする唯一のキーストリングは、リーフ節点ノード５６ｄに関連付けられ、該リーフ節点ノードのｃｈフィールド２４ｄはキャラクタ“ｇ”を含む。キャラクタ“ｃ”でスタートする複数のキーストリング、すなわち、“ｃｄａｆ”及び“ｃｄｄｈ”）、があるので、それ等のキーストリングに関連するリーフ節点ノードはルート根節点ノード４の後継者になり得る。むしろ、内部節点ノード８は、キャラクタ“ｃ”をもってスタートするキーストリング（これはフィールド１４内に記憶されているキャラクタである）が共有していない第１のキャラクタは、どのハッシュバケットが適用可能であるかを決めるために使用される。第３のキャラクタが“ａ”である場合、リーフ節点ノード５ｂに参照が成される。他方、第３のキャラクタが“ｄ”である場合、参照は、リーフ節点ノード５ｃになされる。
【００５３】
初期設定
ライブラリィは初期設定プロセスを介してユーザにより供給されるメモリエリア内に初期設定される。初期設定が完了完結すると、初期設定されたＦＩインデクスに対するハンドルがリターンされる。ユーザは、供給されたメモリバッファを参照すべくアイキャッチャ（ｅｙｅｃａｔｃｈｅｒ）として知られている識別子ストリングを規定し得る。このことにより、マルチプロセスアプリケーションにおける１度での初期設定が保証され、ここでバッファは、通常共通メモリ内に常駐する。次の入力及び出力パラメータは、クリエイト動作に置いて使用され、この動作は、初期設定の有利な実施例態様である。
【００５４】
入力パラメータは、＜ｂｕｆｆｅｒ＞、＜ｉｄｅｎｔ＞、＜ｍａｘＩｎｄｅｘ＞、＜ｍａｘＫｅｙｓ＞、＜ｍａｘＫｅｙＬｅｎ＞、及び＜ｗｉｌｄｃａｒｄＣｎ＞を含む。＜ｂｕｆｆｅｒ＞パラメータは、ＦＩ管理のためにユーザにより供給される順次メモリエリアである。＜ｂｕｆｆｅｒ＞はまた、マルチプロセスアプリケーションに対する共有のメモリアドレスであり得る。＜ｉｄｅｎｔ＞パラメータはＦＩインスタンスを特有―意的に識別するアイキャッチャ（ｅｙｅｃａｔｃｈｅｒ＞であり、マルチスレッドアプリケーションにおける多重初期設定を阻止するため使用される。＜ｍａｘＩｎｄｅｘ＞パラメータは、独立にハンドルし得る個別インデックスの最大数を与える。＜ｍａｘＫｅｙｓ＞パラメータは、インデックスにエントリ（キーストリング）の最大数を与え、すべての個別のインデックスの非繰り返し和である。＜ｍａｘＫｅｙＬｅｎ＞パラメータは、すべてのインデックスにおいて、キーストリングに対して、バイトで、最大キーストリング長さを与える。＜ｗｉｌｄｃａｒｄＣｈ＞パラメータは、パーシャルマッチング探索に対するワイルドカードとして使用されるキャラクタを含む。
【００５５】
出力パラメータ＜ｈａｎｄｌｌｅ＞は、新たにクリエイト（生成）されるＦＩインスタンスであり、後続のＦＩライブラリィコールに対するハンドル（参照）として使用される。
【００５６】
初期設定プロセスは、いくつかの目的を達成する。１つの目的は、メモリにおけるＦＩ管理構造を初期設定することである。もう１つの目的は任意の多重の初期設定を検出ためアイキャッチャを提供することである（マルチプロセス及び／又は、マルチスレッド環境における一度での初期設定を確保するため）。また、初期設定プロセスは、固定サイズの高速ＬＩＦＯ（ｌａｓｔｉｎ、  ｆｉｒｓｔ  ｏｕｔ）に基づくメモリマネージメントを初期化し、実質的に一定時間でインデクスツリーノード割当てをアロケートし、フリー解放するものである。更に、内部ノードスタックが初期設定され、その結果パーシャルマッチング問い合わせにてインデクスツリーを再帰的にサーチする際ハッシュフラグポイントを記憶し得る。
【００５７】
インデクスオブジェクトのオープニング
多重インデクスは同時にデータの同じセット上にオープンされ得、この同じセットにより、インデックスが同時に使用され得る。ＯＰＥＮ  Ｏｐｅｒａｔｉｏｎは、ＣＲＥＡＴＥ  Ｏｐｅｒａｔｉｏｎ  により先に初期設定されたグローバルなＦＩインスタンス内に１つの新たな空のインデクスオブジェクトをクリエイト生成する。次の入力及び出力パラメータは、ＯＰＥＮ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例において使用される。
【００５８】
入力パラメータは＜ｆｉＨｄ＞、＜ＩｄｘＩｄ＞、及び＜ｍａｘＫｅｙＬｅｎ＞を含む。＜ｆｉＨｄ＞  ｐａｒａｍｅｔｅｒは、グローバルｆｉインスタンス（ＣＲＥＡＴＥ  Ｏｐｅｒａｔｉｏｎによりターンされる）。＜ＩｄｘＩｄ＞は、オープンされつつあるインデクスを特有一義的に識別するアイキャッチャであり、メモリを共有するマルチプロセスアプリケーションにおける多重初期設定を阻止するために使用される。＜ｍａｘＫｅｙＬｅｎ＞パラメータは、インデクス中に置かれるべきキーストリングに対してバイトにて、最大のキーストリングを与えるものであり、ＣＲＥＡＴＥ  ｏｐｅｒａｔｉｏｎにおける＜ｍａｘＫｅｙＬｅｎ＞の値に等しいか、又はそれにより小である。
【００５９】
出力パラメータ＜ｈａｎｄｌｅ＞は、新たにクリエイト生成されるインデクスオブジェクトに対する参照であり、後続のインデクス動作に対するハンドル処理である。
【００６０】
ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ
ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎは、指定されたキーストリングを指定されたインデクスオブジェクト中に挿入する。前述のように、ユーザにより供給されるデータは、インデクスにおける各キーストリングに関連付けられる。
【００６１】
１つのキーストリングが１つのインデクス中に挿入される度ごとに、１つの新たなＦＩキーオブジェクト（すなわちインデクスツリーのリーフ）が内部的に生成され、そして、キーに対するハンドルがコールする者、コーラー（ｃａｌｌｅｒ）にリターンされる。該ハンドルは、インデクスツリー内でキーエントリを参照するため使用され得る（例えば  ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎのため）。キーストリング自体は、インデクスメモリ内に記憶されない。むしろ、ＦＩは、ユーザにより供給される参照を介してストリングを参照する。
【００６２】
有利な実施例では、挿入すべきストリングはＯＰＥＮ  Ｏｐｅｒａｔｉｏｎにより指定された少なくとも＜ｍａｘＫｅｙＬｅｎ＞の長さを有し、ストリング終端キャラクタを有しない。この実施例では、＜ｍａｘＫｅｙＬｅｎ＞より短いストリングは、右側が空白文字キャラクタでパディングされるべきである。
【００６３】
留意すべきことには、ストリング終端キャラクタ及び／又はワイルドカードを使用する本発明の実施例は、任意の２進データを含むキーストリングのインデクシングを複雑化し得る。現在公知の技術（代替選択的オルタナティブ、フォーマットにおける２進データのコーディング又はキーストリングの長さを指定する各キーストリングフィールドをもっての＜ＫｅｙＬｅｎ＞の蓄積）がそのような複雑性を克服するため使用され得る。
【００６４】
有利な実施例では、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  を、ワイルドカードキャラクタを含むストリング上に使用し得、その結果キーセット全体を単一の挿入オペレーション動作によりロジカルに記憶し得る。例えば“＊”がワイルドカードであり、動作オペレーション  ＩＮＳＥＲＴ（“ｂｃｄ＊＊”）にＦＩＮＤ（“ｂｃｄｅｆ”）及びＦＩＮＤ（“ｂｃｄｇｈ”）が続くものと仮定すると、（ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎは以下詳述する）、両問い合わせにより、“ｂｃｄ＊＊”が与えられる。こうして、ＦＩのワイルドカードを衝突検出目的のため（例えば、データベースのロジカルロックマネージメント）のため使用し得る。次の入力、出力パラメータは、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例にて使用される。
【００６５】
＜ｉｄｘＨｄ＞入力パラメータはアクセスされているインデクスオブジェクトのハンドルである。＜ＫｅｙＳｔｒ＞入力パラメータは、インデクス中に挿入されるべきキーストリングに対するポインタである。＜ｕｓｒＩｎｆｏ＞入力パラメータは、インデクス中に挿入されているキーストリングと関連付けたいとユーザが願うデータに対するポインタである。
【００６６】
出力パラメータ＜ＫｅｙＨａｎｄｌｅ＞は、新たに挿入されるキーオブジェクトに対する１つのハンドルである。
【００６７】
ＩＮＳＥＲＴ  ｏｐｅｒａｔｉｏｎの有利な実施例により実行されるステップは、フローチャート２００に概略が示されており、これは、図２及び図２ａに示されている。第１ステップは、メモリ内での１つの新たなリーフノードブロックのアロケーション２０２である。次に参照２０４は、＜ｔ＞を、入力パラメータ＜ｉｄｘＨｄ＞により参照されるインデクスツリーの根ルートにすることによりなされる。
【００６８】
判定２０６は、インデクスがルートにて空であるか否かを判定する。ＹＥＳの場合、＜ｎｅｗＫｅｙ＞のレジストレーション２０８がインデクスツリーの新たなルート根としてなされ、オペレーション動作は、出力パラメータ＜ＫｅｙＨａｎｄｌｅ＞として、アプリケーション２０２にてアロケート割り当てされた新たなリーフノードブロックに対する参照のリターン２８４へ進む。
【００６９】
他方では、デシジョン２０６にてインデクスが根にて空でないことが判明した場合、判定２１０は、１つのリーフノードに到達したか否かを判定する。ＹＥＳの場合には、判定２１８が実行される。他方ではＮＯの場合には、ルックアップ２１２過程が、第１のｐｏｓキャラクタ（上述のようにｐｏｓは現在ノード節点に対するキャラクタ比較位置を表す）の後直ちにキーストリング＜ＫｅｙＳｔｒ＞キャラクタに相応するエントリに対する現在ノード節点のローカル後継者ハッシュ表にて実行され、１つの相応のエントリがルックアップ２１２にて見出された場合、現在ノード節点としてそのエントリにて参照されたノード節点のアサインメント２１６過程が生起する（すなわち、参照されたノード節点が現在ノード節点となる）。他方では、ルックアップ２１２のプロセス中にて相応のエントリが見出されない場合、現在ノード節点として第１の後継者ノード節点（ｓｕｃｃＦｉｒｓｔ  フィールドから取られた）のアサインメント２１４過程が生起する。いずれのケースにおいても、次いで現在ノード節点が判定２１０へ与えられる。
【００７０】
判定２１８は、キーストリング＜Ｋｅｙ  Ｓｔｒ＞に一致する１つのキーストリングが既に現在ノード節点にて存在しているか否かを判定するため実行される。そのようなキーストリングに既に存在する場合、挿入過程が生起せず、そして、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  の終端ターミネーション２２０過程がエラー条件と共に生起する。同一のキーストリングが既に存在しない場合には、比較２２２は、現在ノードに関連するキーストリング及びキーストリング＜ＫｅｙＳｔｒ＞により共有されるサブストリングの長さ＜ｊ＞を決定するため実行される。次いで、現在ノード節点からスタートして、ツリーのトラバース走査２２４過程が、それぞれのノード節点の親ノード節点をポイントするリンクをたどることにより上方に向かって生起進行していって、ついには、ノード＜ｔ＞に到達するようになり、このノード節点＜ｔ＞のキャラクタ比較位置ｐｏｓは、サブストリング長さ＜ｊ＞に等しい、又は、それより小である。このノード節点に到達すると、外部又は内部ツリー挿入を実行すべきかの判定２３０が、図２ａに示すように実行される。
【００７１】
判定２３２及び２３４により、ノード＜ｔ＞が空であるか、又は＜ｔ＞の比較位置ｐｏｓが＜ｊ＞に等しいことが判定された場合、内部ツリー挿入２４０が実行される。これに反し＜ｔ＞が空でなく、そして、＜ｔ＞の比較位置が＜ｊ＞に等しくない場合、内部ツリー挿入インサート２６０が実行される。
【００７２】
外部ツリー挿入２４０は、次のステップを含む。新たなノード節点の親ノード節点＜ｔ＞のレジストレーション２４２過程ステップが実行される。新たなノード節点（これは、アロケーション２０２においてアロケートされた新たなリーフノード節点ブロックである）へのポインタの挿入２４４は、適当なキーストリングキャラクタのもとで＜ｔ＞のローカル後継者ハッシュ表にて実行され、そして、任意の悪影響を受けたフィールドが更新される（例えば、ｈａｓｈＮｅｘｔ  フィールド又は、実施例で使用される場合には、ｈａｓｈＰｒｅｖ  フィールド）。＜ｔ＞の後継者ノード節点の２重にリンクされたサイブリングリスト内への新たなノード節点の挿入２４６もまた、適当なｓｂｌＮｅｘｔ及びｓｂｌＰｒｅｖ  フィールドを更新することにより実行される。判定２４８は、ノード節点＜ｔ＞の比較位置がワイルドカードキャラクタであるか否かを判定するため実行される。ＹＥＳの場合＜ｔ＞のワイルドカードフラグ（実施例中に存在するならば）がセットされる。
【００７３】
内部ツリー挿入２６０は次のステップを含む。新たなノード節点ブロックのアロケーション２６２が実行される。次に、新たなリーフ節点ブロック（これはアロケーション２０２にてアロケートされたものである）へのポインタの挿入２６４が第２の新たなノード節点ブロックのローカルサクセッサ後継者ハッシュ表にて実行される。判定２６６は、ノード＜ｔ＞がＮＵＬＬ参照であるか否か判定するため実行される。ＹＥＳの場合は、インデクスツリーの新たな根としての第２の新たなノード節点ブロックのレジストレーションが実行される。判定２６６の結果如何に係わらず、第２の新たなノード節点ブロックの、それの親のローカル後継者ハッシュ表内への挿入２７０が実行される。内部ツリー挿入２６０は第２の新たなノード節点ブロックの、それの親の後継者ノード節点の２重にリンクされたサイブリングリスト内への挿入２７２をもって終了する。挿入２７２もまた、適当なｓｂｌＮｅｘｔ及びｓｂ１  Ｐｒｅｖフィールドを更新する。
【００７４】
出力ツリー挿入２４０又は、入力ツリー挿入２６０過程が実行されるかに係わりなく、次のステップは、親ノード節点の後継者カウンタのインクリメント２８０である。それに引き続いて、親ノードのワイルドカードフラグのセッティング２８２は、１つのワイルドカードがそれの後継者ノード節点間にある場合には実行される。アロケーション２０２にてアロケーション割当られた新たなリーフノード節点への参照のリターン２８４が出力パラメータ＜ＫｅｙＨａｎｄｌｅ＞  として実行される。
【００７５】
上述のようなフローチャート２００に対する上述のステップにより示されているように、高速ＬＩＦＯメモリマネージャの使用により、従来のメモリマネージメントに対する改良がクリエイト創出される。従来のメモリマネージメントの実行時間が、概して、少なくとも最悪のケースにおいて、アロケーション割当られたメモリブロックの総数に依存する。多数のエントリが存在する状況では、従来方法は禁止的に低速である。ＬＩＦＯメモリマネージャは、示されているように、ツリーノード節点の固定サイズを利用し、これによりツリーノード節点がフリー、自由なエントリのスタック上に置かれ得る。スタック上に自由なフリーノードを、プッシュすること、又はアロケートされたノードをスタックから除去することが単一のスタックオペレーション動作に含まれるので、ＬＩＦＯメモリマネージメントの実行時間がアロケーション割当られたノード節点の数に無関係である。
【００７６】
ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎの事例  
次いでＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  の１例の概略を説明する。図３及び図４に関連して述べると、そこに示されたＩＮＳＥＲＴ  （“ｃｅｄｇ”）Ｏｐｅｒａｔｉｏｎ  の１事例がインデクスツリー３０２上で実行され、このインデクスツリーは、インデクスツリー２と同じようにスタートする。ＦＩは、新たなキーストリングに対する挿入の場所を見出すためインデクスツリー３０２をトラバース走査する。ＦＩは、根ノード節点４でスタートし、この根ノード節点４のｐｏｓフィールド３３１は、最初の第１の零キャラクタが、根ノード節点４から発するサブツリー内に含まれているすべてのキーストリングに対して同一である（すなわち、第１のキャラクタのどれもが同一でない）ことを指示する。こうして、挿入すべきストリングの第１キャラクタが“ｃ”であるので、ＦＩハッシュ表配列３４０内でハッシュバケット３４１をルックアップする。ＦＩは内部ノード節点８への“ｃ”ブランチ参照３５０過程を引き続いて行う。更に留意すべきことには、挿入ストリングが第１のキャラクタとして“ｇ”を有するならば、ハッシュ衝突が生じることとなり（それというのは、“ｃ”と“ｇ”の双方がハッシュバケット３４１を占めることとなるからである）、そして、ｈａｓＮｅｘｔ  フィールド１９に含まれるリーフノード節点５ｄへの参照リンクをたどることとなるからである。
【００７７】
内部ノード節点８にて、ｐｏｓフィールド１１は、キャラクタ比較位置ｐｏｓが２であることを指示する。こうして、挿入すべきストリングの第３のキャラクタ、すなわち、“ｄ”が考慮され、ＦＩはハッシュ表配列１８にてハッシュバケット１８ｄをルックアップする、ＦＩはリーフノード節点５ｃへの“ｄ”ブランチ３６０過程を実行する。
【００７８】
次いで、ＦＩは、次のようなノードを見出すまでツリーインデックス３０２を再びバックアップ方向にトラバース走査する、すなわち、その比較位置ｐｏｓが、サブストリングの長さに等しいか、それより、小であるノードを見出すまでトラバース走査するものであり、当該のサブストリングは、“ｃｅｄｇ”がリーフノード５ｃに関連付けられたキーストリング（すなわち、“ｃｄｄｈ”）と共有するのである。結論付けられることは、ＦＩは、そこにてｐｏｓが１に等しいか、それより小であるｐｏｓフィールドを探す。ＦＩが親ノード節点リンク３７０及び３８０を通してそれの上向きのトラバース走査上にて見出す、当該の基準を充足する第１のｐｏｓフィールドは、ｐｏｓフィールド３３１であり、このｐｏｓフィールドは、根ノード節点４の１つのフィールドであり得る。ノード節点が空でなく（上記の判定２３２）そして、ｐｏｓフィールド３３１が１に等しくない（上記の判定２３４）ので、内部ツリー挿入２６０は、実行される必要がある。
【００７９】
図４は、内部ツリー挿入２６０の実行の際のインデクスツリー４０２へのインデクスツリー３０２の変換を示す。第１に２つの新たなノード節点である、新たな内部ノード節点４０８及び新たなリーフノード節点４０５がＦＩのＬＩＦＯメモリマネージャ（ＬＩＦＯ―ＭＭ）４４０からアロケーション割当られる。新たな内部ノード節点４０８がノード節点４の“ｃ”ブランチ参照３５０の後継者として挿入される。古い“ｃ”ブランチのサクセッサ継承者−これは内部ノード節点８であるーは今や新たな内部ノード節点４０８の“ｄ”ブランチ参照４５０のサクセッサ継承者になる。更に新たにリーフノード４０５は、新たな内部ノード節点４０８の“ｅ”ブランチとなる。
【００８０】
ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ
ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎは、関連付けられたノード節点をリムーブ除去することにより、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  により先に挿入された１つの所定のインデクスエントリをリムーブ除去するものである。リムーブ除去すべきインデクスエントリは、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ又はＦＩＮＤ  Ｏｐｅｒａｔｉｏｎによりリターンされるような、それの相応のキーハンドルにより指定される。
【００８１】
次の入力パラメータはＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ又はＦＩＮＤ  Ｏｐｅｒａｔｉｏｎの有利な実施例において使用される。＜ｉｄｘＨｄ＞入力パラメータは、そこからインデクスエントリを除去すべきインデクスオブジェクトのハンドル処理である。（ＫｅｙＨａｎｄｌｅ＞入力パラメータは、除去すべきインデクスエントリ（又はノード節点）に対するハンドルである。
【００８２】
図５に関連して述べると、ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例により実行されるステップは、フローチャート５００に概略が示されている。第１のステップは、除去すべきノード節点が、親ノード節点を有するか否かを判定することである。ＮＯの場合には、ＮＵＬＬ参照へのインデクスツリーの根のセッティング５０６過程が実行され、その後、除去されたツリーノード節点に属するメモリブロック８のフリー解放５５０が実行される。他方では、ノード節点が１つの親ノード節点が有する場合、親ノード節点に対する当該ノード節点への参照を除くステップ５０８（親ノード節点のｓｕｃｃＦｉｒｓｔ  フィールドもまたモデファイし得る）が実行される。更に、親ノード節点の後継者ノード節点の２重連結されたサイブリングリストからのノード節点の除去５１０が適当なｓｂｌＮｅｘｔ  ｓｂｌＰｒｅｖ  フィールドを更新することにより実行される。次に親ノード節点のサクセッサ後継者カウンタのデクリメント５１２が実行される。このポイントにて、インデクスツリー中には除去されたノード節点への参照がもはや無い。しかしながら、ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  は、インデクスツリーをモデファイする必要が起こり得る。
【００８３】
判定５２０は、親ノード節点が１つより多くの後継者ノード節点を左に有するかを判定する。ＹＥＳの場合には、除去されたノード節点の比較キャラクタがワイルドカードであったか否かを判定する。他方では親ノード節点が唯一の後継者ノード節点のみを左に有する場合には、親ノード節点は、ブランチングポイントとしてもはや使いものにならず、判定５２２は、グランドペアレント（すなわち、除去されたノード節点のグランドペアレント、また、親ノード節点の親）が存在するか否かを判定する。グランドペアレントノード節点が存在しない場合、インデクスツリーの新しい根のアサインメント割当５２４が除去されたノード節点の唯一のサイブリングに与えられ、その後、除去されたノード節点の唯一のサイブリングの比較キャラクタがワイルドカードであったか否かの判定５４０が実行される。他方では、グランドペアレントが存在する場合には、グランドペアレントノードハッシュ表からの親ノードの連結分離５２１が実行される。次に除去されたノード節点の唯一のサイブリングへの参照の挿入５２８がグランドペアレントにて実行される。親ノード節点の除去５３０が実行される。グランドペアレントは今や新たな親ノードとなる。
【００８４】
判定５４０は、除去されたノード節点の比較キャラクタがワイルドカードであったか否かを判定する。ＹＥＳの場合、ワイルドカードフラグの削除５４２が親ノード節点にて実行される。除去されたノード節点の比較ｖｒｋがワイルドカードであったか否かに拘わらず、ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  は、除去されたツリーノード節点に属するメモリブロックのフリー解放５５０で終了する。
【００８５】
フローチャート５００で上述のステップで示されているように、ノード節点へのリンクの除去（２重リンクされたサイブリングリストからのノード節点の除去５１０のような）によりメモリブロックのフリー解放５５２が生ぜしめられる。従来のシングルリンク、単一連結されたリストが使用された場合には１つのノード節点を除くには、除去すべきノード節点が見出されるまでにサイブリングリストを直線的にサーチすることが必要となる。このことにより、ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎの実行時間に対して直線的成分が生成されることとなる。最悪の場合には、サイブリングリスト全体をサーチしなければならなくなる。しかしながら、２重に連結されたサイブリングリストは、ＬＩＦＯメモリと相俟って、いずれの直線的リストスキャニングなしでもノードの削除をサポートし、それにより全体的性能を改善する。
【００８６】
ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  の事例
次にＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎの１事例の概略を説明する。図６及び図７について説明すると、ＲＥＭＯＶＥ（“ｃｄａｆ”）  Ｏｐｅｒａｔｉｏｎの１事例がインデクスツリー６０２上へ実行され、これはインデクスツリー２と同じようにスタートする。先ず、仮定されていることによれば、ユーザは、除去すべきリーフノード節点（事例中のリーフノード節点５ｂ）を識別する必要なキーハンドル＜ＫｅｙＨａｎｄｌｅ＞を供給する。リーフノード５ｂは、先ず、内部ノード節点８から除去される。内部ノード節点は、今や唯一の後継者ノード節点（すなわち、リーフノード節点５ｃ）を有するので、内部ノード節点は、ブランチングポイントとしてもはや使用されなくなり、除去する必要がある。従って、内部ノード節点８及び根ノード節点４の“ｃ”のブランチ参照３５０が除去される。フリー解放ノード、リーフノード節点５ｂ及び内部ノード節点８は、ＬＩＦＯ―ＭＭ４４０にリターンされる。
【００８７】
図７に関連して述べると、インデクスツリー７０２は、古いリーフノード節点５ｃから変換された、新たなリーフノード節点７１０を有する。根ノード節点４の“ｃ”ブランチ参照３５０は、リーフノード７１０への“ｃ”ブランチ参照７５０により置換される。リーフノード７１０は、リーフノード５ａ及び５ｄを有する２重リンクされたサイブリングリスト７６０を継承インヘリタンスする。リーフノード７１０の  ＨａｓｈＮｅｘｔ  フィールド７２０は、ｈａｓｈＮｅｘｔ  フィールド１９のコンテンツを継承インヘリタンスする。
【００８８】
ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ（Ｅｘａｃｔ  Ｍａｔｃｈ）（精確なマッチング）
ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ（Ｅｘａｃｔ  Ｍａｔｃｈ）の精確なマッチングーバージョンは、サーチキーストリングを精確にマッチングするエントリに対する指定されたインデクスをサーチする。パーシャルマッチング問い合わせと異なって、ワイルドカードキャラクタは、精確なサーチにおいて特別な意味を有しない。せいぜい、１つのインデクスエントリは、サーチストリングをマッチングする。当該のオペレーション動作が成功を収めて完結すると、マッチングインデクスエントリのＫｅｙＨａｎｄｌｅがリターンされる。次の入力、出力パラメータは、ＦＩＮＤ  ＯｐｅｒａｔｉｏｎのＥｘａｃｔ  Ｍａｔｃｈ  ｖｅｒｓｉｏｎ  の精確なマッチングーバージョンの有利な実施例において使用される。
【００８９】
＜ｉｄｘＨｄ＞入力パラメータは、サーチすべきインデクスオブジェクトのハンドルである。＜ＫｅｙＳｔｒ＞入力パラメータは、インデクスに対してサーチされているキーストリングに対するポインタである。＜ＫｅｙＨａｎｄｌｅ＞出力パラメータは、マッチングインデクスエントリに対するハンドルである。
【００９０】
図８について述べれば、  ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ（Ｅｘａｃｔ  Ｍａｔｃｈ）の精確なマッチングーバージョンの有利な実施例により実行されるステップは、フローチャート８００に概略が示されている。第１のステップは、サーチされているインデクスツリーの根ノード節点への参照８０２である。
【００９１】
次に、判定８０４は、現在ノードが内部ノードであるか否かを判定する。ＮＯの場合には、完結したストリング比較８２０が、サーチキーストリングと、現在ノードに関連したキーストリングとの間で実行される。現在ノードが内部ノードである場合には、ノードのキャラクタ比較位置にてサーチキーストリングキャラクタの考慮検討８０６がなされる。次のノードへのポインタの検索８０８が、現在ノードの後継者ハッシュ表を使用することにより実施される。次に新たな現在ノードとなるべき次のノードのアサインメント割当８１０が実行される。判定８０４は、新たな現在ノードに対して実行される。
【００９２】
サーチキーストリングと、現在ノードに関連したキーストリングとの間で完結したストリング比較８２０が実行される。  ストリングが同一でない場合、サーチの終端ターミネーション８２２が実行され、エラーコンディションが立てられる。他方では、ストリングが同一である場合、インデクスエントリに対するハンドルとして現在リーフノードへの参照のリターン８２４が実行される。
【００９３】
ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ（Ｐａｒｔｉａｌ  Ｍａｔｃｈ）
ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ（Ｐａｒｔｉａｌ  Ｍａｔｃｈ）を、すべてのインデクスエントリのセットに対して反復的に、ワイルドカードキャラクタを有する１つの指定されたサーチストリングマッチングをスキャンするため使用し得る（本発明の有利な実施例ではワイルドカードキャラクタは略称では“＊”である。例えば、オペレーション動作Ｏｐｅｒａｔｉｏｎ  ＩＮＳＥＲＴ（“ａｂａｄｃ”）、ＩＮＳＥＲＴ（ａｂｂｃｄ“）、ＩＮＳＥＲＴ（”ｂａ＊ｄｃ）、ＩＮＳＥＲＴ（“ｂａ＊ｄｄ）、ＩＮＳＥＲＴ（“ｂａｄａｃ”）、ＩＮＳＥＲＴ（“ｂａｄｂｃ”）、及びＩＮＳＥＲＴ（“ｄ＊ａ＊＊”）の条件下で、パーシャルマッチング問い合わせ検出ｐａｒｔｉａｌ  ｍａｔｃｈ  ｑｕｅｒｙ  ＦＩＮＤ（“＊ｂ＊ｃｄ”）により“ａｂｂｃｄ”及び“ｄ＊ａ＊＊”が与えられる。それというのは、ストリングエントリの第１，第２キャラクタは、当該の特定の目的に重要でないからである。次の入力、出力パラメータがＦＩＮＤＯｐｅｒａｔｉｏｎのパーシャルマッチングバージョン  ｐａｒｔｉａｌ  ｍａｔｃｈ  ｖｅｒｓｉｏｎ  の有利な実施例において使用される。
【００９４】
入力パラメータは＜ｉｄｘＨｄ＞、＜ＫｅｙＳｔｒ＞、＜ｍａｘＲｅｓｕｌｔｓ＞及び＜ｒｅｓｕｌｔｓＢｕｆｆｅｒ＞を含む。＜ｉｄｘＨｄ＞パラメータは、サーチすべきインデクシングオブジェクトのハンドルである。＜ＫｅｙＳｔｒ＞パラメータは、インデクスにてサーチされているキーストリングに対するポインタである。＜ｍａｘＲｅｓｕｌｔｓ＞パラメータはＦＩＮＤ  Ｏｐｅｒａｔｉｏｎの繰り返しごとにリターンされるべきキーハンドルの最大数である。＜ｒｅｓｕｌｔＢｕｆｆｅｒ＞は結果バッファに対するポインタであり、これは、＜ｍａｘＲｅｓｕｌｔｅ＞エントリまでホールドするのに十分な大きさのキーハンドルの配列である。
【００９５】
出力パラメータは＜ａｃｔＲｅｓｕｌｔｓ＞及び＜ｍｏｒｅＲｅｓｕｌｔｓ＞を含む＜ａｃｔＲｅｓｕｌｔｓ＞パラメータは、結果バッファにおいてリターンされるキーの実際の数をリターンする。＜ｍｏｒｅＲｅｓｕｌｔｓ＞パラメータ、また、サーチコントロールパラメータとも称され、＜ｍａｘＮｕｍｂｅｒ＞結果より多くのものがあったか否かを指示するためのフラグとして用いられる。
【００９６】
ｐａｒｔｉａｌ  Ｍａｔｃｈ  ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎの有利な実施例により実行されるステップがフローチャート９００にて概略が示されており、これは図９及び図９ａに示されている。第１のステップは、これがＦＩＮＤ  Ｏｐｅｒａｔｉｏｎのコール（ｃａｌｌ）であるか否かを判定するための判定９０４である。ＹＥＳの場合、インデクスツリーの根節点ノードへのローカルバックトラッキングスタックポインタ＜ｓｐ＞のリセット９０６が実行される。他方、ＮＯの場合、ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ  の先行コール呼出から先にセーブされたスタックポインタのリロード９０８が実行される。ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ  の最初のコールであっても、なくても、次のステップは、バックトラッキングスタックが空であるか否かを判定すること９１０である。ＹＥＳの場合、ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ  は、結果バッファのリターン９９４で終わる。他方では、否定の場合は、現在スタックトップからのツリーノード＜ｔ＞の検索９１１が実行される。次いで＜ｔ＞がリーフノードであるか否かを判定する判定９１２が実行される。ＹＥＳである場合、リーフノード解析９２０が実行される。他方ＮＯの場合、内部ノード解析９５０が実行される。
【００９７】
リーフノード解析９２０は、サーチキーストリング及びリーフノードに関連するキーストリングが同じであるかを判定する比較９２２及びワイルドカードが考慮される際サーチキーストリング及びリーフノードに関連するキーストリングが同じであるか否かを判定する比較９２８からスタートする。２つのストリングが同じであるか、又はワイルドカードとマッチングする場合、リーフノードに関連するインデクスエントリの結果バッファへの加算９３０が、実行される（すなわち、インデクスエントリが結果バッファに加えられる）。ストリングが同じであるか、又はマッチングをしているかに拘わらず、サーチキーストリング及びリーフストリングに関連するキーストリングが相異なる場合にてワイルドカードでない第１キャラクタ位置であるべきとき現在キャラクタ位置のアサインメント９３１が実行される。リーフノード解析９２０は、バックトラックスタックの枝刈り９３２で終わる。バックトラックスタックの枝刈り９３２は反復的に次のことをチェック９３３すること及び除去９３４により実行され、すなわち、（ａ）スタックが空でないか否か、そして（ｂ）親ノードのキャラクタ比較位置＜ｐｏｓ＞がキャラクタ比較位置＜ｊ＞より大であるか否かのチェック９３３により実行され、そのことは、そして、それ等の２つの条件のうちの少なくとも１つがもはや充足されなくなるまでバックトラックスタックからのノードの除去９３４が実行されるのである。リーフノード解析９２０が終わった後、判定９１０が再び実行される。
【００９８】
内部ノード解析９５０は、現在ノードのキャラクタ比較位置にて＜ｃｈ＞をサーチキーストリングキャラクタであるとのアサインメント９５２をもってスタートする。ワイルドカード  チェック９５４は、＜ｃｈ＞がワイルドカードキャラクタであるか否かを判定する。ＹＥＳの場合、ワイルドカードは、バックトラックスタック上へのすべての後継者ノードのプッシュ９７０で終わる。プッシュ９７０は＜ｔ＞の後継者リスト内のサイブリングーリンク過程をたどることにより、当該タスクを成し遂げ、このことの意味することは、＜ｔ＞から下降するサブツリー全体が更なるサーチに対してマーキングされるということである。他方で、＜ｃｈ＞がワイルドカードキャラクタでない場合は、ハッシュ表のルックアップ９５５が実行される。ルックアップ９５５は、＜ｃｈ＞に関連する後継者ノード（又は、代替選択的に＜ｃｈ＞に関連する後継者ノードが存在しない場合は、第１の後継者ノード）を見出し、ノードをバックトラックスタック上にプッシュする。次に、判定９５６は、＜ｔ＞がそれの後継者ノード内にワイルドカードを有しているか否かを判定する。＜ｔ＞がワイルドカードを有していない場合には、内部ノード解析９５０は終了する。他方＜ｔ＞がワイルドカードを有している場合には内部ノード解析９５０はバックトラックスタック上へのワイルドカードノードのプッシュ９５８で終わる。内部ノード解析９５０が終わった後、判定９１０が再び実行される。
【００９９】
ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎ (ｐａｒｔｉａｌ  Ｍａｔｃｈ)の事例
次にＰａｒｔｉａｌ  Ｍａｔｃｈ  ＦＩＮＤ  Ｏｐｅｒａｔｉｏｎの１事例の概略を説明する。図１０に関して述べると、ＦＩＮＤ（“＊ｂ＊ｃｄ”）ｏｐｅｒａｔｉｏｎ  がインデクスツリー１００２上にて実行される様子が示されている。インデクスツリー１００２は、ノード１０１０，１０２０，１０３０，１０４０，１０５０，１０６０，１０７０，１０８０，１０９０，１１００，及び１１２０を比較する。ノード１０１０は、インデクスツリー１００２の根ノードである；従って、キャラクタ比較位置ｐｏｓ零を有する。内部ノード１０２０はｐｏｓ２及びキャラクタ“ａ”を有する；内部ノード１０３０はｐｏｓ２及びキャラクタ“ｂ”を有する；内部ノード１０７０はｐｏｓ４及び比較キャラクタ“＊”（ワイルドカードキャラクタ）を有する。内部ノード１０８０はｐｏｓ３及びキャラクタ“ｄ”を有する。リーフノード１０４０は、ノード１０１０の後継者ノードであり、キーストリング“ｄ＊ａ＊＊”に関連付けられている。リーフノード１０５０及び１０６０は、ノード１０２０の後継者ノードであり、それぞれキーストリング“ａｂａｄｃ”及び“ａｂｂｃｄ”に関連付けられている。リーフノード１０９０及び１１００はノード１０７０の後継者ノードであり、キーストリング“ｂａ＊ｄｃ”及び“ｂａ＊ｄｄ”に関連付けられている。リーフノード１１１０及び１１２０はノード１０８０の後継者ノードであり、それぞれキーストリング“ｂａｄａｃ”及び“ｂａｄｂｃ”に関連付けられている。
【０１００】
ＦＩは、インデクスツリー１００２の根ノード１０１０におけるサーチをスタートする。ｐｏｓは、ノード１０１０に対して零であるのでＦＩは、サーチキーストリング“＊ｂ＊ｃｄ”の第１のキャラクタに注目する。これはワイルドカードキャラクタであり、而して、ＦＩは、ノード１０１０の各々の後継者ノード（すなわちノード１０２０，１０３０，及び１０４０）をバックトラッキングスタック上へプッシュする。留意すべきことには、バックトラッキングスタックは、トップ（最初）からボトム（最後）へ向かって、ノード１０２０，１０３０，及び１０４０を有する。バックトラッキングスタックにおける第１のノード、ノード１０２０は、トップからポップされる。ノード１０２０はｐｏｓ２を有するので、サーチキーストリングの第３キャラクタが評価される。これは、再度ワイルドカードキャラクタであり、而して、ＦＩは、ノード１０２０の各後継者ノード（則ちノード１０５０，１０６０）をバックトラックスタック上へプッシュする。バックトラックスタックは今やトップからボトムへ向かってノード１０５０，１０６０，１０３０，及び１０４０を有する。
【０１０１】
次いでノード１０５０はバックトラックスタックのトップからポップされる。これはリーフノードであるので、ＦＩは、第１の非ワイルドカードキャラクタ位置＜ｊ＞を判定し、ここでは、サーチキーストリングはノード１０５０に関連付けられたキーストリングとは相異なる。キーストリング“＊ｂ＊ｃｄ”及び“ａｂａｄｃ”は、第４のキャラクタにて差異があり（それ等は最初の３つのキャラクタに対してマッチングし、＜ｊ＞は３であるから）、そしてノード１０５０は、ミスマッチとして破棄される。ノード１０６０は、バックトラックスタックのトップからポップされる。これもまた、リーフノードであり、ＦＩは第１の非ワイルドカードキャラクタ位置＜ｊ＞を求め、ここで、サーチキーは、ノード１０６０に関連付けられたキーストリングとは異なる。しかしながら、“＊ｂ＊ｃｄ”及び“ａｂｂｃｄ”はマッチングし、而して、ノード１０６０に関連するキーエントリが結果バッファへの第１の加算になる。
【０１０２】
ＦＩは、バックトラックスタックにおいてなおスタックがあることを判定し、しかして、次のノード、ノード１０３０はトップからポップされる。ノード１０３０は、ｐｏｓ２を有する内部ノードになり、而して、サーチキーストリングの第３キャラクタが評価される。これはまた、ワイルドカードであり、而して、ＦＩはノード１０３０の各後継者ノード（則ち、ノード１０７０及び１０８０）をバックトラックスタック上へプッシュする。バックトラックスタックは、今やトップからボトムへ向かってノード１０７０，１０８０，１０３０，及び１０４０を有する。
【０１０３】
バックトラッキングスタックにおいて、なおノードがあり、而して、ノード１０７０は、トップからポップされる。ノード１０７０はｐｏｓ４を有する内部ノードであり、而してサーチキーストリングの第５キャラクタが評価される。この位置におけるキャラクタは“ｄ”であり、而して、ノード１０７０の“ｄ”ブランチ１０７２は、ノード１１００へ向けられる（プロセスにおけるノード１０９０破棄）。
【０１０４】
ノード１１００はリーフノードであり、而して、ＦＩは、第１の非ワイルドカードキャラクタ位置＜ｊ＞を判定し、ここで、サーチキーストリングは、ノード１０５０に関連するキーストリングとは異なる。キーストリング“＊ｂ＊ｃｄ”及び“ｂａ＊ｄｄ”は、第２のキャラクタにて相違なり、（それというのは、それ等は第１のキャラクタに対してマッチングするから＜ｊ＞は１である）そしてノード１１００はミスマッチとして破棄される。このポイントにおいてこそ発見的ヒューリスティックな枝刈り（ｐｒｕｎｉｎｇ）が付加的なサブツリー全体を破棄するため使用される。キーストリングがリーフノード１１００とは異なるー＜ｊ＞が１に等しい時―場合には、それの親ノードのｐｏｓが１より大である他のいずれのノードとも異ならなければならないということは、ＦＩツリーの性質、特性である。この性質、特性は、次のことに由来、導出される、すなわち、サブツリーに関連するすべてのキーストリングが、サブツリーの根における内部ノードのｐｏｓに等しい長さを有するプレフィックスを共有することに由来、導出される。従って、ノード１０３０は、ｐｏｓ２を有するので、バックトラッキングスタック内になお存在するサブツリー中のすべてのノード（すなわちノード１０７０及び１０８０）が破棄され得、それによりインデクスツリーが枝刈り（ｐｒｕｎｉｎｇ）される。
【０１０５】
バックトラッキングスタックにおいてなお残っている唯一のノード、ノード１０４０が、ポップされる。これはリーフノードであり、ＦＩは、第１の非ワイルドカードキャラクタ位置＜ｊ＞を求め、ここで、サーチキーは、ノード１０４０に関連するキーストリングとは異なる。しかしながら、“＊ｂ＊ｃｄ”及び“ｄ＊ｃ＊＊”はマッチングし、而してノード１０４０に関連するキーエントリは、結果バッファに加算される。考慮すべきノードはもはやなく、そして、結果スタックがリターンされる。
【０１０６】
図１１にはロジカルロックマネージメントを実行するためのＦＩメソッドを有利に利用する事例が表されている。ＦＩメソッドを、ヒューマンリソースマネージメント、ファイナンシャルズ、ロジスティックス、ビジネスワークフロー、組織マネージメント、及び他のシステムにおけるようなデータベースアプリケーションにおいて、衝突検出又は衝突マネージメントのため使用し得る。そのようなアプリケーションにおいて、多数のユーザ、例えば図１１中ユーザ１〜６は、データベース１２００にて記憶されているデータをアクセスする。ロジカルロックマネージメントは、いくつかのユーザがそこにてデータセットが変更訂正されるリクエスト又はオペレーションをもってデータベース中の同じデータセットへのアクセスするのを阻止するために実行され、前記のリクエスト又はオペレーション操作では、データセットは、例えば、書込又は削除により変更される。保証されなければならないのは、相次いでのユーザにより当該のデータセットの変更が所定の順序で実行されることである。
【０１０７】
このことを保証するためデータベース１２００への複数ユーザのリクエスト間の衝突を検出するためロックマネージャ１２０１が確立される。図１１例中、例えばユーザ１と６との間に衝突が起こる。明らかに、１つのデータベースのマルチユーザ環境の性能が、ロックマネージャ１２０１の性能に関してクリティカルである、それというのは、データベースのアクセス前に各ユーザのリクエストがロック衝突テストに合格しなければならないことに鑑みて、ロックマネージャ１２０１がシステム全体のスループットのボトルネックになり得るからである。本発明によれば、複数のストリングエントリを含めて、データベース１２００をアクセスするいくつかのユーザの複数リクエストの衝突検出、又は衝突マネージメントの方法メソッド、例えば、ロックマネージメントを実行するための方法メソッドは、ユーザのリクエストを含めてダイナミックロックテーブル１２０１のメンテナンスを包含し、前記のダイナミックロックテーブル１２０１では、リクエストは、本発明により、例えばＦＩメソッドによりインデクシングされる。１つのユーザのリクエストに関連して、ロックテーブル１２０２への問い合わせが、ユーザのリクエストがデータベース１２００に伝達される前に、例えば、ＦＩにより、実行される。ロックマネージャ１２０１は、ＦＩインデクシングされるロックテーブル１２０２を維持し、ここにはユーザによりリクエストされるロックが常駐する。
【０１０８】
例えば、ユーザ６のリクエスト“＊＊５＊”は、同じデータセットをアクセスするユーザの５つのリクエスト“ＣＹ５”の故に拒絶される。
【０１０９】
例えば、インデクシング“ＤＸＯ”を有するデータセットへのユーザ１の書込リクエストがある場合、先ず、ＦＩインデクシングされるロックテーブルへの挿入インサートオペレーション動作が実行され、それにより、インデクス“ＤＸＯ”インサートが、ＦＩサーチツリー内に挿入される。インサート動作オペレーションが成功を収めて実行され、インデクス“ＤＸＯ”がサーチツリー中に挿入され得たならば、ユーザ１はデータベース１２００における相応のデータセットへの書込アクセスを実行し得る。ところが、インサートオペレーション動作が、成功しなかった場合、インデクスーストリング“ＤＫＯ”は既にＦＩサーチツリー内にリーフノードとして含まれ、このことはロックマネージャ１２０１により検出される。この場合において、衝突が指示され、データベース１２００における関連するデータセットへのユーザ１の書込アクセスが否認される
データベース１２００への成功を収めた書込アクセスが終了ｆｉｎｉｓｈｅｄされる場合、除去オペレーション動作は、ＦＩロックテーブル１２０２において実行され、これにより、インデクシングされたストリング“ＤＸＯ”を有するリーフツリーが削除される。その後、他のユーザは、データベース１２００における相応のデータセットをアクセスし得る。
【０１１０】
単一の（すなわち、フルに指定された）データベーステーブルエントリ（例えば“ＡＸ３”）に対してのみならず、セット全体である（すなわち部分的パーシャルに指定された）エントリ（例えば、“Ｂ＊＊”ここで“＊”は基礎となるアルファベットの任意の文字であるワイルドカードを表す）に対してもロックを付与し得る。
【０１１１】
データベース１２００へのすべてのリクエスト及びアクセスが単一のＦＩサーチツリー内にマッチングされることに鑑みて、ロックマネージャ１２０１のレスポンス及び性能がデータベース１２００へのアクセスの総合的性能にとって重要である。ロックマネージャ１２０１がインデクシングされたロックテーブル１２０２を維持する場合、短いレスポンスタイム、ひいてはロックマネージャ１２０１の良好な性能が結果的に生じる。この点に関し、例えば、次の特徴事項は有利であり得る；サーチツリーはプレフィックスツリーとして構成され、ローカルハッシュ表が使用され、パーシャルにマッチングされたリクエストが実行され得ること、ＬＩＦＯメモリマネージメントの性能、サーチ期間中の枝刈り（ｐｒｕｎｉｎｇ）及び／又はバックトラッキングの実行である。
【０１１２】
本発明の利点は、ロックテーブル１２０１においてまた、部分的に指定されたストリング（例えば“ａｂ＊ｃ”又は“＊ｂｃ＊”）をも記憶し得ることである。従って、ＦＩロックテーブル１２０２内へのシングルインデクスインサートによりアクセスされるデータセットの部分をマッチングすることが可能である。直線的サーチ及びハッシングのような公知のサーチアルゴリズムにおいて必要なように、当該部分内に含まれる個々のデータセットをマークする必要がない。パーシャルに指定されたインデクスリクエストを実行し得る可能性により、ＦＩサーチの上述の特徴及びそれに基づくサーチメソッドのほかにさらにＦＩロックテーブル１２０２における所要のサーチ時間が低減される。
【０１１３】
他のサーチメソッドとの比較
次に、どのように本発明のアクチュアルなインプリメンテーション、−“ＦＩ”と称されるーが上述の他のサーチメソッドに比較されるかを展望的に示す。表１は、Ｉｎｔｅｌ  Ｐｅｎｔｉｕｍ  Ｐ１８０  ｍａｃｈｉｎｅ  上にて１つの完全な  ＩＮＳＥＲＴ/ＦＩＮＤ/ＲＥＭＯＶＥ  ｃｙｃｌｅ  が実行される時間μｓ（マイクロ秒）を示す。この比較のためＦＩプログラム及び通常使用されるＵＮＩＸスタンダードストリングインデクシング及びサーチライブラリィは実世界データベース上でサイクルを実行した（ここで、エントリはサーチツリーでは均一に分布していない）。ＢＴＲＥＥ  サーチは、ＵＮＩＸ/ＸＰＧ４  ｔｓｅａｒｃｈ（３Ｃ）  Ｓｔａｎｄａｒｄ  ｈａｓｈ  ｌｉｂｒａｒｙを用いて実行された。一方  ＬＩＮＥＡＲ  ｓｅａｒｃｈ  は、直線的２重連結されたリストバスリニアサーチで実行された。
【０１１４】
留意すべきことには高速ストリングメソッドに対する実行時間が、数１０μｓの大きさに留まる。―１００万エントリにわたるサーチの場合でも―。
【０１１５】
また明らかになっていることは、高速ストリングメソッドはサーチすべきキーストリングの大きさに対する優れた性能及びロバストネスを提供する。表２は、種々の長さのキーストリングを含むデータベース上へのＦＩ及びＨＡＳＨがサーチを実行するため時間μｓを示す。高速ストリングメソッドに対する実行時間は、キーストリングが数オーダの大きさ分も一層より大である場合でさえも、たんにわずかしか変化しない。
【０１１６】
本発明及び他のメソッドの特徴の要約を表３に示す。１つのセルにおけるプラス“＋”は、サーチメソッドが指示された特徴に特に適する（又はロバストである）ことを指示する。
【０１１７】
本発明の実施例に適用された本発明の基本的な新規な特徴を示してあり、説明し、指摘してあるが、本発明の精神を逸脱することなく、ここに開示されたような、本発明の形態及び詳細上の種々の省略、過程及び変更がなされ得る。明示されているところによれば、同じ成果を達成するため、実質的に同じ手法で、同じ機能を実行する要素及び／又は方法ステップの一切の組合せは、本発明の範囲内に入る。従って、添付されたクレームの範囲により指示されているものは、そこに指示されたいくつかの限定的な態様に限って規定されているに過ぎない。
【０１１８】
【表１】
2006004439.tif 000003
【０１１９】
【表２】
2006004439.tif 000004
【０１２０】
【表３】
2006004439.tif 000005
【図面の簡単な説明】
【０１２１】
【図１】図１は高速ストリングインデクシングのアプリケーションを具現化するインデクスツリーの基本的データ構造の例を示す概念図である。
【図２】図２は、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例に対するフローチャートの図である。
【図２ａ】図２ａは、ＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例に対するフローチャートの図である。
【図３】図３は、実行されているＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎの１事例の第１半部の概念図である。
【図４】図４は、実行されているＩＮＳＥＲＴ  Ｏｐｅｒａｔｉｏｎの１事例の第２半部の概念図である。
【図５】図５は、ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例に対するフローチャートを表す図である。
【図６】図６は、ＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  の１事例の第１半部に対するフローチャートを表す図である。
【図７】図７は、実行されているＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  の１事例の第２半部に対するフローチャートを表す図である。
【図８】図８は、Ｅｘａｃｔ  Ｍａｔｃｈ  ＦＩＮＤ  ＯｐｅｒａｔｉｏｎのＲＥＭＯＶＥ  Ｏｐｅｒａｔｉｏｎ  の有利な実施例に対するフローチャートを表す図である。
【図９】図９は、  Ｐａｒｔｉａｌ  Ｍａｔｃｈ  Ｆｉｎｄ  Ｏｐｅｒａｔｉｏｎの有利な実施例に対するフローチャートを表わす図である。
【図９ａ】図９ａは、  Ｐａｒｔｉａｌ  Ｍａｔｃｈ  Ｆｉｎｄ  Ｏｐｅｒａｔｉｏｎの有利な実施例に対するフローチャートを表わす図である。
【図１０】図１０は、実行されているＰａｒｔｉａｌ  Ｍａｔｃｈ  Ｆｉｎｄ  Ｏｐｅｒａｔｉｏｎの事例を表す概略図である。
【図１１】図１１は、ＦＩ  ｉｎｄｅｘｅｄ  ｌｏｃｋ  ｔａｂｌｅ  を使用したロジカルロックマネージメントを表わす概念図である。
【符号の説明】
【０１２２】
２    インデクスツリー
４  根ノード
５ａ  リーフノード
５ｂ  リーフノード
６ａ  キーストリングフィールド
６ｂ  キーストリングフィールド
６ｃ  キーストリングフィールド
６ｄ  キーストリングフィールド
７ａ  情報フィールド
７ｂ  情報フィールド
７ｃ  情報フィールド
７ｄ  情報フィールド
８    内部ノード
１０  親ノード
１１  ｐｏｓ  フィールド
１２  ｓｕｃｃ  フィールド
１３  ｓｕｃｃＦｉｒｓｔ  フィールド
１４  ｃｈ  フィールド
１５  ｓｂｌＰｒｅｖ  フィールド
１６  ｓｂｌＮｅｘｔ  フィールド
１７  ローカルサクセッサハッシュ表
１８  ハッシュ表配列
１８ａ  ハッシュバケット  
１８ｂ  ハッシュバケット
１８ｃ  ハッシュバケット
１８ｄ  ハッシュバケット
１９  ｈａｓｈＮｅｘｔ  フィールド
２０  ｐａｒｅｎｔ  フィールド
２１  ｐｏｓ  フィールド  
２２  ｓｕｃｃ  フィールド
２４ａ  ｃｈ  フィールド
２４ｂ  ｃｈ  フィールド
２４ｃ  ｃｈ  フィールド
２４ｄ  ｃｈ  フィールド
２５  ｓｐｌＰｒｅｖ  フィールド
２６  ｓｂｌＮｅｘｔ  フィールド
２７  キーフィールド
２８  フィールド
２００  フローチャート
２０２  アロケーション
２０４  参照
２０６  判定
２０８  レジストレーション
２１０  レジストレーション
２１２  ルックアップ
２１４  アサインメント
２１６  アサインメント
２１８  アサインメント
２２０  終端
２２２  比較
２２４  トラバース横断
２３０  判定
２３２  判定
２３４  判定
２４０  外部ツリー構成
２４２  レジストレーション
２４４  挿入
２４６  挿入
２４８  判定
２６０  内部ツリー挿入
２６２  アロケーション
２６４  挿入
２６６  判定
２６８  レジストレーション
２７０  挿入
２７２  挿入
２８０  インクリメント
２８２  セッティング
２８４  リターン
３０２  インデクスツリー
３３１  ｐｏｓフィールド
３４０  ハッシュ表配列
３４１  ハッシュバケット
３５０  参照
３６０  ブランチ
３７０  リンク
３８０  リンク
４０２  インデクスツリー
４０５  リーフノード
４０８  内部ノード
４４０  メモリマネージャ
４６０  参照
５００  フローチャート
５０４  判定
５０６  セッティング
５０８  除去
５１０  除去
５１２  デクリメント
５２０  判定
５２２  判定
５２４  アサインメント割当
５２６  連結、解離
５２８  挿入
５３０  除去
５４０  判定
５４２  削除
５５０  フリー解放
６０２  インデクスツリー
７０２  インデクスツリー
７１０  リーフノード
７２０  ｈａｓｈＮｅｘｔ  フィールド
７５０  参照
７６０  リンク
８００  フローチャート
８０２  参照
８０４  割当
８０６  考慮
８０８  検索
８１０  アサインメント
８２０  比較
８２２  終端
８２４  リターン
９００  フローチャート
９０４  判定
９０６  リセット
９０８  リロード
９１０  判定
９１１  検索
９１２  検索
９２０  リーフノード解析
９２２  比較
９２８  比較
９３０  加算
９３１  アサインメント
９３２  枝刈り（ｐｒｕｎｉｎｇ）
９３３  チェッキング
９３４  除去
９５０  内部ノード解析
９５２  アサインメント
９５４  ワイルドカード  チェック
９５５  ルックアップ
９７０  プッシュ
１００２  インデクスツリー
１０１２  ノード
１０２０  ノード
１０３０  ノード
１０４０  ノード
１０５０  ノード
１０６０  ノード
１０７０  ノード
１０８０  ノード
１０９０  ノード
１１００  ノード
１１１０  ノード
１１２０  ノード
１２００  データベース
１２０１  ロックマネージャ
１２０２  ロックテーブル
【図１】
2006004439.tif 000006
【図２】
2006004439.tif 000007
【図２ａ】
2006004439.tif 000008
【図３】
2006004439.tif 000009
【図４】
2006004439.tif 000010
【図５】
2006004439.tif 000011
【図６】
2006004439.tif 000012
【図７】
2006004439.tif 000013
【図８】
2006004439.tif 000014
【図９】
2006004439.tif 000015
【図９ａ】
2006004439.tif 000016
【図１０】
2006004439.tif 000017
【図１１】
2006004439.tif 000018