作者：孔德雨
MongoDB的geo索引是其一大特色，本文從原理層面講述geo索引中的2d索引的實現。
2d 索引的創建與使用
通過 db.coll.createIndex({"lag":"2d"}, {"bits":int}))來創建一個2d索引，索引的精度通過bits來指定，bits越大，索引的精度就越高。更大的bits帶來的插入的overhead可以忽略不計。
通過
db.runCommand({
geoNear: tableName,
maxDistance: 0.0001567855942887398,
distanceMultiplier: 6378137.0,
num: 30,
near: [ 113.8679388183982, 22.58905429302385 ],
spherical: true|false})
來查詢一個索引，其中spherical：true|false 表示應該如何理解創建的2d索引，false表示將索引理解為平面2d索引，true表示將索引理解為球面經緯度索引。這一點比較有意思，一個2d索引可以表達兩種含義，而不同的含義是在查詢時被理解的，而不是在索引創建時。
2d索引的理論
Mongodb 使用一種叫做Geohash的技術來構建2d索引，但是Mongodb的Geohash並沒有使用國際通用的每一層級32個grid的Geohash描述方式（見wiki geohash)。而是使用平面四叉樹的形式。
如下圖：
很顯然的，一個2bits的精度能把平面分為4個grid，一個4bits的精度能把平面分為16個grid。2d索引的默認精度是長寬各為26，索引把地球分為(2^26)(2^26)塊，每一塊的邊長估算為
2*PI*6371000/(1<<26) = 0.57 米
mongodb的官網上說的60cm的精度就是這麼估算出來的:
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中的存儲
上面我們講到Mongodb使用平面四叉樹的方式計算Geohash。事實上，平面四叉樹僅存在於運算的過程中，在實際存儲中並不會被使用到。
插入
對於一個經緯度座標[x,y]，MongoDb計算出該座標在2d平面內的grid編號，該編號為是一個52bit的int64類型，該類型被用作btree的key，因此實際數據是按照 {GeoHashId->RecordValue}的方式被插入到btree中的。
查詢
對於geo2D索引的查詢，常用的有geoNear和geoWithin兩種。geoNear查找距離某個點最近的N個點的座標並返回，該需求可以說是構成了LBS服務的基礎（陌陌，滴滴，摩拜）， geoWithin是查詢一個多邊形內的所有點並返回。我們著重介紹使用最廣泛的geoNear查詢。
geoNear的查詢過程
geoNear的查詢語句如下：
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可以理解為一個從起始點開始的不斷向外擴散的環形搜索過程。如下圖所示：
由於圓自身的性質，外環的任意點到圓心的距離一定大於內環任意點到圓心的距離，所以以圓環進行擴張迭代的好處是：
1）減少需要排序比較的點的個數2）能夠儘早發現滿足條件的點從而返回，避免不必要的搜索
點集密度估算
那麼，如何確定初始迭代步長呢，mongoDB認為初始迭代步長和點集密度相關。
geoNear 會根據點集的密度來確定迭代的初始步長。估算步驟如下：
1）從最小步長默認為60cm向外以矩形範圍搜索，如果範圍內有至少一個點，則停止搜索，轉3）否則轉 2)
2）步長倍增，繼續步驟1）
3）以矩形對角線長度的三倍作為初始迭代步長。
圓環覆蓋與索引前綴原理
上面我們說過，每一次的搜索都是以圓環為單位進行的，但是真實存入Btree中的是{GeoHashId->RecordValue}，計算出與圓環相交的所有邊長60cm的格子的GeoHash的值並在Btree中搜素絕對是一個非常愚蠢的做法，因為如果圓環的面積很大，光是枚舉所有的GeoHash就有上百萬個。
但是換個角度來看，其實以地球為一個整體去看待存儲的點，絕對是稀疏的。這個稀疏的性質使得我們可以粗略的以平面四叉樹的角度自上而下的找出與圓環相交的四叉樹中間節點。
整個平面與圓環必然是相交的，於是將平面一分為四，剔除不相交的部分，對於每個留下來的子平面，繼續一分為四，剔除不相交的部分，經過多輪迭代，留下來的子平面的GeoHash都是該子平面中所有grid的索引前綴，如下面四幅圖所示：
上面四幅圖中，分別為整個平面被四叉樹劃分0,1,2,3次後與圓環的相交情況，如果繼續往下細分，所形成的圖形就越來越逼近整個圓環。MongoDB中使用參數internalGeoNearQuery2DMaxCoveringCells來限制最多逼近到多少個子平面與圓環相交，默認為16。
我們注意到，上述平面劃分過程為四叉樹的分裂過程，每一次分裂都使得遞歸搜索的子平面與父平面有相同的GeoHash前綴（這裡需要思考為什麼，可能不太明顯），因此每一個子平面可以對應於BTree中一段連續的Range(這裡又是為什麼？)，也正因此，該參數越大，會使得需要搜索的子平面越少，但是會使得Btree的Range搜索更趨向於隨機化搜索，導致更多的IO。我們知道Btree更適合於做Range搜索，所以對該參數的調整需要慎重。
展望
MongoDB原生的geoNear接口是國內各大LBS應用的主流選擇。騰訊雲的MongoDB專家經過測試發現，在點集稠密的情況下，MongoDB原生的geoNear接口效率會急劇下降，單機甚至不到1000QPS。騰訊雲MongoDB對此進行了持續的優化，在不影響效果的前提下，geoNear的效率有10倍以上的提升，建議大家選擇騰訊雲MongoDB作為LBS應用的存儲方案。
相關推薦
