数据结构中的 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 次浏览

开启您的 职业

完成课程即可获得认证

开始吧
广告