B樹

B樹是一種專用的M階樹，可廣泛用於磁碟存取。 M階樹順序的B樹最多可以有m-1個鍵和M個子樹。 使用B樹的主要原因之一是它能夠在單個節點中儲存大量鍵，並且通過保持樹的高度相對較小來儲存大鍵值。

排序M的B樹包含M階樹的所有屬性。 此外，它還包含以下屬性。

• B樹中的每個節點最多包含m個子節點。
• 除根節點和葉節點外，B樹中的每個節點至少包含m/2個子節點。
• 根節點必須至少有2個節點。
• 所有葉節點必須處於同一級別。

所有節點都不必包含相同數量的子節點，但每個節點必須具有m/2個節點數。

在下圖中顯示了4階B樹。

在B樹上執行某些操作時，B樹的任何屬性都可能違反節點可以擁有的最小子節點數。 為了維護B 樹的屬性，樹可能會分裂或連線。

操作

1. 搜尋

在B樹中搜尋類似於二元搜尋樹中的搜尋。 例如，如果在以下B樹中搜尋資料項：49。 該過程將如下所示：

• 將資料項49與根節點78進行比較。因為49 <78因此，移動到其左子樹。
• 因為，40 <49 <56，遍歷右子樹40。
• 49> 45，向右移動。 比較49。
• 找到匹配，則返回。

在B樹中搜尋取決於樹的高度。 搜尋演算法需要O(log n)時間來搜尋B樹中的任何元素。

2. 插入

插入在葉節點級別完成。要將專案插入B樹，需要遵循以下演算法。

• 遍歷B樹以找到可插入節點的適當葉節點。
• 如果葉節點包含少於m-1個鍵，則按遞增順序插入元素。
• 否則，如果葉節點包含m-1個鍵，則按照以下步驟操作。
  • 按元素的遞增順序插入新元素。
  • 將節點拆分為中間的兩個節點。
  • 將中值元素推播到其父節點。
  • 如果父節點還包含m-1個鍵，則按照相同的步驟將其拆分。

範例：

將節點8插入到下圖所示的5階B樹中。

8將插入5的右側，因此插入8。

該節點現在包含5個鍵，大於(5 -1 = 4)個鍵。 因此，將節點從中間分開，即8，並將其推到其父節點，如下所示。

3. 刪除

還在葉節點處執行刪除。 要刪除的節點可以是葉節點或內部節點。 需要遵循以下演算法才能從B樹中刪除節點。

• 找到葉節點。
• 如果葉節點中有多於m/2個鍵，則從節點中刪除所需的鍵。

• 如果葉節點不包含m/2個鍵，則通過從8個或左兄弟中獲取元素來完成鍵。

  • 如果左側兄弟包含多於m/2個元素，則將其最大元素推播到其父元素，並將插入元素向下移動到刪除鍵的節點。
  • 如果右側兄弟包含多於m/2個元素，則將其最小元素向上推播到父節點，並將插入元素向下移動到刪除鍵的節點。

• 如果兄弟節點都不包含多於m/2個元素，則通過連線兩個葉節點和父節點的插入元素來建立新的葉節點。

• 如果父節點的節點少於m/2，那麼也應在父節點上應用上述過程。
• 如果要刪除的節點是內部節點，則將節點替換為其有序後繼或前一個節點。 由於後繼或前任將始終位於葉節點上，因此該過程將類似於從葉節點中刪除節點。

範例1

從下圖所示的5階B樹中刪除節點：53。

元素49的右子節點中存在53，則刪除它。

現在，57是唯一留在節點中的元素，在5階B樹中必須存在的最小元素數是2。它小於左邊和右邊子樹中的元素 因此，也不足以將其與父母的左兄弟和干預元素合併，即49。

最終的B樹如下所示。

B樹的應用

B樹用於索引資料並提供對儲存在磁碟上的實際資料的快速存取，因為儲存在磁碟上的大型資料庫中儲存的值的存取是非常耗時的過程。
在最壞的情況下，搜尋包含n個鍵值的未索引和未排序的資料庫需要O(n)執行時間。 但是，如果使用B樹來索引此資料庫，則在最壞的情況下將在O(log n)時間內搜尋它。