B트리와 B+트리

왜 배우는가: B트리와 B+트리는 데이터베이스와 파일 시스템의 인덱스 구조로 널리 쓰이며, 디스크 I/O 횟수를 줄이는 원리를 이해하는 기본 개념이다. 기술사 시험에서는 정의, 삽입·삭제 알고리즘, 직접 그리는 문제, 두 구조의 비교 문제로 반복 출제된다.

출제 이력: 제101회 3교시 4번, 제98회 2교시 3번

1. 한 줄 정의와 핵심 키워드

B트리는 자식 노드 수가 정해진 범위에서 변하며 키를 정렬 상태로 유지하는 균형 다진 탐색 트리이다.

• B트리: 모든 리프가 같은 깊이에 있고, 노드마다 키와 자식 포인터를 함께 가지는 다진 탐색 트리
• B+트리: 키만 내부 노드에 두고, 모든 데이터 포인터를 리프에 두며 리프끼리 연결한 B트리 변형
• 차수(order, m): 한 노드가 가질 수 있는 자식 노드의 최대 수
• 최소 채움률: 루트를 제외한 노드가 유지해야 하는 최소 키 수 또는 자식 수
• 분할(split): 노드가 넘치면 절반으로 나누고 중간 키를 부모로 올리는 연산
• 병합(merge)·재분배(redistribution): 노드가 모자라면 형제와 합치거나 키를 빌려오는 연산
• 리프 노드(leaf node): 트리의 가장 아래층 노드

2. 개념 풀이

쉽게 말하면 B트리는 한 노드에 키를 여러 개 담아 두고, 그 키 사이로 자식을 가리키는 넓고 얕은 트리다. 키를 찾을 때 디스크 블록을 적게 읽도록 설계되었다.

정식으로 정의하면, 차수 m인 B트리는 다음 조건을 만족하는 탐색 트리다. 모든 노드는 최대 m개의 자식을 가진다. 루트를 제외한 내부 노드는 구현에서 정한 최소 자식 수 이상을 가진다. 모든 리프는 같은 깊이에 있다. 한 노드의 키는 정렬되어 있으며, n개의 키를 가진 노드는 n+1개의 자식 포인터를 가진다(s1<s2<…<sn, 포인터 t0~tn). 포인터가 하나 많다고 설명한다.

B트리의 핵심은 자식 수가 미리 정한 범위 안에서만 바뀐다는 점이다. 삽입과 삭제 때 노드가 넘치거나 모자라면 분할 또는 병합으로 범위를 맞춘다. 이 과정이 상향식이라는 점이 이진 탐색 트리와 다르다. 이진 탐색 트리는 보통 새 노드를 하향식으로 붙인다.

B+트리는 B트리를 변형한 구조다. 모든 레코드 또는 데이터 포인터는 가장 아래 리프에 있고, 내부 노드는 탐색용 키만 가진다. 그래서 내부 노드에 더 많은 키를 담을 수 있어 팬아웃(fanout)이 커진다. 팬아웃이 커지면 트리 높이가 낮아져 검색에 필요한 디스크 I/O가 줄어든다.

B+트리는 데이터를 리프에만 두고, 리프끼리 연결해 범위 검색을 지원하는 B트리 변형이다.

3. 등장 배경과 필요성

방대한 자료를 검색할 때 모든 레코드를 하나씩 비교하면 시간이 너무 많이 든다. 자료를 정렬해 두고 이진 탐색을 쓰면 비교 횟수는 줄지만, 자료가 디스크에 있을 때는 노드 하나를 읽을 때마다 디스크 접근이 발생한다. 이진 탐색 트리는 노드당 자식이 2개뿐이라 높이가 커지고, 디스크 접근 횟수도 많아진다.

그래서 한 노드에 많은 키를 담아 트리를 넓고 낮게 만드는 다진 탐색 트리가 필요해졌다. B트리는 이 요구를 해결하기 위해 제안된 구조이며, 디스크 블록 단위로 노드를 읽고 쓰는 파일 시스템과 데이터베이스에 맞는다.

다만 B트리는 키와 데이터를 내부 노드에 함께 두므로, 범위 검색을 하려면 트리를 여러 번 오르내려야 한다. 또 내부 노드에 데이터가 있어 노드당 키 수가 줄어든다. B+트리는 이 두 가지 한계를 줄이기 위해 나왔다. 리프를 연결해 순차 접근을 빠르게 하고, 내부 노드를 키만으로 채워 팬아웃을 높인다.

또한 B트리는 자식 수 범위를 유지하는 방식이라 자가 균형 이진 탐색 트리보다 재균형이 덜 자주 일어난다. 그 대가로 노드 안에 빈 공간이 생겨 저장 공간을 일부 잃는다. 이 트ade-off가 B트리 설계의 출발점이다.

4. 구성요소·원리·절차

B트리는 노드 하나에 키와 자식 포인터를 함께 담는 다분 트리다. 노드의 자식 수가 최소와 최대 사이에서 변하며, 삽입·삭제 때 노드를 분리하거나 합쳐 균형을 유지한다. 구성요소는 다음과 같다.

차수가 3이면 노드마다 자식은 최대 3개다. 노드의 키 수 상한은 구현 기준에 따른다. 키 집합은 항상 정렬된 상태를 유지한다. 내부 노드의 키 s_1 < s_2 < \\cdots < s_n 은 포인터 t_0, t_1, \\cdots, t_n 사이를 나눈다.

B트리는 상향식으로 성장하며 루트 분할 시 높이가 1 증가한다

원리는 다음과 같다. 키 범위마다 하위 노드가 하나씩 대응하므로 검색은 루트에서 리프까지 한 번씩 내려가며 끝난다. 노드가 꽉 차면 중간 키를 부모로 올려 보내고 노드를 둘로 나눈다. 노드가 너무 비면 형제 노드에서 키를 빌리거나 형제와 합친다. 이 과정이 루트까지 전파되어 트리 높이가 늘거나 줄어든다.

삽입 절차

• 루트에서 시작해 삽입할 키가 들어갈 리프 노드를 찾는다.
• 리프에 키를 정렬 순서대로 넣는다.
• 노드의 키 수가 구현에서 정한 최대 키 수를 넘지 않으면 종료한다.
• 넘으면 노드를 두 개로 분할하고 중간 키를 부모에 삽입한다.
• 부모도 넘치면 같은 과정을 반복하고, 루트를 분할했다면 새 루트를 만들어 높이를 1 증가시킨다.

삭제 절차

• 삭제할 키가 있는 노드를 찾는다.
• 리프에서 삭제하고, 내부 노드의 키라면 후계자 또는 선행자 키로 대체한다.
• 노드의 키 수가 구현에서 정한 최소 키 수 이상이면 종료한다.
• 미달이면 형제 노드에 여분 키가 있을 때 재분배(빌려오기)한다.
• 형제에도 여분이 없으면 형제와 병합하고, 부모에서 키 하나를 내린다.
• 병합이 부모로 전파되면 루트까지 확인하며, 루트의 키가 0이 되면 높이가 1 줄어든다.

B+트리와의 구조 차이

B트리는 내부 노드에도 데이터를 둘 수 있다. B+트리는 데이터를 리프에만 두고 리프끼리 연결 리스트로 묶는다. 리프가 연결되어 있어 범위 검색이 빠르다.

도식

5. 관련 법령·기준·표준

B트리와 B+트리는 데이터베이스 엔진의 구현 기준이며, 법령이나 고시로 정한 수치가 없다. 아래 값은 자료구조의 수학적 조건이다. 실제 차수는 DBMS와 페이지 크기에 따라 정한다.

B트리는 상향식으로 구성된다는 점이 근거에 있다. 개정 연혁은 자료구조 기준이라 해당 없음이다. 국내 법령은 직접 규정하지 않으며 관련 기준은 DBMS 제품 문서가 된다.

외국 기준 비교

세부 수치 비교는 이 절에서 다루지 않는다.

6. 유형과 비교

B트리와 B+트리는 같은 균형 다진 트리 구조를 쓰지만 키와 데이터 포인터를 저장하는 위치가 다르다. 이 차이가 검색 방식, 순차 접근, 노드 분할·병합 규칙을 바꾼다. 아래 표는 두 구조를 같은 기준으로 나란히 비교한 것이다.

표의 핵심은 팬아웃이다. B+트리는 내부 노드가 키만 가지므로 한 블록에 더 많은 포인터를 담고, 트리 높이가 낮아진다. 그래서 디스크 I/O 횟수가 줄어든다. 범위 검색은 단말 노드의 연결 리스트를 따라가면 되므로 B트리보다 효율적이다.

다음으로 차수 정의를 비교한다. 두 구조 모두 차수 m인 노드는 최대 m개의 자식을 갖는다. 다만 B트리 내부 노드는 (루트를 제외하고) 최소 L 항목, 최대 U 항목을 가지며 자식 포인터는 항목 수보다 하나 많다. B+트리 단말 노드는 구현에서 정한 최소·최대 키 수 범위로 유지하는 규칙이 일반적이다. 정확한 경계는 교재와 구현마다 표기가 다르므로 답안에는 '최소 반 이상 채움'이라는 원칙으로 쓴다.