R树和四叉树比较

Question

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

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

四叶树是相反的,它不平衡并且有空叶,但它不需要被重新修剪.

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

您认为这些观点是否正确？那里有没有涵盖这个主题的好文件？

Auf Wiedersehen,安德烈

Answer 1

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

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

一些差异:

• Quadtrees需要通过选择合适的平铺级别进行微调,以优化性能.R树不需要特定的调整.
• Quadtree可以在现有的B树之上实现.R树 - 无法
• 四叉树索引的创建速度比R树快.
• 对于最近邻居查询,R树比Quadtree快得多.
• 对于窗口查询,R树比四叉树快得多,比如"内部","包含","封面"等.

Answer 2

"重组整个指数".否.重组R树仅限于单一路径,而不是"整体"索引.实际上它的工作方式类似于B树.

考虑实现这两者,并自己做一些基准测试,以真正了解它们的表现.不要只使用理论.

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