我有一个地球上100万个(缓慢)移动点的列表(存储为纬度和经度)。每隔一段时间，每个点都会请求100个最近的其他点的列表(如果有帮助，可以配置最大范围)。
不幸的是，SELECT * SORT BY compute_geodetic_distance() LIMIT 100太慢了，不能一次又一次地通过每个点来完成。所以我的问题是:我应该如何有效地处理这个问题?有没有更好的算法/数据结构/…以此闻名?或者这是唯一的方法，我是否应该考虑分配服务器负载?
为了你的任务，地理空间数据库已经被发明了。
有Oracle Spatial(昂贵的)和PostGres(免费的)。这些数据库将你的数百万个点存储在一个地理索引中，一个四叉树(Oracle)。这样的查询几乎不需要时间。
有些人，比如我，更喜欢把数据库放在一边，自己建立四叉树。
查找和插入操作易于实现。更新/删除可能更复杂。(与实现工作相关的最便宜的是每分钟构建一个新的四叉树)
使用四叉树，您可以在一秒钟内执行数百或数千个最接近的100点。
在架构上，我会安排每个"点"在其变化超过一定数量时将其位置打电话给服务器。在服务器上，您可以执行计算移动点与其他每个点之间的距离的繁重工作，并为每个其他点更新100个最近点的列表(如果需要)。然后你可以将更改推送到最近的100个列表中(如果你使用的是App Engine, Android支持推送)。
这将所涉及的工作量减少到绝对最小:
- 仅当一个点移动到足够远时报告位置变化
- 只在收到报告时重新计算距离
- 不要每次都为一个点重新构建最近的100列表，构建一次列表，然后计算是否将移动的点从其他点的列表中添加或删除。
- 仅通知其前100个列表中的更改点以保留带宽。
你可以使用一些算法来使这个超级高效，这个问题也有一个分叉/连接的感觉，允许你在这个问题上投入马力。
你必须将地球划分为区域，然后使用内部点算法来找出手机所在的区域。每个可能的区域子集将唯一地确定最接近公平近似值的100个节点。您可以通过逐个检查候选节点的距离来获得精确的100个节点的集合，候选节点(同样)是由区域子集决定的。
除了r-tree或四叉树，也就是空间索引，你还可以使用四叉键和怪物曲线。这条曲线减少了尺寸，完全填满了空间。你可以从phpclasses.org下载我的php类hilbert curve。您可以为四键使用一个简单的varchar列，并从左到右搜索关卡。一个很好的解释来自微软必应地图quadkey网站