一、為什么有關(guān)MongoDB采用B樹(shù)索引，以及Mysql B+樹(shù)做索引

B-樹(shù)和B+樹(shù)最重要的一個(gè)區(qū)別就是B+樹(shù)只有葉節(jié)點(diǎn)存放數(shù)據(jù)，其余節(jié)點(diǎn)用來(lái)索引，而B(niǎo)-樹(shù)是每個(gè)索引節(jié)點(diǎn)都會(huì)有Data域。
這就決定了B+樹(shù)更適合用來(lái)存儲(chǔ)外部數(shù)據(jù)，也就是所謂的磁盤(pán)數(shù)據(jù)。
從Mysql（Inoodb）的角度來(lái)看，B+樹(shù)是用來(lái)充當(dāng)索引的，一般來(lái)說(shuō)索引非常大，尤其是關(guān)系性數(shù)據(jù)庫(kù)這種數(shù)據(jù)量大的索引能達(dá)到億級(jí)別，所以為了減少內(nèi)存的占用，索引也會(huì)被存儲(chǔ)在磁盤(pán)上。
那么Mysql如何衡量查詢(xún)效率呢？磁盤(pán)IO次數(shù)，B-樹(shù)（B類(lèi)樹(shù)）的特定就是每層節(jié)點(diǎn)數(shù)目非常多，層數(shù)很少，目的就是為了就少磁盤(pán)IO次數(shù)，當(dāng)查詢(xún)數(shù)據(jù)的時(shí)候，較好的情況就是很快找到目標(biāo)索引，然后讀取數(shù)據(jù)，使用B+樹(shù)就能很好的完成這個(gè)目的，但是B-樹(shù)的每個(gè)節(jié)點(diǎn)都有data域（指針），這無(wú)疑增大了節(jié)點(diǎn)大小，說(shuō)白了增加了磁盤(pán)IO次數(shù)（磁盤(pán)IO一次讀出的數(shù)據(jù)量大小是固定的，單個(gè)數(shù)據(jù)變大，每次讀出的就少，IO次數(shù)增多，一次IO多耗時(shí)啊！），而B(niǎo)+樹(shù)除了葉子節(jié)點(diǎn)其它節(jié)點(diǎn)并不存儲(chǔ)數(shù)據(jù)，節(jié)點(diǎn)小，磁盤(pán)IO次數(shù)就少。這是優(yōu)點(diǎn)之一。
另一個(gè)優(yōu)點(diǎn)是什么，B+樹(shù)所有的Data域在葉子節(jié)點(diǎn)，一般來(lái)說(shuō)都會(huì)進(jìn)行一個(gè)優(yōu)化，就是將所有的葉子節(jié)點(diǎn)用指針串起來(lái)。這樣遍歷葉子節(jié)點(diǎn)就能獲得全部數(shù)據(jù)，這樣就能進(jìn)行區(qū)間訪(fǎng)問(wèn)啦。

(數(shù)據(jù)庫(kù)索引采用B+樹(shù)的主要原因是 B樹(shù)在提高了磁盤(pán)IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題。正是為了解決這個(gè)問(wèn)題，B+樹(shù)應(yīng)運(yùn)而生。B+樹(shù)只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹(shù)的遍歷。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢(xún)是非常頻繁的，而B(niǎo)樹(shù)不支持這樣的操作（或者說(shuō)效率太低）)。
至于MongoDB為什么使用B-樹(shù)而不是B+樹(shù)，可以從它的設(shè)計(jì)角度來(lái)考慮，它并不是傳統(tǒng)的關(guān)系性數(shù)據(jù)庫(kù)，而是以Json格式作為存儲(chǔ)的nosql，目的就是高性能，高可用，易擴(kuò)展。首先它擺脫了關(guān)系模型，上面所述的優(yōu)點(diǎn)2需求就沒(méi)那么強(qiáng)烈了，其次Mysql由于使用B+樹(shù)，數(shù)據(jù)都在葉節(jié)點(diǎn)上，每次查詢(xún)都需要訪(fǎng)問(wèn)到葉節(jié)點(diǎn)，而MongoDB使用B-樹(shù)，所有節(jié)點(diǎn)都有Data域，只要找到指定索引就可以進(jìn)行訪(fǎng)問(wèn)，無(wú)疑單次查詢(xún)平均快于Mysql（但側(cè)面來(lái)看Mysql至少平均查詢(xún)耗時(shí)差不多）。
總體來(lái)說(shuō)，Mysql選用B+樹(shù)和MongoDB選用B-樹(shù)還是以自己的需求來(lái)選擇的。

延伸閱讀：

二、二叉樹(shù)和紅黑樹(shù)