附近的人怎麼計算出來的?

01-15

比如: 餓了么搜索附近的餐廳，qq，微信附件的人，後端怎麼搜索出來的呢
資料庫裡面有1w條餐廳的坐標記錄，當用戶打開附件的餐廳的時候，搜集到用戶的坐標，比如針對某一個店的話，兩點的坐標，計算球面距離是好計算的，問題是，有1w條店，怎麼找出來附件500米，1000米，2000米....

實現方案有很多：

1. mysql的空間資料庫:

Mysql gis 空間資料庫功能詳解學習；

2. solr空間索引天然支持按經緯度索引，按位置查詢，按距離排序；

http://tech.meituan.com/solr-spatial-search.html

3. redis新版本也支持geohash了；

Redis GEO 特性簡介

1、把經緯度換成整數。

2、不算圓型算方型，避開乘方根號運算，直接 between 經度 and between 緯度。

3、確定了這個方內的人後，再進行乘方(但不開根號)排序就行。

一般都採用Geohash演算法，用一個字元串表示二維坐標，並且兩個點越接近，這兩個Geohash的字元串前綴相同的位數就越多（這句話可能不太嚴謹），這樣查詢的效率就會高很多。

Geohash

大家的坐標保存起來，然後把你的坐標與大家的坐標求距離就行了。

一般都是Geohash演算法，不過這個演算法的問題是可能很近的但是分在不同格子里就撈不到了，會選取周圍8個格子來計算，另外就是這個演算法不好按照範圍搜，比如附近xx米。

第二種演算法是附近xx米是一個圓，計算出圓的外接正方形的經緯度範圍，就是當前位置為中心邊長是xx*2的一個正方形的經緯度範圍，然後在資料庫里通過大於小於條件來撈落入正方形內的POI(店鋪)，然後，要嚴謹的話把四個角邊緣的數據剔除（通過計算距離就可以，這時候數據量很少，不需要全表掃描計算，就很快了），精度要求不高的話，不需要剔除直接就能用了，這種做法只要把資料庫中經度和緯度兩個欄位做索引，應付一般數據量足夠了，做法也簡單直白，題主只有1W條數據，這種方法妥妥的。

第三種就是利用資料庫的空間索引來做，貌似MySQL本身就支持的，用R Tree實現的，效率更高。

mysql和mongodb都有空間索引，存下坐標就可以查了

GeoHash演算法，看我的博客http://miketech.it/geohash-algorithm/

Mysql5.5+

11.5.2 The OpenGIS Geometry Model

The data types and functions are available for MyISAM, InnoDB, NDB, and ARCHIVE tables. For indexing spatial columns, MyISAM and InnoDB support both SPATIAL and non-SPATIAL indexes. The other storage engines support non-SPATIAL indexes, as described in Section 14.1.14, 「CREATE INDEX Syntax」.

畢

一般是利用 GeoHash，介紹可見： GeoHash核心原理解析 - zhanlijun - 博客園

Redis 的 Geo 功能，MongoDB的2d索引都是利用geohash實現的。

GeoHash 的缺點在於：突變性（填充曲線決定的）、不平衡性（Area Ratio 可達5.2）。

MongoDB的 2dSphere索引 支持更多的geo功能，其實現是利用 Google S2庫，該演算法用於Google Map、Mongo、Foursquare等。

它的優秀特性來源於：希爾伯特填充曲線、獨特的映射方式、緊湊的Cell表示。

詳細可見：Google S2，球面幾何，希爾伯特曲線

geohash，可以先把經緯度轉成geohash，然後需要查詢附近的時候把經緯度轉成geohash來查詢，以上的mysql就能搞定，

如果需要排序或者資料庫大的話可以用solr和mongodb

geohash | rtree

查找 1000 米以內的人，資料庫設計和查詢如何實現這個功能？ - 資料庫設計

用mongodb，自帶這類演算法

我記得有個kdtree，不知道可以不。。你試試

mysql和mongodb都有空間索引，存下坐標就可以查了,如果是mongodb更簡單了，幾行代碼就可以算位置了

實現的方法有很多種，我舉我們的方法：

步驟一：按照電子圍欄畫正方形，剔除正方形外的結果

步驟二：按照電子圍欄畫圓

步驟三：步驟二在步驟一的結果集中查詢

步驟四：考慮地球表面的弧度，將曲線距離轉化為直線距離

涉及到的知識：正弦、餘弦、勾股等一系列數學知識

如果比較精確，那就是步驟一和步驟二

如果不精確，那就是步驟一

目前我們採用的是步驟一+步驟二

可以看下r tree的實現不過微信附近的人用了更簡單的方案

redis的矢量地理

快使用開源工具，橫橫哈嘿，快打開源代碼，嘿嘿哈橫。