作者：孔德雨

MongoDB的geo索引是其一大特色，本文從原理層面講述geo索引中的2d索引的實(shí)現(xiàn)。

2d 索引的創(chuàng)建與使用

通過(guò) db.coll.createIndex({"lag":"2d"}, {"bits":int})) 來(lái)創(chuàng)建一個(gè)2d索引，索引的精度通過(guò)bits來(lái)指定，bits越大，索引的精度就越高。更大的bits帶來(lái)的插入的overhead可以忽略不計(jì)。

通過(guò)

db.runCommand({ 
    geoNear: tableName, 
    maxDistance: 0.0001567855942887398, 
    distanceMultiplier: 6378137.0, 
    num: 30, 
    near: [ 113.8679388183982, 22.58905429302385 ], 
    spherical: true|false})

來(lái)查詢一個(gè)索引，其中spherical：true|false 表示應(yīng)該如何理解創(chuàng)建的2d索引，false表示將索引理解為平面2d索引，true表示將索引理解為球面經(jīng)緯度索引。這一點(diǎn)比較有意思，一個(gè)2d索引可以表達(dá)兩種含義，而不同的含義是在查詢時(shí)被理解的，而不是在索引創(chuàng)建時(shí)。

2d索引的理論

Mongodb 使用一種叫做Geohash的技術(shù)來(lái)構(gòu)建2d索引，但是Mongodb的Geohash并沒(méi)有使用國(guó)際通用的每一層級(jí)32個(gè)grid的Geohash描述方式（見(jiàn)wiki geohash)。而是使用平面四叉樹(shù)的形式。

如下圖：

很顯然的，一個(gè)2bits的精度能把平面分為4個(gè)grid，一個(gè)4bits的精度能把平面分為16個(gè)grid。2d索引的默認(rèn)精度是長(zhǎng)寬各為26，索引把地球分為(2^26)(2^26)塊，每一塊的邊長(zhǎng)估算為

2*PI*6371000/(1<<26) = 0.57 米

mongodb的官網(wǎng)上說(shuō)的60cm的精度就是這么估算出來(lái)的:


By default, a 2d index on legacy coordinate pairs uses 26 bits of precision, which is roughly equivalent to 2 feet or 60 centimeters of precision using the default range of -180 to 180.

2d索引在Mongodb中的存儲(chǔ)

上面我們講到Mongodb使用平面四叉樹(shù)的方式計(jì)算Geohash。事實(shí)上，平面四叉樹(shù)僅存在于運(yùn)算的過(guò)程中，在實(shí)際存儲(chǔ)中并不會(huì)被使用到。

插入

對(duì)于一個(gè)經(jīng)緯度坐標(biāo)[x,y]，MongoDb計(jì)算出該坐標(biāo)在2d平面內(nèi)的grid編號(hào)，該編號(hào)為是一個(gè)52bit的int64類型，該類型被用作btree的key，因此實(shí)際數(shù)據(jù)是按照 {GeoHashId->RecordValue}的方式被插入到btree中的。

查詢

對(duì)于geo2D索引的查詢，常用的有g(shù)eoNear和geoWithin兩種。geoNear查找距離某個(gè)點(diǎn)最近的N個(gè)點(diǎn)的坐標(biāo)并返回，該需求可以說(shuō)是構(gòu)成了LBS服務(wù)的基礎(chǔ)（陌陌，滴滴，摩拜）， geoWithin是查詢一個(gè)多邊形內(nèi)的所有點(diǎn)并返回。我們著重介紹使用最廣泛的geoNear查詢。

geoNear的查詢過(guò)程

geoNear的查詢語(yǔ)句如下：

db.runCommand(
   {
     geoNear: "places", //table Name
     near: [ -73.9667, 40.78 ] ,  // central point
     spherical: true,  // treat the index as a spherical index
     query: { category: "public" }  // filters
     maxDistance: 0.0001531 //  distance in about one kilometer
   }
)

geoNear可以理解為一個(gè)從起始點(diǎn)開(kāi)始的不斷向外擴(kuò)散的環(huán)形搜索過(guò)程。如下圖所示：

由于圓自身的性質(zhì)，外環(huán)的任意點(diǎn)到圓心的距離一定大于內(nèi)環(huán)任意點(diǎn)到圓心的距離，所以以圓環(huán)進(jìn)行擴(kuò)張迭代的好處是：

1）減少需要排序比較的點(diǎn)的個(gè)數(shù)
2）能夠盡早發(fā)現(xiàn)滿足條件的點(diǎn)從而返回，避免不必要的搜索

點(diǎn)集密度估算

那么，如何確定初始迭代步長(zhǎng)呢，mongoDB認(rèn)為初始迭代步長(zhǎng)和點(diǎn)集密度相關(guān)。

geoNear 會(huì)根據(jù)點(diǎn)集的密度來(lái)確定迭代的初始步長(zhǎng)。估算步驟如下：

1）從最小步長(zhǎng)默認(rèn)為60cm向外以矩形范圍搜索，如果范圍內(nèi)有至少一個(gè)點(diǎn)，則停止搜索，轉(zhuǎn)3）否則轉(zhuǎn) 2)
2）步長(zhǎng)倍增，繼續(xù)步驟1）
3）以矩形對(duì)角線長(zhǎng)度的三倍作為初始迭代步長(zhǎng)。

圓環(huán)覆蓋與索引前綴原理

上面我們說(shuō)過(guò)，每一次的搜索都是以圓環(huán)為單位進(jìn)行的，但是真實(shí)存入Btree中的是{GeoHashId->RecordValue}，計(jì)算出與圓環(huán)相交的所有邊長(zhǎng)60cm的格子的GeoHash的值并在Btree中搜素絕對(duì)是一個(gè)非常愚蠢的做法，因?yàn)槿绻麍A環(huán)的面積很大，光是枚舉所有的GeoHash就有上百萬(wàn)個(gè)。

但是換個(gè)角度來(lái)看，其實(shí)以地球?yàn)橐粋€(gè)整體去看待存儲(chǔ)的點(diǎn)，絕對(duì)是稀疏的。這個(gè)稀疏的性質(zhì)使得我們可以粗略的以平面四叉樹(shù)的角度自上而下的找出與圓環(huán)相交的四叉樹(shù)中間節(jié)點(diǎn)。

整個(gè)平面與圓環(huán)必然是相交的，于是將平面一分為四，剔除不相交的部分，對(duì)于每個(gè)留下來(lái)的子平面，繼續(xù)一分為四，剔除不相交的部分，經(jīng)過(guò)多輪迭代，留下來(lái)的子平面的GeoHash都是該子平面中所有g(shù)rid的索引前綴，如下面四幅圖所示：




上面四幅圖中，分別為整個(gè)平面被四叉樹(shù)劃分0,1,2,3次后與圓環(huán)的相交情況，如果繼續(xù)往下細(xì)分，所形成的圖形就越來(lái)越逼近整個(gè)圓環(huán)。MongoDB中使用參數(shù)internalGeoNearQuery2DMaxCoveringCells來(lái)限制最多逼近到多少個(gè)子平面與圓環(huán)相交，默認(rèn)為16。

我們注意到，上述平面劃分過(guò)程為四叉樹(shù)的分裂過(guò)程，每一次分裂都使得遞歸搜索的子平面與父平面有相同的GeoHash前綴（這里需要思考為什么，可能不太明顯），因此每一個(gè)子平面可以對(duì)應(yīng)于BTree中一段連續(xù)的Range(這里又是為什么？)，也正因此，該參數(shù)越大，會(huì)使得需要搜索的子平面越少，但是會(huì)使得Btree的Range搜索更趨向于隨機(jī)化搜索，導(dǎo)致更多的IO。我們知道Btree更適合于做Range搜索，所以對(duì)該參數(shù)的調(diào)整需要慎重。

展望

MongoDB原生的geoNear接口是國(guó)內(nèi)各大LBS應(yīng)用的主流選擇。騰訊云的MongoDB專家經(jīng)過(guò)測(cè)試發(fā)現(xiàn)，在點(diǎn)集稠密的情況下，MongoDB原生的geoNear接口效率會(huì)急劇下降，單機(jī)甚至不到1000QPS。騰訊云MongoDB對(duì)此進(jìn)行了持續(xù)的優(yōu)化，在不影響效果的前提下，geoNear的效率有10倍以上的提升，建議大家選擇騰訊云MongoDB作為L(zhǎng)BS應(yīng)用的存儲(chǔ)方案。

 

相關(guān)閱讀

MongoDB復(fù)制集原理

MongoDb Mmap引擎分析

基于用戶畫(huà)像大數(shù)據(jù)的電商防刷架構(gòu)

此文已由作者授權(quán)騰訊云技術(shù)社區(qū)發(fā)布，轉(zhuǎn)載請(qǐng)注明文章出處，獲取更多云計(jì)算技術(shù)干貨，可請(qǐng)前往騰訊云技術(shù)社區(qū)

原文鏈接：https://www.qcloud.com/community/article/36629001491016578

歡迎大家關(guān)注騰訊云技術(shù)社區(qū)-博客園官方主頁(yè)，我們將持續(xù)在博客園為大家推薦技術(shù)精品文章哦~

http://www.cnblogs.com/qcloud1001/p/6676616.html