MongoDB的索引代碼實作--BtreeBasedAccessMethodMongoDB的索引代碼實作--BtreeBasedAccessMethod

學習開源軟體的最好的辦法就是閱讀代碼，mongodb整個代碼庫有接近90萬行代碼，db核心層大概50萬行，代碼量确實非常多。本文作為mongodb代碼導讀的第一篇，從index部分上入手分析代碼實作。

為何從索引部分開始介紹，首先代碼量較少，總共5000多行，且相對其他子產品來說比較獨立；其次索引對資料庫的優化至關重要，了解其實作，對日後的運維優化和索引自身的限制約定都具有實際意義。畢竟文檔上的描述還是沒有代碼來的準确。本文沒有逐行的去分析源碼，一來工作量太大，二來也沒有辦法完全揣測出作者的意圖，莫不如隻描述大概，剩下的留給閱讀者自己思考。

代碼集中在src/db/index目錄下，裡面并沒有涉及具體的btree資料結構，而是描述了一些操作方法，索引解析等。mongodb的代碼實作上涉及到了比較多的設計模式，比如builder，combination，strategy，factory等。如圖，這部分代碼主要采用的是combination和adapter模式，整個代碼都圍繞着btreebasedaccessmethod。

構造函數和初始化成員

areindexoptionsequivalent

檢查是否是稀疏索引，是否是_id索引，并且是否是唯一索引，注釋裡也說明了，不關心id索引的排序順序，因為升序或者降序，對查詢來說，都是等價的，最後比較options，注意version和ns是不比較的，background是建立時的參數，建立後就不再有意義

定義了一些遊标接口方法，并聲明了yield邏輯，注釋寫的很清晰：

如果遊标指向的元素在yield期間沒有被删除，那麼在恢複後仍然指向這個位置。在yield時，插入，删除，或者修改的元素，是否會被遊标發現是不确定的。

因為考慮的效率問題，遊标可能會cache一批資料，這部分資料不會與原始的資料同步。同樣，yield時沒有加入或者删除的元素，都會被傳回，且隻傳回一次。

元素的傳回順序應該按照指定的順序傳回（升序或者降序），甚至是在yield期間，指向的元素被删除了也要維持原有的順序傳回。

操作接口，crud方法，注意是非線程安全的。對調用者來說，需要考慮底層的是以結構，接口的行為是不透明的。注釋比較簡單，不翻譯了：

繼承自indexaccessmethod，聲明getkeys，交給由子類實作，是個adapter模式。

insert

通過getkeys獲得doc的所有key，然後進行疊代修改index，修改成功後，會對numinserted++，計數，統計本次操作修改索引次數。如果遇到失敗情況，則要清理所有之前已經寫入的資料，保證操作的原子性，即使失敗，也要保證恢複到操作之前的資料狀态（索引結構可能會發生變化，但是資料集合是等價的）。 另外，background build index，可能會重複插入索引，因為doc資料可能會在磁盤上移動，也就是會被重複掃描到。

remove

remove比insert就簡單多了，因為remove是不可能失敗的

find

找到後傳回recordid

update

對比先後兩個對象，計算出diff，包括需要删除的和需要增加的，然後批量送出修改。注意，這裡可能會失敗，但是失敗後索引沒有再復原到之前的資料集合。并且是先删除後增加，極端情況下會導緻索引錯誤。思考：如果是先增加後删除，是不是更合适一點？

隻支援insert的bulk操作，insert的資料先儲存在一個外部存儲裡，最大記憶體使用10mb大小，commit時再全部讀出處理。

該對象封裝了一套解析解析算法，目的是解析出obj中的索引key，mongodb相比較于傳統的db系統，在索引建立上支援array結構，array資料内容會根據索引擴充出來。

例如：

特别說明的是，隻支援并列的一個數組索引，如果是多個資料都想被索引，會失敗。因為會造成索引數量的不可控(a*b)。

實際上，mongodb這裡提供了兩個版本的算法，v0和v1，2.0以後的mongodb預設采用了v1，v0與wt存儲引擎上還有寫相容性問題，參見：server-16893

是以，mongodb現在隻在mmap上支援v0算法，相關的檢驗代碼：

v1和v0的不同點也集中在數組的處理上，v0版本，過于簡單，很多數組結構索引解析出來的結果不完整，主要展現在了null的處理。

pattern

obj

v0

v1

{'a.b.c':1}

{a:[1,2,{b:{c:[3,4]}}]}

[{:3 }{:4}]

[{:null}{:3}{:4}]

{'a':1,'a.b':1}

{a:[{b:1}]}

[{:[{b:1} ],:1}]

[{:{b:1},:1}]

{a:1,a:1}

{a:[1,2]}

[{:1,:[ 1,2]}{:2,:[1,2]}]

[{:1,:1}{:2,:2}]

更多的資料測試可以參考btree_key_generator_test.cpp中的測試case。

雖然官方在releasenote裡說明：v1版本的索引更快，更節省空間，但實際上是v0版本算法漏洞太多。參見releasenote 2.0

index目錄下還包含了fts，geo相關的代碼沒有說明，fts部分等閱讀到了在說，畢竟使用的場景不多；geo部分涉及到了一些地理運算，圖形學運算，雖然不複雜，後面作為geo的專題讨論。餘下的代碼，主要邏輯在btreekeygenerator部分，尤其是v1算法，讀者可以再認真學習下。