隨著移動互聯網的興起，越來越多的App中加入了LBS的元素。而在各種LBS應用中，查找附近的地點是一種最基本也是最常見的形式。前段時間項目中加入了一個新的特性，需要根據用戶所在的位置，查找附近的用戶和用戶發表的廣播。本文將對此項目中使用的一些關鍵技術和遇到的問題做個簡單的介紹。

在進行具體的技術介紹之前，需要先從產品層面做一些基本的條件設定。首先，地理位置信息是有時效性的，用戶A一個月前來過某個地點，一個月后再向出現在同一個地點的其他用戶推薦A就沒有太大的意義了。所以我們需要根據實際情況對數據進行定期清理，例如只保存最近一周或者最近15天內的數據，這樣不僅能夠給用戶提供最“有效”的數據，而且能夠控制總的數據量，減少server端的壓力。其次，LBS應用對于精度的要求沒有那么高，通過移動設備進行定位本身就有一定的誤差，因此server端在進行算法設計和實現時也并不一定要求100%的準確（實際上也很難做到），只要能把誤差控制在一定的范圍內即可。

關于查找附近地點的算法和實現，網上有不少相關的文章，下面重點介紹一下在本項目開發過程中嘗試和研究過的各種方案，以及最終選擇的實現方式。

1. geohash

geohash是一種地址編碼方式，它可以把用經緯度表示的地理位置信息編碼成一個字符串，例如銀科大廈所在位置的經緯度為（116.306785，39.981998），對應的geohash編碼為wx4eqws0。Geohash的編碼算法很簡單，我們就以（116.306785，39.981998）為例進行簡單的介紹。首先將緯度范圍（-90,90）平分為（-90,0）和（0,90）兩個區間，如果目標緯度位于前一個區間，則編碼為0，否則編碼為1。由于39.981998屬于（0,90），所以編碼為1。然后再將（0,90）分為（0,45）和（45,90）兩個區間，而39.981998位于（0,45），所以編碼為0。以此類推，直到精度符合要求為止，得到緯度編碼為1011 1000 1101 1101 0000。用同樣的方法對經度進行編碼（經度的取值范圍為（-180，180）），得到116.306785的編碼為1101 0010 1011 0101 0000。然后將經度和緯度的編碼合并，奇數位為緯度，偶數位為經度，得到編碼11100 11101 00010 01101 10110 11100 11000 00000。***用0-9、b-z（去掉a，i，l和o）進行base32編碼，得到最終的geohash編碼wx4eqws0。

從以上的計算過程可以看出，geohash表示的是一個格子（矩形區域）而不是一個點，geohash長度越長，這個格子就越小；具有相同前綴的geohash編碼會落在同一個格子內，相同的前綴越長，格子越小，在地理位置上就越接近，利用這一特點，可以實現我們想要的搜索附近的地點的功能。不過geohash編碼算法也有一些缺點，首先是位于格子邊界兩側的點雖然十分接近，但是編碼會完全不同。因此在實際的應用中，我們不僅要搜索當前格子，還要搜索當前格子周圍的8個格子。除此之外，如果我們想要搜索特定范圍內的地點，比如要查找周圍1Km內的人，geohash無法實現這種控制，只能在返回的結果集里再進行一次距離計算，過濾掉這個范圍之外的結果。

2. 基于球面距離公式的算法

查找附近地點算法的難點在于，數據庫中保存的是地點的坐標信息，搜索條件是地點坐標和給定坐標之間的距離，兩者之間無法直接建立聯系。如果我們能把搜索的條件轉換為坐標范圍的話，接下來的事情就比較簡單了。一般我們需要搜索一定范圍內的地點，這個范圍實際上是一個圓，我們可以把搜索的范圍擴大到這個圓的外接正方形，求出這個正方形對應的經緯度范圍，這樣就可以在數據庫中進行查找了。因為實際的搜索范圍有所擴大，所以可能需求對返回的結果進行一次過濾，去除掉不符合條件的結果。要進行上述的計算，我們要用到Haversine公式。Haversine公式的定義為：

haversine(d/R) = haversine(lat2-lat1) + cos(lat2)cos(lat1)haversine(lng2-lng1)

其中
haversine(a) = (1-cos(a))/2

d為兩點間的距離，R為地球半徑，取平均值6371km，lat1和lat2為兩點的緯度，lng1和lng2為兩點的經度。通過這個公式，我們可以根據任意兩點的經緯度計算出兩點間的球面距離。
利用Haversine公式，我們還可以反推出計算經緯度搜索范圍的計算。在Haversin公式中，令lat1=lat2，可以得到
delta(lng)=2arcsin(sin(d/2R)/cos(lat1))

令lng1=lng2，可以得到
delta(lat)=d/R

根據當前點的坐標和經緯度的范圍，就可以得出搜索范圍了。

這個算法的特點是簡單明了，搜索范圍可控，精度也可以接受。但是在實際使用中發現，即使在經度和緯度列上建立索引（使用MySQL），數據量大的時候效率會比較差，達不到性能上的要求。

3. 基于Sptial Indexing的方案

方案2中基于球面距離公式的算法本身沒有太大的問題，瓶頸在于數據庫的效率。這里要介紹的Spatial Indexing——空間索引，就是要解決這個問題。不同于我們常用的BTree索引，基于RTree的空間索引可以在二維空間上進行高效的查詢，非常適合類似查找附近的地點這樣的需求。主流的數據庫，包括MySQL，都在不同的程度上支持空間索引。MySQL中有一個類型Point，可以用來存儲每個位置對應的經緯度。在這一列上建立空間索引，按照方案2中得出的經緯度范圍劃定一個矩形，利用MySQL提供的空間擴展函數判斷某個點是否在這個矩形內，就可以實現查找附近地點的目的了。

以上介紹了在整個項目開發過程中進行的各種嘗試以及每種方案的優缺點，最終采用的方案是以上各個方案的一個綜合：在數據庫中建立空間索引，對于任意一個請求，根據經緯度（lng，lat）和查找范圍（d）以及Haversin公式計算出經緯度范圍（delta(lng)，delta(lat)），然后利用MySQL的空間擴展函數在數據庫中進行查找，得到的結果除了排序、過濾并返回以外還要保存在cache中，cache的key為經緯度（lng，lat）的geohash編碼。geohash編碼的長度是可以配置的，本項目中我們選擇了長度為7的geohash編碼，原因是7位geohash編碼表示的格子的大小大約在150m左右，也就是說150m范圍內的搜索可以返回相同的結果，這基本滿足我們對于精度的要求。