[[393997]]

本文轉(zhuǎn)載自微信公眾號「陳樹義」，作者陳樹義。轉(zhuǎn)載本文請聯(lián)系陳樹義公眾號。

關(guān)于 B 樹與 B+ 樹，網(wǎng)上有一個比較經(jīng)典的問題：為什么 MongoDb 使用 B 樹，而 MySQL 索引使用 B+ 樹?

但實際上 MongoDb 真的用的是 B 樹嗎?

通過查閱資料，我從 MongoDb 的官網(wǎng)和 WiredTiger 官網(wǎng)找到了答案。MongoDb 官網(wǎng)關(guān)于存儲引擎(Storage Engine)的描述寫道：從 MongoDb 3.2 版本開始，其使用了 WiredTiger 作為其默認的存儲引擎。

文檔地址：WiredTiger Storage Engine — MongoDB Manual

而從 WiredTiger 官網(wǎng)文檔，我們可以知道：WiredTiger 使用的是 B+ 樹作為其存儲結(jié)構(gòu)。

文檔地址：WiredTiger: Tuning page size and compression

那為什么會出現(xiàn)很多資料說 MongoDb 使用 B 樹作為存儲的數(shù)據(jù)結(jié)構(gòu)呢?我想可能有兩個原因：一個原因可能是 B+ Tree 本身是 B 樹的一種優(yōu)化，所以很多人就直接把 B+ 樹說成 B 樹了。另一個原因可能是 MongoDb 3.2 之前，確實使用 B 樹作為存儲的數(shù)據(jù)結(jié)構(gòu)。

對于這兩個原因，我沒有深入去探尋，有答案的朋友可以留言討論一下。但我知道，無論是什么原因，都不影響我們對這個問題的討論。表面上，我們是在討論 MongoDb 與 MySQL 存儲的數(shù)據(jù)結(jié)構(gòu)，但實際上我們是在討論 B 樹和 B+ 樹這兩種數(shù)據(jù)結(jié)構(gòu)的特點。

因此，無論 MongoDb 使用的是 B 樹，還是 B+ 樹。只要我們弄清楚 B 樹與 B+ 樹之間的區(qū)別，我們就可以在合適的時候，選擇合適的數(shù)據(jù)結(jié)構(gòu)。

B 樹與 B+ 樹，其比較大的特點是：B 樹對于特定記錄的查詢，其時間復(fù)雜度更低。而 B+ 樹對于范圍查詢則更加方便，另外 B+ 樹相對于 B 樹來說更加扁平。

對于 MongoDb 來說，其是非關(guān)系型數(shù)據(jù)庫，較少做聯(lián)表的范圍查詢。如果這確實是 MongoDb 非常典型的使用場景，使用 B 樹其實可以加快其查詢速度。

但實際上 MongoDb 3.2 之后，其使用了 B+ 樹作為其數(shù)據(jù)結(jié)構(gòu)。B+ 樹其在范圍查詢方面更有優(yōu)勢，那有可能是 B+ 樹更加扁平，可以讓其更加快速地找到數(shù)據(jù)，加快其查找速度。也有可能是 MongoDb 的范圍查詢特性使用更加廣泛了。

說到這里，你可能有點迷糊，那實際情況到底是什么呢?

其實我自己并沒有找到答案。我的思考也是到此為止，我也并沒有找到更好的答案。與其腹死胎中，還不如寫下來與大家討論?；蛟S不久之后我就忽然大悟，明白這其中的道理，到時候再來給大家分享。

寫到這里，腦袋里蹦出另外一個問題：那為啥 MongoDb 要使用 B+ 樹 ?而不使用平衡二叉樹?嗯，答案其實很簡單——是因為需要使用 B 樹能加載大數(shù)據(jù)量的特性，否則其實現(xiàn)不了這么大量數(shù)據(jù)的查詢和排序。