B 트리란? (feat, 검색, 삽입, 삭제 과정)

이리·2025년 4월 24일

쌓다보면늘어가는CS지식 자료구조

B- 트리란 트리 자료구조의 일종으로 하나의 노드가 여러개의 키와 자식 노드를 가질 수 있는 균형 트리입니다.

특히, B- 트리는 검색, 삽입, 삭제 연산 시에도 항상 균형을 유지하면서도 디스크 접근 횟수를 최소화 하도록 설계된 구조입니다.

조금 더 정확하게 표현하면 M차 B트리는 다음 조건을 만족해야합니다.

루트 노드를 제외한 모든 내부 노드는 최소 ceil(M/2) ~ M 개의 자식 노드를 가져야합니다.
하나의 노드에 저장되는 키의 개수는 자식 수 -1개로 최소 ceil(M/2)-1 ~ M-1개 입니다.
모든 리프 노드는 동일한 깊이에 위치합니다.
모든 키는 정렬된 상태로 유지됩니다.

3차 B- 트리를 예로 들자면 노드 당 키의 개수는 ceil(3/2)-1 ~ 3-1개(1~2) 노드 당 ceil(3/2) ~ 3개(2~3)의 자식을 가질 수 있습니다.

1. 데이터 검색

B- 트리에서 데이터 검색은 root 노드부터 시작해 하향식으로 검색하게 됩니다.

먼저 루트 노드를 살펴보고, 찾고자 하는 데이터가 있는지 확인합니다.
데이터가 없다면, 해당 키의 크기를 기준으로 적절한 자식 노드 방향을 선택해 내려갑니다.
이 과정을 리프 노드까지 반복하며 탐색하고,
리프 노드에 도달했음에도 원하는 데이터가 없다면, 해당 데이터는 트리 내에 존재하지 않는 것입니다.

위 B 트리에서 15를 검색해 본다면,

먼저 루트 노드를 살펴보고, 찾고자 하는 데이터가 있는지 확인합니다. → 5, 21이 아닙니다.
데이터가 없다면, 해당 키의 크기를 기준으로 적절한 자식 노드 방향을 선택해 내려갑니다. → 5와 21 사이 노드 방향으로 내려갑니다.
이 과정을 리프 노드까지 반복하며 탐색하고, → 11이 아니므로 11보다 큰 자식 노드 방향으로 내려갑니다.
리프 노드에 도달했음에도 원하는 데이터가 없다면, 해당 데이터는 트리 내에 존재하지 않는 것입니다. → 15를 찾았습니다.

2. 데이터 삽입

B- 트리에서 데이터 삽입은 항상 리프 노드에서 시작되며, 검색과는 달리 상향식으로 처리됩니다.

앞서 언급했듯이, B- 트리의 각 노드는 ceil(M/2)-1 ~ M-1 개의 데이터를 저장할 수 있습니다. 따라서 삽입으로 인해 해당 범위를 초과하게 되면, 노드를 분할하게 되고, 중간키를 부모 노드로 올리는 구조적 조정이 필요합니다.

삽입 과정

트리가 비어있다면 루트 노드를 할당하고 데이터를 삽입한다.
트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.
리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.
리프 노드가 부적절한 상태에 있다면 분리한다.

*부적적한 상태: 각 노드 당 데이터 개수가 ceil(M/2)-1 ~ M-1 범위를 넘어서는 상태

그럼 삽입 과정을 크게 2가지 케이스로 분리해 적용해보겠습니다.

< 노드 분할이 필요 없는 경우 >

위 예시 B- 트리에 16을 삽입해보겠습니다.

(3차 B트리이므로, 노드 당 가능한 데이터 범위는 1~2개입니다.)

트리가 비어있다면 루트 노드를 할당하고 데이터를 삽입한다. → 루트가 비어있지 않습니다.
트리가 비어있지 않다면, 데이터를 넣을 적절한 리프 노드를 탐색한다.

→ 5, 21 사이 자식 노드로 내려갑니다.

→ 1보다 넣으려는 데이터(16)이 크기 때문에 큰 자식 노드로 내려갑니다.
리프 노드에 데이터를 넣고 리프 노드가 적절한 상태에 있다면 종료한다.

→ 15보다 크기 때문에 15 오른쪽에 데이터를 삽입합니다.

→ 노드 당 가능한 데이터 범위 내에 있기 때문에 삽입 과정을 종료합니다.

이처럼, B- 트리 삽입 과정에서 리프 노드에 키가 과도하게 많아질 경우, 가운데 키를 부모 노드로 올리고, 부모 노드 역시 조건을 초과하는지 계속 확인하며, 필요한 경우 상위 노드까지 분할을 반복하게 됩니다.

이러한 과정을 통해 B- 트리는 삽입 후에도 항상 노드의 키 개수와 자식 수 조건을 만족하는 균형 구조를 유지합니다.

3. 데이터 삭제

B- 트리에서는 균형을 맞추기위해 항상 아래 조건을 만족하는 것이 중요합니다.

내부 노드는 ceil(M/2) ~ M개의 자식을 가질 수 있다.
각 노드는 ceil(M/2)-1 ~ M-1개의 데이터를 가질 수 있다.
각 노드 데이터가 K개라면 K+1개의 자식노드를 가진다.

하지만, 데이터가 삭제되면서, 어떤 노드는 최소 데이터 개수나 자식 수 조건을 만족하지 못하는 경우가 발생합니다. 이런 경우에는 형제 노드나 부모 노드로부터 데이터를 가져오거나(재배치) 노드를 병합(병합)하는 등의 조치를 통해 균형을 다시 맞춰야합니다.

각 경우에 따른 과정을 살펴보겠습니다.

< 리프 노드에서 삭제되어도 문제 없는 경우 >

리프 노드에서 삭제되어도 B- 트리 조건을 모두 만족할 경우 그냥 삭제만 해줘도 문제가 없습니다.

위 B- 트리에서 15나 16 둘 중 하나만 삭제할 경우 최소 노드 당 데이터 수가 지켜지기 때문에 문제가 없습니다.

< 리프 노드 삭제 시 최소 유지 개수를 만족하지 못하지만, 형제 노드에서 값을 빌려올 수 있는 경우 >

위 B- 트리에서 21을 삭제할 경우, 최소 노드 당 데이터 개수가 지켜지지 않지만, 23보다 큰 노드에서 31의 값을 23의 위치와 교환한 후, 23을 31의 왼쪽 자식 노드로 둠으로써 조건을 충족시킬 수 있습니다.

→ 회전이 된 것처럼 보입니다!

다음은 리프 노드가 아닌 내부 노드에서 삭제할 경우를 살펴보겠습니다.

< 리프 노드가 아닌 내부 노드에서 삭제할 경우 >

위 B- 트리에서 5를 삭제할 경우, 3의 노드가 최소 데이터 개수를 충족시키지 않기 때문에 자식노드 7을 부모 노드로 올려 3,7이 부모노드가 되고, 나머지 1,4,11이 자식 노드가 되며 조건이 충족되는 것을 알 수 있습니다.

< 내부 노드 삭제 시, 현재 노드와 자식 노드 개수 모두 최소인 경우 >

하지만, 부모와 자식 노드가 모두 최소 개수일 경우 노드를 끌어올 수 없습니다.

위 B- 트리에서 4를 삭제할 경우 부모, 자식 어느 노드에서도 끌어올 수 없습니다.

이 경우, 4를 삭제한 뒤,

자식 노드들을 하나의 노드로 합칩니다. → 1, 11
이후, 삭제된 값의 부모 노드를 삭제된 값의 형제 노드에 합칩니다. → 15를 31의 형제로 합칩니다.
이후, 해당 부모 노드를 이전의 자식 노드들과 연결합니다. → 1,11 노드를 15의 자식 노드로 연결합니다.
만약 이 과정에서 부모 노드의 데이터 수가 조건을 충족시키지 못한다면 그 부모 노드로 올라가며 2번 과정을 반복합니다.

삭제 규칙

위 과정을 살펴보면 모든 삭제는 리프에서 발생하며, 균형을 회복하기 위해 재분배나 병합등의 방식을 사용하는 것을 알 수 있습니다.

삭제할 키를 리프까지 옮깁니다.
- 삭제 대상이 리프에 없다면 전임자(Predecessor) 또는 후임자(Successor)와 값만 교체한 뒤, 실제 삭제는 리프에서 진행합니다.
- 전임자 = 왼쪽 자식에서 가장 큰 값
- 후임자 = 오른쪽 자식에서 가장 작은 값
리프 노드에서 삭제합니다.
- 삭제 후 해당 노드의 Key 수가 최소 개수 미만인지 확인합니다.
균형을 회복합니다.(재분배 or 병합)
1) 형제 노드가 최소 개수보다 더 많은 Key를 가지고 있을 경우 → 하나 빌려와서 균형 맞추기
- 왼쪽 형제에게 빌릴 경우 → 부모의 Key 내려오고 형제의 Key 올라감
- 오른쪽 형제에게 빌릴 경우 마찬가지
2) 형제도 최소 개수라 빌릴 수 없는 경우 → 형제 + 부모 Key 하나 포함해 병합
- 부모에서 Key 하나 빠짐
- 이로 인해 부모 노드도 Key가 부족할 수 있기 때문에 재귀적으로 위로 올라가며 처리