根據位置和指定的半徑獲取數據

Question

場景：我有一個很大的數據集，每個條目包含一個位置（x，y - 座標）。 我希望能夠從這個數據集中請求這個數據集中的每個條目，這個數據集位於這個數據集中的100米內，並將它作爲一個數組返回。

如何去執行這樣的事情？有沒有推薦的模式或框架？我以前只使用關係或簡單的鍵值類型數據。

Answer 1

有效解決此問題的數據結構是k-d tree。有很多可用的實現，包括node.js module。

Answer 2

將您的數據集放入PostgreSQL並使用R-Tree索引。然後，您可以執行邊界框查詢，以獲取任何位置具有+ -100英里的所有點。然後計算徑向距離並接受100英里內的點。您可以推出自己的模式和查詢或使用PostGIS。

與R樹不同KD樹不是內在平衡的。因此，取決於如何構建KD-Tree，由於樹木不平衡和路徑最長，您可能會獲得不一致的性能。