B+樹是B樹的擴充套件,允許有效的插入,刪除和搜尋操作。
在B樹中,鍵和記錄都可以儲存在內部節點和葉子節點中。 然而,在B+樹中,記錄(資料)只能儲存在葉節點上,而內部節點只能儲存鍵值。
B+樹的葉節點以單連結串列的形式連結在一起,以使搜尋查詢更有效。
B+樹用於儲存無法儲存在主記憶體儲器中的大量資料。 由於主記憶體儲器的大小總是有限的事實,B+樹的內部節點(存取記錄的鍵)儲存在主記憶體儲器中,而葉節點儲存在輔助儲存器中。
B+樹的內部節點通常稱為索引節點。 B+樹的排序3,如下圖所示。
編號 | B樹 | B+樹 |
---|---|---|
1 | 搜尋鍵無法重複儲存。 | 可以存在冗餘搜尋鍵。 |
2 | 資料可以儲存在葉節點以及內部節點中 | 資料只能儲存在葉節點上。 |
3 | 搜尋某些資料是一個較慢的過程,因為可以在內部節點和葉節點上找到資料。 | 搜尋速度相對較快,因為只能在葉節點上找到資料。 |
4 | 刪除內部節點非常複雜且耗時。 | 刪除永遠不會是一個複雜的過程,因為元素將始終從葉節點中刪除。 |
5 | 葉節點不能連結在一起。 | 葉節點連結在一起以使搜尋操作更有效。 |
第1步 :將新節點作為葉節點插入。
第2步 :如果葉子沒有所需空間,則拆分節點並將中間節點複製到下一個索引節點。
第3步 :如果索引節點沒有所需空間,則拆分節點並將中間元素複製到下一個索引節點。
範例:
將值195
插入到下圖所示的5階B+樹中。
在190
之後,將在右子樹120
中插入195
。將其插入所需位置。
該節點包含大於最大的元素數量,即4
,因此將其拆分並將中間節點放置到父節點。
現在,索引節點包含6
個子節點和5
個違反B+樹屬性的鍵,因此需要將其拆分,如下所示。
第1步:從葉子中刪除鍵和資料。
第2步:如果葉節點包含少於最小數量的元素,則將節點與其兄弟節點合併,並刪除它們之間的鍵。
第3步:如果索引節點包含少於最小數量的元素,則將節點與兄弟節點合併,並在它們之間向下移動鍵。
範例
從下圖所示的B+樹中刪除鍵為200
。
在195
之後的190
的右子樹中存在200
,刪除它。
使用195
,190
,154
和129
合併兩個節點。
現在,元素120
是節點中存在的違反B+樹屬性的單個元素。 因此,需要使用60
,78
,108
和120
來合併它。
現在,B+
樹的高度將減1
。