이번 글에서는 B+ 트리(B+ Tree)에 새로운 요소를 삽입하는 방법을 단계별로 살펴보겠습니다. 먼저 아래와 같은 형태의 B+ 트리가 이미 존재한다고 가정해 보겠습니다.
B+ 트리 예시
B+ 트리 삽입의 기본 원리
B+ 트리에 요소를 삽입하는 기본 아이디어는 B-트리와 매우 유사합니다. 가장 중요한 차이점은, 새로운 요소가 삽입되면 해당 요소는 반드시 리프 노드(leaf node)에 저장된다는 점입니다. 만약 그 값이 내부 노드(internal node)에도 색인으로 존재한다면, 리프 노드에는 자기 자신의 오른쪽 자식 위치에 동일한 값이 함께 유지됩니다.
예를 들어, 위 트리에 65를 삽입한다고 가정해 보겠습니다. 65는 60보다 크고 75보다 작으므로 가운데 서브트리로 향하게 됩니다. 그런 다음 65는 63이 있는 노드 뒤에 삽입되고, 해당 노드가 가득 차면 두 부분으로 분할(split)됩니다. 이때 65는 상위 노드로 올라가며(복사 업), 동시에 분할된 오른쪽 노드에도 그대로 남아 있게 됩니다.
65를 삽입한 후의 B+ 트리
삽입 알고리즘: BPlusTreeInsert(root, key)
입력: 트리의 루트(root) 노드와 삽입할 키(key)
키가 트리에 존재하지 않는다고 가정합니다.
루트 노드에서 시작하여 리프 노드에 도달할 때까지 키 'key'와 일치하는 경로를 따라 탐색합니다.
탐색 경로를 x1, x2, …, xh라고 하면, x1은 루트 노드이고 xh는 리프 노드입니다.
각 노드 xi는 xi+1의 부모 노드입니다.
키가 'key'이고 값이 v인 새 객체를 xh에 삽입합니다.
i := h
xi가 오버플로우(overflow)되는 동안 반복:
xi의 키 중 큰 절반을 새 노드 p로 옮겨 xi를 두 개의 노드로 분할합니다.
xi가 리프 노드라면, p를 리프 노드 간의 연결 리스트(linked list)에 연결합니다.
부모 레벨에 삽입할 키 k와 p를 가리키는 자식 포인터를 결정합니다.
k의 선택은 노드 xi의 유형에 따라 달라집니다. xi가 리프 노드라면 '복사 업(copy up)'을 수행하여
p에서 가장 작은 키를 k로 복사해 부모 레벨로 올립니다. 반면 xi가 비-리프(non-leaf) 노드라면
'푸시 업(push up)'을 수행하여, p에서 가장 작은 키를 부모 노드의 k로 실제로 옮깁니다.
만약 i = 0이라면,
키 k와 두 자식 xi, p를 저장하는 새로운 인덱스 노드를 생성하여 새 루트로 만듭니다.
반환(return)합니다.
그렇지 않으면,
키 k와 p를 가리키는 자식 포인터를 노드 xi-1에 삽입합니다.
i := i – 1
조건문 종료
반복문 종료
복사 업(Copy Up)과 푸시 업(Push Up)의 차이
B+ 트리 삽입에서 가장 헷갈리기 쉬운 부분이 바로 노드 분할 시 상위 레벨로 올려 보내는 키를 처리하는 방식입니다.
복사 업(Copy Up): 분할 대상이 리프 노드인 경우에 사용됩니다. 리프 노드의 모든 키는 실제 데이터를 가리켜야 하므로, 새 노드 p의 가장 작은 키를 부모로 복사하더라도 원본 키는 리프 노드에 그대로 남아 있어야 합니다. 앞선 예제에서 65가 부모로 올라가면서도 오른쪽 리프 노드에 계속 존재했던 것이 바로 이 때문입니다.
푸시 업(Push Up): 분할 대상이 내부(비-리프) 노드인 경우에 사용됩니다. 내부 노드의 키는 단순한 색인(index) 역할만 하므로, 새 노드 p의 가장 작은 키를 부모로 이동시켜도 데이터 검색에는 문제가 없습니다.
마무리
B+ 트리의 삽입 연산은 '리프 노드에 삽입 → 오버플로우 발생 시 분할 → 부모로 키 전달 → 필요하면 루트까지 반복'이라는 흐름으로 요약할 수 있습니다. 모든 레벨이 꽉 찬 최악의 경우에도 트리의 높이가 하나 증가할 뿐이므로, B+ 트리는 균형이 잘 유지되며 데이터베이스와 파일 시스템의 인덱스 구조로 널리 활용됩니다.