1 簡介

B+樹與B樹相似, 也存在不同. 可以理解為把所有元素都放在葉子節點, 索引B樹化的樹.

B+樹的一些性質:

1. B+樹的節點分類: 內部節點(索引節點), 葉子節點.?如果只有根節點有元素, 那么其可以是內部節點也可以是葉子節點.

2. B+樹與B樹最大的不同是內部節點不保存數據, 只用與索引, 所有數據都放在葉子節點

3. 跟B樹相同的性質: m階B+樹每個節點(包括葉子節點和內部節點)最多有m-1個關鍵字

4. 節點內部的key同B樹相同, 也是從小到大排列, 對于內部節點的每個key, 其左樹中的所有key都小于該key, 右樹中的所有key都大于等于該key(注意是大于等于, 此處也是同B樹的不同)

5. 每個葉子節點都存有相鄰葉子節點的指針(雙向鏈表)

2 增刪操作

2.1 增加節點

跟B樹相同的是, 插入元素也是必須要插入葉子節點, 如果被插入的葉子節點的key數量達到階數, 葉子節點進行分裂, 然后中間的節點(索引為m / 2的, 從0開始)復制一份進入父節點(注意此處是與B樹的不同, B樹是移到父節點, 而不是復制). 當索引節點滿了時, 就按照B樹的方式, 移動到父節點.

舉例說明:

1. 空的5階B+樹, 插入5:

2. 再插入8, 10, 15:

3. 插入16:

3.1 插入該節點

3.2 此時該節點達到了階樹5, 那么進行分裂, 索引(5 / 2 = 2)的節點(key為10)復制到父節點成為內部節點, 而子節點從該key進行分裂(該節點進入右邊, 注意新的兩個葉子節點要連起來):

4. 插入17:

5. 插入18

5.1 直接插入:

5.2 節點key數量達到了5, 裂開, 6復制進入父節點:

6. 插入一些數據后:

7. 插入7:

7.1 直接插入, 此時該節點key數量達到了階數5:

7.2 裂開, 7進入父節點

7.3 父節點分裂, 此時不需要復制:

2.2 刪除操作

首先就是在葉子節點中找到要刪除的節點, 如果沒有找到, 那么刪除失敗. 找到之后, 先把目標節點拿掉, 再看拿掉之后的節點key的數量, 如果大于ceil(m - 1) / 2 - 1(以后用最小key數量代替), 那么刪除動作結束. 如果小于的話, 就需要進行接下來的操作. 如果該節點的兄弟節點key數量大于最小key數量, 那么就向其借一個key, 注意更新其索引節點的key. 如果兄弟節點key不大于最小key數量, 那么就將二者合并, 形成一個新的葉子節點, 并把兩者的父節點中多余的key刪除, 同時按照B樹刪除節點的方式遞歸向上刪除.

舉例說明:

1. 初始狀態:

2. 刪除22:

3. 刪除15

3.1 拿掉15:

3.2 發現此時節點key數量小于最小key數量?--- 2, 其兄弟節點有3個key, 大于2, 那么向其借用一個9, 并更新其父索引節點的key:

4. 刪除7

4.1 拿掉7:

4.2 其節點key小于2, 其兄弟節點key均為2, 沒有大于2, 所以就合并其與兄弟節點, 并刪除其父索引節點的key:

4.3 此時發現其父索引節點的key為1, 小于2, 那么就要按照B樹的方式, 其兄弟節點為2, 沒有大于2, 那么就將其父節點下移與該節點以及其兄弟節點合并:

總結

以上是生活随笔為你收集整理的B+树操作方式的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。