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

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

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

延伸閱讀：

二、二叉樹和紅黑樹