我有一个全球 100 万个（缓慢）移动点的列表（存储为纬度和经度）。时不时地，每个点都会请求 100 个最近的其他点的列表（如果有帮助，可以使用可配置的最大范围）。
不幸的是SELECT * SORT BY compute_geodetic_distance() LIMIT 100，每一个点都一遍又一遍地完成太慢了。所以我的问题是：我应该如何有效地处理这个问题？有没有更好的算法/数据结构/...为此而闻名？或者这是唯一的方法，我应该考虑分配服务器负载吗？
（注意：这是针对 Android 应用程序，重点是用户，所以如果我错过了特定于 android 的解决方案，请随意说！）
为了您的任务，已经发明了地理空间数据库。
有 Oracle Spatial（昂贵）和 PostGres（免费）。
这些数据库将您的数百万个点存储在地理索引、四叉树 (Oracle) 中。这样的查询几乎不需要时间。
有些人，比如我，更喜欢把数据库放在一边，自己建立四叉树。
操作搜索和插入很容易实现。更新/删除可能更复杂。（与实施工作相关的最便宜的是每分钟建立一个新的四叉树）
使用四叉树，您可以在一秒钟内执行数百或数千个最近的 100 个点。
从架构上讲，我会安排每个“点”在服务器的位置变化超过一定数量时将其与服务器联系起来。在服务器上，您可以完成计算移动点与其他每个点之间的距离的繁重工作，并为每个其他点更新其 100 个最近点列表（如果需要）。然后，您可以在更改发生时将更改推送到最接近的 100 个列表（如果您使用 App Engine，这很简单，支持 Android 推送）。
这将涉及的工作量降至最低：
您可以使用一些算法来使这个超级高效，并且这个问题也有一种 fork/join 的感觉，让您可以在问题上投入大量精力。
您必须将地球划分为多个区域，然后使用内点算法来确定手机所在的区域。每个可能的区域子集将唯一地确定 100 个最近的节点，以达到公平的近似值。您可以通过逐个检查候选节点的距离来获得一组精确的 100 个节点，候选节点（再次）由区域的子集确定。
代替 r-tree 或四叉树，即空间索引，您还可以使用四键和怪物曲线。这条曲线减小了尺寸并完全填满了空间。你可以从 phpclasses.org 下载我的 php 类希尔伯特曲线。您可以使用简单的 varchar 列作为四键并从左到右搜索级别。一个很好的解释来自 Microsoft Bing maps quadkey 网站。