(57)【要約】パトリシア・トライを効率的にバルク・ロードする装置及び方法が、開示される。トライは、インデックス・ブロックへの書き込みに先行して、永続的表現に変換される。この変換プロセスでは、4つのアレイが使用され、第1アレイは、値ノードに使用され、第2アレイは、相違ポイントを構成する内部ノードに使用され、第3アレイは、親ポインタの保存に使用され、また、第4アレイは、サブ・トライのランサイズの保存に使用される。インデックス・ノードを作成する一方、インデックス・システムは、完了サブ・トライの境界を継続的に判断しようとする。また、所定サイズのインデックス・ブロックに納まる完了サブ・トライで最大のものを見つけようとし、見つけた場合には、このサブ・トライの永続的表現を作成し、かつこのインデックス・ブロックに書き込む。【特許請求の範囲】
【請求項１】
複数の記憶メディア・ブロックにパトリシア・トライをバルク・ロードする装置であって、
アーキテクチャが、
パトリシア・トライからの値を取り扱うための第1アレイと、
当該パトリシア・トライの内部ノードに関する情報を取り扱うための第2アレイと、
インデックスされる一組のソース・キーからのデータを用いて当該第1アレイ及び当該第2アレイをロードするための手段と、
当該パトリシア・トライの利用可能な最大のサブ・トライを用いて各記憶メディア・ブロックをロードするための手段と、
を備える装置。
【請求項２】
ソース・キーの当該組が、昇順で保存される、請求項1に記載の装置。
【請求項３】
当該第1及び第2アレイをロードするための当該手段が、ソース・キーの当該組における前記キーのものと同じ順序で当該データをロードする、請求項1に記載の装置。
【請求項４】
当該パトリシア・トライのサブ・トライの親ノードへのポインタを取り扱うための第3アレイと、
当該サブ・トライのサイズであるデータを取り扱うための第4アレイと、
インデックスされるソース・キーの当該組からのデータを用いて当該第3アレイ及び当該第4アレイに保存される値を演算するための手段と、
をさらに備える、請求項1に記載の装置。
【請求項５】
演算するための当該手段が、パトリシア・トライのサブ・トライの親ノードへのポインタを演算し、かつ当該第3アレイに結果を保存するための手段、をさらに備える、請求項4に記載の装置。
【請求項６】
演算するための当該手段が、当該パトリシア・トライのサブ・トライのサイズを演算し、かつ当該第4アレイに結果を保存するための手段、をさらに備える、請求項4に記載の装置。
【請求項７】
当該第3アレイのデータを使用して当該パトリシア・トライにおける上方向のナビゲーションを加速するための手段、をさらに備える、請求項4に記載の装置。
【請求項８】
各当該記憶メディア・ブロックが、固定サイズ及び可変サイズのうちの1つである、請求項1に記載の装置。
【請求項９】
データベース・システム、をさらに備える、請求項8に記載の装置。
【請求項１０】
一組のソース・キーに対応する前記パトリシア・トライの複数のノード値により第1アレイを埋め込むステップと、
隣接するキー間の相違位置により第2アレイを埋め込むステップと、
前記アレイに表現された当該パトリシア・トライ・ノードの集合が、当該記憶メディアの単一ブロックに納まる当該パトリシア・トライの最大のサブ・トライを成すことを判断するステップと、
当該第1アレイ及び当該第2アレイの内容を、記憶メディアのインデックス・ブロックに書き込むステップと、
を備える、複数の記憶メディア・ブロックにパトリシア・トライをバルク・ロードする方法。
【請求項１１】
各当該記憶メディア・ブロックが、固定サイズ及び可変サイズのうちの1つである、請求項12に記載の方法。
【請求項１２】
親ポインタを計算するステップと、
第3アレイに当該親ポインタを埋め込むステップと、
をさらに備える、請求項16に記載の方法。
【請求項１３】
サブ・トライの前記サイズを計算するステップと、
第4アレイに当該サブ・トライの当該サイズを埋め込むステップと、
をさらに備える、請求項10に記載の方法。
【請求項１４】
ブロックに書き込まれた当該最大のサブ・トライに関する当該アレイのデータを除去するステップ、をさらに備える、請求項10に記載の方法。
【請求項１５】
さらに、当該パトリシア・トライのすべてのノード値が、当該記憶メディア・ブロックに書き込まれるまで、請求項1に記載のステップを繰り返す、請求項10に記載の方法。
【請求項１６】
ソース・キーの当該組の終わりに到達するまで、ソース・キーの当該組から順次キーを読み取るステップ、をさらに備える、請求項10に記載の方法。
【請求項１７】
当該ソース・キーに対応するデータ参照により順次に当該第1アレイを埋め込むステップ、をさらに備える、請求項16に記載の方法。
【請求項１８】
隣接するソース・キー間の相違位置により順次に当該第2アレイを埋め込むステップ、をさらに備える、請求項16に記載の方法。
【請求項１９】
当該判断ステップが、
当該第2アレイにおいて現在の相違位置と前回の相違位置との間の相違位置を比較するステップ、
をさらに備える、請求項18に記載の方法。
【請求項２０】
当該判断ステップが、
当該第2アレイにおいて現在の相違位置が前回の相違位置よりも大きい場合、ソース・キーを読み取り続けるステップ、
をさらに備える、請求項19に記載の方法。
【請求項２１】
当該判断ステップが、
当該第2アレイにおいて現在の相違位置が前回の相違位置よりも小さい場合、当該パトリシア・トライを上方にナビゲーションし始めるステップ、
をさらに備える、請求項19に記載の方法。
【請求項２２】
当該パトリシア・トライを上方にナビゲーションする当該ステップが、
当該第3アレイにおける親内部ノードへのポインタを使用するステップ、
をさらに備える、請求項21に記載の方法。
【請求項２３】
当該パトリシア・トライを上方にナビゲーションする当該ステップが、
現在の相違位置のものよりも小さい相違位置が見つかった場合、当該パトリシア・トライを上方にナビゲーションするのを止めるステップ、をさらに備える、請求項21に記載の方法。
【請求項２４】
当該判断ステップが、
当該第1アレイ、当該第2アレイ、当該第3アレイ及び当該第4アレイから、当該インデックス・ブロックに書き込まれたサブ・トライに対応するデータを除去するステップ、をさらに備える、請求項18に記載の方法。
【請求項２５】
当該判断ステップが、
当該第3アレイ及び当該第4アレイのデータを調節して、当該第1アレイ及び当該第2アレイでの変更を反映するステップ、をさらに備える、請求項24に記載の方法。
【請求項２６】
当該ソース・キー・データの終わりに到達した場合、当該第1アレイ及び当該第2アレイの残り内容を当該記憶メディアのインデックス・ブロックに書き込むステップ、をさらに備える、請求項10に記載の方法。
【請求項２７】
コンピュータシステム上で実行する複数の指示を収容するコンピュータ・ソフトウェア製品であって、
前記複数の指示は、記憶メディアの複数の固定サイズ・ブロックにパトリシア・トライをバルク・ロード可能にし、
当該指示が、
一組のソース・キーに対応するパトリシア・トライの複数のノード値により第1アレイを埋め込むステップと、
隣接するキー間の相違位置により第2アレイを埋め込むステップと、
当該第1及び第2アレイに表現された当該パトリシア・トライ・ノードのノード集合が、当該記憶メディアの単一ブロックに納まる当該パトリシア・トライの最大のサブ・トライを成すことを判断するステップと、
当該第1アレイ及び当該第2アレイの内容を、記憶メディアのインデックス・ブロックに書き込むステップと、
を実行するための方法を備える、コンピュータ・ソフトウェア製品。
【請求項２８】
当該方法が、
親ポインタを計算するステップと、
第3アレイに当該親ポインタを埋め込むステップと、
をさらに備える、請求項27に記載のコンピュータ・ソフトウェア製品。
【請求項２９】
当該方法が、
サブ・トライのサイズを計算するステップと、
第4アレイに当該サブ・トライの当該サイズを埋め込むステップと、をさらに備える、請求項27に記載のコンピュータ・ソフトウェア製品。
【請求項３０】
当該方法が、
ブロックに書き込まれた当該最大のサブ・トライに関する当該アレイのデータを除去するステップ、をさらに備える、請求項27に記載のコンピュータ・ソフトウェア製品。
【請求項３１】
当該方法が、
当該パトリシア・トライのすべてのノード値が、当該記憶メディアのブロックに書き込まれるまで、当該方法のステップを繰り返すステップ、をさらに備える、請求項27に記載のコンピュータ・ソフトウェア製品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、全般的にパトリシア・トライに関し、より詳細には、永久記憶メディアへのトライの効率的なロードに関する。
【背景技術】
【０００２】
パトリシア（PATRICIA: Practical Algorithm To Retrieve Information Coded In Alphanumeric）は、1968年にD. R. モリソンにより示されたトライである。パトリシアは、インデックスのコンパクトな方法としてこの業界では周知であり、かつデータベース並びにネットワークアプリケーションにおいて一般に使用されている。パトリシアの実施の場合、子を1つしか持たないトライ・ノードは排除される。残りのノードは、この非圧縮トライでのノードの深さを示す文字位置番号をラベルされる。
【０００３】
図1は、一組のアルファベットについて、このようなパトリシア・トライの実施の例を示す。保存される単語は、「greenbeans」、「greentea」、「grass」、「corn」及び「cow」である。最初の3つの単語は、後の2つの単語と第1文字目で異なり、すなわち、3つは、文字「g」で始まる一方、他の2つは、文字「c」で始まる。すなわち、第1位置での相違がある。したがって、深さ「0」において「g」の単語と「c」の単語を分けるノードが、存在する。
【０００４】
「g」の側を移動して、次に相違が見つかるのは第3位置であり、2つの単語は、「e」である一方、1つの単語は、「a」である。したがって、そのレベルでのノードは、深さレベル「2」を示す。
【０００５】
左のパスを下がり続けると、次には、第6位置で異なる文字が見つかることが判明し、1つの単語は、「b」である一方、他方の単語は、「t」である。したがって、深さ「5」にノードが、存在する。
【０００６】
この実施での1つの問題は、キーが検索パスにより一意に指定されなくなってしまうことである。したがって、キー自体は、適切なリーフに保存される必要がある。このパトリシア・トライの実施の利点は、s*nビットについてのみの記憶が要求されることであり、ここで「s」は、アルファベットのサイズであり、かつ「n」は、リーフ数である。
【０００７】
アルファベットは記号のグループであり、ここで、アルファベットのサイズは、このグループにおける記号の数により判断される。すなわち、s=2を有するアルファベットは、2つの記号（可能性としては「0」及び「1」）のみを有する2値のアルファベットである。図2は、このようなアルファベットに対する実施である。2値のアルファベットであれば、他のデータ・タイプもビット文字列として表現できるので、トライでの文字列値のみを保存する制約を克服可能にする。
【０００８】
パトリシア・トライは、キー
2009512950.tif 000002
を収容するリーフ
2009512950.tif 000003
、又はビットオフセット
2009512950.tif 000004
並びに左サブツリー
2009512950.tif 000005
及び右サブツリー
2009512950.tif 000006
を収容するノード
2009512950.tif 000007
の何れかである。これは、パトリシアツリーのノードの再帰的記述であり、ノード
2009512950.tif 000008
から辿り着くリーフは、最初の
2009512950.tif 000009
ビットでは必ず一致する。パトリシア・トライの説明は、コンパクトBツリー（Bumbulis及びBowman）（データ管理に関する2002年ACM SIGMOD国際会議報告、p.533〜541）に紹介されるもので、これを参照して、そのまま全体を本発明に利用している。
【０００９】
このパトリシア・トライのアーキテクチャを使用して、永久記憶、例えば、ディスク・ベースのデータテーブル、に保存されるデータをポイントする参照ブロックを準備してもよい。データベース・システムにおいて、大量のデータをいわゆるバルク・ロード・モードでインデックスすることは、一般的な作業である。バルク・ロードは、クエリを一切介在することなく、一組のデータ全体についてディスク・ベースのインデックスを構築するプロセスとして定義される。この構築プロセスは、原子的な挿入操作の組としてではなく、一組のデータ全体の単一のインデックス操作として扱われるので、バルク・ロードは、複数の繰り返し挿入とは異なる。
【００１０】
バルク・ロードは、いくつもの理由から複数の挿入よりも効率的に優れている。バルク・ロードは、インデックス・ノードをロックすることがないので、並行処理制御での利点がある。バルク・ロードは、インデックス構築中の入出力（I／O）操作が少ないことを特徴とし、インデックス作成を大幅に高速化する。加えて、フィル・ファクタ、すなわち、インデックス・ブロックの使用は、バルク・ロード・モードで作成されたインデックスの場合、非常に高い。バルク・ロードのさらにもう1つの利点は、結果的なインデックス・ブロックでのデータの順次記憶である。これらの利点により、インデックス構造としてBツリーを使用する現代のデータベースにおけるインデックスのバルク・ロードは、大量のソース・データに及ぶインデックスを効率的に作成するための普遍的に通用するアプローチとなる。
【００１１】
【非特許文献１】コンパクトBツリー（A Compact B-Tree）（Bumbulis及びBowman）（データ管理に関する2002年ACM SIGMOD国際会議報告、p.533〜541）
【発明の開示】
【発明が解決しようとする課題】
【００１２】
Bツリーにつての公知のバルク・ロード方法は、ツリー構造及び結果的なインデックス・ブロックの構造が異なるため、パトリシア・トライには適用できない。パトリシア・トライについてのバルク・ロード・インデックスの解決策は、パトリシアをインデックス構造として採用するシステムにおいて非常に望ましい。したがって、従来技術の解決策には限界がある理由から、パトリシア・トライをバルク・ロードする装置及び方法の提供は、有益であろう。
【課題を解決するための手段】
【００１３】
パトリシア・トライを効率的にバルク・ロードする装置及び方法が、開示される。トライは、インデックス・ブロックへの書き込みに先行して、永続的表現に変換される。この変換プロセスでは、4つのアレイが使用され、第1アレイは、値ノードに使用され、第2アレイは、相違ポイントを構成する内部ノードに使用され、第3アレイは、親ポインタの保存に使用され、また、第4アレイは、サブ・トライのランサイズの保存に使用される。インデックス・ノードを作成する一方、インデックス・システムは、完了サブ・トライの境界を継続的に判断しようとする。また、所定サイズのインデックス・ブロックに納まる完了サブ・トライで最大のものを見つけようとし、見つけた場合には、このサブ・トライの永続的表現を作成し、かつこのインデックス・ブロックに書き込む。
【００１４】
ファイルシステムのディスク上にファイルを保存するのと同様、インデックスをブロックで永久記憶メディアに保存する作業は、一般的である。永久記憶からのインデックス・ブロックの読み取りを最適化するため、このブロックのサイズは、記憶及びオペレーティング・システム機能のブロック・サイズと通常揃えられたサイズに固定される。インデックス・ブロックは、パトリシア・トライがツリー表現となる永続的表現を有するため、このトライの永続的表現を作成する装置及び方法を有する必要がある。そして、このトライは、インデックス・ブロックへの書き込みに先行して、永続的表現に変換されるべきである。
【００１５】
永続的表現への変換とは、本質的には、元のトライでのノード構造を保ちながらの、トライ・ノードの順次配列である。永続的トライ表現でのノード順序は、トライ横断アルゴリズムの結果である。パトリシアでのノードは、行きがけ順で横断される。2値ツリーでのこのような横断は、まずルートを訪ねて、次に左のサブツリーに横断し、そして次に右のサブツリーに横断するとして定義される。
【００１６】
図3は、パトリシア・トライの代表例である。パトリシア・トライは、それぞれに値V1〜V6を収容する6つのリーフ・ノード、及び5つの内部ノードI1〜I5を備え、これらの内部ノードは、インデックス値間の相違位置を収容する。パトリシア構造から線形表現への変換を実施する必要がある。この線形表現へのトライ変換の結果は、図4を参照して以下に詳しく説明される。横断は、値I1を収容するルート・ノードで始まり、次に左のノードを訪ねてI2を収容するノードとなり、そして次に値V1を収容するリーフ・ノードとなる。これは、リーフ・ノードであるため、これ以降の横断は必要ない。ここで、I2の右リーフを訪ねると、値I3を有し、値V2を収容する左リーフを最初に訪ねることになり、次にV3を収容する右リーフとなり、さらにパトリシア・トライ全体が横断されるまで続く。
【００１７】
インデックス・システムにおけるメモリー量に限りがあるといった実践的な理由から、完全なインデックス・トライをメモリーに構築し、それを横断し、複数のインデックス・ブロックに結果的な永続的表現を書き込むのは、一般的に実現可能でない。そのため、本発明は、インデックスを作成しながらも、完全なインデックス・トライの形成を回避し、かつ、インデックス・サブ・トライの有限かつ制御可能に割り当てられたメモリー・リソースでのプロセス実施に取り組む。サブ・トライは、1つのインデックス・ノード及びそのすべての子孫ノードから構成される一組のノードとして定義され、サブ・トライは、インデックス・トライ全体よりも小さくなる。
【発明を実施するための最良の形態】
【００１８】
本発明の好適な実施例の場合、インデックス・システムは、昇順の辞書編集順序にソートされたソース・インデックス・キー・データが供給され、かつこのシステムは、キーを継続的に読み取って、それらに対応するインデックス・ノードを、そのソース・キーが尽きるまで作成する。パトリシア・トライに内在するプレフィックス圧縮の理由から、昇順でのソート順序は、キーのシーケンスがトライの行きがけ順横断で揃えられることを保証し、かつトライへの新しいノードの追加は、現在のノードの上又は右の何れかでのみ生じ得ることは、当業者には、直ちに認識されるであろう。新しいノードの追加は、常に、最後に追加されたノードと同じサブ・トライで起きるが、キー・プレフィックスの第1位置の値が、最後にプロセスされたキーと比較して変化する場合は、この限りでない。最後のノードが追加されたサブ・トライは、次に挿入されるノードが、最後に挿入されたノードよりも小さな相違位置を有する場合に完了される。完了サブ・トライを備えるすべてのサブ・トライも、同様に完了される。
【００１９】
インデックス・システムは、インデックス・ノードを作成する一方、完了サブ・トライの境界を継続的に判断しようとする。また、所定サイズのインデックス・ブロックに納まる完了サブ・トライで最大のものを見つけようとし、見つけた場合には、このサブ・トライの永続的表現を作成し、かつこのインデックス・ブロックに書き込む。最大のサブ・トライを判断する1つの目的は、インデックス・ブロックを最大限に使用することである。説明したアルゴリズムの結果として、如何なる時点においても、システムに、インデックス・ブロック・サイズよりも大きい完了サブ・トライは、存在しない。これは、図6を参照して以下に詳細に説明される。
【実施例】
【００２０】
本発明の好適な実施例の場合、インデックス・システムは、少なくとも次の4つのデータ構造、すなわち、ソートされたソース・キーからの読み取り値を保存するためのアレイと、内部ノードを保存するためのアレイと、内部ノードの親ポインタを保存するためのアレイと、サブ・トライのランサイズを保存するためのアレイと、を備える装置、を備える。サブ・トライのサイズは、そのノードのサイズの和である。図4は、本発明により使用される4つアレイを示す線図的なダイアグラムである。より詳細には、これらアレイは、図3に示すパトリシア・トライの代表例の内容に関して示される。値アレイ410では、パトリシア領域のノード値が、横断順序に配置される。したがって、アレイ410に配置される第1値は、「V1」であり、次は「V2」、そして最後の値「V6」まで続く。内部ノード・アレイ420では、パトリシア・トライの内部ノードが、横断の順序に従って配置され、このため、ノードの順序は、「I2」、「I3」、「I1」、「I4」、と続く。とりわけ、ノード「I1」がこの位置に現れるのは、横断がまず、リーフ・ノードを有するノード「I2」に到達し、次に「I3」に行き、そして、リーフ・ノードのため、ここで止まる。このときのみ「I1」が配置されるは、このときにのみ、ノード「I2」及び「I3」が、そのノードのリーフとして考慮されるからである。
【００２１】
親ポインタ・ノード・アレイ430は、アレイにおけるノード間距離、すなわち、現在の内部ノードから親内部ノードまでの距離を収容する。詳細には、次の数式で表される。
2009512950.tif 000010
【００２２】
このため、インデックス＝0を有するノードV1、及びインデックス＝1を有する親ノードI2に対して、距離は、次となる。
2009512950.tif 000011
【００２３】
ノードI2に対しては、インデックス＝1を有し、かつインデックス＝3を有する親ノードI1を有するので、距離は、次となる。
2009512950.tif 000012
【００２４】
ノードI2に対しては、インデックス＝1を有し、かつインデックス＝3を有する親ノードI1を有するので、距離は、次となる。
2009512950.tif 000013
【００２５】
ここで、インデックスは、横断の順序により判断される。この第3アレイの値は、パトリシア・トライの上方向、すなわち、リーフからルートへの、高速なナビゲーションを促進するために使用される。
【００２６】
最後に、サブ・トライのサイズ・アレイ440は、識別される各サブ・トライのサイズを収容する。この情報は、バルク・ロードのため、アレイが、効率的にパトリシア・トライデータを取り扱えるようにするものであり、すなわち、一般的に可用性が乏しくかつ需要の大きいリソースである、システム・メモリーの大きな部分を使用する必要なく、パトリシア・トライのバルク・ロードを効率的に取り扱えるようにする。上に示されるように、追加ノードが1つサブ・トライに追加された場合、記憶メディアのブロックにそれ以上サブ・トライが納まらなくなるようなサブ・トライを識別しようとし続けるので、パトリシア・トライ全体と同じ大きさのアレイを有する必要がない。これにより、それぞれのブロックへのこのようなサブ・トライのロードが、アレイ・スペースを空けることになる。
【００２７】
パトリシア・トライのバルク・ロードを達成するには、いくつかのステップが、要求される。まず、全体的なアプローチを検討し、次に、図5を参照して、特定の実施を説明する。以上で検討されたアレイは、以下のステップで使用される。アレイ410〜420は、データのパトリシア・トライ表現からの入力として読み取ったキーに基づいて、それぞれのデータで充填される。アレイが充填される場合、サブ・トライのサイズは、そのサブ・トライが書き込みできるブロック・サイズに対して比較される。いったんブロック・サイズ閾値を超えると、直前のサブ・トライが、記憶メディアのブロックに書き込まれる。4つのアレイ、すなわち、アレイ410、420、430及び440、の値で、書き込まれるサブ・トライに属するものは、除去され、かつこれらのアレイは、適宜調節されるので、これらのアレイは、取り扱われるパトリシア・トライの全体的なサイズよりも大幅に小さくできる。その後、プロセスは、すべてのソース・キーがプロセスされるまで、始めから再開される。一組のソース・データが尽きた後、アレイに残っているデータは、上述のアルゴリズムにより順次にプロセスされ、かつインデックス・ブロックに書き込まれる。この方法によりルート・ノードに到着した際、アレイにまだあるノードはすべて、永続的なパトリシア・トライのルート・ブロックとして書き込まれる。固定サイズ及び可変サイズのブロックの両方が、開示される本発明とともに使用できることが、当業者には、認識されるであろう。
【００２８】
図5は、以上で検討されるパトリシア・トライをバルク・ロードするためのステップを示すフロー・チャートである。以下の説明は、上記の概要説明と合わせて、図3及び4を参照することで、一層明確となる。ステップS505では、ソース・キーが読み取られ、そして、ステップS510では、相違ポイント（POD）がこのキーについて計算される。ステップS515では、ステップS510で計算されたPODと直前に計算されたPODとの間の比較が、行われる。ステップS520では、前回のPODが現在のものよりも大きいかどうかをチェックし、もしそうであれば、ステップS555を続けて実行する。そうでない場合、ステップS525を続けて実行する。ステップS525では、このサブ・トライが記憶メディアのブロックに納まるかどうかをチェックし、もし収まれば、ステップS555を続けて実行する。そうでない場合、ステップS530を続けて実行する。ステップS530では、現在のサブ・トライの最大のサブ・トライが、ブロックに書き込まれる。次に、ステップS535では、ブロックへの参照が、第1アレイ410に挿入される。ステップS555では、アレイの調節、すなわち、アレイ410〜420の値が調節されて、パトリシア・トライのサブ・トライがブロックに書き込まれた事実を反映する。ステップS545では、上方のサブ・トライのPODが、現在のPODと比較され、そして、ステップS550では、次のPODが小さいと判断された場合、ステップS555を続けて実行する。そうでない場合、ステップS525を続けて実行する。
【００２９】
ここでステップS555に戻り、ソース・キーそれぞれの参照値は、第1アレイ、例えば、アレイ410に入力される。ステップS560では、PODが、第2アレイ、例えば、アレイ420に配置される。ステップS565では、親へのポインタが、上に詳述されるように、計算され、かつ第3アレイ、例えば、アレイ430に挿入される。ステップS570では、第4アレイ、例えば、アレイ440は、それぞれのサブ・トライのサイズで更新される。ステップS575では、ソース・キーがまだあるかどうかをチェックし、肯定する場合、ステップS505を続けて実行する。そうでない場合、ステップS580を続けて実行し、アレイでのデータ・プロセス、すなわち、上に詳述されるように、記憶メディアのブロックに残りノードを配置仕上げることで、タスクが完結する。
【００３０】
図6は、開示される本発明による、記憶メディア610のブロックにマップされたパトリシア・トライ300を示す。パトリシア・トライが、横断され、かつ以上に説明される方法によりチェックされる場合、ブロックに納まるサブ・トライ、例えば、記憶メディア610のブロック610-iが、見つかる。
【００３１】
ブロックに納まる最大のサブ・トライが見つかる場合、このサブ・トライは、このブロックにその永続的表現で書き込まれる。ここで、ノードV1、V2、V3、I2及びI3を収容するパトリシア・トライ300のサブ・トライ301が、記憶メディア610のブロックに納まる最大であると仮定すると、そのサブ・トライ310は、ブロック、例えば、ブロック610-iにマップされる。見つかった次に最大のサブ・トライが、サブ・トライ302であるとすると、例えば、連続するブロック610-jにマップされるであろうことになる、などと続き、これにより、本発明の目的、すなわち、記憶メディア610の固定サイズ・ブロックへのパトリシア・トライのバルク・ロードが、達成される。
【００３２】
図７は、パトリシア・トライをバルク・ロード可能なデータベース・システムへのアクセスを有するコンピュータネットワークを示す。このネットワークは、複数のアクセス・エンド・ポイント710を備え、これらのアクセス・エンド・ポイントには、データ・ベース・アクセスが可能であるか又はその必要がある、パーソナル・コンピュータ（PC）、ワーク・ステーション（WS）、パーソナル・デジタル・アシスタント（PDA）、及びその他のネットワーク・アクセス・デバイスの手段を含むが、これらに限定されない。
【００３３】
デバイスは、ネットワーク720に接続されるが、簡略化する目的のため、ここでは単純にネットワークとして示されている。しかしながら、ネットワーク720は、ローカル・エリア・ネットワーク（LAN）、ワイド・エリア・ネットワーク（WAN）、ワイヤレス・ネットワーク、及びその他のタイプのネットワークでもよく、さらには、これらのあらゆる組み合わせでもよい。サーバ730は、ネットワークに接続され、このサーバは、少なくとも、以上に非常に詳しく開示されたパトリシア・トライのバルク・ロードを実施可能なデータベース管理システム（DBMS）735を収容する。記憶メディア610は、このシステムに接続される。記憶メディア610は、サーバ730の一部に含まれるローカル記憶手段でもよく、地理的に分散された記憶システムでもよく、又はこれらの組み合わせでもよい。パトリシア・トライのバルク・ロード機能が設定されたデータベース・システムは、本発明で説明されるように、従来技術の解決策を超える大幅なパフォーマンス改善を含む、ここに開示される発明の利点を享受することになる。
【００３４】
本発明の開示は、さらには、コンピュータ・ソフトウェア製品での実施も可能であり、このコンピュータ・ソフトウェア製品には、複数の指示を収容し、実行される場合には、本発明の教示内容を実施する。
【００３５】
したがって、本発明は、特定の好適な実施例を参照して詳細が説明されているが、本発明に関してプロセスを行う通常の当業者には、以下の特許請求の精神及び範囲を逸脱することなく、さまざまな変更及び強化を施せることが、理解されるであろう。
【図面の簡単な説明】
【００３６】
【図１】アルファベットの場合についてのパトリシア・トライである（従来技術）。
【図２】数値の場合についてのパトリシア・トライである（従来技術）。
【図３】値及び内部ノードで構成されるパトリシア・トライ構造である。
【図４】本発明により使用されるアレイを示す線図的なダイアグラムである。
【図５】パトリシア・トライのバルク・ロードを示すフロー・チャートである。
【図６】記憶メディアのブロックへの、パトリシア・トライのサブ・トライのロードを示す線図的なダイアグラムである。
【図７】パトリシア・トライをバルク・ロードできるように構成されたシステムを示す線図的なブロック・ダイアグラムである。
【符号の説明】
【００３７】
300  パトリシア・トライ
301、302、303  サブ・トライ
410、420、430、440  アレイ
S505、S510、S515、S520、S525、S530、S535、S540、S550、S555、S560、S565、S570、S575、S580  ステップ
610  記憶メディア
610-i、610-j、610-k  ブロック
710  アクセス・エンド・ポイント
720  ネットワーク
730  サーバ
735  データベース管理システム
【図１】
2009512950.tif 000014
【図２】
2009512950.tif 000015
【図３】
2009512950.tif 000016
【図４】
2009512950.tif 000017
【図５】
2009512950.tif 000018
【図６】
2009512950.tif 000019
【図７】
2009512950.tif 000020