用Golang寫一個搜索引擎 (0x04)
本篇較長較枯燥，請保持耐心看完。
前面兩章介紹了一下倒排索引以及倒排索引字典的兩種存儲結構，分別是 跳躍表 和 哈希表 ，本篇我們介紹另一種數據結構，他也被大量使用在信息檢索領域，我在 github 上實現的搜索引擎的詞典也是用的這個數據結構，它就是B+樹。
首先，我們看看什么是樹，樹是程序設計中一個非常基礎的數據結構，記得大學時候的數據結構課，鏈表，棧，隊列，然后就是樹了，雖然那時候想必大家都被前序遍歷，中序遍歷，后序遍歷折騰過，不過樹確實是一種非常有用的數據結構。
上一篇我們說過，表2的第一列首要解決的問題就是能快速找到對應的詞，然后找到對應詞的倒排列表，除了跳躍表和哈希表，B+樹也能滿足條件，B+樹是B樹的變種，我們B樹我們就不看了，感興趣的大家可以直接去google一下，我們主要講的是B+樹，下圖就是一個3層的B+樹，我畫出來可能和大家搜出來的有點出入，但是沒關系，關鍵B+樹這種數據結構的思想大家了解了就行。
假設我們有一組數字 34，40，67，5，37，12，45，24 ，那么，把他們存成B+樹就是下圖這個樣子。
我們很明顯看到幾個特點
-
每個節點的大小為2
-
非葉子層的最后一個節點的最后一個元素為 NULL
-
最底層的葉子節點是順序排列的，這個例子是從小到大
-
上面的內節點的每一個元素都指向的下一級節點中最大的一個數相等
我盡量的把B+樹說簡單點，網上的資料也好，查書也好，看上去都挺復雜的，首先我們看看怎么建立這棵樹，我盡量用圖了，少一些文字也好理解一點，前方大量圖預警。
首先，我們的數組是 34，12，5，67，37，40，45，24
第一步，初始化B+樹，是這樣子的
這時候，啥也沒有，但是占用了兩個節點，標識為 無 的，表示這個元素無意義，標記為 NULL 表示 無窮大
第二步，插入34這個元素，那么圖變成這樣子
我們看到，插入的過程是順著指針一直走到葉子節點，發現葉子節點是空的，然后把元素插入到葉子節點的頭部，然后返回上一級節點，將NULL后移，然后把第一個元素 置為他的子節點的最大值 ，請記住這句話： 置為他的子節點的最大值
第三步，接著插入第二個元素12
這個步驟復雜一點
-
從根節點開始遍歷，發現12小于根節點的某一個元素【在這里是第1個元素】，順著指針往下走
-
到達葉子節點，發現12小于葉子節點的某一個元素，說明可以放在這個葉子節點中，并且葉子節點還有一個空位置，那么直接把12按大小順序插入到這個節點中
第四步，然后是插入5
這一步更復雜一點，產生了 分裂
-
從根節點開始遍歷，5小于34，順著指針往下走，到達葉子節點
-
到達葉子節點，發現5小于葉子節點的某一個元素，說明可以放在這個葉子節點中，但是，這個節點已經滿了，那么，分裂出一個新的節點，將5放到老節點中，被擠走的元素順移到新節點中
-
返回上一級節點，由于第一個葉子節點的最大元素已經變成12了，所以將該節點的元素由34改成指向的葉子節點的最大元素12
-
由于新生成了一個節點，將NULL這個元素指向新生成的節點
第五步，接著我們插入67
這一步比較簡單
-
從根節點開始遍歷，67小于NULL，順著指針往下走，到達葉子節點
-
到達葉子節點，發現67大于該節點的每一個元素，并且葉子節點有空位，直接插入即可
第六步，我們插入37，插完這個后面的我就不寫了，感興趣可以自己畫一下
這一步復雜了，這一步不僅分裂了，而且分裂了兩次，并且層數增加了一層
-
從根節點開始遍歷，37小于NULL，順著指針往下走，到達葉子節點
-
到達葉子節點，37小于葉子節點中的67，表示可以插入到這個節點中，但是節點滿了，我們按照 第四步 的操作，分裂節點。
-
分裂完了以后，產生了一個[34,37]，一個[67,無]兩個節點，往上走的時候，發現上一層的節點插入了37以后也滿了，繼續按照 第四步 分裂。
-
分裂完了以后，發現上層沒有節點了，那么就新建一個根節點當上層節點，按照分裂的步驟給根節點賦值。
按照這六步，前5個元素就插入到B+樹中了，后面的步驟您可以自己走一走，B+樹基本的思想就是這樣子的，可能我沒有按照教科書上的做法來說，但這并不影響大家的理解，我相信看完了以后雖然你腦子里沒有標準的算法步驟，但應該有個大致的輪廓了，只不過需要自己再仔細想想步驟。
總的來說，B+樹的插入步驟無外乎以下幾個步驟
-
每次都要從根節點開始
-
比較大小，找到小于當前值的元素，順著指針往下走，繼續比較大小，一直到達葉子節點，那么這個葉子節點就是你要操作的節點了。
-
在葉子節點只有幾種操作，一是葉子節點有空位置，那么直接插入進去，一是葉子節點滿了，那么分裂一個節點出來。
-
不管在葉子節點進行了那種操作，最后都要順著指針回去，如果沒有分裂，那么上層就不會分裂，可能會更新上層節點元素的值，如果分裂了，那么就帶著兩個分裂的節點往上走，該更新值就更新值，該分裂就分裂。
-
如果一層一層分裂到最上層了，那么就新增一個根節點吧
查找操作和更新操作幾乎一樣，就是更新操作的前面兩步，就不說了。
一般的更新的時候也是先查找，找到葉子節點，再更新，然后順著指針往上走繼續分裂，這個順著往上走一般情況下首先想到的是雙向指針，但是雙向指針分裂的時候有點麻煩，需要把兩個指針都重新指新節點，我實現的時候用了一個棧，查找葉子節點的時候把經過的節點依次壓棧，到達葉子節點后，完成插入操作，往上遍歷的時候依次把棧彈出來就行了，少了一個指針。
回到上一篇說的那個表2的第一列，如果是那個表的話，用這個B+樹加上倒排鏈的話，最后的數據結構就長成這樣子了（字符串的大小我隨便寫的，中文的順序排列哥的腦子排不出來，你就把他們看成從小到大的順序吧）
好了，至此，一個倒排索引就建立好了，由兩部分組成，我實現的時候就是這么實現的，一個結構用B+樹存儲字典，另外一個就是一個順序的文件，B+樹的葉子節點存一個指向倒排文件的文件偏移量，當然，你也可以用前面的哈希表或者跳躍表，甚至還有其他類型的樹，比如trie樹來實現，或者你還有其他新的高效數據結構也行。
我們再來說說B+樹，為什么選它？
之前我實現的時候用的是哈希表，而且大部分的搜索引擎用的都是哈希表，為什么用樹呢
-
首先，為了節省空間，如果用哈希表的話，假如有一個字段是主鍵，并且是不規則的（比如cookieid），那么如果巨量的文檔的話，哈希表的桶就會很大，會非常占用內存，而我調試的機器才8G內存的mac。
-
其次再來看看哈希表，查詢的時間復雜度是O(1)，看上去確實美好，如果單單是一個全文搜索引擎的話，由于key都是字符串，而且基本都是中文字符串，整個中文的詞匯量才幾十萬，確實很好，但是如果字段不見得是中文分詞的東西，還有一些其他的東西，比如各種ID，由于是個通用的搜索，所以不會給具體字段去定義專門的哈希函數，所以可能會大片產生碰撞，那復雜度就不是O(1)了，如果是一個特定場景的搜索，要規避這個問題，可以根據自己的業務需求來的，甚至可以使用完美哈希函數，而我實現的時候主要是為了更通用，所以用了B+樹。
-
我們再看看B+樹本身，如果我們每個節點可以存儲100個元素，那么一個4層的B+樹，可以存儲1億條數據，不管是主鍵字段還是其他字段都夠了，而一個4層的B+樹檢索起來，需要遍歷4個節點，每個節點用二分查找的話，是log100(2為底)，大概7次吧，4層的話，最差需要查詢28次，如果是3層的話，最差要21次，雖然和哈希比起來慢了這么多，但1次循環大約需要4個CPU的時鐘周期吧，對于現在的服務器的計算機來說，就算21次循環+條件判斷也是微秒級別的，感覺不太出來差別，何況不可能每一次都那么點背，都要查21次吧。
-
再有，我的索引生成的時候是按段生成的，后面會涉及到索引的多個段的合并，如果是B+樹的話，字典是順序的，你看上面那個圖，葉子節點是有指針連起來的，所以合并段的時候可以使用一個多路歸并就合并完了，要是哈希的話，由于不是順序的，合并起來需要重新哈希一遍，比較麻煩。
-
還有，B+樹這種數據結構非常適合磁盤檢索，只需要把每個節點的大小設定成一個磁盤頁的大小（一般是4K，至于為什么設成頁的大小，和機械硬盤的結構以及預讀取機制有關，感興趣的可以自己查查，不過現在都是SSD了，這個的影響不是很大了），把指針改成磁盤的頁編號，那么不用加載進內存，直接在磁盤上就能進行檢索，特別適合巨量數據量的詞典（比如主鍵），索引數據庫的索引（比如Mysql的inneDB）基本上都是B+樹實現的，如果大家感興趣可以單開一篇說這個。
-
最后，B+樹由于是順序存儲的，所以可以進行范圍搜索（雖然我沒有用），而哈希表只能進行全等的搜索。
最后說說我實現的這棵B+樹，首先，為了更少的占用內存，我是用的磁盤的形式實現的，并且用了mmap的方式來加快讀寫速度，沒有用雙向指針，而用的棧來記錄查詢的路徑，速度還行吧，構造一棵10萬個隨機字符串的樹大約需要3秒，隨機查詢10萬次大約需要150毫秒，每次1.5微秒。
當然，我實現的時候比較倉促，就是按照算法硬編碼快速擼出來的，所以我這個B+樹還有非常大的優化空間，首先，我的key現在是確定的，不能超過64字節，并且每個節點最多100個元素，當時為了快，確定的key和元素個數比較好編程，如果變成動態的更加節省空間，其次，沒有特別的考慮連續key的情況，連續key的插入會造成空間浪費一半，還有，把速度問題交給了mmap來解決，如果內存足夠，實際上啟動的時候預讀取非葉子節點到內存的話，查詢起來會更快，不過目前基本上滿足需求了，大家如果對B+樹實現很感興趣，可以看看 bolt 這個項目，這個是一個B+樹實現的KVDB，而且是帶事務的哦。
OK，這一篇就寫到這了，周末要出去玩了，下周繼續。。。
最后，歡迎大家掃描一下下面的微信公眾號訂閱，首先會在這里發出來：）
