data-structures - KD 树和 R 树有什么区别？

Question

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

KD 树和 R 树有什么区别？

Answer 1

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

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