資料結構中的 B+ 樹刪除

在此，我們將介紹如何從 B+ 樹中刪除節點。假設我們有一個 B+ 樹，如下所示 7minus;

B+ 樹示例 −

刪除有兩個部分。首先，我們必須找到該元素。該策略類似於查詢。現在對於刪除，我們必須注意一些規則。一個節點必須至少有 m/2 個元素。因此，如果我們刪除一個元素，並且剩餘元素不足 m-1 個，則它會自行調整。如果整個節點被刪除，則其子節點將被合併，如果其大小與 m 相同，則將其分成兩部分，並且中值將再次向上移動。

假設我們想要刪除 78。現在有兩個子節點。[75, 77] 和 [78, 85]，然後它將首先從葉節點中刪除 78，其次，獲取 85，並複製鍵 85，並將其作為子樹的根節點。

演算法

BPlusTreeDelete(x, key) −

輸入 - 樹的根節點，以及要刪除的鍵

We will assume, that the key is present into the list
Start from root node, perform exact match for key as ‘key’ till a leaf node. Let the search path
be x1, x2, … , xh. The x1 is first node so root, then xh is leaf node. Each node xi is parent of xi+1
delete the object where key is ‘key’ from xh.
if h = 1, then return, as there is only one node which is root.
i := h
while xi underflows, do
   if immediate sibling node s of xi, has at least m/2 + 1 elements, then
      redistribute entries evenly between s and xi.
      corresponding to redistribution, a key k in the parent node xi-1, will be changed.
      if xi is non-leaf node, then
         k is dragged down to xi. and a key from s is pushed up to fill the place of k
      else
         k is simply replaced by a key in s
      return
   else
      merge xi with the sibling node s. Delete the corresponding child pointer in xi-1.
      if xi is an internal node, then
         drag the key in xi-1. which is previously divides xi and s. into the new node
         xi and s, into the new node xi.
      else
         delete that key in xi-1.
      i := i – 1
   end if
done

更新於: 11-Aug-2020

727 次瀏覽

開啟您的 職業

完成課程即可獲得認證

開始吧
廣告