KD树和R树有什么区别？

Question

我看了KD树和R树的定义。在我看来，它们几乎是一样的。

KD树和R树有什么区别？

Answer 1

它们实际上是完全不同的。它们具有相似的目的（空间数据的区域查询），并且它们都是树（并且都属于包围体层次索引家族），但这就是它们的所有共同点。

• R 树是平衡的，kd 树不是（除非批量加载）。这就是为什么 R 树更适合更改数据，因为 kd 树可能需要重建才能重新优化。
• R 树是面向磁盘的。他们实际上将数据组织在直接映射到磁盘上表示的区域中。这使得它们在实际数据库和内存不足操作中更有用。 kd-trees 是面向内存的，并且放入磁盘页面并不简单
• k-d-trees 在批量加载时很优雅（SingleNegationElimination 指出了这一点，值得称赞），而 R-trees 更适合< em>改变数据（尽管当与静态数据一起使用时，它们确实受益于批量加载）。
• R 树不覆盖整个数据空间。空白区域可能会被发现。 kd 树总是覆盖整个空间。
• kd-trees 将数据空间进行二元分割，R-trees 将数据划分成矩形。二元分裂显然是不相交的；虽然 R 树的矩形可能会重叠（这实际上有时是好的，尽管人们试图最小化重叠）
• kd 树在内存中更容易实现，这实际上是它们的主要好处
• R 树可以存储 矩形和多边形，kd树仅存储点向量（因为多边形需要重叠）
• R树具有各种优化策略，不同的分割，批量加载，插入和重新插入策略等。kd
• 树使用到作为边界的分离超平面的一维距离； R 树使用到边界超矩形的 d 维最小距离进行边界（它们还可以使用某些计数查询的最大距离来过滤真阳性）。
• kd 树支持平方欧几里得距离和 Minkowski 范数，而 R 树也被证明支持大地距离（用于查找地理数据上的邻近点）。

Answer 2

R-tree 和 kd-trees 基于类似的想法（基于轴对齐区域的空间划分），但主要区别是：

• 节点kd 树中的节点表示分离平面，而 R 树中的节点表示边界框。
• kd 树将整个空间划分为多个区域，而 R 树仅划分包含感兴趣点的空间子集。
• kd 树表示不相交的分区（点仅属于一个区域），而 R 树中的区域可能重叠。

（有很多类似的用于划分空间的树结构：四叉树、BSP 树、R* 树等）

Answer 3

此答案中未提及的两者之间的主要区别是 KD 树仅在批量加载情况下有效。一旦构建完成，修改或重新平衡 KD 树就并非易事。 R 树不会受此影响。