一、B-樹和B+樹回顧

1.B-樹

B-tree（多路搜索樹）是一種常見的數據結構。使用B-tree結構可以顯著減少定位記錄時所經歷的中間過程，從而加快存取速度。按照翻譯，B 通常認為是Balance的簡稱。這個數據結構一般用于數據庫的索引，綜合效率較高。

B-樹每個節點都存儲key和data，所有節點組成這棵樹，并且葉子節點指針為null。

 

B-樹的特征：

1. 根節點至少有兩個孩子

2. 每個非根節點有[ ,M]個孩；

3. 每個非根節點有[ -1,M-1]個關鍵字，并且以升序排列

4. key[i]和key[i+1]之間的孩子節點的值介于key[i]、key[i+1]之間

5. 所有的葉子節點都在同一層

B-樹的優勢：

B樹的優勢在于多路查找，這便是優于紅黑樹的具體原因，大家想一想，B-樹每個結點有多個key，而紅黑樹每個結點有一個key，那么隨著數據的不斷增多，紅黑樹的高度不斷增加，效率不斷降低，而B樹的高度一般都很低，為甚?因為B樹一個結點可以放N個key,，只有都滿了才分裂一次！B樹為什么會分裂呢？ 因為隨著數據的增多，一個結點的key滿了，為了保持B樹的特性，就會產生分裂，就像紅黑樹和AVL樹為了保持樹的性質需要進行旋轉是一樣一樣的！

2.B+樹

B+樹是B-樹的變體，也是一種多路搜索樹，其定義基本與B樹相同。B+樹上的葉子結點存儲關鍵字以及相應記錄的地址，葉子結點以上各層作為索引使用。

 

B+樹：只有葉子節點存儲data，葉子節點包含了這棵樹的所有鍵值，葉子節點不存儲指針。

B+樹的特征：

1. 所有關鍵字都出現在葉子結點的鏈表中（稠密索引），且鏈表中的關鍵字恰好是有序的；

2. 不可能在非葉子結點命中；

3. 非葉子結點相當于是葉子結點的索引（稀疏索引），葉子結點相當于是存儲（關鍵字）數據的數據層；

4. 更適合文件索引系統；

B+Tree與B-樹的不同：

1. 每個節點的指針上限為2d而不是2d+1；

2. 內節點不存儲data，只存儲key，即所有關鍵字都在葉子結點出現；

3. 葉子節點不存儲指針，而是為所有葉子結點增加一個鏈指針。

B+樹的優勢：

在B+樹上增加了順序訪問指針，也就是每個葉子節點增加一個指向相鄰葉子節點的指針，這樣一棵樹成了數據庫系統實現索引的首選數據結構。 原因有很多，最主要的是這棵樹矮胖，一般來說，索引很大，往往以索引文件的形式存儲的磁盤上，索引查找時產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的時間復雜度。樹高度越小，I/O次數越少。 那為什么是B+樹而不是B樹呢，因為它內節點不存儲data，這樣一個節點就可以存儲更多的key。

二、索引搜索速度的決定性因素是什么？

因為數據庫的大部分數據都是存在磁盤上面的，一般來說，索引本身也很大，不可能全部存儲在內存中，因此索引往往以索引文件的形式存儲的磁盤上。這樣的話，索引查找過程中就要產生磁盤I/O消耗，相對于內存存取，I/O存取的消耗要高幾個數量級，所以評價一個數據結構作為索引的優劣最重要的指標就是在查找過程中磁盤I/O操作次數的時間復雜度。樹高度越小，I/O次數越少。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。

二叉樹的高度過深進行多次磁盤IO，導致查詢效率低下，而B樹和B+樹樹中每個結點最多含有m個孩子，所以相對二叉樹，B-樹和B+樹的高度比較低，顯得又矮又胖！

三、MySQL中的存儲引擎

在MySQL中，最常用的兩個存儲引擎是MyISAM和InnoDB，它們是MySQL的兩代搜索引擎。

它們對索引的實現方式不同，MyISAM data存的是數據地址，索引和數據分開的。InnoDB data存的是數據本身，索引也是數據。

索引分為主索引和輔助索引：一般以主鍵為索引的叫做主索引，而以其他鍵為索引的叫做輔助索引。

四、MyISAM利用B+樹實現

主索引：

 

由上圖可以看出，col1是主鍵，而葉子結點存儲的數據是一個地址，通過地址找到數據。

輔助索引（和主索引不同的是輔助索引的key是可以重復的） :

 

五、InnoDB利用B+樹實現

主索引：

 

注意，和MyISAM不同的是葉子結點的數據域保存的是全部數據。

輔助索引：

 

仔細看輔助索引和主索引的區別，輔助索引的葉子結點保存的是主鍵；這就是MyISAM和InnoDB最大的不同。

六、InnoDB到底比MyISAM好在哪里？

既然MyISAM和InnoDB是MySQL的兩代引擎，肯定會有一個提升，而InnoDB是最新一代，那么它到底優在哪里？

試想，MyISAM和InnoDB都是以B+樹為基礎實現的，相對于B樹的不同其實前面已經講過，即數據域和結點分離；

而MyISAM更是索引和文件分離，B+樹的葉子結點的數據域存放的是文件內容的地址，主索引和輔助索引的B+樹都是如此，那么如果我改變了一個地址，是不是所有的索引樹都得改變，正如前面我們講的在磁盤上頻繁的讀寫操作是效率很低的，而這塊又不適用局部原理，因為邏輯上相鄰的結點，物理上不一定相鄰，那么這樣就會造成效率上的降低；

于是乎，InnoDB就產生了，它讓除了主索引以外的輔助索引的葉子結點的數據域都保存主鍵，先通過輔助索引找到主鍵，然后通過主鍵找到葉子結點的所有數據，聽起來貌似很麻煩，遍歷了兩棵樹，但是，這樣如果有了修改的話，改變的只是主索引，其它輔助縮印都不用動，而且，數據庫中的樹的每一個結點的key可不是咱們給的那么少，試想如果一個結點有1024個key，那么高度為2的B+樹都有1024*1024個key，所以一般樹的高度都很低，所以，遍歷樹的消耗幾乎忽略不計！

七、總結

1.為什么使用B+樹？

• 文件很大，不可能全部存儲在內存中，故要存儲到磁盤上

• 索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數（為什么使用B-/+Tree，還跟磁盤存取原理有關，具體看下邊分析）

• 局部性原理與磁盤預讀，預讀的長度一般為頁（page）的整倍數，（在許多操作系統中，頁得大小通常為4k）

• 數據庫系統巧妙利用了磁盤預讀原理，將一個節點的大小設為等于一個頁，這樣 每個節點只需要一次I/O 就可以完全載入，(由于節點中有兩個數組，所以地址連續)。而紅黑樹這種結構， h 明顯要深的多。由于邏輯上很近的節點（父子）物理上可能很遠，無法利用局部性。

2.為什么B+樹比B樹更適合做索引？

B+樹磁盤讀寫代價更低

B+的內部結點并沒有指向關鍵字具體信息的指針，即內部節點不存儲數據。因此其內部結點相對B 樹更小。如果把所有同一內部結點的關鍵字存放在同一盤塊中，那么盤塊所能容納的關鍵字數量也越多。一次性讀入內存中的需要查找的關鍵字也就越多。相對來說IO讀寫次數也就降低了。

B+-樹的查詢效率更加穩定

由于非終結點并不是最終指向文件內容的結點，而只是葉子結點中關鍵字的索引。所以任何關鍵字的查找必須走一條從根結點到葉子結點的路。所有關鍵字查詢的路徑長度相同，導致每一個數據的查詢效率相當。

3.MySQL兩種索引MyISAM和InnoDB的區別

• MyISAM是非事務安全的，而InnoDB是事務安全的

• MyISAM鎖的粒度是表級的，而InnoDB支持行級鎖

• MyISAM支持全文類型索引，而InnoDB不支持全文索引

• MyISAM相對簡單，效率上要優于InnoDB，小型應用可以考慮使用MyISAM

• MyISAM表保存成文件形式，跨平臺使用更加方便

• MyISAM管理非事務表，提供高速存儲和檢索以及全文搜索能力，如果在應用中執行大量select操作可選擇

• InnoDB用于事務處理，具有ACID事務支持等特性，如果在應用中執行大量insert和update操作，可選擇。