1嚼锄、知識(shí)介紹（轉(zhuǎn)載）

源地址：http://www.cnblogs.com/LBSer
這里主要講的是：通過GeoHash核心原理來分析hbase rowkey設(shè)計(jì)
引子

機(jī)機(jī)是個(gè)好動(dòng)又好學(xué)的孩子，平日里就喜歡拿著手機(jī)地圖點(diǎn)點(diǎn)按按來查詢一些好玩的東西瞳浦。某一天機(jī)機(jī)到北海公園游玩喷舀，肚肚餓了砍濒，于是乎打開手機(jī)地圖，搜索北海公園附近的餐館硫麻，并選了其中一家用餐爸邢。

image

飯飽之后機(jī)機(jī)開始反思了，地圖后臺(tái)如何根據(jù)自己所在位置查詢來查詢附近餐館的呢拿愧？苦思冥想了半天杠河，機(jī)機(jī)想出了個(gè)方法：計(jì)算所在位置P與北京所有餐館的距離，然后返回距離<=1000米的餐館浇辜。小得意了一會(huì)兒券敌，機(jī)機(jī)發(fā)現(xiàn)北京的餐館何其多啊，這樣計(jì)算不得了柳洋，于是想了待诅，既然知道經(jīng)緯度了，那它應(yīng)該知道自己在西城區(qū)熊镣，那應(yīng)該計(jì)算所在位置P與西城區(qū)所有餐館的距離啊卑雁，機(jī)機(jī)運(yùn)用了遞歸的思想，想到了西城區(qū)也很多餐館啊绪囱，應(yīng)該計(jì)算所在位置P與所在街道所有餐館的距離序厉，這樣計(jì)算量又小了，效率也提升了毕箍。

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

一提到索引荷逞，大家腦子里馬上浮現(xiàn)出B樹索引媒咳，因?yàn)榇罅康臄?shù)據(jù)庫(kù)（如MySQL、oracle种远、PostgreSQL等）都在使用B樹涩澡。B樹索引本質(zhì)上是對(duì)索引字段進(jìn)行排序，然后通過類似二分查找的方法進(jìn)行快速查找坠敷，即它要求索引的字段是可排序的妙同，一般而言射富，可排序的是一維字段，比如時(shí)間粥帚、年齡胰耗、薪水等等。但是對(duì)于空間上的一個(gè)點(diǎn)（二維芒涡，包括經(jīng)度和緯度）柴灯，如何排序呢？又如何索引呢费尽？解決的方法很多赠群，下文介紹一種方法來解決這一問題。

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

一闷旧、感性認(rèn)識(shí)GeoHash

首先來點(diǎn)感性認(rèn)識(shí)长豁，http://openlocation.org/geohash/geohash-js/ 提供了在地圖上顯示geohash編碼的功能。

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

image

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

image

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

|

image

城區(qū)

|

image

郊區(qū)

|

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

二狈茉、GeoHash算法的步驟

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

image

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

地球緯度區(qū)間是[-90,90]夫椭， 北海公園的緯度是39.928167，可以通過下面算法對(duì)緯度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總是屬于某個(gè)區(qū)間[a,b]洞豁。隨著每次迭代區(qū)間[a,b]總在縮小，并越來越逼近39.928167荒给；

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

根據(jù)緯度算編碼

圖片.png

同理溪北，地球經(jīng)度區(qū)間是[-180,180]，可以對(duì)經(jīng)度116.389550進(jìn)行編碼。

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

圖片.png

2.2. 組碼

通過上述計(jì)算之拨，緯度產(chǎn)生的編碼為10111 00011茉继，經(jīng)度產(chǎn)生的編碼為11010 01011。奇數(shù)位放經(jīng)度蚀乔，偶數(shù)位放緯度（我轉(zhuǎn)載的原文描述是錯(cuò)誤的：偶數(shù)位放經(jīng)度烁竭，奇數(shù)位放緯度），把2串編碼組合生成新串：11100 11101 00100 01111吉挣。

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

image

三肠虽、GeoHash Base32編碼長(zhǎng)度與精度

下表摘自維基百科：http://en.wikipedia.org/wiki/Geohash

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

image

三慨代、GeoHash算法

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

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

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

image

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

image

四娃承、使用注意點(diǎn)

1）由于GeoHash是將區(qū)域劃分為一個(gè)個(gè)規(guī)則矩形奏夫，并對(duì)每個(gè)矩形進(jìn)行編碼，這樣在查詢附近POI信息時(shí)會(huì)導(dǎo)致以下問題历筝，比如紅色的點(diǎn)是我們的位置酗昼，綠色的兩個(gè)點(diǎn)分別是附近的兩個(gè)餐館，但是在查詢的時(shí)候會(huì)發(fā)現(xiàn)距離較遠(yuǎn)餐館的GeoHash編碼與我們一樣（因?yàn)樵谕粋€(gè)GeoHash區(qū)域塊上）梳猪，而較近餐館的GeoHash編碼與我們不一致麻削。這個(gè)問題往往產(chǎn)生在邊界處。

image

解決的思路很簡(jiǎn)單春弥，我們查詢時(shí)呛哟，除了使用定位點(diǎn)的GeoHash編碼進(jìn)行匹配外，還使用周圍8個(gè)區(qū)域的GeoHash編碼匿沛，這樣可以避免這個(gè)問題扫责。

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

  geohash只是空間索引的一種方式，特別適合點(diǎn)數(shù)據(jù)蔫缸，而對(duì)線腿准、面數(shù)據(jù)采用R樹索引更有優(yōu)勢(shì)（可參考：**[深入淺出空間索引：為什么需要空間索引](http://www.cnblogs.com/LBSer/p/3392491.html)**）。

參考文獻(xiàn)：

http://en.wikipedia.org/wiki/Geohash

http://openlocation.org/geohash/geohash-js/

Cantor空間填充曲線之演算法探討.pdf

2拾碌、例子（1.7.6上運(yùn)行）

PUT /attractions
{
  "mappings": {
    "restaurant": {
      "properties": {
        "name": {
          "type": "string"
        },
        "location": {
          "type": "geo_point",
          "geohash_prefix": true,
          "geohash_precision": "1km"
        }
      }
    }
  }
}

PUT /attractions/restaurant/1
{
     "name":
     "Chipotle Mexican Grill",
     "location": "40.715, -74.011"
}

PUT /attractions/restaurant/2
{
       "name":
       "Pala Pizza",
       "location": {
               "lat":40.722,
               "lon":-73.989
  }

}
PUT /attractions/restaurant/3
{
"name":
"Mini Munchies Pizza",
"location": [ -73.983, 40.719 ]
}

GET /attractions/restaurant/_search
{
  "query": {
    "filtered": {
      "filter": {
        "geohash_cell": {
          "location": {
            "lat": 40.722,
            "lon": -73.983
          },
          "precision": "2km"
        }
      }
    }
  }
}

圖片.png

3吐葱、進(jìn)一步介紹

圖片.png

GET /attractions/restaurant/_search
{
  "size" : 0,
  "query": {
    "constant_score": {
      "filter": {
        "geo_bounding_box": {
          "location": { 
            "top_left": {
              "lat":  40.8,
              "lon": -74.1
            },
            "bottom_right": {
              "lat":  40.4,
              "lon": -73.7
            }
          }
        }
      }
    }
  },
  "aggs": {
    "new_york": {
      "geohash_grid": { 
        "field":     "location",
        "precision": 5
      }
    }
  }
}

圖片.png