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

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

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

Answer 1

有效解决这个问题的数据结构是kd树 。 有很多可用的实现，包括一个node.js 模块 。

Answer 2

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

与R树不同，KD树本身并不平衡。 因此，根据KD-Tree的构build方式，由于树木不平衡和path最长，可能会导致性能不一致。