B樹的學習

B樹也是B-tree,是一個多路平衡查找樹。描述一顆B樹需要指定它的階數，階數表示了一個節點最多有多少個孩子節點，一般用字母M表示階數。當M=2時，就是常見的二叉搜尋樹。

一顆M階的Btree的定義：

1）每個節點最多有m-1個關鍵字。

2）根節點最少可以隻有1個關鍵字。

3）非根節點至少有Math.ceil（m/2）-1個關鍵字。

4）每個節點中的關鍵字都按照從小到大的順序排列，每個關鍵字的左子樹中的所有關鍵字都小于它，而右子樹中的所有關鍵字都是大于他。

5）所有葉子節點都是位于同一層或者說根節點到葉子節點的長度都相同。

資料庫中的索引結構使用的就是B樹或者B+樹。B樹中的key表示鍵值。而data表示了這個鍵對應的條目再硬碟上的邏輯位址。

B-tree的插入操作：

插入操作就是插入一條記錄，即（key，value）的鍵值對，如果B樹種已經存在需要插入的鍵值對，則用需要插入的value替換舊的value。若B樹不存在這個key，則一定在葉子節點中進行插入操作。

1）根據要插入的key的值，找到葉子節點并插入。

2）判斷目前節點key的個數是否小于等于m-1，若滿足則結束，否則進行第三步。

3）以節點中間的key為中心分裂成左右兩部分，然後将這個中間的key插入到父節點中，這個key的左子樹指向分裂後的左半部分，這個key的右子支指向分裂後的右半部分，然後将目前節點指向父節點，繼續進行第三步。、

B樹的插入過程的動畫示範位址：

​ https://www.cs.usfca.edu/~galles/visualization/BTree.html​​

B樹的删除操作：

删除操作是指，根據key删除記錄，如果B樹種的記錄中不存在對應的key的記錄，則删除失敗。

1）如果目前需要删除的key位于非葉子節點上，則用後續key（這裡的後續key指的是後續記錄的意思）覆寫要删除的key，然後在後續key所在的子支中删除該後續的key，此時後續key一定位于子節點上。删除這個記錄後執行第2步。

2）該節點key個數大于等于Math.ceil(m/2)-1，結束删除操作，否則執行第三步。

3）如果兄弟節點key個數大于Math,ceil(m/2)-1,則父節點的key下移到該節點，兄弟節點的key上移，删除操作結束。否則，将父節點中的key下移與目前節點及它的兄弟節點的key合并，形成一個新的節點。原父節點中的key的兩個孩子指針就變成了一個孩子指針，指向這個新節點。然後目前節點的指針指向父節點，重複上第二步。

删除的動畫示範位址：

​ https://www.cs.usfca.edu/~galles/visualization/BTree.html​​

B+樹的定義

1）B+樹包含2中類型的節點：内部節點和子節點。根節點本身既可以是内部節點也可以是子節點。根節點的關鍵字個數最少可以隻有1個。

2）B+樹與B樹最大的不同是内部節點不儲存資料，隻有索引，所有資料都儲存在葉子節點中。

3）M階B+樹表示了内部節點最多有m-1個關鍵字，結束M同時限制了葉子節點最多存儲M-1個記錄。

4）内部節點中的key都按照從小到大的順序排列，對于内部節點中的一個key，左子樹的所有key都小于它，右子樹中的key都大于等于他。葉子節點中的記錄也是按照從小到大排列的，

5）每個葉子節點都存有相鄰葉子節點的指針，葉子本身的依賴關鍵字從小到大排列。

B+樹的插入操作

1）如果是空樹，建立一個葉子節點，然後将記錄插入其中，此時這個葉子節點也是根節點，插入操作結束。

2）針對葉子類型節點：根據Key值找到葉子節點，向這個葉子節點插入記錄。插入後，若目前節點key的個數小于等于m-1，則插入結束。否則将這個葉子節點分裂成左右兩個葉子節點，左葉子節點包含錢m/2個記錄，右節點包含剩下的記錄，将第m/2+1個記錄的key進位到父節點中（父節點一定是索引類型節點），進位到父節點的key左孩子指向左節點，右孩子指向右節點，然後循環執行第三步。

3）針對索引類型節點：若目前結點key的個數小于等于m-1，則插入結束。否則，将這個索引類型結點分裂成兩個索引結點，左索引結點包含前(m-1)/2個key，右結點包含m-(m-1)/2個key，将第m/2個key進位到父結點中，進位到父結點的key左孩子指向左結點, 進位到父結點的key右孩子指向右結點。将目前結點的指針指向父結點，然後重複第3步。、

動畫示範位址

​ https://www.cs.usfca.edu/~galles/visualization/BPlusTree.html​​