存储距离敏感空间数据的最佳数据结构是什么？

Question

假设我有关于气象站坐标、历史温度值和世界各地城市中心坐标的数据。气象站被放置在离市中心不同的距离上。其任务是利用气象站的数据确定城市温度的平均历史值。

为了解决每个城市的问题，我需要找到一些半径内最近的流星站集合，并平均它们的数据。蛮力的方法是计算每个城市到每个气象站的距离，但对我的数据来说太慢了。所以我想树的数据结构能帮上忙。我试着使用R-树将meteo站点按坐标划分，但存在一个问题--这种方法允许我在某些树节点中找到meteo站点，但它不能给我提供有关相邻节点的信息，可以快速计算半径条件(例如，如果城市非常接近R-树节点的边界)。

是否有一种标准的树数据结构，允许快速搜索所需的节点，但同时也提供同一树级上的空间邻居集？

Answer 1

你可能不应该担心“同级邻居”之类的问题，这些信息并不一定意味着什么。我觉得你应该

1. 决定是希望所有气象站都在给定的距离内(范围查询)还是最近的k个气象站。
2. 然后，我将使用索引的API来查找站点。
3. 然后计算距离。

R-树是可以的，但他们通常是相当缓慢的装载。如果加载时间有问题，您可能需要尝试R+tree、R*树，或者是四叉树(用于小数据集)或PH树 (用于大型数据集，我在Java中的实现)。

数据是如何在树中被组织的，这不应该引起关注。谁曾经实现过树可能是最有效的方法，找到理想的邻居。

Answer 2

使用数据库怎么样？然后查询它以找到接近某个特定点的点？许多数据库已经支持地理空间数据，您可以索引和查询：

• 波什
• mongodb 地理空间
• mysql 扩展