データ構造のヒルベルトツリー

RツリーバリアントであるヒルベルトRツリーは、線、領域、3Dオブジェクト、または高次元の特徴ベースのパラメトリックオブジェクトなどの多次元オブジェクトのインデックスとして定義されます。これは、多次元オブジェクトのB+ツリーの拡張として想像できます。

Rツリーのパフォーマンスは、ノード上のデータ長方形をクラスター化するアルゴリズムの品質に依存します。ヒルベルトRツリーは、データの長方形に線形順序を課すために、空間充填曲線、特にヒルベルト曲線を実装します。

ヒルベルトのRツリーには2つのタイプがあります。1つは静的データベース用、もう1つは動的データベース用です。どちらの場合も、ヒルベルト空間充填曲線は、ノード内の多次元オブジェクトのより良い順序付けを実現するために実装されています。この順序は「適切」として扱われる必要があります。つまり、「類似した」データ長方形をグループ化して、結果の最小境界長方形（MBR）の面積と周囲長を小さくする必要があります。パックされたヒルベルトRツリーは、更新が非常にまれであるか、更新がまったくない静的データベースに役立ちます。

基本的な考え方

次の例は静的環境を対象としていますが、優れたRツリー設計の直感的な原則について説明しています。これらの原則は、静的データベースと動的データベースの両方に有効です。

RoussopoulosとLeifkerは、ほぼ100％のスペース使用率を達成するパックされたRツリーを構築するための手法を提案しました。

このアイデアは、長方形の角の1つのx座標またはy座標でデータを並べ替えるために開発されました。 4つの座標のいずれかで並べ替えると、同じ結果が得られます。この説明では、点または長方形のいずれかが、長方形の左下隅のx座標でソートされ、「lowxパックされたRツリー」として示されます。長方形のソートされたリストがスキャンされます。連続する長方形は、ノードがいっぱいになるまで、およびいっぱいにならない限り、同様のRツリーリーフノードに割り当てられます。次に、新しいリーフノードが構築され、ソートされたリストのスキャンが続行されます。したがって、結果として得られるRツリーのノードは、各レベルの最後のノードを除いて、完全にパックされます。これはインシデントにつながるため、スペース使用率は約100％になります。ツリーの上位レベルも同様の方法で構築されます。

アルゴリズムヒルベルトパック

（長方形をRツリーにパックする）

手順1.各データ長方形のヒルベルト値が計算されます。

手順2.ヒルベルト値の昇順のデータ長方形が並べ替えられます。

ステップ3./*リーフノードの作成（レベルl =0）* /

• 一方（長方形はもっとあります）
• 新しいRツリーノードが生成されます
• このノードの次のC長方形が割り当てられます

ステップ4./*より高いレベル（l + 1）でノードを作成する* /

• 一方（レベルlには1つ以上のノードがあります）
• 作成時間の昇順でレベルl≥0のノードが並べ替えられます
• ステップ3が繰り返されます

ここでの前提は、データが静的であるか、変更の頻度が低いことです。これは、スペース使用率が最大100％のRツリーを構築するための単純なヒューリスティックであり、同時に良好な応答時間を実現します。