圖解 MongoDB 地理位置索引的實現原理(轉)

          地理位置索引支持是MongoDB的一大亮點,這也是全球最流行的LBS服務foursquare 選擇MongoDB的原因之一。我們知道,通常的數據庫索引結構是B+ Tree,如何將地理位置轉化為可建立B+Tree的形式,下文將為你描述。

          首先假設我們將需要索引的整個地圖分成16×16的方格,如下圖(左下角為坐標0,0 右上角為坐標16,16):

           

          單純的[x,y]的數據是無法建立索引的,所以MongoDB在建立索引的時候,會根據相應字段的坐標計算一個可以用來做索引的hash值,這個值叫做geohash,下面我們以地圖上坐標為[4,6]的點(圖中紅叉位置)為例。

          我們第一步將整個地圖分成等大小的四塊,如下圖:



          劃分成四塊后我們可以定義這四塊的值,如下(左下為00,左上為01,右下為10,右上為11):

          01 11
          00 10

          這樣[4,6]點的geohash值目前為 00

          然后再將四個小塊每一塊進行切割,如下:



          這時[4,6]點位于右上區域,右上的值為11,這樣[4,6]點的geohash值變為:0011

          繼續往下做兩次切分:




          最終得到[4,6]點的geohash值為:00110100

          這樣我們用這個值來做索引,則地圖上點相近的點就可以轉化成有相同前綴的geohash值了。

          我們可以看到,這個geohash值的精確度是與劃分地圖的次數成正比的,上例對地圖劃分了四次。而MongoDB默認是進行26次劃分,這個值在建立索引時是可控的。具體建立二維地理位置索引的命令如下:

          db.map.ensureIndex({point : "2d"}, {min : 0, max : 16, bits : 4})

          其中的bits參數就是劃分幾次,默認為26次。










           

          posted on 2011-11-25 17:19 胡鵬 閱讀(582) 評論(0)  編輯  收藏


          只有注冊用戶登錄后才能發表評論。


          網站導航:
           

          導航

          <2011年11月>
          303112345
          6789101112
          13141516171819
          20212223242526
          27282930123
          45678910

          統計

          常用鏈接

          留言簿(3)

          隨筆分類

          隨筆檔案

          agile

          搜索

          最新評論

          閱讀排行榜

          評論排行榜

          主站蜘蛛池模板: 清流县| 新巴尔虎右旗| 康定县| 曲沃县| 玉屏| 平邑县| 陆川县| 宝山区| 于田县| 宁德市| 美姑县| 兴和县| 吴旗县| 高平市| 织金县| 石柱| 上栗县| 化州市| 五家渠市| 宝山区| 黑河市| 长丰县| 扎兰屯市| 通渭县| 广饶县| 广昌县| 伽师县| 定南县| 北宁市| 建平县| 孝感市| 惠安县| 布拖县| 铁岭县| 乐昌市| 景谷| 万年县| 蒙山县| 涞水县| 鄂州市| 茶陵县|