地理空间索引如何工作？

Question

我想知道地理空间索引（例如 MongoDB 使用的索引）是如何工作的。谁能解释一下内部使用的数据结构/算法是什么？搜索运行的时间复杂度是多少？

资源链接也很棒。

Answer 1

根据数据类型和使用模式，R-Tree 或变体 (R*, R+)或四叉树，甚至可能是kd-树。

Answer 2

根据另一个SO问题：

当前的实现对地理哈希码进行标准编码
MongoDB B 树。 $near 查询的结果是准确的。一项限制
使用这种编码，虽然速度很快，但前缀查找不会给出
准确的结果，尤其是在位翻转区域周围。 MongoDB 解决了这个问题
通过在初始前缀扫描后进行网格邻居搜索来选择
提高任何落后点。这通常可以确保性能
保持非常高，同时提供正确的结果。