이번 글에서는 B-트리(B-Tree)에 새로운 요소를 삽입하는 방법을 자세히 살펴보겠습니다. 아래와 같은 B-트리가 있다고 가정해 봅시다.
B-트리 예시
B-트리 삽입의 기본 원리
요소를 삽입하는 과정은 이진 탐색 트리(BST)와 매우 유사하지만, 반드시 지켜야 할 몇 가지 규칙이 있습니다. B-트리에서 각 노드는 최대 m개의 자식 노드를 가질 수 있으며, m-1개의 키(요소)를 저장합니다.
새로운 요소를 특정 노드에 삽입할 때는 두 가지 상황으로 나눌 수 있습니다.
- 노드가 가득 차지 않은 경우: 노드가 가진 키의 개수가 m-1개 미만이라면, 새 요소를 해당 노드에 바로 삽입하면 됩니다.
- 노드가 가득 찬 경우: 노드가 이미 m-1개의 키를 가지고 있다면, 기존 키들과 삽입할 키를 모두 모아 중앙값(median)을 구합니다. 이 중앙값은 부모 노드로 올려보내며(부모도 같은 기준으로 처리), 나머지 키들은 중앙값을 기준으로 왼쪽 절반과 오른쪽 절반으로 나누어 두 개의 독립된 노드를 생성합니다.
삽입 예제: 79 삽입하기
이제 위 트리에 79를 삽입해 보겠습니다.
- 먼저 79를 루트 노드의 값과 비교합니다. 79는 56보다 크므로 가장 오른쪽 서브트리로 이동합니다.
- 그다음 81과 비교하면 79가 더 작으므로 왼쪽 서브트리로 내려갑니다.
- 해당 리프 노드에 79를 삽입하면 노드에는 세 개의 키 [66, 78, 79]가 존재하게 됩니다. 하지만 노드가 가득 찼으므로 분할이 필요합니다.
- 중앙값은 78입니다. 따라서 78은 부모 노드로 올라가고, 부모 노드는 [78, 81] 형태가 됩니다.
- 나머지 키들은 두 개의 노드로 분할되어 하나는 66을, 다른 하나는 79를 저장합니다.
79 삽입 후의 B-트리
삽입 알고리즘
BTreeInsert(root, key)
입력: 트리의 루트 노드와 삽입할 키. 단, 삽입하려는 키는 트리에 이미 존재하지 않는다고 가정합니다.
x := 루트 노드 읽기
if x가 가득 찼다면 then
y := 새로운 노드 생성
z := 새로운 노드 생성
x에 저장된 객체 중 중앙 객체 oi의 위치를 찾고,
oi보다 왼쪽에 있는 객체들을 노드 y로 이동
oi보다 오른쪽에 있는 객체들을 노드 z로 이동
만약 x가 인덱스 노드라면, 자식 포인터들도 적절히 재배치
x->child[1] := y의 주소
x->child[2] := z의 주소
end if