?隨著移動互聯(lián)網(wǎng)的發(fā)展，很多基于地理位置信息的服務(wù)也越來越流行。比如說我們平常經(jīng)常使用的查找附近的人，或者是附近的餐館，共享單車等等。

那么，大家有沒有想過，這個查找功能是如何實現(xiàn)的嗎？作為受過高等教育的人，大家肯定立即就想到了可以通過經(jīng)緯度進行計算。具體算法類似于這樣：

地球近似于一個球體，地球赤道周長約40075.04公里，半徑約為6371公里，因此，可以很容易地用立體幾何的方法求出其距離，例如說最常見的大圓距離（Great-Circle Distance）。

公式如下：

其中， R為地球半徑，Aj、Aw分別表示A點的經(jīng)度、緯度；Bj、Bw分別表示B點的經(jīng)度、緯度。這樣，通過簡單的立體幾何方法就可以很容易地求出其距離。

如果有人對于地理信息學(xué)比較了解的話，還會知道半正矢公式（Haversine公式），因為大圓距離公式用到了大量的余弦函數(shù)，因此在兩點距離過短的時候，會導(dǎo)致比較大的舍入誤差。而半正矢公式則因為采用了正弦函數(shù)的方法，因此即使距離過小，也可以保留足夠的有效數(shù)字。半正矢公式的形式如下所示：

其中

這里面的R為地球半徑，可取平均值 6371km；φ1, φ2 表示兩點的緯度；Δλ 表示兩點經(jīng)度的差值。

有了這些算法，那么理論上來查找附近的人就可以很方便地實現(xiàn)了。但是為什么要說從理論上講呢？因為在工程實踐中，這樣查找的計算量太大了。對于幾個經(jīng)緯度的數(shù)據(jù)而言還可以，但是對于大規(guī)模數(shù)據(jù)查詢而言，沒有實際可操作性。就比如想在一個一百萬條數(shù)據(jù)的數(shù)據(jù)庫里查找附近5公里之內(nèi)的餐館有哪些，那么要對一百萬條數(shù)據(jù)做各種三角函數(shù)操作，這顯然是不現(xiàn)實的事情，更別說在互聯(lián)網(wǎng)上應(yīng)用的數(shù)據(jù)體量遠大于百萬條。而且這樣的數(shù)據(jù)也很難對其查詢效率進行優(yōu)化。

那么，要怎么解決這個問題呢？這就是我們今天要介紹的神奇算法，Geohash算法了。通過Geohash算法，我們可以把兩個坐標(biāo)的距離計算簡化為兩個字符串的比較，從而可以最大限度的應(yīng)用速度更快的字符串相關(guān)函數(shù)，并且對其進行排序或索引。

下面我們就來看看Geohash算法具體是怎么做到這一點的。

Geohash的本質(zhì)就是將用到的整個地圖區(qū)域進行矩形分割，然后在各個矩形之中再次進行矩形分割，而每一次分割中所在的區(qū)域用一個字符代表，這樣一次次分割之后，就可以最大可能的逼近實際坐標(biāo)所在地。而這個坐標(biāo)也就可以用一串字符來代替了。常用的Geohash算法中，每個字符用5個比特來標(biāo)識，這樣就會有32個不同的組合（0-31），于是我們就可以將這個地圖區(qū)域劃分為32個區(qū)域。這樣劃分之后，第一個字母劃分的區(qū)域就如下圖所示：

然后我們再對各個區(qū)域繼續(xù)進行劃分，就會得到類似于wx4eqzrx，這樣的一個字符串了。

而這時，我們就可以方便地使用類似于：

Select * from world where geohash like 'wx4eqw%';

這樣的sql語句查詢到附近想要查詢的東西了。是不是很方便呢？通過這種方式，我們就把復(fù)雜的三角函數(shù)計算，轉(zhuǎn)化成了計算化處理效率非常高的字符串操作了。

那么，想必大家一定要問了，坐標(biāo)轉(zhuǎn)化成的字符串是怎么生成的呢？其實也很簡單。

我們以緯度39.928167為例。

a. 首先我們以區(qū)間[-90,90]進行二分為[-90,0),[0,90]，稱為左右區(qū)間，可以確定39.928167屬于右區(qū)間[0,90]，標(biāo)記為1

b. 接著將區(qū)間[0,90]進行二分為 [0,45),[45,90]，可以確定39.928167屬于左區(qū)間 [0,45)，標(biāo)記為0

c. 遞歸上述過程39.928167總是屬于某個區(qū)間[a,b]。隨著每次迭代區(qū)間[a,b]總在縮小，并越來越逼近39.928167，劃分次數(shù)越多，距離就越精確，字符串也就會越長，如下圖所示：

這樣我們就得到了緯度的二進制表示，同樣我們也可以對經(jīng)度進行二進制表示。然后，我們把經(jīng)度放到偶數(shù)位，緯度放到奇數(shù)位，把兩個二進制串合并到一起，最后將得到的二進制串編碼每5位進行base32編碼，最終就得到了我們想要的，對于每個小方格進行表示的Geohash字符串序列。

但是這樣做了之后，很多人會發(fā)現(xiàn)一個問題，那就是每個Geohash字符串事實上都是代表一個小方格的，那么就會產(chǎn)生邊界跨越的問題。就像下圖中的紅點，和上面的綠點并不在一個方格里，因此如果我們光查詢紅點所在的格子的話，就會查詢不到明明離它很近的上面的綠點，反而可以查詢到更遠一點的下面的綠點。

那么怎么解決這個問題呢？其實也很簡單，就是在查詢的時候，把周圍的8個格子也考慮進來一起查詢就行了。那么具體是怎么做的呢？我們可以看到，周圍的8個格子，本質(zhì)上就是經(jīng)度緯度的格子二進制數(shù)與中間的格子差1，所以我們只需要對紅點的經(jīng)緯度二進制數(shù)，進行加減1的操作就可以獲取到附近格子的字符串了。而這樣做本質(zhì)上就是損失了一個格子的精度。而在經(jīng)緯度位數(shù)足夠的情況下，這個誤差是可以忽略不計的。通過計數(shù)我們可以得出：

在緯度相等的情況下，經(jīng)度每隔0.00001度，距離相差約1米；在經(jīng)度相等的情況下，緯度每隔0.00001度，距離相差約1.1米；而在geohash的位數(shù)是9位數(shù)的時候，大概為附近2米；8位的話，大約為附近19米。對于大部分人來講，可以說是一個可以接受的誤差了哦。?