B-트리(B-Tree) 삭제 연산 완벽 정리: 원리와 알고리즘

B-트리에서 노드 삭제하는 방법

이번 글에서는 B-트리(B-Tree)에서 노드를 삭제(delete)하는 과정을 자세히 살펴보겠습니다. 아래와 같은 B-트리가 있다고 가정해 봅시다.

B-트리 예시

삭제 연산의 기본 규칙

삭제 연산은 크게 두 단계로 나뉩니다. 첫 번째 단계는 삭제할 요소(element)를 탐색하는 것으로, 이 과정은 일반적인 검색(querying) 방식과 동일합니다.

두 번째 단계인 실제 삭제에서는 다음과 같은 규칙을 반드시 지켜야 합니다.

하나의 노드는 최소한 m/2개의 요소를 유지해야 합니다.
삭제 후 남은 요소 수가 m/2개보다 적어지면, 해당 노드는 스스로 재조정(rebalancing)을 수행합니다.
노드 전체가 삭제되는 경우에는 그 자식 노드들이 병합됩니다.
병합된 결과 노드의 크기가 m과 같아지면, 다시 두 부분으로 분할(split)하고 중앙값(median)은 상위 노드로 올려 보냅니다.

삭제 예시: 키 46 삭제하기

예를 들어 키 46을 삭제한다고 가정해 보겠습니다. 46이 삭제되면 두 개의 자식 노드인 [45]와 [47, 49]가 하나로 병합되어 [45, 47, 49]가 됩니다. 이때 병합된 노드의 중앙값인 47이 상위 노드로 승격됩니다.

B-트리(B-Tree) 삭제 연산 완벽 정리: 원리와 알고리즘

B-트리 삭제 알고리즘

BTreeDelete(x, key)

입력(Input): 트리의 루트(root) 노드 x와 삭제할 키(key)
키는 항상 리스트에 존재한다고 가정합니다.

if x가 리프(leaf) 노드이면,
    x에서 키 'key'에 해당하는 객체를 삭제
else if x에 키 'key'를 가진 객체가 없으면,
    'key'의 범위를 포함하는 자식 노드 x->child[i]를 찾음
    y := x->child[i]
    if y가 m/2개의 요소를 가지면,
        y의 바로 왼쪽 또는 오른쪽 형제(sibling) 노드 z가
        m/2개보다 많은 객체를 가지고 있다면,
        x->key[i]를 x에서 y로 이동하여 객체를 하나 추가하고,
        z의 마지막(또는 첫 번째) 객체를 x로 이동시킴.
        y가 리프가 아니라면 z의 마지막(또는 첫 번째)
        자식 포인터도 y로 이동시킴
    else
        y의 인접한 어떤 형제도 m/2개의 요소만 가진다면,
        y와 인접 형제 노드를 병합(merge)
    end if
    BTreeDelete(y, key)   // 재귀 호출
else
    if x에서 'key' 앞에 위치한 자식 y가 최소 m/2 + 1개의 객체를 가지면,
        y를 루트로 하는 서브트리에서 'key'의 선행자(predecessor) k를 찾고,
        해당 서브트리에서 k를 재귀적으로 삭제한 뒤,
        x의 key를 k로 교체
    else if y가 m/2개의 요소를 가지면,
        x에서 'key' 바로 뒤를 따르는 자식 z를 확인
        if z가 최소 m/2 + 1개의 요소를 가지면,
            z를 루트로 하는 서브트리에서 'key'의 후임자(successor) k를 찾고,
            해당 서브트리에서 k를 재귀적으로 삭제한 뒤,
            x의 key를 k로 교체
    else
        y와 z 모두 m/2개의 요소만 가진다면,
        두 노드를 하나로 병합하고 'key'도 새 노드로 내림.
        이후 새 노드에서 'key'를 재귀적으로 삭제
    end if
end if

핵심 정리

B-트리의 삭제 연산은 단순히 값을 제거하는 것이 아니라, 최소 요소 수(m/2) 유지, 형제 노드 간 재분배, 노드 병합 및 분할이라는 세 가지 메커니즘을 통해 트리의 균형을 유지합니다. 이러한 과정 덕분에 B-트리는 데이터베이스와 파일 시스템에서 대용량 데이터를 효율적으로 관리할 수 있는 핵심 자료구조로 널리 사용되고 있습니다.