データ構造のR*ツリー

基本概念

データ処理の場合、R *ツリーは、空間情報のインデックスを作成するために実装されたRツリーのバリアントとして定義されます。

R *ツリーは、データの再挿入が必要になる場合があるため、標準のRツリーよりもわずかに高い建設費がかかります。ただし、結果のツリーは通常、クエリのパフォーマンスが向上します。標準のRツリーと同じように、ポイントデータと空間データの両方を格納できます。 R *ツリーの概念は、1990年にNorbert Beckmann、Hans-Peter Kriegel、Ralf Schneider、BernhardSeegerによって提案されました。

R*ツリーとRツリーの違い

R*-ツリーは繰り返し挿入によって構築されます。このツリーにはほとんど（つまりほとんど）重複がないため、クエリのパフォーマンスが向上します。カバレッジとオーバーラップの両方を最小化することは、Rツリーのパフォーマンスにとって非常に重要です。データ挿入またはクエリでのオーバーラップの意味は、ツリーの複数のブランチを拡張する必要があることです（データがオーバーラップする可能性のある領域に分割される方法のため）。カバレッジを最小化すると、プルーニングパフォーマンスが向上し、特にネガティブレンジクエリの場合、ページ全体を検索から頻繁に除外できます。 R *ツリーは、改訂されたノード分割アルゴリズムのコレクションとノードオーバーフローでの強制的な再挿入の概念を実装して、両方を削減しようとします。この概念は、Rツリー構造がエントリの挿入順序に非常に影響を受けやすいという観察に基づいているため、挿入ビルド（バルクロードではなく）構造は最適ではない可能性があります。エントリを削除して再挿入すると、実際の場所よりも適切な場所をツリー内で「見つける」ことができます。

アルゴリズムと複雑さ

• R *ツリーは、クエリおよび削除操作用の通常のRツリーと同様のアルゴリズムを実装します。
• 挿入時に、R*ツリーは複合戦略を実装します。リーフノードの場合、オーバーラップが最小化され、内部ノードの場合、拡大と面積が最小化されます。
• 分割時に、R *ツリーは、周囲長に基づいて分割軸を選択し、オーバーラップを最小限に抑えるトポロジカル分割を実装します。
• 拡張された分割戦略に加えて、R *ツリーは、Bツリーのバランスをとるという概念に触発されて、オブジェクトとサブツリーをツリーに再挿入することにより、分割をスキップしようとします。

したがって、最悪の場合のクエリと削除の複雑さはRツリーに似ています。 R *ツリーへの挿入戦略は、O（M log M）がRツリーの線形分割戦略（O（M））よりも複雑ですが、2次分割戦略（O（M 2 ））Mオブジェクトのページサイズの場合、全体の複雑さにはほとんど影響しません。挿入の複雑さの合計は、依然としてRツリーに匹敵します。再挿入はツリーの最大1つのブランチに影響し、したがってO（log n）の再挿入に影響し、通常のRツリーで除算を実行するのに匹敵します。したがって、全体として、R*ツリーの複雑さは通常のRツリーの複雑さに似ています。