B樹與B+樹的差別一、使用B-樹的好處二、B-樹深入三、B-樹的查找四、B+ 樹五、B-樹和B+樹的差別六、使用B+樹的好處七、拓展：MySQL為什麼使用B-Tree（B+Tree）&& 存儲知識

文章目錄

• 一、使用B-樹的好處
• 二、B-樹深入
• 三、B-樹的查找
• 四、B+ 樹
• 五、B-樹和B+樹的差別
• • • ①B+樹内節點不存儲資料，所有 data 存儲在葉節點導緻查詢時間複雜度固定為 log n。而B-樹查詢時間複雜度不固定，與 key 在樹中的位置有關，最好為O(1)。
    • ② B+樹葉節點兩兩相連可大大增加區間通路性，可使用在範圍查詢等，而B-樹每個節點 key 和 data 在一起，則無法區間查找。
    • ③B+樹更适合外部存儲。由于内節點無 data 域，每個節點能索引的範圍更大更精确
• 六、使用B+樹的好處
• 七、拓展：MySQL為什麼使用B-Tree（B+Tree）&& 存儲知識

• 在B樹中，你可以将鍵和值存放在内部節點和葉子節點；但在B+樹中，内部節點都是鍵，沒有值，葉子節點同時存放鍵和值。
• B+樹的葉子節點有一條鍊相連，而B樹的葉子節點各自獨立。

  

一、使用B-樹的好處

B樹可以在内部節點同時存儲鍵和值，是以，把頻繁通路的資料放在靠近根節點的地方将會大大提高熱點資料的查詢效率。這種特性使得B樹在特定資料重複多次查詢的場景中更加高效。

B-樹,這裡的 B 表示 balance( 平衡的意思),B-樹是一種多路自平衡的搜尋樹（B樹是一顆多路平衡查找樹）它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節點有更多的子節點。下圖是 B-樹的簡化圖.

B-樹有如下特點:

• 所有鍵值分布在整顆樹中（索引值和具體data都在每個節點裡）；
• 任何一個關鍵字出現且隻出現在一個結點中；
• 搜尋有可能在非葉子結點結束（最好情況O(1)就能找到資料）；
• 在關鍵字全集内做一次查找,性能逼近二分查找；

二、B-樹深入

B樹由來:

定義：B-樹是一類樹，包括B-樹、B+樹、B*樹等，是一棵自平衡的搜尋樹，它類似普通的平衡二叉樹，不同的一點是B-樹允許每個節點有更多的子節點。

B-樹是專門為外部存儲器設計的，如磁盤，它對于讀取和寫入大塊資料有良好的性能，是以一般被用在檔案系統及資料庫中。

定義隻需要知道B-樹允許每個節點有更多的子節點即可（多叉樹）。子節點數量一般在上千，具體數量依賴外部存儲器的特性。

先來看看為什麼會出現B-樹這類資料結構：

傳統用來搜尋的平衡二叉樹有很多，如 AVL 樹，紅黑樹等。這些樹在一般情況下查詢性能非常好，但當資料非常大的時候它們就無能為力了。原因當資料量非常大時，記憶體不夠用，大部分資料隻能存放在磁盤上，隻有需要的資料才加載到記憶體中。一般而言記憶體通路的時間約為 50 ns，而磁盤在 10 ms 左右。速度相差了近 5 個數量級，磁盤讀取時間遠遠超過了資料在記憶體中比較的時間。這說明程式大部分時間會阻塞在磁盤 IO 上。那麼我們如何提高程式性能？減少磁盤 IO 次數，像 AVL 樹，紅黑樹這類平衡二叉樹從設計上無法“迎合”磁盤。

上圖是一顆簡單的平衡二叉樹，平衡二叉樹是通過旋轉來保持平衡的，而旋轉是對整棵樹的操作，若隻有部分加載到記憶體中則無法完成旋轉操作。

其次平衡二叉樹的高度相對較大為 log n（底數為2），這樣邏輯上很近的節點實際可能非常遠，無法很好的利用磁盤預讀（局部性原理），是以這類平衡二叉樹在資料庫和檔案系統上的選擇就被 pass 了。

空間局部性原理：如果一個存儲器的某個位置被通路，那麼将它附近的位置也會被通路。

我們從“迎合”磁盤的角度來看看B-樹的設計:

索引的效率依賴與磁盤 IO 的次數，快速索引需要有效的減少磁盤 IO 次數，如何快速索引呢？索引的原理其實是不斷的縮小查找範圍，就如我們平時用字典查單詞一樣，先找首字母縮小範圍，再第二個字母等等。平衡二叉樹是每次将範圍分割為兩個區間。

為了更快，B-樹每次将範圍分割為多個區間，區間越多，定位資料越快越精确。那麼如果節點為區間範圍，每個節點就較大了。是以建立節點時，直接申請頁大小的空間（磁盤存儲機關是按 block 分的，一般為 512 Byte。磁盤 IO 一次讀取若幹個 block，我們稱為一頁，具體大小和作業系統有關，一般為 4 k，8 k或 16 k），計算機記憶體配置設定是按頁對齊的，這樣就實作了一個節點隻需要一次 IO。

上圖是一棵簡化的B-樹，多叉的好處非常明顯，有效的降低了B-樹的高度，為底數很大的 log n，底數大小與節點的子節點數目有關，一般一棵B-樹的高度在 3 層左右。層數低，每個節點區确定的範圍更精确，範圍縮小的速度越快（比二叉樹深層次的搜尋肯定快很多）。上面說了一個節點需要進行一次 IO，那麼總 IO 的次數就縮減為了 log n 次。B-樹的每個節點是 n 個有序的序列(a1,a2,a3…an)，并将該節點的子節點分割成 n+1 個區間來進行索引(X1< a1, a2 < X2 < a3, … , an+1 < Xn < anXn+1 > an)。

點評：B樹的每個節點，都是存多個值的，不像二叉樹那樣，一個節點就一個值，B樹把每個節點都給了一點的範圍區間，區間更多的情況下，搜尋也就更快了，比如：有1-100個數，二叉樹一次隻能分兩個範圍，0-50和51-100，而B樹，分成4個範圍 1-25， 25-50，51-75，76-100一次就能篩選走四分之三的資料。是以作為多叉樹的B樹是更快的

三、B-樹的查找

我們來看看B-樹的查找，假設每個節點有 n 個 key值，被分割為 n+1 個區間，注意，每個 key 值緊跟着 data 域，這說明B-樹的 key 和 data 是聚合在一起的。一般而言，根節點都在記憶體中，B-樹以每個節點為一次磁盤 IO。

比如上圖中，若搜尋 key 為 25 節點的 data，首先在根節點進行二分查找（因為 keys 有序，二分最快），判斷 key 25 小于 key 50，是以定位到最左側的節點，此時進行一次磁盤 IO，将該節點從磁盤讀入記憶體，接着繼續進行上述過程，直到找到該 key 為止。

Data* BTreeSearch(Root *node, Key key)
{
    Data* data;

    if(root == NULL)
        return NULL;
    data = BinarySearch(node);
    if(data->key == key)
    {
        return data;
    }else{
        node = ReadDisk(data->next);
        BTreeSearch(node, key);
    }
}

           

四、B+ 樹

B+樹是B-樹的變體，也是一種多路搜尋樹, 它與 B- 樹的不同之處在于:

• 所有關鍵字存儲在葉子節點出現,内部節點(非葉子節點并不存儲真正的 data)。
• 為所有葉子結點增加了一個鍊指針。

簡化 B+樹 如下圖：

因為内節點并不存儲 data，是以一般B+樹的葉節點和内節點大小不同，而B-樹的每個節點大小一般是相同的，為一頁。

為了增加 區間通路性，一般會對B+樹做一些優化。

如下圖帶順序通路的B+樹。

五、B-樹和B+樹的差別

①B+樹内節點不存儲資料，所有 data 存儲在葉節點導緻查詢時間複雜度固定為 log n。而B-樹查詢時間複雜度不固定，與 key 在樹中的位置有關，最好為O(1)。

如下所示B-樹/B+樹查詢節點 key 為 50 的 data。

從上圖可以看出，key 為 50 的節點就在第一層，B-樹隻需要一次磁盤 IO 即可完成查找。是以說B-樹的查詢最好時間複雜度是 O(1)。

由于B+樹所有的 data 域都在根節點，是以查詢 key 為 50的節點必須從根節點索引到葉節點，時間複雜度固定為 O(log n)。

點評：B樹的由于每個節點都有key和data，是以查詢的時候可能不需要O(logn)的複雜度，甚至最好的情況是O(1)就可以找到資料，而B+樹由于隻有葉子節點儲存了data，是以必須經曆O(logn)複雜度才能找到資料

② B+樹葉節點兩兩相連可大大增加區間通路性，可使用在範圍查詢等，而B-樹每個節點 key 和 data 在一起，則無法區間查找。

根據空間局部性原理：如果一個存儲器的某個位置被通路，那麼将它附近的位置也會被通路。

B+樹可以很好的利用局部性原理，若我們通路節點 key為 50，則 key 為 55、60、62 的節點将來也可能被通路，我們可以利用磁盤預讀原理提前将這些資料讀入記憶體，減少了磁盤 IO 的次數。當然B+樹也能夠很好的完成範圍查詢。比如查詢 key 值在 50-70 之間的節點。

點評：由于B+樹的葉子節點的資料都是使用連結清單連接配接起來的，而且他們在磁盤裡是順序存儲的，是以當讀到某個值的時候，磁盤預讀原理就會提前把這些資料都讀進記憶體，使得範圍查詢和排序都很快。

③B+樹更适合外部存儲。由于内節點無 data 域，每個節點能索引的範圍更大更精确

這個很好了解，由于B-樹節點内部每個 key 都帶着 data 域，而B+樹節點隻存儲 key 的副本，真實的 key 和 data 域都在葉子節點存儲。前面說過磁盤是分 block 的，一次磁盤 IO 會讀取若幹個 block，具體和作業系統有關，那麼由于磁盤 IO 資料大小是固定的，在一次 IO 中，單個元素越小，量就越大。這就意味着B+樹單次磁盤 IO 的資訊量大于B-樹，從這點來看B+樹相對B-樹磁盤 IO 次數少。

點評：由于B樹的節點都存了key和data，而B+樹隻有葉子節點存data，非葉子節點都隻是索引值，沒有實際的資料，這就時B+樹在一次IO裡面，能讀出的索引值更多。進而減少查詢時候需要的IO次數！

從上圖可以看出相同大小的區域，B-樹僅有 2 個 key，而B+樹有 3 個 key。

六、使用B+樹的好處

由于B+樹的内部節點隻存放鍵，不存放值，是以，一次讀取，可以在記憶體頁中擷取更多的鍵，有利于更快地縮小查找範圍。 B+樹的葉節點由一條鍊相連，是以，當需要進行一次全資料周遊的時候，B+樹隻需要使用O(logN)時間找到最小的一個節點，然後通過鍊進行O(N)的順序周遊即可。而B樹則需要對樹的每一層進行周遊，這會需要更多的記憶體置換次數，是以也就需要花費更多的時間

七、拓展：MySQL為什麼使用B-Tree（B+Tree）&& 存儲知識

上文說過，紅黑樹等資料結構也可以用來實作索引，但是檔案系統及資料庫系統普遍采用B-/+Tree作為索引結構，這一節将結合計算機組成原理相關知識讨論B-/+Tree作為索引的理論基礎。

一般來說，索引本身也很大，不可能全部存儲在記憶體中，是以索引往往以索引檔案的形式存儲的磁盤上。這樣的話，索引查找過程中就要産生磁盤I/O消耗，相對于記憶體存取，I/O存取的消耗要高幾個數量級，是以評價一個資料結構作為索引的優劣最重要的名額就是在查找過程中磁盤I/O操作次數的漸進複雜度。換句話說，索引的結構組織要盡量減少查找過程中磁盤I/O的存取次數。

下面先介紹記憶體和磁盤存取原理，然後再結合這些原理分析B-/+Tree作為索引的效率。