B+ 트리는 데이터베이스와 파일 시스템에서 널리 사용되는 균형 트리 자료구조입니다. 이 글에서는 B+ 트리에서 노드(키)를 삭제하는 방법을 단계별로 살펴보겠습니다.
B+ 트리 삭제의 기본 개념
삭제 연산은 크게 두 단계로 나눌 수 있습니다. 첫 번째는 삭제할 요소를 찾는 것입니다. 이 과정은 탐색(query)과 동일한 전략을 사용합니다. 두 번째는 실제로 요소를 제거하고 트리의 균형을 유지하는 것입니다.
삭제 시 반드시 지켜야 할 핵심 규칙이 있습니다. 바로 각 노드는 최소 m/2개의 요소를 가져야 한다는 것입니다. 따라서 요소를 하나 삭제했을 때 남은 요소 수가 m-1개 미만이 되면, 해당 노드는 스스로 조정(rebalancing) 작업을 수행해야 합니다.
만약 노드 전체가 삭제되어야 하는 상황이라면 그 자식 노드들이 병합됩니다. 병합 후 크기가 m과 같아지면 다시 두 부분으로 분할(split)하고, 중앙값(median)은 부모 노드로 올려보냅니다.
삭제 예제
아래와 같은 B+ 트리가 있다고 가정해 보겠습니다.
여기서 값 78을 삭제하고 싶다고 해봅시다. 현재 리프 노드는 [75, 77]과 [78, 85] 두 개입니다. 삭제 절차는 다음과 같습니다.
- 먼저 리프 노드에서 78을 삭제합니다.
- 그다음 형제 노드의 키 85를 가져와 복사본을 만듭니다.
- 복사한 키 85를 해당 서브트리의 루트(부모 노드) 위치에 배치합니다.
삭제 알고리즘
아래는 B+ 트리 삭제 알고리즘의 의사 코드입니다.
BPlusTreeDelete(x, key)
입력: 트리의 루트 노드와 삭제할 키
키가 리스트에 존재한다고 가정합니다.
루트 노드에서 시작하여, 리프 노드에 도달할 때까지 'key'와 정확히 일치하는 값을 탐색합니다.
탐색 경로를 x1, x2, …, xh라고 하면,
x1은 첫 번째 노드 즉 루트이고, xh는 리프 노드입니다.
각 노드 xi는 xi+1의 부모 노드입니다.
xh에서 'key'에 해당하는 객체를 삭제합니다.
만약 h = 1이면, 트리가 루트 하나뿐이므로 종료합니다.
i := h
xi가 언더플로우(underflow) 상태인 동안 반복:
xi의 인접 형제 노드 s가 최소 m/2 + 1개 이상의 요소를 가지고 있다면
s와 xi 사이에서 요소를 균등하게 재분배(redistribute)합니다.
재분배에 따라 부모 노드 x(i-1)의 키 k가 변경됩니다.
xi가 내부(비-리프) 노드라면
k는 아래로 끌어내려져 xi로 들어가고,
s의 키 하나가 위로 올라가 k의 자리를 채웁니다.
아니라면(리프 노드라면)
k는 단순히 s의 키로 교체됩니다.
종료(return)
아니라면
xi를 형제 노드 s와 병합(merge)합니다.
x(i-1)에서 해당 자식 포인터를 삭제합니다.
xi가 내부 노드라면
기존에 xi와 s를 나누던 x(i-1)의 키를
새로 병합된 노드로 끌어내립니다.
아니라면(리프 노드라면)
x(i-1)에서 해당 키를 삭제합니다.
i := i - 1
조건문 종료
반복 종료핵심 포인트 정리
- 탐색 우선: 삭제 전에 반드시 대상 키를 리프 노드까지 탐색해야 합니다.
- 최소 요소 수 유지: 모든 노드는 최소 ⌈m/2⌉개의 요소를 유지해야 합니다.
- 재분배 vs 병합: 형제 노드에 여유가 있으면 재분배하고, 없으면 병합합니다.
- 언더플로우 전파: 병합으로 인해 부모 노드도 언더플로우가 발생하면 루트 방향으로 위쪽으로 전파되며 처리됩니다.
이 알고리즘을 통해 B+ 트리는 삭제 연산 후에도 항상 균형 잡힌 상태를 유지하며, O(log n)의 시간 복잡도로 효율적인 삭제를 보장합니다.