[[393997]]

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

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

但實(shí)際上 MongoDb 真的用的是 B 樹嗎?

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

文檔地址：WiredTiger Storage Engine — MongoDB Manual

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

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

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

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

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

B 樹與 B+ 樹，其比較大的特點(diǎn)是：B 樹對(duì)于特定記錄的查詢，其時(shí)間復(fù)雜度更低。而 B+ 樹對(duì)于范圍查詢則更加方便，另外 B+ 樹相對(duì)于 B 樹來(lái)說(shuō)更加扁平。

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

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

說(shuō)到這里，你可能有點(diǎn)迷糊，那實(shí)際情況到底是什么呢?

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

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