34

地理空間データの R-Tree と Quadtree を比較したいと考えています。そこには文献がありますが、実際の基本的な比較をカバーするドキュメントを見つけるのに苦労しています. そこで、この質問をすることにしました。

私の意見では、R ツリーにはバランスがとれているという利点があり、ツリーには空の葉がありません。欠点として、挿入や削除などの基本的な操作によって、インデックス全体が再構築される可能性があります。

四分木は反対で、バランスが取れておらず、空のリーフがありますが、再構築する必要はありません。

そのため、R ツリーは必要なメモリが少なく、高さが最小限であるため、検索が高速であると言えます。更新操作が多い場合は四分木の方が適していますが、結果として得られるツリーのバランスが崩れる可能性があります。

これらの点はあなたの意見で正しいですか。このトピックをカバーする適切なドキュメントはありますか?

アウフ・ヴィーダーセヘン、アンドレ

4

2 に答える 2

45

これは、QuadTrees と R Trees の非常に優れた比較を示す論文です。

Oracle Spatial の四分木インデックスと R ツリー インデックス: GIS データを使用した比較

いくつかの違い:

  • クアッドツリーは、パフォーマンスを最適化するために適切なタイル レベルを選択して微調整する必要があります。R ツリーに特別な調整は必要ありません。
  • 四分木は、既存の B ツリーの上に実装できます。R-Tree -できません
  • Quadtree インデックスは、R ツリーよりも高速に作成されます。
  • 最近傍クエリでは、R ツリーは Quadtree よりもはるかに高速です。
  • R ツリーは、"inside"、"contains"、"covers" などのウィンドウ クエリで Quadtree よりも大幅に高速です。
于 2015-01-13T19:31:35.610 に答える
13

「インデックス全体の再構築」。いいえ。R ツリーの再構築は、「全体」のインデックスではなく、単一のパスに制限されています。実際には、B ツリーと同様に機能します。

両方を実装し、自分でいくつかのベンチマークを実行して、それらがどのように機能するかを実際に把握することを検討してください。理論だけを使うな。

変更頻度の高い均一に分散されたデータでは、通常、四分木がより適切に機能します。ディスク上では、R ツリーには明らかな利点があります。

于 2014-05-02T21:17:21.007 に答える