MySQL用B+樹(而不是B樹)做索引的原因

https://www.jianshu.com/p/7ce804f97967

眾所周知，MySQL的索引使用了B+樹的數據結構。那麼為什麼不用B樹呢？
先看一下B樹和B+樹的區別。

1.B樹

維基百科對B樹的定義為“在電腦科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序並允許以O(log n)的時間複雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多於2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B-樹為系統最優化大塊數據的讀和寫操作。B-tree演算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在資料庫和文件系統。”

B 樹可以看作是對2-3查找樹的一種擴展，即他允許每個節點有M-1個子節點。

1.1定義

• 根節點至少有兩個子節點
• 每個節點有M-1個key，並且以升序排列
• 位於M-1和M key的子節點的值位於M-1 和M key對應的Value之間

• 其它節點至少有M/2個子節點
  下圖是一個M=4 階的B樹:

  
    M=4的B樹
  

  可以看到B樹是2-3樹的一種擴展，他允許一個節點有多於2個的元素。

B樹的插入及平衡化操作和2-3樹很相似，這裡就不介紹了。下麵是往B樹中依次插入
6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4 的演示動畫：

2.B+樹

B+樹是對B樹的一種變形樹，它與B樹的差異在於：

• 有k個子結點的結點必然有k個關鍵碼。
• 非葉結點僅具有索引作用，跟記錄有關的信息均存放在葉結點中。

• 樹的所有葉結點構成一個有序鏈表，可以按照關鍵碼排序的次序遍歷全部記錄。
  如下圖是一個B+樹：

  
    M=4的B+樹
  

  下圖是B+樹的建立過程：

  
    Bplustreebuild.gif

B+樹和B樹的區別

B+樹的非葉子結點只包含導航信息，不包含實際的值，所有的葉子結點和相連的節點使用鏈表相連，便於區間查找和遍歷。
B+ 樹的優點在於：

• IO次數更少：由於B+樹在內部節點上不包含數據信息，因此在記憶體頁中能夠存放更多的key。 數據存放的更加緊密，具有更好的空間局部性。因此訪問葉子節點上關聯的數據也具有更好的緩存命中率。
• 遍歷更加方便：B+樹的葉子結點都是相鏈的，因此對整棵樹的遍歷只需要一次線性遍歷葉子結點即可。而且由於數據順序排列並且相連，所以便於區間查找和搜索。而B樹則需要進行每一層的遞歸遍歷。相鄰的元素可能在記憶體中不相鄰，所以緩存命中性沒有B+樹好。

但是B樹也有優點，其優點在於，由於B樹的每一個節點都包含key和value，因此經常訪問的元素可能離根節點更近，因此訪問也更迅速。下麵是B 樹和B+樹的區別圖:

為什麼MySQL選擇B+樹做索引

1、 B+樹的磁碟讀寫代價更低：B+樹的內部節點並沒有指向關鍵字具體信息的指針，因此其內部節點相對B樹更小，如果把所有同一內部節點的關鍵字存放在同一盤塊中，那麼盤塊所能容納的關鍵字數量也越多，一次性讀入記憶體的需要查找的關鍵字也就越多，相對IO讀寫次數就降低了。

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

3、B+樹更便於遍歷：由於B+樹的數據都存儲在葉子結點中，分支結點均為索引，方便掃庫，只需要掃一遍葉子結點即可，但是B樹因為其分支結點同樣存儲著數據，我們要找到具體的數據，需要進行一次中序遍歷按序來掃，所以B+樹更加適合在區間查詢的情況，所以通常B+樹用於資料庫索引。

4、B+樹更適合基於範圍的查詢：B樹在提高了IO性能的同時並沒有解決元素遍歷的我效率低下的問題，正是為瞭解決這個問題，B+樹應用而生。B+樹只需要去遍歷葉子節點就可以實現整棵樹的遍歷。而且在資料庫中基於範圍的查詢是非常頻繁的，而B樹不支持這樣的操作或者說效率太低。

參考