我正在阅读 Guttman 的论文链接至论文/书籍
我想知道 R-Tree 是如何处理最近邻查询的，或者实际上是如何实现的。我的想法是从根节点开始遍历树，并检查其中一个条目是否包含查询点。
因此，第一个问题是，如果一个矩形包括查询点，并不意味着该矩形内的所有矩形自动成为查询点最接近的矩形。即使查询点不在矩形内，仍然可能存在另一个距离更短的矩形。
第二个问题是，假设查询点实际上是一个最小边界框，例如 mbr = [left,bottom, right, top]，我想要所有重叠该区域的矩形，或者更好地说，其质心位于给定区域内的所有矩形。这也可能吗？
编辑
通过进行多次实验，Hjaltason、Gísli R.和Hanan Samet在1999年发表的论文《空间数据库中的距离浏览》（ACM Transactions on Database Systems（TODS）24.2（1999）：265-318）中提出的算法（由@Anony-Mousse在答案中发布）明显优于我在这里描述的算法。
旧回答：
据我所知，最好的kNN搜索算法是Cheung、King Lum和Ada Wai-Chee Fu在1998年发表的论文《R-tree上的增强最近邻搜索》（ACM SIGMOD Record 27.3（1998）：16-21）中提出的算法（由@Anony-Mousse复制）。PDF下载
基本算法也在这个演示文稿中解释。
如果我没记错的话，它会执行以下操作：
因此，这个算法非常快地找到最近的邻居，并且几乎不会遍历不包含最终结果的任何节点。
有趣的是，Cheung等人的算法通过删除一些旨在在遍历它们之前排除更多子节点的检查来改进以前的算法。他们可以证明，额外的检查不可能排除节点。
有许多关于在R树中查找最近邻居的论文。
Roussopoulos，Nick，Stephen Kelley和Frédéric Vincent。“Nearest neighbor queries.”ACM sigmod record。Vol。24. No. 2. ACM，1995年。
Papadopoulos，Apostolos和Yannis Manolopoulos。“Performance of nearest neighbor queries in R-trees.”Database Theory-ICDT'97（1997）：394-408。
Hjaltason，Gísli R.和Hanan Samet。“Distance browsing in spatial databases。”ACM Transactions on Database Systems（TODS）24.2（1999）：265-318。
Cheung，King Lum和Ada Wai-Chee Fu。 "Enhanced nearest neighbour search on the R-tree." ACM SIGMOD Record 27.3（1998）：16-21。
Berchtold，S.，Böhm，C.，Keim，D.A.和Kriegel，H.P.（1997年5月）。高维数据空间中最近邻搜索的成本模型。在Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems（pp.78-86）。ACM。
