node.js - 根据位置和指定半径获取数据

Question

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

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

Answer 1

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

Answer 2

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

与 R-Trees 不同，KD-trees 并不是天生平衡的。因此，根据 KD-Tree 的构建方式，您可能会因为不平衡的树和最长的路径而获得不一致的性能。