引子

　　機機是個好動又好學(xué)的孩子，平日里就喜歡拿著手機地圖點點按按來查詢一些好玩的東西。某一天機機到北海公園游玩，肚肚餓了，于是乎打開手機地圖，搜索北海公園附近的餐館，并選了其中一家用餐。

　　飯飽之后機機開始反思了，地圖后臺如何根據(jù)自己所在位置查詢來查詢附近餐館的呢？苦思冥想了半天，機機想出了個方法：計算所在位置P與北京所有餐館的距離，然后返回距離《=1000米的餐館。小得意了一會兒，機機發(fā)現(xiàn)北京的餐館何其多啊，這樣計算不得了，于是想了，既然知道經(jīng)緯度了，那它應(yīng)該知道自己在西城區(qū)，那應(yīng)該計算所在位置P與西城區(qū)所有餐館的距離啊，機機運用了遞歸的思想，想到了西城區(qū)也很多餐館啊，應(yīng)該計算所在位置P與所在街道所有餐館的距離，這樣計算量又小了，效率也提升了。

　　機機的計算思想很樸素，就是通過過濾的方法來減小參與計算的餐館數(shù)目，從某種角度上講，機機在使用索引技術(shù)。

　　一提到索引，大家腦子里馬上浮現(xiàn)出B樹索引，因為大量的數(shù)據(jù)庫（如MySQL、oracle、PostgreSQL等）都在使用B樹。B樹索引本質(zhì)上是對索引字段進(jìn)行排序，然后通過類似二分查找的方法進(jìn)行快速查找，即它要求索引的字段是可排序的，一般而言，可排序的是一維字段，比如時間、年齡、薪水等等。但是對于空間上的一個點（二維，包括經(jīng)度和緯度），如何排序呢？又如何索引呢？解決的方法很多，下文介紹一種方法來解決這一問題。

　　思想：如果能通過某種方法將二維的點數(shù)據(jù)轉(zhuǎn)換成一維的數(shù)據(jù)，那樣不就可以繼續(xù)使用B樹索引了嘛。那這種方法真的存在嘛，答案是肯定的。目前很火的GeoHash算法就是運用了上述思想，下面我們就開始GeoHash之旅吧。

　　一、感性認(rèn)識GeoHash

　　1）GeoHash將二維的經(jīng)緯度轉(zhuǎn)換成字符串，比如下圖展示了北京9個區(qū)域的GeoHash字符串，分別是WX4ER，WX4G2、WX4G3等等，每一個字符串代表了某一矩形區(qū)域。也就是說，這個矩形區(qū)域內(nèi)所有的點（經(jīng)緯度坐標(biāo)）都共享相同的GeoHash字符串，這樣既可以保護(hù)隱私（只表示大概區(qū)域位置而不是具體的點），又比較容易做緩存，比如左上角這個區(qū)域內(nèi)的用戶不斷發(fā)送位置信息請求餐館數(shù)據(jù)，由于這些用戶的GeoHash字符串都是WX4ER，所以可以把WX4ER當(dāng)作key，把該區(qū)域的餐館信息當(dāng)作value來進(jìn)行緩存，而如果不使用GeoHash的話，由于區(qū)域內(nèi)的用戶傳來的經(jīng)緯度是各不相同的，很難做緩存。

　　2）字符串越長，表示的范圍越精確。如圖所示，5位的編碼能表示10平方千米范圍的矩形區(qū)域，而6位編碼能表示更精細(xì)的區(qū)域（約0.34平方千米）

　　3）字符串相似的表示距離相近（特殊情況后文闡述），這樣可以利用字符串的前綴匹配來查詢附近的POI信息。如下兩個圖所示，一個在城區(qū)，一個在郊區(qū)，城區(qū)的GeoHash字符串之間比較相似，郊區(qū)的字符串之間也比較相似，而城區(qū)和郊區(qū)的GeoHash字符串相似程度要低些。

　　                     城區(qū)                           郊區(qū)

　　通過上面的介紹我們知道了GeoHash就是一種將經(jīng)緯度轉(zhuǎn)換成字符串的方法，并且使得在大部分情況下，字符串前綴匹配越多的距離越近，回到我們的案例，根據(jù)所在位置查詢來查詢附近餐館時，只需要將所在位置經(jīng)緯度轉(zhuǎn)換成GeoHash字符串，并與各個餐館的GeoHash字符串進(jìn)行前綴匹配，匹配越多的距離越近。

　　二、GeoHash算法的步驟

　　下面以北海公園為例介紹GeoHash算法的計算步驟

　　2.1. 根據(jù)經(jīng)緯度計算GeoHash二進(jìn)制編碼

　　地球緯度區(qū)間是［-90，90］， 北海公園的緯度是39.928167，可以通過下面算法對緯度39.928167進(jìn)行逼近編碼：

　　1）區(qū)間［-90，90］進(jìn)行二分為［-90，0），［0，90］，稱為左右區(qū)間，可以確定39.928167屬于右區(qū)間［0，90］，給標(biāo)記為1；

　　2）接著將區(qū)間［0，90］進(jìn)行二分為 ［0，45），［45，90］，可以確定39.928167屬于左區(qū)間 ［0，45），給標(biāo)記為0；

　　3）遞歸上述過程39.928167總是屬于某個區(qū)間［a，b］。隨著每次迭代區(qū)間［a，b］總在縮小，并越來越逼近39.928167；

　　4）如果給定的緯度x（39.928167）屬于左區(qū)間，則記錄0，如果屬于右區(qū)間則記錄1，這樣隨著算法的進(jìn)行會產(chǎn)生一個序列1011100，序列的長度跟給定的區(qū)間劃分次數(shù)有關(guān)。

　　根據(jù)緯度算編碼　

　　同理，地球經(jīng)度區(qū)間是［-180，180］，可以對經(jīng)度116.389550進(jìn)行編碼。

　　根據(jù)經(jīng)度算編碼

 　　2.2. 組碼

　　通過上述計算，緯度產(chǎn)生的編碼為10111 00011，經(jīng)度產(chǎn)生的編碼為11010  01011。偶數(shù)位放經(jīng)度，奇數(shù)位放緯度，把2串編碼組合生成新串：11100 11101 00100 01111。

　　最后使用用0-9、b-z（去掉a， i， l， o）這32個字母進(jìn)行base32編碼，首先將11100 11101 00100  01111轉(zhuǎn)成十進(jìn)制，對應(yīng)著28、29、4、15，十進(jìn)制對應(yīng)的編碼就是wx4g。同理，將編碼轉(zhuǎn)換成經(jīng)緯度的解碼算法與之相反，具體不再贅述。

　　三、GeoHash Base32編碼長度與精度

　　可以看出，當(dāng)geohash  base32編碼長度為8時，精度在19米左右，而當(dāng)編碼長度為9時，精度在2米左右，編碼長度需要根據(jù)數(shù)據(jù)情況進(jìn)行選擇。

表摘自維基百科

　　三、GeoHash算法

　　上文講了GeoHash的計算步驟，僅僅說明是什么而沒有說明為什么？為什么分別給經(jīng)度和維度編碼？為什么需要將經(jīng)緯度兩串編碼交叉組合成一串編碼？本節(jié)試圖回答這一問題。

　　如圖所示，我們將二進(jìn)制編碼的結(jié)果填寫到空間中，當(dāng)將空間劃分為四塊時候，編碼的順序分別是左下角00，左上角01，右下腳10，右上角11，也就是類似于Z的曲線，當(dāng)我們遞歸的將各個塊分解成更小的子塊時，編碼的順序是自相似的（分形），每一個子快也形成Z曲線，這種類型的曲線被稱為Peano空間填充曲線。

　　這種類型的空間填充曲線的優(yōu)點是將二維空間轉(zhuǎn)換成一維曲線（事實上是分形維），對大部分而言，編碼相似的距離也相近，  但Peano空間填充曲線最大的缺點就是突變性，有些編碼相鄰但距離卻相差很遠(yuǎn)，比如0111與1000，編碼是相鄰的，但距離相差很大。

　　除Peano空間填充曲線外，還有很多空間填充曲線，如圖所示，其中效果公認(rèn)較好是Hilbert空間填充曲線，相較于Peano曲線而言，Hilbert曲線沒有較大的突變。為什么GeoHash不選擇Hilbert空間填充曲線呢？可能是Peano曲線思路以及計算上比較簡單吧，事實上，Peano曲線就是一種四叉樹線性編碼方式。

　　四、使用注意點

　　1）由于GeoHash是將區(qū)域劃分為一個個規(guī)則矩形，并對每個矩形進(jìn)行編碼，這樣在查詢附近POI信息時會導(dǎo)致以下問題，比如紅色的點是我們的位置，綠色的兩個點分別是附近的兩個餐館，但是在查詢的時候會發(fā)現(xiàn)距離較遠(yuǎn)餐館的GeoHash編碼與我們一樣（因為在同一個GeoHash區(qū)域塊上），而較近餐館的GeoHash編碼與我們不一致。這個問題往往產(chǎn)生在邊界處。

　　解決的思路很簡單，我們查詢時，除了使用定位點的GeoHash編碼進(jìn)行匹配外，還使用周圍8個區(qū)域的GeoHash編碼，這樣可以避免這個問題。

　　2）我們已經(jīng)知道現(xiàn)有的GeoHash算法使用的是Peano空間填充曲線，這種曲線會產(chǎn)生突變，造成了編碼雖然相似但距離可能相差很大的問題，因此在查詢附近餐館時候，首先篩選GeoHash編碼相似的POI點，然后進(jìn)行實際距離計算。