為什麼 MongoDB 索引選擇B樹，而 Mysql 索引選擇B+樹？

愚公要移山1

優質創作者

本文獻給准備面試或者是還在面試的你。常見面試題，送分題目，不拿白不拿。

本文收錄在個人博客《愚公要移山》中，地址 www.javachat.cc

這篇是修改版，針對知乎上很多人提出的問題，進行了一次修複

一、B樹和B+樹的區別

很明顯，我們想向弄清楚原因就要知道B樹和B+樹的區別。為了不長篇大論。我們直接給出他們的形式總結他們的特點。

1、B樹

B樹是一種自平衡的搜索樹，形式很簡單：

這就是一顆B-樹。針對我們這個問題的最核心的特點如下：

（1）多路，非二叉樹

（2）每個節點既保存索引，又保存數據

（3）搜索時相當於二分查找

其他的基本上都是一些常見的數據結構，假定都已經了解了B樹相關的結構。

2、B+樹

B+樹是B樹的變種

最核心的特點如下：

（1）多路非二叉

（2）只有葉子節點保存數據

（3）搜索時相當於二分查找

（4）增加了相鄰接點的指向指針。

從上面我們可以看出最核心的區別主要有倆，

一個是數據的保存位置：B樹保存在所有的節點中，B+樹保存在葉子節點

一個是相鄰節點的指向：B樹葉子節點之間沒有指針，B+樹有

這裏區別分別給B樹和B+樹帶來了什麼好處呢？其實對於數據庫來說，選用什麼數據結構無非就是為了增刪改查和存儲更加高效，因為找特點時也要從這個點去回答。

3、從區別找特點

第一：查找元素

（1）B樹的數據保存在所有節點，查詢複雜度最好是 O(1)。

（2）B+樹的數據保存在葉子節點，查詢時間複雜度固定是O(log(n))

第二：區間查找

（1）B樹每個節點 key 和 data 在一起，則無法區間查找。

（2）B+樹相鄰接點的指針可以大大增加區間訪問性，可使用在範圍查詢等

第三：存儲

（1）B樹每個節點即保存數據又保存索引，所以每一節點特別大，這一層所有節點加起來數據量將非常大。磁盤每次IO一定量的數據，對於Mysql來說如何衡量查詢效率呢？就是磁盤IO次數。既然B樹每一層特別大，那每一層就需要對數據分開從而進行多次IO操作。所有Mysql不用。

（2）B+樹更適合外部存儲，也就是磁盤存儲。由於內節點無 data 域，每個節點能索引的範圍更大更精確，所以不需要用B+樹。

有了他們的區別之後，現在我們再來解釋這個原因就好多了。

二、原因解釋

上面解釋了不使用的原因，我們再來看為什麼Mysql使用B+樹，而MongoDB使用B樹，想要解釋原因，我們還必須要了解一下MongoDB和Mysql的基本概念。

1、MongoDB

MongoDB 是文檔型的數據庫，是一種 nosql，它使用類 Json 格式保存數據。比如之前我們的表可能有用戶表、訂單表、購物籃表等等，還要建立他們之間的外鍵關聯關系。但是類Json就不一樣了。

我們可以看到這種形式更簡單，通俗易懂。那為什麼 MongoDB 使用B-樹呢？

MongoDB使用B樹，所有節點都有Data域，只要找到指定索引就可以進行訪問，無疑單次查詢平均快於Mysql
。

2、Mysql

Mysql作為一個關系型數據庫，數據的關聯性是非常強的，區間訪問是常見的一種情況，B+樹由於數據全部存儲在葉子節點，並且通過指針串在一起，這樣就很容易的進行區間遍曆甚至全部遍曆。

還有一點，B+樹只有葉子節點保存數據，所以每一節點比較小，每一層所有節點加起來數據量也相對比較小。磁盤每次IO一定量的數據，對於Mysql來說。既然B+樹每一層小，那每一層只需要少量IO操作。

這倆區別的核心如果你能看懂B-樹和B+樹的區別就很容易理解。

回複關鍵字獲取java相關5T資源，

視頻,電子書,面試,簡曆,IDEA破解等

只有你想不到的，沒有找不到