KD树和R树之间有什么区别？

Question

我看了KD树和R树的定义.在我看来,他们几乎是一样的.

KD树和R树之间有什么区别？

Answer 1

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

• R树是平衡的,kd树不是(除非是大量装载).这就是R树更改数据的首选原因,因为可能需要重建kd树以进行重新优化.
• R-Trees是面向磁盘的.它们实际上在直接映射到磁盘表示的区域中组织数据.这使它们在真实数据库和内存不足操作中更有用.kd-tree是面向内存的,并且放入磁盘页面并不重要
• R-Trees不覆盖整个数据空间.可以揭开空白区域.kd-trees总是覆盖整个空间.
• kd-trees 二进制分割数据空间,r-trees将数据分割成矩形.二进制分裂显然是不相交的; 而r树的矩形可能重叠(实际上有时是好的,尽管有人试图最小化重叠)
• kd-tree在内存中更容易实现,这实际上是它们的关键优势
• R树可以存储矩形和多边形,kd树只存储点矢量(多边形需要重叠)
• R-tree具有各种优化策略,不同的分割,批量加载,插入和重新插入策略等.

Answer 2

R树和k d树基于类似的想法(基于轴对齐区域的空间划分),但关键区别是:

• k中的节点 d树中的表示分离平面,而R树中的节点表示边界框.
• k d-trees将整个空间划分为区域,而R-tree仅划分包含感兴趣点的空间子集.
• k个 d树表示不相交的分区(点仅属于一个区域),而R树中的区域可以重叠.

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

Answer 3

这个答案中没有提到的两者之间的主要区别是KD树只在批量加载情况下有效.一旦构建,修改或重新平衡KD树是非常重要的.R树不会受此影响.