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

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

(數(shù)據(jù)庫(kù)索引采用B+樹的主要原因是 B樹在提高了磁盤IO性能的同時(shí)并沒(méi)有解決元素遍歷的效率低下的問(wèn)題。正是為了解決這個(gè)問(wèn)題，B+樹應(yīng)運(yùn)而生。B+樹只要遍歷葉子節(jié)點(diǎn)就可以實(shí)現(xiàn)整棵樹的遍歷。而且在數(shù)據(jù)庫(kù)中基于范圍的查詢是非常頻繁的，而B樹不支持這樣的操作（或者說(shuō)效率太低）)。
至于MongoDB為什么使用B-樹而不是B+樹，可以從它的設(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ù)據(jù)都在葉節(jié)點(diǎn)上，每次查詢都需要訪問(wèn)到葉節(jié)點(diǎn)，而MongoDB使用B-樹，所有節(jié)點(diǎn)都有Data域，只要找到指定索引就可以進(jìn)行訪問(wèn)，無(wú)疑單次查詢平均快于Mysql（但側(cè)面來(lái)看Mysql至少平均查詢耗時(shí)差不多）。
總體來(lái)說(shuō)，Mysql選用B+樹和MongoDB選用B-樹還是以自己的需求來(lái)選擇的。

延伸閱讀：

二、二叉樹和紅黑樹