B+ 트리란 무엇인가?
B+ 트리는 이진 탐색 트리(Binary Search Tree)를 일반화한 자료구조로, 하나의 노드가 두 개 이상의 자식을 가질 수 있습니다. 스스로 균형을 유지하는(self-balancing) 트리 구조이기 때문에 정렬된 데이터를 안정적으로 관리하며, 순차 접근·검색·삽입·삭제 연산을 모두 로그 시간(logarithmic time)에 처리할 수 있습니다.
B+ 트리는 각 노드가 키(key)만을 담는 B-트리로 볼 수 있으며, 최하위 레벨에 링크로 연결된 리프(linked leaves) 계층이 추가된 형태입니다. 이러한 특성 덕분에 범위 검색과 순차 접근이 매우 효율적이어서 데이터베이스 인덱스나 파일 시스템에서 널리 활용됩니다.
노드 삽입 알고리즘
시작
insert() 함수 : 트리에 노드를 삽입한다
x를 루트(root)로 초기화한다
x가 리프 노드이고 데이터를 하나 더 저장할 공간이 있다면 a를 x에 삽입한다
그렇지 않고 x가 리프 노드가 아니라면 아래를 수행한다
다음에 탐색할 x의 자식 노드를 찾는다
자식이 가득 차 있지 않으면, x가 해당 자식을 가리키도록 변경한다
자식이 가득 차 있으면 자식을 분할(split)하고, x가 분할된 두 부분 중 하나를 가리키도록 한다
a가 자식의 중간(mid) 키보다 작으면 첫 번째 부분을, 그렇지 않으면 두 번째 부분을 선택한다
끝
C++ 예제 코드
아래 코드는 차수(order) 6짜리 B+ 트리를 구현한 것으로, 노드 생성(init), 트리 순회(traverse), 정렬(sort), 자식 분할(split_child), 삽입(insert) 기능을 포함합니다.
#include<iostream>
using namespace std;
struct BplusTree {
int *d;
BplusTree **child_ptr;
bool l;
int n;
}*r = NULL, *np = NULL, *x = NULL;
BplusTree* init() // 노드 생성 {
int i;
np = new BplusTree;
np->d = new int[6]; // 차수(order) 6
np->child_ptr = new BplusTree *[7];
np->l = true;
np->n = 0;
for (i = 0; i < 7; i++) {
np->child_ptr[i] = NULL;
}
return np;
}
void traverse(BplusTree *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(BplusTree *x, int i) {
int j, mid;
BplusTree *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() : 새로운 노드를 생성하고 키 배열(d), 자식 포인터 배열(child_ptr) 등을 초기화합니다.
- traverse() : 트리를 재귀적으로 순회하며 저장된 모든 키를 출력합니다.
- sort() : 노드 내부의 키들이 항상 오름차순을 유지하도록 정렬합니다.
- split_child() : 가득 찬 노드를 중간 키를 기준으로 둘로 나누고, 중간 키를 부모 노드로 올려 트리의 균형을 유지합니다.
- insert() : 새로운 키가 들어갈 적절한 리프 노드를 찾아 내려간 뒤 삽입하며, 경로상의 노드가 가득 차 있으면 분할을 수행합니다.
실행 결과
삽입할 원소의 개수를 입력하세요 10 원소를 입력하세요 10 원소를 입력하세요 20 원소를 입력하세요 30 원소를 입력하세요 40 원소를 입력하세요 50 원소를 입력하세요 60 원소를 입력하세요 70 원소를 입력하세요 80 원소를 입력하세요 90 원소를 입력하세요 100 생성된 B+ 트리의 순회 결과 10 20 30 40 50 60 70 80 90 100