寻找可移动的地理标记对象的体系结构

Question

我目前有一个Postgres数据库，里面填满了大约。全球300.000辆行驶车辆的数据集。我经常重复的问题是:给我半径为5/10/20英里范围内的所有车辆。目前，我在数据库中花费了大约600到1200ms来准备定位的车辆对象集。

如果可能的话，我希望这一次能有一个或两个数量级的理想改进。我在Ruby on Rails 3.0beta环境中工作，如果这是相关的话。

你知道如何构建整个系统来加速这个查询吗？有没有NoSQL数据库能够提供这样的地理定位性能？我知道MongoDB正在开发一个扩展来简化这种情况，但还没有尝试过。有没有聪明地使用Redis来实现这一点？

这里SQL- DB的一个问题似乎是我不可能使用索引，因为我的车辆大多在移动，这意味着我必须不断地创建DB索引，这本身可能比只进行没有索引的搜索更昂贵。

期待您的意见，谢谢！

Answer 1

如果您使用正确的算法来组织您的数据，您将能够使用spatial index来显著加快您的查询速度。

地理位置域的最佳实践是使用geohash、quad-tree、R-tree或类似的数据结构(R树是最通用的，但听起来像是在查询点数据，所以这可能无关紧要)。在每种情况下，都可以创建使用单个线性列的空间索引，其中每个值表示一个大小和形状不同的边界框。这应该可以让您在数据库中使用单个范围查询来回答大多数查询。空间索引可以用SQL实现(PostGIS、MS SQL、MySQL都有空间数据类型和使用这些技术之一的空间索引)或NoSQL (因为其水平可伸缩性而流行；AppEngine有geomodel，SimpleGeo使用Cassandra，Foursquare使用MongoDB)。

使用索引可能会因为不断移动点而变得复杂，但我怀疑写操作，即使是更新索引的稍微重一点的写操作，也不会成为瓶颈。

Answer 2

即使你的车辆一直在移动，我也假设它们有某种速度限制。您可以做的是创建某种离散坐标系，例如经纬度坐标的整数部分。然后将这些值放在单独的列中，将确切位置保留在另一列中。然后，您应该能够对整数列进行索引，因为车辆不会移动太多，因此它们不会经常更改这些值。

在进行搜索时，首先找出哪些“正方形”是有趣的，并使用索引列将查询限制在这些正方形内的车辆上。然后你必须对每个方块内的所有车辆进行全面搜索。你必须对所有车辆进行全面搜索的车辆数量现在应该只占所有车辆的一小部分。这个策略的效率当然取决于你的车辆的分布。如果他们中的50%在某个城市的某个地方，这将不起作用，但假设在一个地方的最大车辆组是5-10%，它应该会提高性能。