谁能告诉我KD-tree和R-tree有什么区别

我看看KD-tree和R-tree的定义,看起来它们差不多。

谁能告诉我KD-tree和R-tree有什么区别? 谢谢

R树和K树是基于相似的思想(基于轴alignment区域的空间分割),但是关键的区别是:

  • k棵树中的节点表示分离平面,而R树中的节点表示边界框。
  • k d-trees将整个空间分割成区域,而R-树仅分割包含兴趣点的空间的子集。
  • k d-trees表示不相交的分区(点只属于一个区域),而R-树中的区域可能重叠。

(有很多类似的树结构用于划分空间:四叉树,BSP树,R *树等等)

他们实际上是完全不同的。 它们的用途相似(对空间数据进行区域查询),它们都是树木,但这些都是他们所有的共同点。

  • R树是平衡的 ,kd树不是(除非批量加载)。 这就是为什么R树更适合改变数据的原因,因为kd树可能需要重build以重新优化。
  • R-Trees是面向磁盘的 。 他们实际上将数据组织在直接映射到磁盘表示的区域中。 这使得它们在真实数据库和内存不足操作中更有用。 kd-trees是以内存为导向的,并且可以放入磁盘页面
  • R-树不覆盖整个数据空间。 空的地方可能被发现。 kd-trees总是覆盖整个空间。
  • kd-trees 二进制分割数据空间,r-trees将数据分割成矩形 。 二元分裂显然是不相交的; 而r-树的矩形可能会重叠(实际上有时是好的,虽然人们试图最小化重叠)
  • kd-trees在内存中实现起来要容易得多,这实际上是他们的主要好处
  • R树可以存储矩形和多边形 ,kd树只存储点向量(因为多边形需要重叠)
  • R树带有各种优化策略,不同的分割,批量加载器,插入和重新插入策略等。

Gareth Rees没有提到的两个主要区别在于,Kd树只能在批量加载情况下有效。 一旦build成,修改或重新平衡Kd树是不平凡的。 R树不会受到这个。