algorithm - Rtrees - 算法基础

Question

我试图了解 RTree 算法的基础知识，并试图弄清楚它如何执行搜索，例如 1 公里内的所有 retaurants。我们会将所有对象存储在数据库中的矩形中，然后（可能）根据当前位置构建一个查询矩形，然后找到与其重叠的所有矩形。然后我们是否会扫描结果以找到感兴趣的对象，即只有餐厅的对象？

Answer 1

是的，这基本上就是R 树上的范围查询的工作方式：如果一个矩形与您的查询区域重叠，则展开它（查看内容、矩形或点）。否则，忽略它。对于矩形到矩形的重叠测试很简单，对于球形查询，您需要计算球体中心到矩形的最小距离（“minDist”）。

k 最近邻查询有点棘手；在这里你需要优先队列。始终扩展最佳候选对象（通过“minDist”），直到找到比下一个矩形“minDist”更近的 k 个对象。

由于您无法真正索引“是餐厅”属性，因此您必须构建仅包含餐厅的 r-tree，或者按餐厅属性过滤结果。（这也是在 SQLite 中完成的方式；空间部分使用 R-tree 进行索引，而餐厅属性例如通过连接或位图索引获得）

R-tree 的棘手部分不是查询，而是如何构建它。批量加载点数据 (STR) 有非常简单但很好的方法，但对于在线数据库，您需要一些棘手的方法。根据我的经验，R*-trees 明显优于经典 R-trees；R*-trees 使用的重新插入在真正的 DBMS 中实现特别棘手。一个有趣的权衡是只使用 R* 的插入和拆分，而不是重新插入。在查询方面，无论如何 R 和 R* 之间没有区别。

kd-trees：它们与 r-trees 相关，但有一些关键区别：首先，它们不是为磁盘存储而设计的，而是仅用于内存中的操作。其次，它们并不意味着要更新（它们不是平衡树），但是如果您有更改，则必须不时重新构建它们以保持良好的性能。所以在某些情况下，它们会表现得非常好（而且它们实现起来相当简单），但是一旦你获得大数据和磁盘，它们就会更加痛苦。此外，它们不允许不同的加载策略。