根据位置和指定的半径获取数据

Question

场景：我有一个很大的数据集，每个条目包含一个位置（x，y - 坐标）。 我希望能够从这个数据集中请求这个数据集中的每个条目，这个数据集位于这个数据集中的100米内，并将它作为一个数组返回。

如何去执行这样的事情？有没有推荐的模式或框架？我以前只使用关系或简单的键值类型数据。

Answer 1

有效解决此问题的数据结构是k-d tree。有很多可用的实现，包括node.js module。

Answer 2

将您的数据集放入PostgreSQL并使用R-Tree索引。然后，您可以执行边界框查询，以获取任何位置具有+ -100英里的所有点。然后计算径向距离并接受100英里内的点。您可以推出自己的模式和查询或使用PostGIS。

与R树不同KD树不是内在平衡的。因此，取决于如何构建KD-Tree，由于树木不平衡和路径最长，您可能会获得不一致的性能。