여기서는 B+ Tree에서 노드를 삭제하는 방법을 살펴보겠습니다. 7minus 이하와 같은 B+ 트리가 있다고 가정합니다.
B+ 트리의 예 -
삭제에는 두 부분이 있습니다. 먼저 요소를 찾아야 합니다. 그 전략은 쿼리와 같습니다. 이제 삭제를 위해 몇 가지 규칙에 주의해야 합니다. 하나의 노드에는 최소 m/2개의 요소가 있어야 합니다. 따라서 하나의 요소를 삭제하고 m-1개 미만의 요소가 남아 있으면 자동으로 조정됩니다. 전체 노드가 삭제되면 자식 노드가 병합되고 크기가 m과 같으면 두 부분으로 나누면 다시 중앙값이 올라갑니다.
78을 삭제한다고 가정합니다. 이제 두 개의 자식이 있습니다. [75, 77] 및 [78, 85], 그러면 먼저 리프 노드에서 78을 삭제한 다음 85를 가져와서 키 85의 복사본을 만들어 하위 트리의 루트로 만듭니다.
알고리즘
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