B+樹


B+樹是B樹的擴充套件,允許有效的插入,刪除和搜尋操作。

在B樹中,鍵和記錄都可以儲存在內部節點和葉子節點中。 然而,在B+樹中,記錄(資料)只能儲存在葉節點上,而內部節點只能儲存鍵值。

B+樹的葉節點以單連結串列的形式連結在一起,以使搜尋查詢更有效。

B+樹用於儲存無法儲存在主記憶體儲器中的大量資料。 由於主記憶體儲器的大小總是有限的事實,B+樹的內部節點(存取記錄的鍵)儲存在主記憶體儲器中,而葉節點儲存在輔助儲存器中。

B+樹的內部節點通常稱為索引節點。 B+樹的排序3,如下圖所示。

1. B+樹的優點

  • 可以在相同數量的磁碟存取中獲取記錄。
  • 樹高度保持平衡,與B樹相比較少。
  • 可以順序存取儲存在B+樹中的資料,也可以直接存取。
  • 鍵用於索引。
  • 更快的搜尋查詢,因為資料僅儲存在葉節點上。

2. B樹與B+樹比較

編號 B樹 B+樹
1 搜尋鍵無法重複儲存。 可以存在冗餘搜尋鍵。
2 資料可以儲存在葉節點以及內部節點中 資料只能儲存在葉節點上。
3 搜尋某些資料是一個較慢的過程,因為可以在內部節點和葉節點上找到資料。 搜尋速度相對較快,因為只能在葉節點上找到資料。
4 刪除內部節點非常複雜且耗時。 刪除永遠不會是一個複雜的過程,因為元素將始終從葉節點中刪除。
5 葉節點不能連結在一起。 葉節點連結在一起以使搜尋操作更有效。

3. B+樹插入操作

第1步 :將新節點作為葉節點插入。
第2步 :如果葉子沒有所需空間,則拆分節點並將中間節點複製到下一個索引節點。
第3步 :如果索引節點沒有所需空間,則拆分節點並將中間元素複製到下一個索引節點。

範例:

將值195插入到下圖所示的5階B+樹中。

190之後,將在右子樹120中插入195。將其插入所需位置。

該節點包含大於最大的元素數量,即4,因此將其拆分並將中間節點放置到父節點。

現在,索引節點包含6個子節點和5個違反B+樹屬性的鍵,因此需要將其拆分,如下所示。

4. B+樹刪除操作

第1步:從葉子中刪除鍵和資料。
第2步:如果葉節點包含少於最小數量的元素,則將節點與其兄弟節點合併,並刪除它們之間的鍵。
第3步:如果索引節點包含少於最小數量的元素,則將節點與兄弟節點合併,並在它們之間向下移動鍵。

範例

從下圖所示的B+樹中刪除鍵為200

195之後的190的右子樹中存在200,刪除它。

使用195,190,154129合併兩個節點。

現在,元素120是節點中存在的違反B+樹屬性的單個元素。 因此,需要使用60,78,108120來合併它。

現在,B+樹的高度將減1