34

我想比较地理空间数据的 R-Tree 和 Quadtree。虽然那里有文献，但我很难找到涵盖真正基本比较的文件。所以我决定问这个问题。

在我看来，R-Tree 的优点是平衡，树没有空叶子。作为一个缺点，插入或删除等基本操作可能会导致整个索引的重构。

四叉树则相反，它不平衡并且有空叶子，但不需要重新构造。

因此，我想说的是，R-Tree 确实需要更少的内存，并且由于高度最小，因此搜索速度更快。当有许多更新操作时，四叉树更好，但结果树可能不平衡。

您认为这些观点正确吗？有没有涵盖这个主题的好文档？

Auf Wiedersehen，安德烈

4

2 回答 2

45

这是对 QuadTrees 和 R Trees 进行了很好比较的论文：

Oracle Spatial 中的四叉树和 R 树索引：使用 GIS 数据进行比较

一些区别：

  • 四叉树需要通过选择适当的平铺级别进行微调，以优化性能。R-Trees 不需要特定的调整。
  • Quadtree 可以在现有的 B-tree 之上实现。R-Tree - 不能
  • 四叉树索引的创建速度比 R-tree 快。
  • 对于最近邻查询，R-trees 比 Quadtree 快得多。
  • 对于窗口查询，R-trees 比 Quadtree 快得多，例如“inside”、“contains”、“covers”等。
于 2015-01-13T19:31:35.610 回答
13

“重组整个指数”。不可以。重构 R 树仅限于单个路径，而不是“整个”索引。实际上，它的工作原理类似于 B 树。

考虑实现两者，并自己做一些基准测试，以真正了解它们的性能。不要只使用理论。

在具有高变化频率的均匀分布的数据上，四叉树通常会更好地工作。在磁盘上，R-tree 具有明显的优势。

于 2014-05-02T21:17:21.007 回答