geohash的原理實際是個四叉樹/網格處理

看了下geohash的過程，原以為是一個新的索引過程，發現本質上是一個QuadTree。

不同點是，geohash僅保留了每一個四叉樹節點的KEY，而不需要計算四叉樹本身的索引。換句話說，如果我們建立一棵四叉樹，建立過程如果為每一個節點都生産KEY，{00,01,10,11}表示4個節點。那麼也就生産了一個geohash的KEY。

如同四叉樹一樣，

（0）每一個四叉樹節點都是一個區域（網格），是以，geohash也是一個區域，四叉樹的深度，對應geohash的精度。

（1）四叉樹中通路目前節點的子節點是容易的，是以geohash可以通過KEY找到目前區域的子區域。

（2）四叉樹通路一個節點的父節點是容易的，是以geohash也可以通過KEY的特點通路包含目前節點的區域的父節點區域。

（3）四叉樹查詢目前同一個父節點的另外3個兄弟節點是容易的，geohash可以找到其他3個相鄰的區域。

（4）四叉樹尋訪<X,Y>中的周圍一定區域的所有Items，是不容易的。同理，geohash要查找<X,Y>一個Items也是不容易的。

      因為在（2）中，隻能容易通路目前節點的兄弟節點，而不是所有周邊節點。

      四叉樹一般是通過結合前面3條來逐層搜尋。

geohash的優勢：

個人覺得，對于不習慣建立四叉樹索引、或者不手動寫空間索引的人有優勢外，如使用mysql或者其他資料庫存儲友善等。

順便提下，大規模經緯度資料中的統計熱點問題。

(0)如果是分布式，就用網格索引的KEY（可以看成是一個滿四叉樹的geohash的KEY），因為可以保證每台機器上不同資料，但都是同樣的KEY結構。

(1)如果是單個檔案，檔案不太大就用四叉樹索引；檔案較大，用geohash；四叉樹因為存儲了大量的節點資訊。如果還是太大，結合（0）方式，建構一個N*N叉樹，每N*N個網格作為一組存放在一個檔案中。

N一般選取，2,4,8

• 結果圖

先留個坑，過幾天填上

• 結論

無論使用什麼樣的hash方式，隻要對二維或者多元資料進行hash算法，都不可避免的遇到鄰接邊問題。解決這個問題的辦法，要麼吧周邊鄰近的塊搜尋下，要麼不用hash，而改用樹。QuadTree是存儲平面坐标點比較有效的辦法。