algorithm - Rtrees - 算法基础

Question

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

Answer 1

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

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

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

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

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