如何在mysql中最好地实现最近邻搜索？

Question

所以，简而言之，

1. 经纬度的数据类型应该是什么？
2. 例如，我应该调用什么 SQL 命令来获取前 100 家最近的餐馆？

细节：

我有 100k biz 记录，每个记录都带有纬度和经度。我看到 MySQL 实际上支持一种名为 point 的数据类型。我应该使用它吗？

MySQL 是否支持 KDTree 存储系统http://en.wikipedia.org/wiki/File:KDTree-animation.gif

最好使用点数据类型而不是常规的浮点数据类型来存储纬度和经度吗？

最终，我想找到诸如最接近点 105,6 的前 100 家餐厅之类的东西，例如，我的数据库包含很多 biz 和点。显然，为每个记录和每个点一个一个地计算距离将是 O(n)，因此很糟糕。

请注意，我知道如何像 Yelp 这样的应用程序有效地从数据库中检索距离信息中描述了一个更简单的解决方案，并且我也将在开始时实施该解决方案。这是一个很好的答案。

但是，我认为有一种最佳答案应该胜过它，对吗？事实上，根据纬度和经度存储位置并找到离它最近的东西是一个非常常见的问题，我希望 mysql 有一个特殊的设计模式。它有吗？

我在哪里可以了解更多信息？谢谢。

Answer 1

就设计模式而言，Yelp 问题是非常标准的问题。

对于更复杂的答案，您可能需要地理空间距离。这是有关该主题的引人入胜的powerpoint（这里也是该主题的pdf版本）。然而，所涉及的数学是相当丑陋的。

从他们的幻灯片：

set @orig_lat=122.4058; set @orig_lon=37.7907;
set @dist=10;

SELECT *, 3956 * 2 * ASIN(SQRT(
POWER(SIN((@orig_lat - abs(dest.lat)) * pi()/180 / 2), 2) +  COS(@orig_lat * pi()/180 ) * COS(abs(dest.lat) * pi()/180) *  POWER(SIN((@orig_lon – dest.lon) * pi()/180 / 2), 2) )) as  distance
FROM hotels dest 
having distance < @dist
ORDER BY distance limit 10

Stack Overflow上有一个关于地理空间距离的更长、更深入的答案。

但是您仍然希望通过纬度和经度来限制结果。

最终，我会避免使用 POINT 数据类型并使用纬度/经度。目前无法确定两个 POINT 之间的距离，因此无论如何您都必须为该计算存储纬度/经度。

最后一个链接：您可能还想查看有关使用空间索引加速查询的SO 线程。