geohash算法

geohash算法

       geohash算法的原理是将區域進行4分，讓後将每一塊區域繼續進行四分，直到符合精度要求停止，這樣得到一個二進制的資料，然後将這二進制的資料進行base32轉換得到一個字元串。如下圖：

      首先将一整塊區域将其分成4份，然後給其編号00、01、10和11。然後取出一塊，繼續分成四份，在上次編号的基礎上後面按同樣的規則增加00、01、10和11編号。每塊繼續分，直到符合誤差要求，最終得到一個編号，該編号為一個二進制數。例如得到：0110101100011011001110010101。将該二進制數經過base32轉換成一個字元串，轉換時每5b對應一個字母。由上面的劃分算法可知道，二進制的字首代表更大的區域。經base32轉換後，其前面的字母就同樣代表着更大的區域（base32轉換的本質是替換）。是以經過geohash算法，可以通過字首判斷是否在同一個區域内。通過區域算法，可以判斷兩點是否在相差在一定的範圍内，但由于在邊緣的兩點，其編碼會有很大差異，是以在判斷周圍點時需要周遊周圍8個區域的點。

geohash進行base32轉換的優缺點

       将一個二進制數進行base32轉換後，便于閱讀與了解，可以用字元串相關處理的接口，友善處理。但進行base32轉換後一個字母代表2.5次劃分，在區間比較時縮放速度比較快，在一定程度上影響查找算法。

      若不為閱讀與了解，我們可以直接用二進制資料進行處理。

geohash編碼排序

       geohash編碼得到的資料是二進制資料，可以進行排序。我們将geohash編碼的點建立搜尋二叉樹，在查找時通過區域搜尋，能夠快速從搜尋二叉樹中找到指定字首的點。

改進Geohash的測試可以參考：快速全球索引