91

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

KD树和R树有什么区别？

4

3 回答 3

116

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

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

R-trees和k d-trees基于相似的思想（基于轴对齐区域的空间划分），但主要区别在于：

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

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

于 2010-12-03T12:58:32.930 回答
43

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

于 2010-12-03T13:03:24.437 回答