圖解 MongoDB 地理位置索引的實現(xiàn)原理

so_brave

圖解 MongoDB 地理位置索引的實現(xiàn)原理

地理位置索引支持是MongoDB的一大亮點，這也是全球最流行的LBS服務(wù)foursquare 選擇MongoDB的原因之一。我們知道，通常的數(shù)據(jù)庫索引結(jié)構(gòu)是B+ Tree，如何將地理位置轉(zhuǎn)化為可建立B+Tree的形式，下文將為你描述。

首先假設(shè)我們將需要索引的整個地圖分成16×16的方格，如下圖（左下角為坐標(biāo)0,0 右上角為坐標(biāo)16,16）：



單純的［x，y］的數(shù)據(jù)是無法建立索引的，所以MongoDB在建立索引的時候，會根據(jù)相應(yīng)字段的坐標(biāo)計算一個可以用來做索引的hash值，這個值叫做geohash，下面我們以地圖上坐標(biāo)為［4，6］的點（圖中紅叉位置）為例。

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



劃分成四塊后我們可以定義這四塊的值，如下（左下為00，左上為01，右下為10，右上為11）：

01 11
00 10

這樣［4，6］點的geohash值目前為 00

然后再將四個小塊每一塊進(jìn)行切割，如下：



這時［4，6］點位于右上區(qū)域，右上的值為11，這樣［4，6］點的geohash值變?yōu)椋?011

繼續(xù)往下做兩次切分：





最終得到［4，6］點的geohash值為：00110100

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

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

db.map.ensureIndex({point : "2d"}, {min : 0, max : 16, bits : 4})其中的bits參數(shù)就是劃分幾次，默認(rèn)為26次。

相關(guān)鏈接：Mongo in Flatland

小忻黑夜

謝謝分享