B 트리(B-Tree)는 하나의 노드가 둘 이상의 자식을 가질 수 있다는 점에서 이진 탐색 트리(Binary Search Tree)를 일반화한 자료구조입니다. 스스로 균형을 유지하는(self-balancing) 트리 구조로, 정렬된 데이터를 관리하며 로그 시간(logarithmic time) 안에 순차 접근, 탐색, 삽입, 삭제 연산을 수행할 수 있습니다.
이 글에서는 C++를 사용하여 차수(order)가 6인 B 트리를 구현하는 방법을 소개합니다.
B 트리의 핵심 특징
- 하나의 노드에 여러 개의 키와 여러 개의 자식 포인터를 저장합니다.
- 모든 리프 노드가 같은 깊이(레벨)에 위치하도록 균형을 유지합니다.
- 데이터베이스와 파일 시스템에서 대용량 데이터 인덱싱에 널리 활용됩니다.
알고리즘
노드를 트리에 삽입하는 insert() 함수는 아래와 같은 절차로 동작합니다.
시작
노드를 트리에 삽입하는 함수 insert():
x를 루트(root) 노드로 초기화한다.
x가 리프 노드이고 데이터를 하나 더 저장할 공간이 있으면,
삽입하려는 값 a를 x에 추가한다.
그렇지 않고 x가 리프 노드가 아니라면 다음을 수행한다.
다음으로 내려갈 x의 자식 노드를 찾는다.
해당 자식이 가득 차지 않았다면, x를 그 자식을 가리키도록 변경한다.
자식이 가득 찼다면 분할(split)하고, x가 자식의 두 부분 중
하나를 가리키도록 한다. 값 a가 자식의 중앙 키(mid key)보다
작으면 첫 번째 부분으로, 크면 두 번째 부분으로 이동한다.
자식을 분할할 때는 자식에서 키 하나를 부모 노드 x로 끌어올린다.
종료예제 코드
#include<iostream>
using namespace std;
struct BTree//노드 선언 {
int *d;
BTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
BTree* init()//노드 생성 {
int i;
np = new BTree;
np->d = new int[6];//차수 6
np->child_ptr = new BTree *[7];
np->l = true;
np->n = 0;
for (i = 0; i < 7; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(BTree *p)//트리 순회 {
cout<<endl;
int i;
for (i = 0; i < p->n; i++) {
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout << " " << p->d[i];
}
if (p->l == false) {
traverse(p->child_ptr[i]);
}
cout<<endl;
}
void sort(int *p, int n)//키 정렬 {
int i, j, t;
for (i = 0; i < n; i++) {
for (j = i; j <= n; j++) {
if (p[i] >p[j]) {
t = p[i];
p[i] = p[j];
p[j] = t;
}
}
}
}
int split_child(BTree *x, int i) {
int j, mid;
BTree *np1, *np3, *y;
np3 = init();//새 노드 생성
np3->l = true;
if (i == -1) {
mid = x->d[2];//중앙 키 찾기
x->d[2] = 0;
x->n--;
np1 = init();
np1->l= false;
x->l= true;
for (j = 3; j < 6; j++) {
np3->d[j - 3] = x->d[j];
np3->child_ptr[j - 3] = x->child_ptr[j];
np3->n++;
x->d[j] = 0;
x->n--;
}
for (j = 0; j < 6; j++) {
x->child_ptr[j] = NULL;
}
np1->d[0] = mid;
np1->child_ptr[np1->n] = x;
np1->child_ptr[np1->n + 1] = np3;
np1->n++;
r = np1;
} else {
y = x->child_ptr[i];
mid = y->d[2];
y->d[2] = 0;
y->n--;
for (j = 3; j <6 ; j++) {
np3->d[j - 3] = y->d[j];
np3->n++;
y->d[j] = 0;
y->n--;
}
x->child_ptr[i + 1] = y;
x->child_ptr[i + 1] = np3;
}
return mid;
}
void insert(int a) {
int i, t;
x = r;
if (x == NULL) {
r = init();
x = r;
} else {
if (x->l== true && x->n == 6) {
t = split_child(x, -1);
x = r;
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
x = x->child_ptr[i];
} else {
while (x->l == false) {
for (i = 0; i < (x->n); i++) {
if ((a >x->d[i]) && (a < x->d[i + 1])) {
i++;
break;
} else if (a < x->d[0]) {
break;
} else {
continue;
}
}
if ((x->child_ptr[i])->n == 6) {
t = split_child(x, i);
x->d[x->n] = t;
x->n++;
continue;
} else {
x = x->child_ptr[i];
}
}
}
}
x->d[x->n] = a;
sort(x->d, x->n);
x->n++;
}
int main() {
int i, n, t;
cout<<"삽입할 요소의 개수를 입력하세요\n";
cin>>n;
for(i = 0; i < n; i++) {
cout<<"요소를 입력하세요\n";
cin>>t;
insert(t);
}
cout<<"생성된 B 트리의 순회 결과\n";
traverse(r);
}코드 주요 구성 요소 살펴보기
init() – 노드 생성
새로운 B 트리 노드를 동적으로 할당하고 초기화합니다. 차수가 6이므로 각 노드는 최대 6개의 키(d)와 7개의 자식 포인터(child_ptr)를 저장할 수 있습니다.
traverse() – 트리 순회
재귀적으로 트리를 순회하며 모든 키를 오름차순으로 출력합니다. 내부 노드라면 먼저 자식을 방문한 뒤 자신의 키를 출력하는 방식입니다.
split_child() – 노드 분할
가득 찬 노드를 분할하는 핵심 함수입니다. 노드의 중앙 키(d[2])를 추출해 부모로 올리고, 나머지 키들을 새로운 노드(np3)로 옮깁니다. 루트 노드가 분할되는 경우(i == -1)에는 새로운 루트(np1)가 생성됩니다.
insert() – 노드 삽입
루트부터 시작해 값이 들어갈 적절한 리프 노드를 찾아 내려갑니다. 도중에 가득 찬 자식을 만나면 미리 분할(split)한 후 진행하며, 마지막으로 리프 노드에 값을 삽입하고 sort()로 키 배열을 정렬합니다.
실행 결과
삽입할 요소의 개수를 입력하세요 7 요소를 입력하세요 10 요소를 입력하세요 20 요소를 입력하세요 30 요소를 입력하세요 40 요소를 입력하세요 50 요소를 입력하세요 60 요소를 입력하세요 70 생성된 B 트리의 순회 결과 10 20 30 40 50 60 70
위 실행 결과에서 볼 수 있듯이, 요소가 계속 삽입되어 루트 노드가 가득 차면 노드가 분할되면서 트리의 높이가 증가합니다. 10~60까지 삽입된 후 70을 삽입하는 시점에 분할이 발생하여 중앙 키 30이 새로운 루트로 올라가고, 나머지 키들이 두 개의 자식 노드로 나뉜 것을 확인할 수 있습니다. 순회 결과는 항상 정렬된 순서로 출력되므로, B 트리가 검색 연산에 적합한 구조임을 알 수 있습니다.