(57)【要約】ＣＲ‐ツリーと呼ばれるＲ‐ツリーのキャッシュ‐コンシャス版が開示される。一つのノードにより多数のエントリを入れるために、前記ＣＲ‐ツリーはインデックスデータの相当部分を占めるＭＢＲキーを圧縮する。まず、前記ＣＲ‐ツリーは、相対座標の表現から先行０を除去するために、親ＭＢＲの左下コーナーに対するＭＢＲキーの座標を表現する。その後、前記ＣＲ‐ツリーは後位の無効ビットを更に除去することで、一定の数のビットで相対座標を量子化する。その結果、前記ＣＲ‐ツリーは通常のＲ‐ツリーより非常に広くなり且つ小さくなる。実験的な結果及び分析的な結果を通じて、２次元ＣＲ‐ツリーは同様の更新性能を維持し、且つ更に少ないメモリー空間を消費しながら、通常のＲ‐ツリーより迅速に検索を行える。
2004519774.tif 000002
【特許請求の範囲】
【請求項１】
各ノードのＭＢＲ（Ｍｉｎｉｍｕｍ Ｂｏｕｎｄｉｎｇ Ｒｅｃｔａｎｇｌｅ）はリーフノードの場合、該当データのオブジェクトを囲み、内部ノードの場合、子ノードにある全てのハイパーレクタングル（Ｈｙｐｅｒ−Ｒｅｃｔａｎｇｌｅ）を囲む最小ハイパーレクタングルの各ノードに前記ＭＢＲを連関させる段階と、
一つ以上の前記ＭＢＲをそれぞれ参照ＭＢＲの座標に対して表現されるＭＢＲの相対座標（”ＲＭＢＲ”）で表現する段階と、
量子化の後、後位の無効ビットを切捨てることで、前記それぞれのＲＭＢＲを有限精密度で量子化し、前記それぞれのＲＭＢＲを量子化したＲＭＢＲで圧縮する段階とを含むことを特徴とする、データベースに貯蔵されたデータオブジェクトに対する参照を容易にするためにメインメモリーに常住する、子ノードに対するポインタを有する内部ノードと、データベースオジェジェクトに対するポインタを有するリーフノードとで構成された多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項２】
前記多次元インデックス構造はＲ‐ツリーであることを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項３】
前記多次元インデックス構造はＲ＊‐ツリーであることを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項４】
前記多次元インデックス構造はＲ＋‐ツリーであることを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項５】
前記多次元インデックス構造はヒルバート（Ｈｉｌｂｅｒｔ）Ｒ‐ツリーであることを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項６】
それぞれの内部ノードは一番目のエントリが一つのＱＲＭＢＲと一つのポインタを有する反面、残りエントリはＱＲＭＢＲのみを有する複数のエントリを含むことを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項７】
それぞれのノードは参照ＭＢＲを貯蔵することを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項８】
一つのノードの前記参照ＭＢＲは、前記ノードの親ノードに貯蔵された該当ＱＲＭＢＲから得られることを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項９】
前記リーフノードはＭＢＲを貯蔵する反面、前記内部ノードはＱＲＭＢＲを貯蔵することを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１０】
前記データベースはメインメモリーに常住することを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１１】
前記データベースはディスクに常住することを特徴とする請求項１記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１２】
リーフノードの場合、該当データオブジェクトを囲み、内部ノードの場合、子ノードにある全ての最小境界形態をそれぞれのノードと連関させる段階と、
一つ以上の前記最小境界形態をそれぞれ参照最小境界形態の座標に対して表現される相対座標で表現する段階と、
量子化の後、後位の無効ビットを切捨てることで、それぞれの相対座標を有限精密度で量子化し、それぞれの相対表現を量子化した表現で圧縮する段階とを含むことを特徴とする、データベースに貯蔵されたデータオブジェクトに対する参照を容易にするために、メインメモリーに常住する子ノードに対するポインタを有する内部ノードと、データベースオブジェクトに対するポインタを有するリーフノードとで構成された多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１３】
それぞれの内部ノードは一番目のエントリが量子化した表現とポインタを有する反面、残りのエントリは量子化した表現のみを有する複数のエントリを含むことを特徴とする請求項１２記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１４】
一つのノードの前記参照最小境界形態は、前記ノードの親ノードに貯蔵された該当量子化表現から得られることを特徴とする請求項１２記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１５】
前記データベースはメインメモリーに常住することを特徴とする請求項１２記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１６】
前記データベースはディスクに常住することを特徴とする請求項１２記載の多次元インデックス構造にアクセスするキャッシュ機能を向上させる方法。
【請求項１７】
親ノードに対するポインタを有する内部ノードと、データオブジェクトに対するポインタを有するリーフノードとを含むツリーを形成するための複数のノード、
それぞれのＭＢＲがリーフノードの場合に該当データオブジェクトを囲み、内部ノードの場合、子ノードにある全てのハイパーレクタングルを囲む最小ハイパーレクタングルであるＭＢＲ、
ＭＢＲの相対表現は参照ＭＢＲに対して計算され、有限精密度で量子化するＱＲＭＢＲ（ｑｕｎｔｉｚｅｄ， ｒｅｆｅｒｅｎｃｅ ＭＢＲ）を含むことを特徴とする、データベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項１８】
前記ツリーはＲ‐ツリーであることを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項１９】
前記ツリーはＲ＊‐ツリーであることを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２０】
前記ツリーはＲ＋‐ツリーであることを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２１】
前記ツリーはヒルバート（Ｈｉｌｂｅｒｔ）Ｒ‐ツリーであることを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２２】
それぞれの内部ノードは、一番目のエントリが一つのＱＲＭＢＲと一つのポインタを有する反面、残りのエントリはＱＲＭＢＲのみを有する複数のエントリを含むことを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２３】
それぞれのノードは参照ＭＢＲを貯蔵することを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２４】
一つのノードの前記参照ＭＢＲは前記ノードの親ノードに貯蔵された参照ＭＢＲから得られることを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２５】
前記参照ＭＢＲはルートノードにのみ貯蔵されることを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２６】
前記内部ノードはＱＲＭＢＲを貯蔵する反面、前記リーフノードはＭＢＲを貯蔵することを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２７】
前記データベースはメインメモリーに常住することを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２８】
前記データベースはディスクに常住することを特徴とする請求項１７記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックス構造。
【請求項２９】
子ノードに対するポインタを有する内部ノードと、データオブジェクトに対するポインタを有するリーフノードとを含む複数のノード、
リーフノードの場合、該当データオブジェクトを囲み、内部ノードの場合、子ノードにある全ての境界形態を囲む最小の多次元形態の最小境界形態、
参照境界形態に対して計算され、後位の無効ビットを切捨てることで、有限精密度で量子化された最小境界形態の相対表現を含むことを特徴とするデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックスツリー。
【請求項３０】
前記複数のノードはＲ‐ツリーを形成することを特徴とする請求項２９記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックスツリー。
【請求項３１】
前記データベースはメインメモリーに常住することを特徴とする請求項２９記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックスツリー。
【請求項３２】
前記データベースはディスクに常住することを特徴とする請求項２９記載のデータベースに貯蔵されたデータオブジェクトに対する参照を容易にするための多次元のインデックスツリー。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明はデータベースシステムに関し、特にメインメモリーデータベースシステムのインデックスキャッシュ機能を改善するための圧縮方法に関する。
【０００２】
【従来の技術】
サーバーのＤＲＡＭモジュールが小型化するに伴い、多数のデータベーステーブルとインデックスが昨今のコンピュータシステムのメインメモリーに貯蔵され得るようになった。また、今後１０年以内にデータベースシステムのメインメモリーはテラバイト程度になるものと予想されている。
【０００３】
このような大容量のメモリーにより、特に検索トランザクション時にディスクアクセスの伝統的なボトルネック現象が解消される代わりに、メモリーアクセスが新たなボトルネック現象となっている。常用のＤＢＭＳ（Ｄａｔａｂａｓｅ Ｍａｎａｇｅｍｅｎｔ Ｓｙｓｔｅｍ）に対する最近の研究によれば、全体のデータベースがメモリーに常住する時、実行時間の殆どがメモリーアクセスに費やされる。
【０００４】
ＤＲＡＭチップの速度は容量の増加により減少するので、ＣＰＵ速度とＤＲＡＭ速度との差異はこの十年の間で非常に大きくなった。今日のコンピュータシステムにおいてそれぞれのメモリーアクセス時間はプロセッサ動作周期の数十倍が費やされる。この様なギャップを克服するために、現行のプロセッサーはキャッシュとして１回又は２回のプロセッサー動作の周期にアクセスし得る数メガバイトのＳＲＡＭを実装している。
【０００５】
ＣＰＵ速度とＤＲＡＭ速度との差の拡大が認識されつつ、最近メインメモリーインデックスの設計においてキャッシュ機能の重要性が目立っている。
読み込み専用の環境でキャッシュコンシャス検索ツリー（Ｃａｃｈｅ−Ｃｏｎｓｃｉｏｕｓ Ｓｅａｒｃｈ ｔｒｅｅ、ＣＳＳ−ｔｒｅｅ）は二進検索ツリー及び、Ｔ‐ツリーより遙かに迅速な検索を行う。また、Ｂ＋‐ツリー、及びその変形は非常に優れたキャッシュ機能を現す。
【０００６】
例えば、キャッシュセンシティブＢ＋‐ツリー（ＣＳＢ＋‐ツリー）は、子ノードをメモリーに連続的に貯蔵して、最初の一つを除いては前記ノードの中の大部分の子ポインタを除去する。
ｉ番目の子ノードの位置は一番目の子ノードから計算する。ノード内にキーのための空間を更に提供すると、前記ポインタ除去方法はＢ＋‐ツリーの展開を効果的に倍加させる。キャッシュブロックのサイズ順にノードの大きさが与えられると、前記展開の倍加はＢ＋‐ツリーの高さを減少させるので、ツリー検索時にキャッシュ損失の数を減らすことができる。
【０００７】
このようなポインタ除去技術は、ファンアウト（展開）が通常数百程度あるので、その倍加がツリーの高さを即刻減少させることに繋がることはないディスクベースのインデックスにおいてはあまり効果がない。
【０００８】
【発明が解決しようとする課題】
しかしながら、上記ポインタ除去技術は、時空間データベース、データウェアハウス、及びディレクトリサーバーなどのような分野で多く使用されるＲ‐ツリーのような多次元インデックス構造には直接適用され難い。
【０００９】
Ｒ‐ツリーに貯蔵されるデータオブジェクトは、多次元インデックス空間で所謂ＭＢＲ（Ｍｉｎｉｕｍ Ｂｏｕｎｄｉｎｇ Ｒｅｃｔａｎｇｌｅ）により近似化され、この際、それぞれのＭＢＲは、該当データオブジェクトを含む最小ハイパーレクタングル、つまり、二次元或いは高次元レクタングル、又はボックスである。当業者は前記ＭＢＲが複数のボックスやピラミッドを含む多次元形態で拡張され得ることが分かるだろう。
【００１０】
一般に、ＭＢＲはポインタよりずいぶん大きい。従って、ポインタ除去だけではツリーの高さを大幅に減らすためにインデックスツリーを広げ難い。例えば、前記１６‐バイトのＭＢＲが２次元キーに対して使用される時、単純な４‐バイトポインタの除去では、前記キーのための空間として２５％しか増加させ得ない。そして、このような増加は向上したキャッシュ機能のためのツリーの高さの差異に多く影響しない。
従って、メインメモリーデータベースにアクセスするための多次元インデックスへのアクセスにおいてキャッシュの機能を向上させるための技術が要求される。
【００１１】
そこで、本発明の目的は、多次元インデックス、つまり、Ｒ‐ツリーにてインデックスデータの大部分を占めるものがＭＢＲキーであることを認識する時、インデックスキャッシュ機能を向上させるためのＭＢＲキーの簡便な圧縮方法を提供することにある。
【００１２】
【課題を解決するための手段】
上記目的を達成するために、本発明の好ましい実施形態の所謂キャッシュ‐コンシャスＲ‐ツリー（ＣＲ‐ツリー）では、子ノードが一つの親ノードにグループで所属するので、それぞれのノードはその親ノードのデータ空間のごく小さな一部のみを占有する。前記ＣＲ‐ツリーで、一つのＭＢＲはその親ＭＢＲに連関して表現されるので、その結果の相対ＭＢＲ座標は、前側に多数の０を有するより少ない数の有効ビット数を有する。ＭＢＲ当たりビットの数を更に減らすためには、前記ＣＲ‐ツリーは、さらに量子化によって後位の無意味なビットを切捨てる。
【００１３】
分析的及び実験的な結果を通じて、圧縮技術によれば圧縮前の４分の１以下にＭＢＲサイズを減らすことができ、その結果、展開を１５０％以上増加させられることが分かる。前記提案された技術の潜在的な問題として、量子化による情報損失がフォルスヒットを引き起こすことがある。前記フォルスヒットは、後続の精製段階を通じて排除されるべきであり、このような精製段階は大部分の多次元インデックスで必要なので、その精製段階の必要性自体が問題になるわけではない。そして、フォルスヒットの排除負担がキャッシュミスの著しい減少により補償され得るように量子化水準を適切に選択することで、フォルスヒットの回数を可及的に減らすことができる。
【００１４】
本発明はＣＲ‐ツリーのデザインにおいて、ＣＳＢ＋‐ツリーに導入されたポインタ除去技術の使用可否により、前記提案された圧縮技術をリーフノードに提供するか否かにより、量子化水準に従って、或いはノードの大きさによって多様な実施形態を含む。実験的な結果によれば全ての前記Ｒ‐ツリーの変形が検索性能や空間活用度の側面でＲ‐ツリーを凌いでいることが分かる。前記提案された技術のみを使用する基本ＣＲ‐ツリーは、前記Ｒ‐ツリーと同様に更新動作が行われ、より少ないメモリー空間を使用するが、前記Ｒ‐ツリーより迅速な検索動作が行える。前記基本ＣＲ‐ツリーと比較する時、大部分のＣＲ‐ツリーの変形は若干のアルゴリズム上の負担は存在するものの、メモリー空間の使用が少ないという長所がある。
【００１５】
【発明の実施の形態】
本発明はＭＢＲを圧縮することでＲ‐ツリーがキャッシュ‐コンシャスとなるようにする方法に基づくものである。Ｒ‐ツリーはデータベースで多次元のデータオブジェクトをインデックス付けするために特別に設計された高さの均一なツリー構造である。前記Ｒ‐ツリーはリーフページにおいてキーで２次元以上のデータオブジェクトを有するＭＢＲを貯蔵する。また、本発明は、挿入時にエントリを再分配し、ツリーを動的に再構成するためにより優れた経験的な方法を使用することで検索性能を向上させる、所謂Ｒ＊‐ツリーのＲ‐ツリーへの変形に適用され得る。当業者であれば本発明がＲ＋‐ツリー、ヒルバート（Ｈｉｌｂｅｒｔ）Ｒ‐ツリー、Ｘ‐ツリーのようなＲ‐ツリーの変形においても容易に適用され得ることが理解可能であろう。
【００１６】
図１は本発明に使用された圧縮技法を示す。図１ＡはＲ０〜Ｒ３の絶対座標を示す。図１ＢはＲ０の左下コーナーに対して相対的に示されるＲ１〜Ｒ３座標を示す。この相対座標は絶対座標より少数の有効ビットを有する。図１Ｃは下位有効ビットを切捨てることで１６レベル、又は４ビットに量子化されたＲ１〜Ｒ３の座標を示す。その結果のＭＢＲは量子化されたＭＢＲ（ＱＲＭＢＲ）と称する。ＱＲＭＢＲは本来のＭＢＲよりやや大きい。
【００１７】
本発明の好ましい実施形態は所謂ＣＲ‐ツリー（キャッシュ依存型Ｒ‐ツリー）と称するインデックスツリーであって、ＱＲＭＢＲをインデックスキーとして使用するＲ‐ツリーの変形である。量子化レベルの数は一つのＣＲ‐ツリーにおいて全てのノードに対して同一であるのが好ましい。
【００１８】
図２ＡはＣＲ‐ツリーノードのデータ構造を示す。それぞれのノードはＭ個のエントリまで含める。また、前記ノードは自分がリーフノードであるか否かを示すフラグ２０１、貯蔵されたエントリ２０２の数、全体の子ＭＢＲを含む参照ＭＢＲ２０３、そして、多数のエントリ２０４を有する。
前記参照ＭＢＲはノードに貯蔵されたＱＲＭＢＲを計算するために使用される。
【００１９】
図２Ｂは（ＱＲＭＢＲ２１１，ｐｔｒ２１２）の形態でエントリを貯蔵する、リーフでないノード、つまり、内部ノードを示す。この際、ＱＲＭＢＲ２１１は子ノードＭＢＲが量子化された相対的な表現であり、ｐｔｒ２１２は子ノードのアドレスである。
【００２０】
図２Ｃは（ＱＲＭＥＲ２２１，ｐｔｒ２２２）の形態でエントリを貯蔵するリフトノードを示す。この際、ＱＲＭＢＲ２２１はオブジェクトＭＢＲの量子化された相対的な表現であり、ｐｔｒ２２２はデータオブジェクトを意味する。一般的にｘ，ｙ座標はそれぞれ２５６レベル、つまり、１バイトに量子化する。
【００２１】
本発明の目的は、特に、多次元インデックスを用いて、メインメモリーデータベースでのインデックス検索時間を減らすことにある。ディスクベースのインデックスにおいて、ノードの大きさが適当である時、ディスクアクセス負担はノードの大きさとはほぼ無関係でないが、前記メモリーアクセス負担はノードの大きさにほぼ比例する。ディスクベースのインデックスがディスクアクセスの回数を最小化するように設計されているが、メインメモリーインデックスは、アクセスされたインデックスデータ量、つまり、ｃ．Ｎｎｏｄｅ ａｃｃｅｓｓが最小となるように設計する。
ここで、ｃはキャッシュブロック内のノードの大きさを示し、Ｎｎｏｄｅ ａｃｃｅｓｓはアクセスされたノードの個数を示す。
【００２２】
メインメモリーインデックスにおいて、検索時間は主にキー比較時間と、キャッシュミスによるメモリーアクセス時間とで構成される。キャッシュミスが発生すると、ＣＰＵはフォルスヒットしたデータがキャッシュされるまで待たなければならない。キャッシュミスは次の３つの理由、つまり、データフォルスヒット、命令語フォルスヒット、ＴＬＢ（Ｔａｂｌｅ Ｌｏｏｋ−ａｓｉｄｅ Ｂｕｆｆｅｒ）エントリフォルスヒットの理由から発生する。前記ＴＬＢは仮想メモリーアドレスを物理的なアドレスにマッピングするのに必要である。
従って、キャッシュするキーを比較するのにかかる時間をＴｋｅｙ ｃｏｍｐａｒｅ、データをキャッシュするのにかかる時間をＴｄａｔａ ｃａｃｈｅ、ＴＬＢエントリをキャッシュするのにかかる時間をＴＴＬＢ ｃａｃｈｅとする時、目標は
2004519774.tif 000003
を最小化することにある。
ここで、命令語フォルスヒットの回数は殆ど使用されるコンパイラに依存し、それによるキャッシュ時間の調節が難しいので、命令語フォルスヒットに対するキャッシュ時間は省略する。
【００２３】
ｃをキャッシュブロック内のノードの大きさ、Ｎｎｏｄｅ ａｃｃｅｓｓをクェリー（ｑｕｅｒｙ）を行う間にアクセスするノードの個数とする。Ｃｋｅｙ ｃｏｍｐａｒｅをキャッシュブロック当たりキー比較負担とし、Ｃｃａｃｈｅ ｍｉｓｓをキャッシュブロックの交替負担とする。そして、ＣＴＬＢ ｍｉｓｓを単一のＴＬＢフォルスヒットの処理負担とする。ノードの大きさがメモリーページの大きさより小さい時、一つのノードに対するそれぞれのアクセスはわずかに一回だけのＴＬＢフォルスヒットを引き起こす。説明の便宜上、ノードは任意に割り当てられていると仮定し、ノードとＴＬＢエントリ共に最初はキャッシュされていないものと仮定する。すると、
Ｔｉｎｄｅｘ ｓｅａｒｃｈ＝
ｃ×Ｃｋｅｙ ｃｏｍｐａｒｅ×Ｎｎｏｄｅ ａｃｃｅｓｓ＋ｃ×Ｃｃａｃｈｅ ｍｉｓｓ×Ｎｎｏｄｅ ａｃｃｅｓｓ＋ＣＴＬＢ ｍｉｓｓ×Ｎｎｏｄｅ ａｃｃｅｓｓ
＝ｃ×Ｎｎｏｄｅ ａｃｃｅｓｓ×（Ｃｋｅｙ ｃｏｍｐａｒｅ＋Ｃｃａｃｈｅ ｍｉｓｓ＋ＣＴＬＢ ｍｉｓｓ／ｃ）
ここで、Ｃｃａｃｈｅ ｍｉｓｓとＣＴＬＢ ｍｉｓｓは所定のプラットフォームに対して一定であるので、ｃ， Ｃｋｅｙ ｃｏｍｐａｒｅ，及びＮｎｏｄｅ ａｃｃｅｓｓの３つの媒介変数を調節可能である。これらのうち、キーの比較は一般的に非常に単純であるので、Ｃｋｅｙ ｃｏｍｐａｒｅを大きく減らすことは無理であり、またＣＴＬＢ ｍｉｓｓとＣｃａｃｈｅ ｍｉｓｓは典型的に類似値を有するので、インデックスの検索時間は大体ｃ ・ Ｎｎｏｄｅ ａｃｃｅｓｓにより決定される。
【００２４】
アクセスしたインデックスデータの量はインデックスエントリを圧縮することで最も多く減少する。ｃ ・ Ｎｎｏｄｅ ａｃｃｅｓｓは３つの方法により最小化され得る。ｃ ・ Ｎｎｏｄｅ ａｃｃｅｓｓが最小となるようにノードの大きさを変更すること、一定の大きさのノード内により多量のエントリを入れること（圧縮）、そして、インデックスエントリを効率的にノード内にクラスタすること（クラスタリング）がそれである。
【００２５】
最適なノードの大きさは１次元の場合にキャッシュブロックのそれと同一である。Ｂ＋‐ツリーのような１次元ツリーでは、正確に一つの内部のノードが同一範囲のクェリーでさえそれぞれの高さに対してアクセスするので、アクセスされた内部ノードの数はノードの大きさに対してログ関数的に減少する。これと異なり、アクセスされたリーフノードの数はノードの大きさに従って線形的に減少し、ｃはノードの大きさに従って線形的に増加する。従って、ｃ ・ Ｎｎｏｄｅ ａｃｃｅｓｓはノードの大きさと共に増加し、これにより、ｃが１である時に最小となる。
【００２６】
多次元インデックスの場合、同一の高さの１以上の内部ノードが正確に一致するクェリーに対してさえアクセス可能であり、ノードの大きさが増加するほど同一の高さのアクセスしたノードの数は減少する。このような減少はツリーの高さのログ関数的な減少と結合するので、ノードアクセスの前記結合された減少率はｃの線形的な増加率を超える可能性がある。分析を通じて、最適なノードの大きさはクェリーの選択性やカーディナリティ（インデックス構造でエントリの数）のような幾つかの要素により決定されることが分かる。
【００２７】
インデックスエントリの圧縮はｃを増加せずノードの大きさを増加させることと同様である。即ち、ｃを固定し、Ｎｎｏｄｅ ａｃｃｅｓｓを減らすもので、これは非常に好ましい方法である。圧縮はツリーの高さを減らせることからディスクベースのインデックスで良く行われてきたが、多次元インデックス分野では殆ど適用されない。
次の簡単な分析は、圧縮がディスクベースのインデックスではあまり重要ではないが、メインメモリーインデックスでは重要なものであることを示す。
【００２８】
ツリーＡは一つのノード内で平均ｆ個のエントリをパッキングすることができ、ツリーＢは優れた圧縮技法を用いて一つのノード内で平均２ｆ個のエントリをパッキング可能であると仮定しよう。すると、これらの予想される高さはそれぞれｌｏｇｆＮとｌｏｇ２ｆＮである。
従って、Ｂの高さはＡのそれより１／ｌｏｇ２ｆ＋１（＝ｌｏｇｆＮ／ｌｏｇ２ｆＮ）倍だけ低い。
【００２９】
2004519774.tif 000004
要約すると、ノードの大きさが小さいため、ノードの圧縮によってメインメモリーインデックスの高さを大きく減らすことができる。
【００３０】
クラスタリングはディスクベースの構造で光範囲に研究されてきた。クラスタリングにおいて、Ｂ＋‐ツリーは１次元空間では最適であるが、多次元の場合は最適のクラスタリング技法が知られていない。その代わりに、多様な多次元のインデックス構造で様々な経験的な技法が研究されてきた。本発明はそのようなクラスタリング技法と共に使用され得る。
【００３１】
ＭＢＲ圧縮
ＭＢＲ圧縮技法に対しては２つの好ましい特性がある。第一は、圧縮を解かずに可能なオーバーラップ確認特性である。２つのＭＢＲがオーバーラップされたか否かは、これらの圧縮を解かずとも該当した圧縮ＭＢＲから直接に決定され得る。基本的なＲ‐ツリー動作は、一つのノード内でそれぞれのＭＢＲが所定のクェリーレクタングルとオーバーラップするかどうかを確認することである。従って、ノード内に圧縮ＭＢＲを貯蔵する時、前記特性はノード内にある全ての圧縮ＭＢＲの圧縮を解かずともクェリーレクタングルを一度に圧縮させることでＲ‐ツリー動作が行われ得るようにする。
【００３２】
第二の特性は単純性である。圧縮や圧縮解凍は計算が簡単であるべきで、既キャッシュされたデータのみで行われ得るべきである。
ＧＮＵ ｇｚｉｐプログラムで使用されたもののような従来の無損失圧縮アルゴリズムは、これらの殆どが圧縮や圧縮解凍のためにエントロピーベースのマッピングテーブルを保有するか、前記テーブルを検索するため、計算及びメモリーアクセスの側面で相当な負担がかかる。
従って、これらはディスクベースのインデックスでは有用であるが、メインメモリーインデックスには適合ではない。
【００３３】
ＲＭＢＲ技術
単一のノード内で参照ＭＢＲに対して相対的にキーを表現する圧縮方法である。ＭＢＲの座標がその親ＭＢＲの左下コーナーに対して表現されると、その結果的な相対座標は前部に多数の０を有する。ＭＢＲの相対的な表現で（”ＲＭＢＲ”）、このような０を除去すると、ＭＢＲの大きさを効果的に減らすことができる。
【００３４】
ＰとＣを左下と右上の座標（ｘｌ， ｙｌ， ｘｈ， ｙｈ）で表現されるＭＢＲと仮定し、ＰがＣを含むと仮定しよう。すると、Ｐを基準にしたＣの相対的な表現はＰの左下コーナーを基準にした座標を有する。
ＲＭＢＲＰ（Ｃ）＝（Ｃ．ｘｌ−Ｐ．ｘｌ， Ｃ．ｙｌ−Ｐ．ｙｌ， Ｃ．ｘｈ−Ｐ．ｘｌ， Ｃ．ｙｈ−Ｐ．ｙｌ）
しかしながら、次の簡単な分析は、このＲＭＢＲ技術がＭＢＲ当たりただ３２ビットのみを減らすことを示す。説明の便宜上、ＭＢＲの座標がドメイン上に均一に分布されていると仮定し、同一の高さのＲ‐ツリーノードはほぼ同じ大きさの正方形のＭＢＲを有すると仮定しよう。一般性を維持しながらｘ座標のドメインは単位の長さを有し、同一の間隔を有する２３２個の相異値で構成される。
【００３５】
ｆをリーフノードの平均展開とし、Ｎをデータオブジェクトの総個数としよう。すると、略Ｎ／ｆ個のリーフノードがあり、これらのＭＢＲはｆ／Ｎの面積や、それぞれの軸方向に√（ｆ／Ｎ）の辺の長さを有する。
それぞれの軸方向に単位間隔当たり２３２個の相異値があるので、√（ｆ／Ｎ）の長さを有する区間には２３２ √（ｆ／Ｎ）個の相異値が存在する。
従って、それぞれのｘ軸値に対して３２‐ｌｏｇ２ （２３２ √（ｆ／Ｎ））ビット、つまりｌｏｇ２√（ｆ／Ｎ）ビットを減らすことが可能である。Ｎが１００万でｆが１１である場合、約８．２ビットが減る。４を乗算すると、ＭＢＲ当たり略３２ビットを減らすことが可能である。只、減少するビットの数が元のビットの数より少ない限り、減少するビットの数は元のビットの数に影響を受けない。
【００３６】
減少したビットの数が次元別に容易に媒介変数化するように、前記分析結果を容易に拡張することができる。その拡張結果は、ｌｏｇ２ ｄ√（Ｎ／ｆ）、つまり
（ｌｏｇ２Ｎ−ｌｏｇ２ｆ）／ｄ          （１）
である。
式（１）はＮに対してログ関数的に増加し、ｆに対してログ関数的に減少するが、ｄに対しては線形に減少する。従って、減少するビットの個数は主に次元に依存する。１次元空間の場合、相対座標を用いて表現する技術は、それぞれのスカラーに対してほぼ１６ビットを減らせるが、次元の増加に伴ってその効用性が減少する。
【００３７】
ＱＲＭＢＲ技術
ＲＭＢＲ技術の他に、より効率的な圧縮のために量子化段階が更に行われる。前記ＲＭＢＲ技術は、ＭＢＲから先行の無効ビットを除去する反面、前記量子化したＲＭＢＲ（”ＱＲＭＢＲ”）技術における量子化の段階は、ＲＭＢＲから後位の無効ビットを除去する。以下、ＲＭＢＲの量子化はインデックス検索の正確性に影響を与えず、量子化に伴う若干のオーバーヘッドはキャッシュミスの相当な減少によって保障され得ることを示す。
【００３８】
Ｉを参照ＭＢＲ、１を所定数の量子化レベルとすると、それによるＭＢＲ Ｃの量子化した相対座標を使用した表現は次の通りである。
ＱＲＭＢＲＩ，ｌ（Ｃ）＝φＩ．ｘｌ，Ｉ．ｘｈ，ｌ（Ｃ．ｘｌ），φＩ．ｙｌ，Ｉ．ｙｈ，ｌ（Ｃ．ｙｌ），ΦＩ．ｘｌ，Ｉ．ｘｈ，ｌ（Ｃ．ｘｈ），ΦＩ．ｙｌ，Ｉ．ｙｈ，ｌ（Ｃ．ｙｈ）
ここで、φａ，ｂ，ｌ：Ｒ→｛０，…，ｌ−１｝ 及び、Φａ，ｂ，ｌ：Ｒ→｛１，…，ｌ｝ は
2004519774.tif 000005
2004519774.tif 000006
である。
【００３９】
次の命題はＱＲＭＢＲが上述したＭＢＲの有する２つの特性のうち一番目のものを満足させていることを示す。従って、ＱＲＭＢＲ技術の計算的なオーバーヘッドは、訪問するそれぞれのノード毎にクェリーレクタングルをＱＲＭＢＲに圧縮する負担である。本実施形態で、ＭＢＲをＱＲＭＢＲに圧縮するためにはおよそ約６０個の命令語が必要であり、これはパイプライニングによって４００ＭＨｚプロセッサで約１２０ｎｓ未満の時間に該当する。更に、直ぐにアクセスされたノードのＭＢＲ、及びクェリーＭＢＲがキャッシュされている限り、メモリーアクセスは発生されない。
【００４０】
命題１：ＡとＢをＭＢＲとしよう。任意のＭＢＲ Ｉと定数１に対してＱＲＭＢＲＩ，１（Ａ）とＱＲＭＢＲＩ，１（Ｂ）とがオーバーラップされないと、ＡとＢもオーバーラップされない。
証明：前記命題は、ＡとＢとがオーバーラップされると、ＱＲＭＢＲＩ，１（Ａ）とＱＲＭＢＲＩ，１（Ｂ）とがオーバーラップされることを証明することで証明される。定義に従って、２つのレクタングルは少なくとも一つの点を共有する時にのみオーバーラップされる。従って、ＡとＢは少なくとも一つの点を共有する。この点を（ｘ，ｙ）とすると、次のことが成立する。
2004519774.tif 000007
説明の便宜上、下付きのａ，ｂ及び１は量子化関数φとＦから省略された。
φとＦは単調増加関数であり、任意のｒ∈Ｒに対して、φ（ｒ）≦Φ（ｒ）であるので、
2004519774.tif 000008
となる。
従って、ＱＲＭＢＲＩ，１（Ａ）とＱＲＭＢＲＩ，１（Ｂ）は少なくとも一つの点（φ（ｘ），φ（ｙ））を共有する。即ち、これらはオーバーラップされ、このことから上記命題は証明された。
【００４１】
一般に、ＭＢＲの元座標をそれのＱＲＭＢＲから復旧することは不可能であるので、２つのＭＢＲ同士のオーバーラップ関係を間違って決定する可能性がある。しかしながら、命題１は、実際にオーバーラップされる２つのＭＢＲがオーバーラップされないと云える可能性がないことを保障する。従って、ＱＲＭＢＲ技術は、クェリーを満足させるデータオブジェクトを見逃さない。
【００４２】
しかしながら、実際にオーバーラップされない２つのＭＢＲがオーバーラップされる可能性は相変わらず存在する。これは、インデックス検索の結果が後で精製段階を経て濾過されるフォルスヒットを含むことがあることを意味する。
前記精製段階は、ＭＢＲがデータオブジェクトの正確なキーでない場合が時々あるので、殆どの多次元インデックス構造でも必要である。従って、前記精製段階の必要性自体がオーバーヘッドになるわけではないが、フォルスヒットの数はオーバーヘッドになり得る。フォルスヒットの数は量子化の水準を適切に選択することで、無視するほど（１％以下）に減らすことができる。
【００４３】
本発明のＣＲ‐ツリー
図３Ａ乃至図３Ｇは本発明のＣＲ‐ツリーと関連した手順（アルゴリズム）を示す。前記ＣＲ‐ツリーアルゴリズムと、従来のＲ‐ツリーの変形したものとの間の２つの主な相異点は次の通りである。
即ち、前記ＣＲ‐ツリーは、ノード内にＱＲＭＢＲを貯蔵し、そのＭＢＲが大きくなるか小さくなる時に前記ＱＲＭＢＲを維持する。
【００４４】
図３Ａは前記検索アルゴリズムの流れ図である。前記検索アルゴリズムは、ＣＲ‐ツリーがクェリーレクタングルをノードにあるＱＲＭＢＲと比較する必要があるという点を除いては、他のＲ‐ツリーの変形で使用されるものと類似している。ＱＲＭＢＲからＭＢＲを復旧する代わりに、前記ＣＲ‐ツリーは、各ノードのＭＢＲを参照ＭＢＲとして使用して、クェリーレクタングルを該当ＱＲＭＢＲに変換する。その後、それらが重なるかどうかを決定するために２つのＱＲＭＢＲを比較する。
【００４５】
検索過程：一つのＣＲ‐ツリーと一つのクェリーレクタングルＱとが与えられる時、ＱＲＭＢＲがＱとオーバーラップされる全てのインデックスレコードを探す。
１．初期に空いているスタックＳにルートノードをプッシュする（ステップ３０１）。
２．Ｓが空いている場合（ステップ３０２）、結果セットを返還し（ステップ３０３）、停止する（ステップ３０４）。
３．Ｓが空いていない場合（ステップ３０２）、ＳからノードＮをポップし（ステップ３０５）、ＲをＱＲＭＢＲＮ．ＭＢＲ，ｌ（Ｑ）と設定する（ステップ３０６）。
４．Ｎがリーフノードでなければ（ステップ３０７）、それぞれのエントリＥを確認して、Ｅ．ＱＲＭＢＲがＲとオーバーラップするかどうかを決定する。もし、オーバーラップする場合は、Ｅ．ｐｔｒをＳにプッシュする（ステップ３０８）。
５．Ｎがリーフノードであれば（ステップ３０７）、全てのエントリＥを確認して、Ｅ．ＱＲＭＢＲがＲとオーバーラップするかどうかを決定する。もし、オーバーラップする場合は、Ｅ．ｐｔｒを結果セットに追加する（ステップ３０９）。
６．２段階から繰り返す。
【００４６】
図３Ｂは挿入プロシージャの流れ図である。前記挿入プロシージャは、リーフ選択とインストールプロシージャを呼び出して、ＭＢＲがＣである新たなデータオブジェクトＯをＣＲ‐ツリーに挿入する。ノード分割とツリー調整プロシージャも必要な場合に呼び出される。
前記インストールプロシージャは、Ｎ．ＭＢＲがＣを含むように前記Ｎ．ＭＢＲを拡張し、（ＱＲＭＢＲＮ．ＭＢＲ，ｌ（Ｃ）， ｐ）のエントリを生成し、それをノードＮに追加することで、一対のＭＢＲ Ｃとデータオブジェクトポイントｐを前記ノードＮにインストールする。
Ｎ．ＭＢＲが拡張されていれば、実際のＭＢＲにアクセスすることでＮ内の全てのＱＲＭＢＲを再計算し、Ｎをパスする前記ツリー調整プロシージャを呼び出す。
【００４７】
新たなデータオブジェクトを挿入するために（ステップ３１５）、ＣＲ‐ツリーはオブジェクトＭＢＲの新たなキーを含むための最小限の拡張を必要とする子ノードを選択することでルートから下る。前記ノードのＭＢＲが新たなキーを含めば（ステップ３１６）、新たなエントリのために関連キーが計算される（ステップ３１７）。前記ノードのＭＢＲが新たなキーを含まないと（ステップ３１６）、前記ノードのＭＢＲは前記新たなキーを含むように拡張されなければならない（ステップ３１８）。
【００４８】
このうち何れかを選択するために内部ノードを訪問する時、前記オブジェクトＭＢＲは、ノードＭＢＲを参照ＭＢＲとして使用することで、まずＱＲＭＧＲに変換される。次に、一対のＱＲＭＢＲの間で拡張が計算される。関連キーも全てのエントリに対して計算される（ステップ３１９）。リーフノードに到達すると、ノードＭＢＲはまずオブジェクトＭＢＲを含むように調整される。
その後、データオブジェクトのためのインデックスエントリが前記ノード内に生成される。前記ノードＭＢＲが調整されたら、前記ノード内のＱＲＭＢＲはこれらの参照ＭＢＲが変更されたので、再び計算される。
前記ノードがオーバーフローすると（ステップ３１２）、前記ノードは分離され（ステップ３１３）、その分離はツリー全体に伝播される。
【００４９】
図３ＣはルートからＣＲ‐ツリーの下位に新たなＭＢＲ Ｃを位置させるリーフノードを選択するリーフ選択プロシージャの流れ図である。
ルートノードから始まり、選択可能なノードがリーフノードでなければ（ステップ３３２）、挿入キーがノードのＭＢＲと関連して作られ（ステップ３３５）、子ノードは、関連挿入キーを含む程度の最小の拡張を必要とするように選択される（ステップ３３６）。この過程はリーフノードに到達するまで続けられる（ステップ３３３）。
【００５０】
図３ＤはＲ‐ツリーに使用される線形的な分離アルゴリズムに基づいて一つのノードを２つに分離するノード分割プロシージャの流れ図である。
前記ノードのＱＲＭＢＲは、それらのＭＢＲに従って再計算される必要がある。分離は、２次分離アルゴリズムのような、Ｒ‐ツリー、及びその変形に用いられるその他の分離アルゴリズムを使用して行われ得る。
【００５１】
最も離れているエントリ対はシードで選択される（ステップ３４１）。２つのノードが作られ、それぞれのシードは一つのノードに割り当てられる（ステップ３４２）。 残りエントリのうち何れか一つを選択し（ステップ３４４）、そのＭＢＲの最小拡張が前記選択されたエントリを含むようにするノードに前記エントリを割り当てる（ステップ３４７）。Ｍが一つのノードに含まれる最大限のエントリ数字であり、ｍが一つのノードに含まれる既定義された最小の数字である時、一つのノードが（Ｍ−ｍ）個のエントリを有したら（ステップ３４５）、残りの全てのエントリは他のノードに割り当てられなければならない（ステップ３４６）。前記段階により、それぞれのノードは少なくともｍ個のエントリを有する。全てのエントリが割り当てられると（ステップ３４３）、各ノードのＭＢＲが得られ、各ノードの関連キーも計算される（ステップ３４８）。
【００５２】
分離されるノードがルートであれば、新たなルートが作られ、２つの分離されたノードは、その子として前記ルートに追加される（ステップ３４９）。そして、ＭＢＲ、及び前記ルートの関連キーは再計算される（ステップ３５１）。
仮に、分離されるノードがルートではなく、その親ノードが満杯状態であれば（ステップ３５２）、その親ノードは分離される（ステップ３５５）、
前記親ノードが満杯状態でなく（ステップ３５２）、前記親ノードのＭＢＲが新たなキーを含めていれば（ステップ３５５）、関連キーは２つの新たなエントリに対してのみ再計算される（ステップ３７６）、仮に、親ノードのＭＢＲが新たなキーを含めないと（ステップ３５５）、親ノードのＭＢＲは新たなキーを含むように拡張され（ステップ３５７）、そのノード内の関連キーは全てのエントリに対して再計算され（ステップ３５８）、前記エントリは調整される（ステップ３５９）。
【００５３】
図３ＥはリーフノードＬからルートまで上がりつつノードのＭＢＲを調停し、必要な場合、ノード分離を伝播する前記ツリー調整プロシージャを示す。ノードＭＢＲが調整されると、ノード内のＱＲＭＢＲが再計算される。
まず、前記拡張されたノードがルートであるか否かがチェックされる（ステップ３７１）。前記拡張されたノードがルートではなく、その親ノードのＭＢＲが前記ノードのＭＢＲを含めば（ステップ３７３）、前記親ノードのエントリは更新され、関連キーは再計算される（ステップ３７４）。仮に、親ノードのＭＢＲが前記ノードのＭＢＲを含めていなければ（ステップ３７３）、前記親ノードのＭＢＲは、前記拡張されたノードのＭＢＲを含むように拡張される（ステップ３７５）。前記親ノードのエントリは更新され、前記親ノードの全ての関連キーは再計算され（ステップ３７７）、前記親ノードは一つの拡張されたノードとなるように設定される（ステップ３７８）。
【００５４】
図３ＦはＣＲ‐ツリーからインデックスレコードＥを除去する削除プロシージャの流れ図を示す。削除キーは、ノードのＭＢＲと関連するように変形される（ステップ３８６）。前記ノードがリーフノードであれば（ステップ３８７）、前記ノード内の各エントリは削除オブジェクトと比較される（ステップ３８９）。
もし、何れかのエントリが前記削除オブジェクトと一致すると（ステップ３９０）、そのエントリはリーフノードから削除される（ステップ３９１）。
もし、削除されたエントリのキーが前記リーフノードのＭＢＲと接触すると（ステップ３９３）、各エントリの関連キーは再計算され（ステップ３９４）、ツリーは圧縮される（ステップ３９５）。
【００５５】
図３ＧはＣｏｎｄｅｎｓｅＴｒｅｅプロシージャの流れ図を示す。リーフノードＬから一つのエントリが削除された結果、前記リーフノードにエントリが殆ど残っていなければ、前記ＣｏｎｄｅｎｓｅＴｒｅｅプロシージャは前記ノードを除去し、その全てのエントリは再配置される。ノードの除去は必要に応じてツリーの上部に繋がる。できるだけ大きさが減るように、ルートに向かう経路でノードの全てのＭＢＲを調停する。ノードのＭＢＲが調整されると、ノード内のＱＲＭＢＲは再計算される。
【００５６】
まず、収縮したノードの親エントリが見つけられる（ステップ４０１）。エントリのキーが親ノードと接触しないと（ステップ４０２）、親ノード内で収縮したノードのエントリは更新され（ステップ４０９）、中断される（ステップ４１０）。
エントリのキーが親ノードのＭＢＲと接触すれば（ステップ４０２）、前記エントリキーと、前記収縮したノードのＭＢＲとが比較される（ステップ４０３）。
前記親ノードが収縮され得ないと（ステップ４０４）、親ノードで収縮したノードのエントリは更新されない（ステップ４０５）。しかしながら、前記親ノードが収縮され得ると（ステップ４０４）、親ノード内の収縮したノードのエントリは更新される（ステップ４０５）。親ノードのＭＢＲは再計算され（ステップ４０６）、親ノード内の各エントリの関連キーも再計算される（ステップ４０７）。
前記親ノードは収縮したノードと設定される（ステップ４０８）。
当業者であればＲ‐ツリーとＲ＊‐ツリーで使用された任意の削除アルゴリズムも若干の変更を通じて使用され得ることが分かるだろう。
【００５７】
バルクローディング（Ｂｕｌｋ Ｌｏａｄｉｎｇ）
ＣＲ‐ツリーのバルクローディングは他のＲ‐ツリーの変形と同様である。
ＱＲＭＢＲが正しく管理される限り、既存のボトム‐アップ（Ｂｏｔｔｏｍ−ｕｐ）ローディングアルゴリズムがそのまま使用され得る。
【００５８】
ＣＲ‐ツリーの変形
図４Ａ乃至図４Ｃは、本発明によるＣＲ‐ツリーの３つの変形、つまり、ＰＥ（Ｐｏｉｎｔｅｒ−Ｅｌｉｍｉｎａｔｅｄ）ＣＲ‐ツリー、ＳＥ（Ｓｐａｃｅ−Ｅｆｆｉｃｉｅｎｔ）ＣＲ‐ツリー、そして、ＦＦ（Ｆａｌｓｅ−ｈｉｔ Ｆｒｅｅ）ＣＲ‐ツリーを示す。
【００５９】
図４ＡはＰＥ ＣＲ‐ツリーと呼ばれる一番目の変形を示す。この一番目の変形は、ＣＳＢ＋‐ツリーと同様に、一番目のエントリのポインタを除いては内部ノードから子ノードに対するポインタを除去する。各々のノードは、前記ノードがリーフノードであるか、内部ノードであるかを表示するフィールド（４２１）、前記ノード内のエントリの数字を表示するフィールド４２２、参照ＭＢＲを貯蔵するフィールド４２３、子ノードに対するポインタを貯蔵するフィールド４２４、及びＱＲＭＢＲを貯蔵するためのフィールド４２５を含む。
【００６０】
前記ＰＥ ＣＲ‐ツリーは、例えば、ＣＲ‐ツリーのキーのサイズがＲ‐ツリーのそれより小さいため、大部分のポインタを除去することでＣＲ‐ツリーを大きく拡張する。例えば、ＱＲＭＢＲの大きさが４バイトであるば、ポインタが４バイトである時、前記拡張は内部ノードの展開を２倍にする。
しかしながら、リーフノードに貯蔵されたデータオブジェクトに対するポインタは殆ど除去されない。内部ノードとリーフノードの平均展開が１０である時、内部ノードの数はリーフノードの約９分の１である。従って、全体の展開の増加は約１０％に過ぎない。
【００６１】
一方、ポインタの除去は同じ親元の子ノードを連続的に貯蔵することで可能であるので、ノードの分離作業は相当な負担がかかる。
分離により新たに生成されたノードは、その兄弟ノードと連続的に貯蔵されなければならず、これによって新たな空間が割当てられ、兄弟ノードがその空間に移動されなければならない。
【００６２】
図４Ｂは基本ＣＲ‐ツリーのノードから参照ＭＢＲを除去する所謂ＳＥ（”Ｓｐａｃｅ Ｅｆｆｉｃｉｅｎｔ”）ＣＲ‐ツリーである、二番目の変形を示す。これは各ノードの参照ＭＢＲがその親ノードで一致するエントリから得られることを用いる。
【００６３】
前記図面はルートノードを除いたノードの構造を示す。前記ノードは前記ノードがリーフノードであるか、又は内部ノードであるかを表示するフィールド４３１、前記ノード内のエントリの数字を表示するフィールド４３２、子ノードに対するポインタを貯蔵するためのフィールド４３３、及びＱＲＭＢＲを貯蔵するためのフィールド４３４を含む。参照ＭＢＲは、ルートノードを除いては各ノードに存在しない。
【００６４】
前記ＳＥ ＣＲ‐ツリーは、ＭＢＲの大きさが１６バイトで、ＱＲＭＢＲの大きさが４バイトである時、内部ノードの展開を４倍に増加させ、リーフノードの展開を２倍に増加させる。このような展開の増加は、ノードの大きさが一つ又は二つのキャッシュブロック分だけ小さい時にＰＥ ＣＲ‐ツリーで得られる増加より大きい。
【００６５】
図４ＣはＦＦ（”Ｆａｌｓｅ−ｈｉｔ Ｆｒｅｅ”） ＣＲ‐ツリーと呼ばれる基本ＣＲ‐ツリーの三番目の拡張板を示す。上述した２つの拡張板がリーフノードの展開を増加させるのに対し、前記ＦＦ ＣＲ‐ツリーはリーフノードの展開を減少させる。ＱＲＭＢＲ技術は損失圧縮技法であるので、検索結果は所定のクェリーに対する実際の結果のスーパーセットになり得る。
このような現象は、前記ＱＲＭＢＲ技術が内部ノードにのみ適用され、リーフノードには本来の無関係なＭＢＲを貯蔵する場合には避けられる。
【００６６】
図はオブジェクトＭＢＲ４４１がオブジェクト４４２に対するポインタと共に本来の無関係なフォーマットに貯蔵されるリーフノードの構造を示す。前記ＦＦ ＣＲ‐ツリーは、後続の精製段階が相当な負担がかかる場合に有用である。
例えば、管轄地域の複雑な境界多角形がそれらのＭＢＲによりインデックスされる時、インデックスを検索して得られるデータオブジェクトの実際の形態を所定のクェリー形態と比較する精製段階には相当な負担がかかる。
【００６７】
表１は本発明によるインデックス構造の多様な実施形態に対する所要空間を示す。この際、Ｎはリーフノードエントリの数であり、Ｓはバイトで表現されたノードの大きさである。ＭＢＲの大きさは１６バイトで、ＱＲＭＢＲの大きさは４バイトであり、ポインタの大きさは４バイトであると仮定しよう。ノードが７０％満たされていると仮定し、Ｎが１００万で、Ｓが１２８である時、典型的なインデックスの大きさが計算される。ＰＥ Ｒ‐ツリーはポインタ除去技術を適用した結果としてのＲ‐ツリーの拡張板である。内部ノードの空間はリーフノードの空間を内部ノードの平均展開より１だけ小さい値に分けて計算される。
このような分析は空間要求の面でＰＥ ＣＲ‐ツリーがＣＲ‐ツリーと大きな違いがなく、ＰＥ Ｒ‐ツリーがＲ‐ツリーと違いのないことを示す。
【００６８】
【表１】
2004519774.tif 000009
【００６９】
分析の結果
一般性を維持しながら単位ハイパースクエアのデータドメインを仮定する。
説明の便宜上、データオブジェクトはそのドメイン上で均一に分布されており、クェリーＭＢＲはハイパースクエアと仮定する。更に、他の分析と同様に、同じ高さを有するＲ‐ツリーノードは、ほぼ同一の大きさの正方形のＭＢＲを有すると仮定しよう。上記分析の結果を視覚的に比較するために必要な数値の計算を行うために、マセマティカ（Ｍａｔｈｅｍａｔｉｃａ）（登録商標）３．０が使用された。
【００７０】
リーフノードの高さが１であり、ノードの高さ、つまり、レベルをｈと仮定しよう。Ｍｈをｈの高さを有するノードの個数とすると、
2004519774.tif 000010
となる。
ａｈを高さｈのノードが含む平均領域と仮定すると、ａｈは１／Ｍｈである。ミンコースキー（Ｍｉｎｋｏｗｓｋｉ）の和公式を使用すると、高さｈのノードが所定のクェリーレクタングルとオーバーラップする確率は（ｄ√ｓ＋ｄ√ａｈ）ｄである。
ここで、ｓはクェリーレクタングルの大きさである。従って、クェリーレクタングルとオーバーラップする高さｈのノードの個数はＭｈ（ｄ√ｓ＋ｄ√ａｈ）ｄ、又は
2004519774.tif 000011
この式をリーフノードからルートまで合わせることで、Ｒ‐ツリーでアクセスされたノードの総数は次の通りである。
2004519774.tif 000012
【００７１】
一方、Ｒ‐ツリーがＭＢＲを比較する反面、ＣＲ‐ツリーはノードを訪問するかどうかを決定するためにＱＲＭＢＲを比較する。ＱＲＭＢＲが平均量子化セルの長さ程度だけ本来のＭＢＲより大きいため、ノードアクセスの回数は前記ＣＲ‐ツリーで多少増加する。
【００７２】
１を量子化レベルの数とすると、それぞれのノードは１ｄ個の量子化セルを有し、それぞれのセルの辺の長さは、ｈをノードの高さとする時、ｄ√ａｈ／ｌである。子ノードを訪問するかどうかはクェリーレクタングルのＱＲＭＢＲと、子ノードの貯蔵されたＱＲＭＢＲとを比較することで決定されるので、子ノードを訪問する確率は（ｄ√ｓ＋ｄ√ａｈ／ｌ＋ｄ√ａｈ−１＋ｄ√ａｈ／ｌ）ｄである。Ｍｈを乗算してリーフノードからルートノードまで合わせることで、ＣＲ‐ツリーでのアクセスノードの総数は次の通りである。
2004519774.tif 000013
【００７３】
図５Ａ及び図５Ｂはカーディナリティが１００万で、クェリーの選択性が０．０１％である時、式（２）及び式（３）を示すものである。ここで、ポインタの大きさは４バイトであり、それぞれのノードは７０％が満たされていると仮定する。また、ＭＢＲの大きさは２次元上で１６バイトで、次元の増加に伴って線形的に増加すると仮定する。ＱＲＭＢＲの大きさはＭＢＲサイズの４分の１であると仮定する。前記分析の結果は、アクセスノードの数はノードの大きさが増加することにより減少することを示す。初期にはその減少比率が大きいが、ノードの大きさが増加することによりその比率は次第に減少する。全てのノードの大きさや３つの次元においてＣＲ‐ツリーはＲ‐ツリーを２倍以上凌ぐ。
【００７４】
キャッシュミスの回数
キャッシュミスの回数は一回のノードアクセスが起こすキャッシュミスの回数を式（２）と（３）に乗算することで簡単に求められる。前記結果を得るために、式（２）と（３）にはＳ／６４が乗算される。ここで、Ｓはバイト単位のノードの大きさである。
【００７５】
図６Ａ及び図６Ｂは、図４Ａ及び図４Ｂのような構成に対するキャッシュミスの回数の計算結果を示す。その分析結果から、ノードの大きさが増加するほどキャッシュミスの回数が速やかに最小値に近接し、その後、徐々に増加していることが分かる。キャッシュミスの観点で、ＣＲ‐ツリーはＲ‐ツリーよりほぼ４．３倍だけ優れた性能をあらわす。
【００７６】
図６Ａはキャッシュミスの回数が一般的にはノードの大きさと共に増加した後、特定のノードの大きさで急激に減少するようなこぎり歯状のパターンを示す。このような急激な変化はツリーの高さがより低くなる時に生じる。例えば、ノードの大きさが４４８バイト、或いは５１２バイトである時、４次元Ｒ‐ツリーの高さは７であるが、ノードの大きさが５７６バイトである場合にはツリーの高さが６となる。即ち、このような急激な変化は、ツリーの高さの減少により得られる利点がノードの大きさの増加によるオーバーヘッドを圧倒する時に発生する。
【００７７】
キャッシュミス回数の側面で最適な１次元ノードの大きさが上記したキャッシュブロックの大きさであると示したが、図６Ａ及び図６Ｂは、このようなノードの大きさが、上述したように、多次元の場合には最適ではないことを示す。
【００７８】
図７Ａ及び図７Ｂは、クェリーの選択性を０．００１％〜１％まで変化させながら計算されたキャッシュミスの回数を比較している。Ｒ‐ツリーとＣＲ‐ツリーの場合、共にクェリーの選択性が増加することに伴い最適のノードの大きさも増加することが分かる。
図７Ａはクェリー選択性が増加することで１２８バイト、１９２バイト、３２０バイト、６４０バイト、９６０バイトの順で最適のノードの大きさが増加することを示す。図７Ｂは、クェリー選択性が増加することで６４バイト、１２８バイト、２５６バイト、３２０バイトの順で最適のノードの大きさが増加することを示す。前記最適のノードの大きさはカーディナリティや次元の増加と同様の方法で増加する。
【００７９】
量子化によるフォルスヒット率
リーフノードのそれぞれの量子化セルはｆ／ｌｄＮの面積を有し、各軸に沿ってｄ√（ｆ／ｌｄＮ）の辺の長さを有し、クェリーＭＢＲのＱＲＭＢＲと、オブジェクトＭＢＲとがオーバーラップする確率は（ｄ√ｓ＋ｄ√ａ＋２ｄ√（ｆ／ｌｄＮ））ｄである。
従って、フォルスヒットが発生する確率は、（ｄ√ｓ＋ｄ√ａ＋２ｄ√（ｆ／ｌｄＮ））ｄ−（ｄ√ｓ＋ｄ√ａ）ｄである。これを（ｄ√ｓ＋ｄ√ａ）ｄに分けると、正確な答えに対する量子化によるフォルスヒット率は、
（１＋２（ｄ√（ｆ／ｌｄＮ））／（ｄ√ｓ＋ｄ√ａ））ｄ−１．        （３）
である。
【００８０】
図８Ａ及び図８Ｂはカーディナリティが百万で、クェリー選択性が０．０１％である時の式（４）を示したものである。ここで、ポインタの大きさは４バイトで、それぞれのノードは約７０％満たされていると仮定しよう。
図８Ａは２，４，８バイトの互いに異なるＱＲＭＢＲの大きさに従う２次元ＣＲ‐ツリーのフォルスヒット率を示し、図８Ｂは、２次元、３次元、及び、４次元の３つの次元に対するフォルスヒット率を示す。前記フォルスヒット率は、ノードの大きさや次元が増加するのと共に増加する。４バイトのＱＲＭＢＲを使用すると、前記構成では約１回のフォルスヒットが発生するが、これによって、図６Ａ及び図６Ｂに示すように、数十乃至数百回のキャッシュミスが減少する。
【００８１】
実験の結果
本発明によるＣＲ‐ツリー、及びそれを変形したものの長所を確認するために、Ｓｏｌａｒｉｓ（登録商標）２．７を駆動するＳＵＮ ＵｌｔｒａＳＰＡＲＣ（登録商標）プラットフォーム（８ＭＢ Ｌ２キャッシュを有した４００ＭＨｚ ＣＰＵ）下で幾つかの実験が行われた。
本来のＲ‐ツリー、ＰＥ Ｒ‐ツリー、ＣＲ‐ツリー、ＰＥ ＣＲ‐ツリー、ＳＥ ＣＲ‐ツリー、及びＦＦ ＣＲ‐ツリーの６つのインデックス構造が実現された。バルクローディングアルゴリズムもまた実現された。ノードの大きさは、実現されたインデックス構造内で６４バイトから１０２４バイトまで変化した。
１６バイトのＭＢＲが使用され、ＱＲＭＢＲの大きさは２バイトから８バイトまで変化した。別に明示されない場合は、ＱＲＭＢＲの基本的な大きさは４バイトであり、ノードは約７０％が満たされている。
【００８２】
２つの合成データセットが生成されており、これらは単位正方形に位置した百万個の小さいレクタングルで構成されている。一方は単位正方形内に均一に分布された反面、他方は０．２５の標準偏差を有して中心点（０．５，０．５）の周囲にガウシアン分布を形成する。レクタングルの平均的な辺の長さは０．００１と設定される。
【００８３】
検索性能
本発明による多様なインデックスツリーの検索性能は、２次元領域のクェリーを処理する時に所要される時間を測定することで比較される。中心点が均一に分布される同一の大きさの１０，０００個の互いに異なるクェリーレクタングルが生成される。クェリーレクタングルの大きさは、データ空間の０．０１％から１％まで変化する。データ空間が単位正方形であるので、クェリー選択性はクェリーレクタングルの大きさとほぼ同一である。
【００８４】
図９Ａ及び図９Ｂは、それぞれのノードが７０％満たされるように均一なデータセットでバルクローディングされた多様なインデックスを検索するにかかる時間を示す。ノードの大きさが大きくなるほど、検索時間は速やかに最小値に接近する。前記最小値を過ぎた後、検索時間は徐々に増加する。クェリー選択性が増加すると、前記最小点は右側に移動する。このような傾向は前記６つの全てのツリーに対して成立し、前記分析結果とも一致する。ＣＲ‐ツリー、ＰＥ ＣＲ‐ツリー、ＳＥ ＣＲ‐ツリーは最も速やかなグループを形成する。
Ｒ‐ツリー及びＰＥ Ｒ‐ツリーは最も遅いグループを形成する。ＦＦ ＣＲ‐ツリーは前記２つのグループの間に位置する。
【００８５】
ＳＥ ＣＲ‐ツリーの幅はＣＲ‐ツリー及びＰＥ ＣＲ‐ツリーのそれより広いが、性能は良くない。これは、ＳＥ ＣＲ‐ツリーがその親ノードで一致するエントリからノードの参照ＭＢＲを計算するためである。本実施形態で前記計算は約４０個のＣＰＵ命令語と１６バイトのメモリー書き込みを伴う。
【００８６】
図１０Ａ及び図１０Ｂは、偏重したデータセットでバルクローディングされたインデックスを検索するのにかかる時間を示す。図１０Ａ及び図１０Ｂの間には特別な違いはない。これは、６つの全てのツリーが任意のノードの大きさに対してデータ偏重の観点で多少堅固であることを意味する。
【００８７】
図１１Ａ及び図１１Ｂは、カーディナリティに従ってＣＲ‐ツリーが比例していることを示す。この実験で、クェリーレクタングルの大きさは、検索されたデータオブジェクトの数が類似するようカーディナリティの逆に設定された。
【００８８】
更新性能
更新性能を測定するために、１メガの均一なデータセットでバルクローディングされたツリーに１０万個のデータオブジェクトが挿入された後、前記ツリーからランダムに選択された１０万個のオブジェクトが削除された。
図１２Ａ及び図１２Ｂは、挿入及び削除時にかかる時間をそれぞれ測定したものである。所定のノードの大きさに対して、ＣＲ‐ツリーは挿入時にＲ‐ツリーより約１５％の時間を更に消費する。しかしながら、展開が同一である場合（例えば、２５６バイトのノードの大きさを有するＣＲ‐ツリーと６４０バイトのノードの大きさを有するＲ‐ツリー）、ＣＲ‐ツリーがＲ‐ツリーより同じか或いは更に優れた性能をあらわす。その理由は次の通りである。
【００８９】
挿入のためにツリーに沿って下方に移動する時、最小に拡張する必要がある子ノードが選択される。本実施形態で前記拡張計算は、約３０個のＣＰＵ命令語を消耗するので、前記拡張計算は、ＣＲ‐ツリーとその変形においてキャッシュミスより更に負担がかかる。一つのキャッシュブロックはＣＲ‐ツリーで約５．６個のＱＲＭＢＲを含むので、前記拡張計算負担は、キャッシュブロック当たり約１６８個の命令語であるが、一つのキャッシュミスは、４００ＭＨｚ ｕｌｔｒａＳＰＡＲＣ ＩＩで約８０〜１００回のプロセッササイクルを消耗する。一方、挿入はそれぞれの高さ毎に一つのノードのみにアクセスするので、アクセスしたノードの数は展開でログ関数的に減少するが、それぞれのノードに対する拡張計算の回数は、前記展開と共に線形的に増加する。従って、拡張計算の総回数は展開と共に増加する。
【００９０】
ＰＥ Ｒ‐ツリーは、展開を２５％以下に増加させるため、Ｒ‐ツリーより性能が多少劣る。ＣＲ‐ツリーの展開は、Ｒ‐ツリーのそれより約１５０％更に大きいので、前記ＣＲ‐ツリーは所定のノードの大きさに対してＲ‐ツリーより性能が劣る。
ＰＥ ＣＲ‐ツリーの展開はＲ‐ツリーのそれより約４００％更に大きいので、前記ＰＥ ＣＲ‐ツリーは所定のノードの大きさに対してＲ‐ツリーより性能が遙かに劣る。
反面、展開が同一である時、前記ＣＲ‐ツリーの順位はノードＭＢＲが大きくなるか小さくなる時にＱＲＭＢＲを更新するオーバーヘッドとキャッシュミスの減少により決定される。
【００９１】
図１２Ｂは、削除の順位は挿入の場合とは多少違いがあることを示す。削除は高度の選択的な検索とノード更新との組合せである。
図９Ａ及び図９Ｂに示すように、前記ＣＲ‐ツリーはクェリー選択性が減少する時、Ｒ‐ツリーと同様な性能をあらわす。ところが、ノード更新はノードの大きさが大きくなる時、ＱＲＭＢＲを更新する負担が大きくなるので、負担が更に所要される。従って、ＣＲ‐ツリーは、ノードの大きさが小さい時はＲ‐ツリーより優れた性能をあらわすが、ノードの大きさが増加しながらその関係は逆転される。
【００９２】
図１３Ａ及び図１３Ｂは、挿入や削除後の検索時間を示す。この実験は、挿入や削除がツリーの特性に影響を与えるかどうかを確認するために行われた。
図９Ａ及び図９Ｂに示すように、これらのツリーは、動的な挿入や削除に対してあまり影響を受けない。
【００９３】
量子化レベルの影響
量子化レベルの影響を評価するために、２４，２８，２１６の互いに異なる３つの量子化レベルに対して、量子化により引き起こされるフォルスヒット率、ＭＢＲサイズにおいての量子化エラー、及び検索時間が測定された。これらはそれぞれ２，４，及び８バイトのＱＲＭＢＲと一致する。前記実験は１メガの均一なデータセットでバルクローディングされたツリーを使用した。
【００９４】
図１４Ａ乃至図１４Ｃは、互いに異なる量子化レベルに対して測定されたフォルスヒット率を示す。上述したように、前記フォルスヒット率は（１＋２√（ｆ／ｌ２Ｎ）／（√ｓ＋√ａ））２により計算される。
前記フォルスヒット率は、展開又はノードの大きさに従って増加し、量子化レベル及びクェリー選択性に従って減少する。その測定の結果は前記分析結果と一致する。
【００９５】
１６ビットで量子化する時、検索結果はクェリーの正確な応答とほぼ一致する。８ビットで量子化する時、検索結果はクェリーの正確な応答に比べてせいぜい１％が多いデータオブジェクトを含む。４ビットで量子化することはクェリーの選択性が高い時にのみ使用され得る。
【００９６】
図１５Ａ及び図１５Ｂは、互いに異なる量子化レベルに対して測定されたＭＢＲサイズの増加を示す。この分析は、量子化セルの大きさはリーフノードに対して略ｆ／（１２Ｎ）であり、ＱＲＭＢＲは、本来のＭＢＲがそれぞれの座標軸に従ってセルの長さだけ延長されることを示す。従って、ＱＲＭＢＲの大きさは展開やノードの大きさに従って増加し、量子化レベルの増加に従って減少する。前記測定された結果は分析的な結果と一致する。１６ビットで量子化する時、ＭＢＲの大きさは約０．０１％未満に増加する。８ビットで量子化する時、前記ＭＢＲの大きさはノードの大きさに従って約１〜７％が増加可能であるが、これは図１５Ａ乃至図１５Ｃに示す検索結果の大きさに伴う増加量と同一ではない。
【００９７】
図１６Ａ乃至図１６Ｃは量子化レベルを変化させながら測定した検索時間を示す。ここでは、過度な量子化はクェリーの選択性が低く、且つノードのサイズが大きい時に検索時間の増加を引き起こすことがあるのを示す。これはフォルスヒット率が非常に大きいからである。
要約すると、クェリーの選択性やカーディナリティが増加する時、より少ない数のビットで量子化することは可能であるが、ノードの大きさが増加する時はより多数のビットで量子化する必要がある。
【００９８】
図１７Ａ及び図１７Ｂはアクセスしたインデックスデータの量を示し、これは、初期にインデックス資料がキャッシュされていないか、キャッシュ的中率が最悪の場合のＬ２キャッシュミスである。最悪のキャッシュミスにおいて、６つのツリーは最善から最悪まで、ＳＥ ＣＲ‐ツリー、ＰＥ ＣＲ‐ツリー、ＣＲ‐ツリー、ＦＦ ＣＲ‐ツリー、ＰＥ Ｒ‐ツリー、及びＲ‐ツリーのような順序を形成する。図９Ａ及び図９Ｂに示すように、前の３つが一方のグループを形成し、後の２つが他方のグループを形成する。前記測定された結果も図６Ａ及び図６Ｂの分析的な結果と一致する。
【００９９】
図１８Ａ及び図１８Ｂはパーフモンツール（Ｐｅｒｆｍｏｎ ｔｏｏｌ）（ベンチマークテストプログラム）を用いて測定されたＬ２キャッシュミスの回数を示す。ＵｌｔｒａＳＰＡＲＣプロセッサは、プロセッサイベントを測定するために２つのレジスタカウンターを提供する。前記パーフモンツールは、前記レジスタが前記Ｌ２キャッシュミスの回数をカウントするようにし、これらに貯蔵された値を読み出すために使用される。前記Ｌ２キャッシュミスの回数は、キャッシュ的中と否存在する命令語によりアクセスされたインデックスデータの量とは多少異なる。
否存在する命令語によるＬ２キャッシュミスは、ノードの大きさとクェリー選択性が小さい時に測定されたキャッシュミスの回数が図１７Ａ及び図１７Ｂで最悪の場合のキャッシュミスの回数より更に多くなり得る理由を説明する。
【０１００】
また、ノードの大きさの増加に従ってキャッシュ的中率が増加することも分かる。これは、プロセッサのキャッシュの交替方式により説明され得る。
メモリーブロックは、キャッシュブロックに環形にマッピングされるので（例えば、物理的なアドレスをキャッシュの大きさに分けた残り）、キャッシュされたメモリーブロックは連続的なメモリーブロックに交替されない。
ノードの大きさが増加する時、連続的なメモリーブロックに対するアクセス比率は増加し、それにより、キャッシュ的中率も増加する。
【０１０１】
図１９Ａ及び図１９Ｂは選択性の変化により測定されたキーの比較回数を示す。キャッシュミスの回数とは逆に、ＱＲＭＢＲ技術はキーの比較回数を減らさずにやや増加させる。２つのＭＢＲ間のオーバーラップテストは、本実施形態で平均１０個未満の命令語を所要するので、Ｌ２キャッシュミスを減らすことは少なくとも１０回のオーバーラップテストを減らす価値がある。Ｒ‐ツリー及びＰＥ Ｒ‐ツリーは、類似した展開を有して一方のグループを形成し、前記ＰＥ ＣＲ‐ツリー、及びＳＥ ＣＲ‐ツリーも類似した展開を有して他方のグループを形成する。
【０１０２】
同時性の制御
ＣＲ‐ツリーによる性能の向上を大きく維持するためには、それに合うインデックス同時性制御技法の最適化が必要である。
従来のハッシュ（ｈａｓｈ）に基づいたロック及びアンロック動作は、メインメモリーデータベースでは相当な負担が要求されるので、より迅速なラッチ及びアンラッチ動作が提案されてきた。ラッチデータの構造を静的に割当て、それらを直ぐにアクセス可能であるようにすることで、前記ラッチ及びアンラッチ動作は、約１００個のＲＩＳＣ命令語に該当する約２０個のＣＩＳＣ（ＩＢＭ  ３７０）命令語を使用する。しかしながら、ＣＳＢ＋‐ツリー、及び良く知られたロックカップリング技術に対する本実験は、それぞれのノードが単に約４０プロセッサ周期の間にのみロック状態にあるため、前記ラッチ及びアンラッチ動作は、メインメモリーインデックスツリーの同時性の制御目的には相変わらず相当な負担がかかる。
【０１０３】
ロッキング動作時に追加的なキャッシュミスを防止するために、ロッキングのためのデータ構造は、一致するインデックスノード内に維持される必要がある。
これを可能にするためには、ロッキングのための資料構造ができるだけ小さい方が良い。例えば、本実施形態はそれぞれのノードから単に１バイトのみを使用する。
ロック衝突が発生しても、典型的に数十又は数百のクロックサイクル内に解決される。従って、ロックを解決するためには、数千個の命令語が所要されるコンタクトスイッチを発生させるブロッキングよりはスピニング方法が好ましい。
【０１０４】
ロック動作を簡単に解決すると共に、ロック動作の回数を減らすことが好ましい。これは、ディレクトリサーバーでのように検索が集中的に発生するアプリケーションでの検索機能を強化することで可能である。例えば、更新が進行されない場合、検索動作がツリー全体をロッキングするか、バージョニング（ｖｅｒｓｉｏｎｉｎｇ）技術を用いて検索動作がロックを設定できないようにすることが可能である。
【０１０５】
復旧
本発明はインデックスの大きさをほぼ６０％減少させるので、ディスクアクセス時間を減らすことで、チェックポイント、及び停止後のリスタートプロセスの速度を増加させる。
【０１０６】
メインメモリーデータベースにおいて、プロジェクションの連続性はログ及び間欠的なチェックポイントを通じて維持され得る。メインメモリーデータベースにおけるチェックポイントは、メモリーにあるデータベースのスナップシャットをディスクに貯蔵するプロセスである。停止後のリスタートプロセスは、前記最後のスナップシャットをローディングする段階と、前記最後のチェックポイント後に発生したログの記録を再生する段階とで構成される。従って、前記チェックポイント、及びリスタート動作時のディスクアクセス時間がインデックスの大きさが小さくなる時に減少することは当然である。例えば、ＣＳＢ＋‐ツリーのディスクアクセス時間はＢ＋‐ツリーに比べて１０％だけ減少し、ＣＲ‐ツリーに対するディスクアクセス時間はＲ‐ツリーに比べて半分以下に減少する。
【０１０７】
図２０Ａ及び図２０Ｂは前記分析的な結果が実験的な結果と一致することを示す。
【０１０８】
以上の好ましい実施形態を参照して説明された発明では、それらの実施形態に限定されることが意図される。しかしながら、本発明の精神および範囲を逸脱することなく、説明された実施形態の構造および形式に多様な変更を施すことができることは、当業者によって理解される。
【図面の簡単な説明】
【図１Ａ乃至図１Ｃ】
本発明のＱＲＭＢＲ技術を示す説明図である。
【図２Ａ乃至図２Ｃ】
ＣＲ‐ツリーのデータ構造を示す説明図である。
【図３Ａ乃至図３Ｇ】
ＣＲ‐ツリーの操作に関する流れ図である。
【図４Ａ乃至図４Ｃ】
３つのＣＲ‐ツリーの変形のデータ構造の変化を示す説明図である。
【図５Ａ及び図５Ｂ】
Ｒ‐ツリー及びＣＲ‐ツリーでのノードアクセスを示すグラフである。
【図６Ａ及び図６Ｂ】
Ｒ‐ツリー及びＣＲ‐ツリーでのキャッシュミスを示すグラフである。
【図７Ａ及び図７Ｂ】
２次元Ｒ‐ツリーとＣＲ‐ツリーでのクェリー（ｑｕｅｒｙ）選択性による最適なノードサイズの増加を示すグラフである。
【図８Ａ及び図８Ｂ】
ＱＲＭＢＲのサイズや次元によるフォルスヒット率を示すグラフである。
【図９Ａ及び図９Ｂ】
均一なデータセットを有する大型２次元ツリーの検索性能を示すグラフである。
【図１０Ａ及び図１０Ｂ】
非対称データセットを有する大型２次元ツリーの検索性能を示すグラフである。
【図１１Ａ乃至図１１Ｂ】
カーディナリティ変化による２次元Ｒ‐ツリーとＣＲ‐ツリーの検索時間を示すグラフである。
【図１２Ａ及び図１２Ｂ】
均一なデータセットを有する大型ツリーの更新性能を示すグラフである。
【図１３Ａ及び図１３Ｂ】
挿入又は削除後の検索性能を示すグラフである。
【図１４Ａ乃至図１４Ｃ】
量子化によるフォルスヒット率を示すグラフである。
【図１５Ａ及び図１５Ｂ】
量子化レベルの変化によるＭＢＲサイズの増加を示すグラフである。
【図１６Ａ乃至図１６Ｃ】
量子化レベルの変化による検索時間を示すグラフである。
【図１７Ａ及び図１７Ｂ】
アクセスされたインデックスデータの量を示すグラフである。
【図１８Ａ及び図１８Ｂ】
Ｌ２キャッシュミスの回数を示すグラフである。
【図１９Ａ及び図１９Ｂ】
キーの比較回数を示すグラフである。
【図２０Ａ及び図２０Ｂ】
２次元ＣＲ‐ツリーの分析的及び実験的な結果を比較したグラフである。
【図１Ａ】
2004519774.tif 000014
【図１Ｂ】
2004519774.tif 000015
【図１Ｃ】
2004519774.tif 000016
【図２Ａ】
2004519774.tif 000017
【図２Ｂ】
2004519774.tif 000018
【図２Ｃ】
2004519774.tif 000019
【図３Ａ】
2004519774.tif 000020
【図３Ｂ】
2004519774.tif 000021
【図３Ｃ】
2004519774.tif 000022
【図３Ｄ】
2004519774.tif 000023
【図３Ｅ】
2004519774.tif 000024
【図３Ｆ】
2004519774.tif 000025
【図３Ｇ】
2004519774.tif 000026
【図４Ａ】
2004519774.tif 000027
【図４Ｂ】
2004519774.tif 000028
【図４Ｃ】
2004519774.tif 000029
【図５Ａ】
2004519774.tif 000030
【図５Ｂ】
2004519774.tif 000031
【図６Ａ】
2004519774.tif 000032
【図６Ｂ】
2004519774.tif 000033
【図７Ａ】
2004519774.tif 000034
【図７Ｂ】
2004519774.tif 000035
【図８Ａ】
2004519774.tif 000036
【図８Ｂ】
2004519774.tif 000037
【図９Ａ】
2004519774.tif 000038
【図９Ｂ】
2004519774.tif 000039
【図１０Ａ】
2004519774.tif 000040
【図１０Ｂ】
2004519774.tif 000041
【図１１Ａ】
2004519774.tif 000042
【図１１Ｂ】
2004519774.tif 000043
【図１２Ａ】
2004519774.tif 000044
【図１２Ｂ】
2004519774.tif 000045
【図１３Ａ】
2004519774.tif 000046
【図１３Ｂ】
2004519774.tif 000047
【図１４Ａ】
2004519774.tif 000048
【図１４Ｂ】
2004519774.tif 000049
【図１４Ｃ】
2004519774.tif 000050
【図１５Ａ】
2004519774.tif 000051
【図１５Ｂ】
2004519774.tif 000052
【図１６Ａ】
2004519774.tif 000053
【図１６Ｂ】
2004519774.tif 000054
【図１６Ｃ】
2004519774.tif 000055
【図１７Ａ】
2004519774.tif 000056
【図１７Ｂ】
2004519774.tif 000057
【図１８Ａ】
2004519774.tif 000058
【図１８Ｂ】
2004519774.tif 000059
【図１９Ａ】
2004519774.tif 000060
【図１９Ｂ】
2004519774.tif 000061
【図２０Ａ】
2004519774.tif 000062
【図２０Ｂ】
2004519774.tif 000063
【国際公開パンフレット】
2004519774.tif 000064
2004519774.tif 000065
2004519774.tif 000066
2004519774.tif 000067
2004519774.tif 000068
2004519774.tif 000069
2004519774.tif 000070
2004519774.tif 000071
2004519774.tif 000072
2004519774.tif 000073
2004519774.tif 000074
2004519774.tif 000075
2004519774.tif 000076
2004519774.tif 000077
2004519774.tif 000078
2004519774.tif 000079
2004519774.tif 000080
2004519774.tif 000081
2004519774.tif 000082
2004519774.tif 000083
2004519774.tif 000084
2004519774.tif 000085
2004519774.tif 000086
2004519774.tif 000087
2004519774.tif 000088
2004519774.tif 000089
2004519774.tif 000090
2004519774.tif 000091
2004519774.tif 000092
2004519774.tif 000093
2004519774.tif 000094
2004519774.tif 000095
2004519774.tif 000096
2004519774.tif 000097
2004519774.tif 000098
2004519774.tif 000099
2004519774.tif 000100
2004519774.tif 000101
2004519774.tif 000102
2004519774.tif 000103
2004519774.tif 000104
2004519774.tif 000105
2004519774.tif 000106
2004519774.tif 000107
2004519774.tif 000108
2004519774.tif 000109
2004519774.tif 000110
2004519774.tif 000111
2004519774.tif 000112
2004519774.tif 000113
2004519774.tif 000114
2004519774.tif 000115
2004519774.tif 000116
2004519774.tif 000117
2004519774.tif 000118
2004519774.tif 000119
2004519774.tif 000120
2004519774.tif 000121
2004519774.tif 000122
2004519774.tif 000123
2004519774.tif 000124
2004519774.tif 000125
【国際調査報告】
2004519774.tif 000126
2004519774.tif 000127