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

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

本文收錄在個人部落格《愚公要移山》中，地址 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破解等

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