[TOC] ### B樹 ***** #### B樹定義 B樹也稱B-樹,它是一顆多路平衡查找樹。我們描述一顆B樹時需要指定它的階數，階數表示了一個結點最多有多少個孩子結點，一般用字母m表示階數。當m取2時，就是我們常見的二叉搜索樹。 ` ` 一顆m階的B樹定義如下： 1）每個結點最多有m-1個關鍵字。 2）根結點最少可以只有1個關鍵字。 3）非根結點至少有Math.ceil(m/2)-1個關鍵字。 4）每個結點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小于它，而右子樹中的所有關鍵字都大于它。 5）所有葉子結點都位于同一層，或者說根結點到每個葉子結點的長度都相同。 ` `  上圖是一顆階數為4的B樹。在實際應用中的B樹的階數m都非常大（通常大于100），所以即使存儲大量的數據，B樹的高度仍然比較小。每個結點中存儲了關鍵字（key）和關鍵字對應的數據（data），以及孩子結點的指針。**我們將一個key和其對應的data稱為一個記錄**。**但為了方便描述，除非特別說明，后續文中就用key來代替（key, value）鍵值對這個整體**。在數據庫中我們將B樹（和B+樹）作為索引結構，可以加快查詢速速，此時B樹中的key就表示鍵，而data表示了這個鍵對應的條目在硬盤上的邏輯地址。 ` ` #### B樹的基本操作 ***** ##### B樹的插入操作 插入操作是指插入一條記錄，即（key, value）的鍵值對。如果B樹中已存在需要插入的鍵值對，則用需要插入的value替換舊的value。若B樹不存在這個key,則一定是在葉子結點中進行插入操作。 1）根據要插入的key的值，找到葉子結點并插入。 2）判斷當前結點key的個數是否小于等于m-1，若滿足則結束，否則進行第3步。 3）以結點中間的key為中心分裂成左右兩部分，然后將這個中間的key插入到父結點中，這個key的左子樹指向分裂后的左半部分，這個key的右子支指向分裂后的右半部分，然后將當前結點指向父結點，繼續進行第3步。 ` ` 示例： ` ` ##### B樹的刪除操作： 刪除操作是指，根據key刪除記錄，如果B樹中的記錄中不存對應key的記錄，則刪除失敗。 1）如果當前需要刪除的key位于非葉子結點上，則用后繼key（這里的后繼key均指后繼記錄的意思）覆蓋要刪除的key，然后在后繼key所在的子支中刪除該后繼key。此時后繼key一定位于葉子結點上，這個過程和二叉搜索樹刪除結點的方式類似。刪除這個記錄后執行第2步 2）該結點key個數大于等于Math.ceil(m/2)-1，結束刪除操作，否則執行第3步。 3）如果兄弟結點key個數大于Math.ceil(m/2)-1，則父結點中的key下移到該結點，兄弟結點中的一個key上移，刪除操作結束。 ` ` 否則，將父結點中的key下移與當前結點及它的兄弟結點中的key合并，形成一個新的結點。原父結點中的key的兩個孩子指針就變成了一個孩子指針，指向這個新結點。然后當前結點的指針指向父結點，重復上第2步。 有些結點它可能即有左兄弟，又有右兄弟，那么我們任意選擇一個兄弟結點進行操作即可。 ` ` ### B+樹 ***** #### B+樹的定義 即關鍵字個數比孩子結點個數小1，這種方式是和B樹基本等價的。上圖就是一顆階數為4的B+樹。  B+樹的特點： 1）B+樹包含2種類型的結點：內部結點（也稱索引結點）和葉子結點。根結點本身即可以是內部結點，也可以是葉子結點。根結點的關鍵字個數最少可以只有1個。 2）B+樹與B樹最大的不同是內部結點不保存數據，只用于索引，所有數據（或者說記錄）都保存在葉子結點中。 3） m階B+樹表示了內部結點最多有m-1個關鍵字（或者說內部結點最多有m個子樹），階數m同時限制了葉子結點最多存儲m-1個記錄。 4）內部結點中的key都按照從小到大的順序排列，對于內部結點中的一個key，左樹中的所有key都**小于**它，右子樹中的key都**大于等于**它。葉子結點中的記錄也按照key的大小排列。 5）每個葉子結點都存有相鄰葉子結點的指針，葉子結點本身依關鍵字的大小自小而大順序鏈接。 ` ` #### B+樹的基本操作 ***** ##### B+樹的插入操作 1）若為空樹，創建一個葉子結點，然后將記錄插入其中，此時這個葉子結點也是根結點，插入操作結束。 2）針對葉子類型結點：根據key值找到葉子結點，向這個葉子結點插入記錄。插入后，若當前結點key的個數小于等于m-1，則插入結束。否則將這個葉子結點分裂成左右兩個葉子結點，左葉子結點包含前m/2個記錄，右結點包含剩下的記錄，將第m/2+1個記錄的key進位到父結點中（父結點一定是索引類型結點），進位到父結點的key左孩子指針向左結點,右孩子指針向右結點。將當前結點的指針指向父結點，然后執行第3步。 3）針對索引類型結點：若當前結點key的個數小于等于m-1，則插入結束。否則，將這個索引類型結點分裂成兩個索引結點，左索引結點包含前(m-1)/2個key，右結點包含m-(m-1)/2個key，將第m/2個key進位到父結點中，進位到父結點的key左孩子指向左結點, 進位到父結點的key右孩子指向右結點。將當前結點的指針指向父結點，然后重復第3步。 ##### B+樹的刪除操作 如果葉子結點中沒有相應的key，則刪除失敗。否則執行下面的步驟 1）刪除葉子結點中對應的key。刪除后若結點的key的個數大于等于Math.ceil(m-1)/2 – 1，刪除操作結束,否則執行第2步。 2）若兄弟結點key有富余（大于Math.ceil(m-1)/2 – 1），向兄弟結點借一個記錄，同時用借到的key替換父結（指當前結點和兄弟結點共同的父結點）點中的key，刪除結束。否則執行第3步。 3）若兄弟結點中沒有富余的key,則當前結點和兄弟結點合并成一個新的葉子結點，并刪除父結點中的key（父結點中的這個key兩邊的孩子指針就變成了一個指針，正好指向這個新的葉子結點），將當前結點指向父結點（必為索引結點），執行第4步（第4步以后的操作和B樹就完全一樣了，主要是為了更新索引結點）。 4）若索引結點的key的個數大于等于Math.ceil(m-1)/2 – 1，則刪除操作結束。否則執行第5步 5）若兄弟結點有富余，父結點key下移，兄弟結點key上移，刪除結束。否則執行第6步 6）當前結點和兄弟結點及父結點下移key合并成一個新的結點。將當前結點指向父結點，重復第4步。 >注意，通過B+樹的刪除操作后，索引結點中存在的key，不一定在葉子結點中存在對應的記錄。 ### 應用場景