互聯網 - 大數據

文章版權由作者李曉暉和博客園共有，若轉載請于明顯處標明出處：http://www.cnblogs.com/naaoveGIS/。

1.背景

1.1普通地理編碼流程

將采集的POI入庫后，數據庫里保存有該POI的位置描述、X、Y等信息。當需要進行逆編碼查詢時，前端傳入坐標的X、Y值，后臺構建查詢范圍查詢，并且對查詢出來的值進行距離排序。

1.2普通地理編碼的幾點劣勢

a.前端查詢url中的X、Y值為真實值，可能會暴露相關真實信息。

b.前端查詢的url因為X、Y值的長度而變得比較長。

c.后臺中，需要同時對X列、Y列做查詢判斷。

d.因為傳入的X、Y值總在變化，數據庫中的查詢很難進行緩存優化。

e.數據庫中保存的是真實X、Y數據，增加了存儲空間。

2 GeoHash算法簡介

2.1算法背景

Geohash的初衷是如何用盡量短的URL來標志地圖上的某個位置，而地圖上的位置一般是用經緯度來表示，問題就轉化為如何把經緯度轉化為一個盡量短的URL。

2.2GeoHash算法的描述

具體來說GeoHash算法的主要思想是對某一數字通過二分法進行無限逼近。這里以經緯度區間（經度（-180,180），緯度（-90,90））為例子來進行講解。

2.2.1 哈夫曼編碼

假設緯度值為48，精確到1度即可，則其編碼流程如下所示：

以左向為0，右向為1，最后48精確到1度的編碼為：11000010。

對經度同樣可以做該編碼逼近。

2.2.2編碼融合

對經緯度分別做了編碼后，需要將兩個編碼進行融合。融合規則為：將經度和緯度的編碼合并，奇數位是緯度，偶數位是經度。

比如：緯度39.92324精確到0.001后的編碼為1011 1000 1100 0111 1001。經度116.3906精確到0.001后的編碼為1101 0010 1100 0100 0100。兩者融合后的編碼為：11100 11101 00100 01111 00000 01101 01011 00001。

2.2.3 編碼字符串化

這里使用Base32算法對編碼進行字符串 化，Base32的規則如下：

我們將39.92324, 116.3906（11100 11101 00100 01111 00000 01101 01011 00001）進行Base32的字符串化后獲得字符串：wx4g0ec1。

3.基于GeoHash算法的擴展

3.1互聯網GeoHash算法的局限

互聯網GeoHash算法主要針對的是經緯度系統，所以其算法中的編碼范圍、編碼精確度都相對固定。

范圍為[-90,90],[-180,180]。

在緯度相等的情況下：

經度每隔0.00001度，距離相差約1米；

每隔0.0001度，距離相差約10米；

每隔0.001度，距離相差約100米；

每隔0.01度，距離相差約1000米；

每隔0.1度，距離相差約10000米。

在經度相等的情況下：

緯度每隔0.00001度，距離相差約1.1米；

每隔0.0001度，距離相差約11米；

每隔0.001度，距離相差約111米；

每隔0.01度，距離相差約1113米；

每隔0.1度，距離相差約11132米。

Geohash，如果geohash的位數是6位數的時候，大概為附近1千米。

但是假如需要編碼的坐標為平面坐標時，以上算法必須進行相關修改才能使用。

3.2GeoHash算法擴展

3.2.1 根據所需精確度獲取編碼長度

這里以平面坐標系為例子。平面坐標的單位是M，如果想要編碼的精確度精確到1M，則需要算出此時需要保留的編碼長度應該是多少。具體算法與哈夫曼編碼的思路基本相同，以下是代碼截取：

這里，需要知道編碼范圍、編碼精確位數。因為5位數的編碼等于一個Base32字符串，所以最后返回的值除以5。

當然，這里是經緯度坐標系也可以，只要規定好范圍以及編碼精確位數即可。

3.2.2 編碼算法優化

編碼時，編碼范圍不再是固定的經緯度范圍，而是根據傳遞進來的范圍值來進行編碼。具體代碼如下：

4.性能測試

4.1數據準備

這里我準備了13萬條數據（測試數據中大量重復數據）：

數據為平面坐標系數據，對所有數據已經進行了GeoHash編碼，為了方便測試，這里同樣存入了X、Y坐標。

4.2 普通編碼查詢 VS GeoHash編碼查詢

測試坐標點為：505214.06,305104.09。對其進行精確到100M的GeoHash編碼，編碼值為：kx5。

4.2.1范圍查詢命中率

4.2.1.1普通查詢命中率

查詢中為了去掉重復項，所以稍顯繁瑣。

查詢范圍為（CoordinateX < 505314.06 and CoordinateX > 505114.06 and CoordinateY < 305204.09 and CoordinateY >305004.09）具體如下，共查詢到：12項。

4.2.1.2 GeoHash查詢命中率

因為編碼已經精確到100M了，所以直接等于該編碼即可，查詢得到的結果為6項。

4.2.1.3 對比分析

對比兩種查詢，很明顯GeoHash編碼查詢法查詢到的數據要少一些。仔細分析可見：在傳統查詢中，距離在50M以內的前6項，均出現在了GeoHash查詢中。但是其他6項則沒有。

我們可以推斷為，雖然編碼精度設置的為100M，但是最后一位的編碼應該具體是精確到了100/2=50M 的范圍。

所以，我們可以推斷：GeoHash是能大致查詢出要求范圍的數據的，精確度比較高，但是查詢所得數據量比真實的范圍查詢要少。

4.2.2 查詢效率

4.2.2.1普通查詢

清除查詢緩存后，進行范圍查詢，需要0.281S。

在X、Y上分別建立索引后，需要0.172S。

4.2.2.2 GeoHash查詢

不建立索引，需要耗時0.499S。

建立索引后，耗時0.156S。

第二次命中時，耗時：0.031S。

4.2.2.3查詢性能對比分析

4.2.2.3.1查詢時間

不考慮網絡環境、查詢時電腦本身CPU等性能偶然影響，單純測試結果如下：

可見GeoHash因為是字符串查詢，其本身是比較耗時的。但是當做了索引后，其查詢速度是快于普通查詢的，而且其二次命中時查詢速度比普通查詢二次命中會更快。其原因比較簡單：單列索引、單列命中顯然是高于多列的。

4.2.3.2 資源消耗分析

普通查詢的資源消耗信息：

GeoHash查詢的資源消耗信息：

其中：

cardinality是指計劃中這一步所處理的行數。

cost指cbo中這一步所耗費的資源，這個值是相對值，和cpu_cost、io_cost是有關系的。

cost是由其他幾個因素共同決定的，這里暫時不進行深入的研究。一般情況下，在一張表只有一條記錄的情況下，cpu_cost會有個初始值(常見的是2萬多或3萬多)，隨著記錄的增加，cpu_cost也成比例的增加。對于io_cost來說，如果訪問的記錄在一個db_block中，值是不變的。

bytes指cbo中這一步所處理所有記錄的字節數，是估算出來的一組值。

對比性能分析表可見：

GeoHash表中的cardinality和bytes是明顯低于普通查詢的，究其原因也還是因為其只需查詢一列即可。

5.總結

GeoHash算法的幾個特點：

a.GeoHash編碼后，獲得的位置信息為范圍信息，而非真實的坐標精確值。

b.GeoHash編碼后，將X、Y坐標融合成一個值，數據庫存在中既可以減少存儲空間，也便于優化查詢。尤其是編碼后，一定范圍內的點均是同樣編碼，興趣點查詢的二次命中率會大大提高，進一步加快查詢速度。

c.GeoHash的編碼可以容易的表示出范圍包含關系，這樣非常便于進行范圍查詢。

d.查詢時前端URL長度變短。

6.三個問題

6.1如何查詢最近點

GeoHash查詢出來的僅僅是某個范圍內的數據，需要對返回的數據在進行距離運算，排序后最近的便是。其優化效率主要體現在范圍查詢上。

6.2查詢效率能優化多少？

測試在1W條數據以下時不明顯。

10W條附近時，開始有0.1S間的小差距。

類推，當數據量越大時，效果越明顯。

6.3兩個點離的越近，geohash的結果相同的位數越多，對么？

這一點是有些用戶對geohash的誤解，雖然geo確實盡可能的將位置相近的點hash到了一起，可是這并不是嚴格意義上的(實際上也并不可能，因為畢竟多一維坐標)，例如在方格4的左下部分的點和大方格1的右下部分的點離的很近，可是它們的geohash值一定是相差的相當遠，因為頭一次的分塊就相差太大了，很多時候我 們對geohash的值進行簡單的排序比較，結果貌似真的能夠找出相近的點，并且似乎還是按照距離的遠近排列的，可是實際上會有一些點被漏掉了。
上述這個問題，可以通過搜索一個格子，周圍八個格子的數據，統一獲取后再進行過濾。這樣就在編碼層次解決了這個問題。
    既然不能做到將相近的點hash值也相近，那么geohash的意義何在呢？
    個人覺覺得geohash還是相當有用的一個算法，畢竟這個算法通過無窮的細分，能確保將每一個小塊的geohash值確保在一定的范圍之內，這樣就為靈活的周邊查找和范圍查找提供了可能。

7.最后提一個有趣的問題——倫敦到紐約的距離怎么算

這個問題是前幾天一個讀博士的朋友問的我，思考這個問題挺有趣的。其中會涉及到長距離和短距離問題，推薦一篇類似博客：我們看到的地圖一直都錯得離譜（http://blog.sina.com.cn/s/blog_517eed9f0102w4rm.html）；

                                                                           -----歡迎轉載，但保留版權，請于明顯處標明出處：http://www.cnblogs.com/naaoveGIS/

                                                                           如果您覺得本文確實幫助了您，可以微信掃一掃，進行小額的打賞和鼓勵，謝謝 ^_^