Computer >> 컴퓨터 >  >> 프로그램 작성 >> 프로그램 작성

데이터 구조에서 B+ 트리 삭제

<시간/>

여기서는 B+ Tree에서 노드를 삭제하는 방법을 살펴보겠습니다. 7minus 이하와 같은 B+ 트리가 있다고 가정합니다.

B+ 트리의 예 -

데이터 구조에서 B+ 트리 삭제

삭제에는 두 부분이 있습니다. 먼저 요소를 찾아야 합니다. 그 전략은 쿼리와 같습니다. 이제 삭제를 위해 몇 가지 규칙에 주의해야 합니다. 하나의 노드에는 최소 m/2개의 요소가 있어야 합니다. 따라서 하나의 요소를 삭제하고 m-1개 미만의 요소가 남아 있으면 자동으로 조정됩니다. 전체 노드가 삭제되면 자식 노드가 병합되고 크기가 m과 같으면 두 부분으로 나누면 다시 중앙값이 올라갑니다.

78을 삭제한다고 가정합니다. 이제 두 개의 자식이 있습니다. [75, 77] 및 [78, 85], 그러면 먼저 리프 노드에서 78을 삭제한 다음 85를 가져와서 키 85의 복사본을 만들어 하위 트리의 루트로 만듭니다.

데이터 구조에서 B+ 트리 삭제

알고리즘

BPlusTreeDelete(x, 키) -

입력 - 트리의 루트, 삭제할 키

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