ongoDB的geo索引是其一大特色，本文從原理層面講述geo索引中的2d索引的實作。
通過 <code>db.coll.createIndex({"lag":"2d"}, {"bits":int}))</code> 來建立一個2d索引，索引的精度通過bits來指定，bits越大，索引的精度就越高。更大的bits帶來的插入的overhead可以忽略不計。
通過
來查詢一個索引，其中spherical：true|false 表示應該如何了解建立的2d索引，false表示将索引了解為平面2d索引，true表示将索引了解為球面經緯度索引。這一點比較有意思，一個2d索引可以表達兩種含義，而不同的含義是在查詢時被了解的，而不是在索引建立時。
Mongodb 使用一種叫做Geohash的技術來建構2d索引，但是Mongodb的Geohash并沒有使用國際通用的每一層級32個grid的Geohash描述方式（見wiki geohash)。而是使用平面四叉樹的形式。
如下圖：
很顯然的，一個2bits的精度能把平面分為4個grid，一個4bits的精度能把平面分為16個grid。2d索引的預設精度是長寬各為26，索引把地球分為(2^26)(2^26)塊，每一塊的邊長估算為
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.
上面我們講到Mongodb使用平面四叉樹的方式計算Geohash。事實上，平面四叉樹僅存在于運算的過程中，在實際存儲中并不會被使用到。
對于一個經緯度坐标[x,y]，MongoDb計算出該坐标在2d平面内的grid編号，該編号為是一個52bit的int64類型，該類型被用作btree的key，是以實際資料是按照 {GeoHashId->RecordValue}的方式被插入到btree中的。
對于geo2D索引的查詢，常用的有geoNear和geoWithin兩種。geoNear查找距離某個點最近的N個點的坐标并傳回，該需求可以說是構成了LBS服務的基礎（陌陌，滴滴，摩拜）， geoWithin是查詢一個多邊形内的所有點并傳回。我們着重介紹使用最廣泛的geoNear查詢。
geoNear的查詢語句如下：
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應用的存儲方案。