问题标签 [r-tree]

我已经阅读了几篇关于 KD Trees 与 R-Trees 的 SO 帖子，但我仍然对我的具体应用有一些疑问。

对于我的 Java 应用程序，我想维护相对少量的空间数据点（几十万）。关键是数据插入不会被批量加载，而是频繁且增量地插入。我还应该提到，我将对空间域的子区域执行大量的周期性范围查询。

我读过 KD 树通常不支持增量构建，而 R 树更适合于此，因为它们保持平衡状态。

但是，在查看了此处建议的解决方案后： Java 对商业友好的 R-tree 实现？

我没有发现这些实现很容易用于返回范围搜索中的点列表。但是，我发现： http: //java-ml.sourceforge.net/有一个非常好的 KD 树实现，它可以快速运行，并且在一组测试点（~25K）方面优于标准数组存储。此外，我读过 R 树在处理点时会存储冗余信息（因为点是最小 = 最大值的矩形）。

由于我使用的点数较少，因此这两种结构之间的差异是否比使用存储数百万点的数据库应用程序更重要？

传单是否提供了一种方法来确定多边形内的哪个渲染点（如果有）？不是通过迭代一堆形状和检查边界，而是通过使用 rtree 索引，也许？

我是 R-Tree 概念的新手。对不起，如果我问一个与 Rtree 相关的非常基本的问题。我已经阅读了一些关于 R-Tree 的文献来了解 R-Tree 的基本概念。但是，我无法理解 MBR 中的聚类或分组步骤。困扰我的是：

每个 MBR 中可以容纳多少点或对象？我可以看到每个 MBR 中存储的对象数量是不同的。那么是否有任何条件或过程或公式或任何东西来确定每个 MBR 中将存储多少对象？

谢谢你的帮助！格拉西亚斯！

我有一组对象（我们称之为points），其中包含它们在某个确定空间内的位置的 x-y-和 z-分量。我想对 中的对象之间的交互进行建模points，但是，除非我能快速找到集合中与该集合中的一个对象之间的距离小于一定距离的对象，否则我不能这样做。

这无疑听起来有点不清楚，所以让我换一种说法：如果第一个点points有坐标<x, y, z>，我想弄清楚哪个对象points与第一个点的距离小于[某个任意值] .

我正在考虑在 Java 中实现 R-Tree 来执行此操作，但我觉得这是一个足够常见的问题，存在一个更简单的解决方案。如果没有，我将不胜感激对查询 R-Tree 以查找x与树中x已知对象有一定距离内的对象的方法的简单解释。

编辑：注意这些对象的位置值将会改变

我对 R-Tree 数据结构有疑问。R-Tree 中的扇出是什么。它是最大条目数吗？

我们如何确定 R-Tree 中的最小和最大条目数？假设我有 10000 个点并且我的页面大小为 8kb。

谢谢

我对 R-Tree 高度 ( h ) 方程的“m”符号感到困惑。这个“m”代表什么？是最低进入还是最高进入？这是等式：

在哪里，

N = 数据对象的数量

h = R-Tree 高度的最大值

谢谢！

1) 我看到一张图片（见下文），其中显示了一个 R+-Tree 示例，其中包含一些数据。节点“A”和“B”之间怎么可能有空格？据我了解，任何新节点都是通过拆分过程创建的，因此它们之间总是必须共享一些边界，这是应用“拆分平面”的结果。我能想到的只是图片是一系列复杂的添加-删除-重建操作的结果......

2) 假设我们有一个由节点“A”和“B”组成的 R+-Tree（见图 2），我们试图在这个 R+-Tree 中插入一个绿色矩形 G。G 命中“A”和“B”节点（因此必须同时添加）。但是“A”和“B”节点必须如何扩展？（G 必须完全被一个节点覆盖）。

拆分算法会影响我们的查询答案吗？R-tree 有几种分裂算法，例如 Quadratic、Linear、Greene's、Ang 和 Tan 等。除了搜索时间之外，这些算法是否会影响我们的查询答案？

选择 R+-Tree 而不是 R-Tree 进行空间索引的主要原因是什么？据我所知，R+-Tree 避免了节点重叠导致更复杂的代码、更复杂的划分算法等等。R*-tree 与 R-tree 非常相似，但最大限度地减少了节点重叠，并且比 R+-tree 需要更少的代码。那么，除了每个节点查找都需要昂贵的 IO 的情况外，选择 R+-tree 而不是 R*-Tree 的理由是什么？

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

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

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

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

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

Auf Wiedersehen，安德烈