[DB] B+Tree

do_it·2025년 11월 20일

database

목록 보기

11/11

2. B-Tree

2-1. B-Tree (Balanced Tree)

1) B-Tree의 정의와 특징

B-Tree는 이름처럼 균형 잡힌 탐색 트리(Search Tree) 자료구조임.
DB의 인덱스나 파일 시스템에서 디스크 I/O를 최소화하여 대용량 데이터를 효율적으로 관리하기 위해 설계됨.
하나의 노드가 2개 이상의 데이터(Key)와 2개 이상의 자식 노드를 가질 수 있는 다진 트리 구조임.
(M-way Tree)

2) 이진 탐색 트리와의 차이점

구분	B-Tree (B-트리)	이진 탐색 트리 (BST)
노드당 Key 수	여러 개 (M-1개 이하)	1개
자식 노드 수	2개 이상 (최대 M개)	최대 2개
균형 유지	자동 균형 유지 (항상 균형 잡힌 구조)	데이터 삽입 순서에 따라 불균형해질 수 있음 (별도의 균형 메커니즘 필요)
주 사용처	디스크 기반 환경 (DB 인덱스, 파일 시스템)	메모리 기반 환경 (알고리즘 구현)
높이	노드당 많은 Key를 가지므로 트리 높이가 매우 낮음	노드당 1개의 Key를 가지므로 B-Tree보다 트리 높이가 높음

B-Tree는 노드당 더 많은 정보를 저장하여 트리의 전체 높이를 낮춤.
트리의 높이가 낮다는 것은 디스크 I/O 횟수가 줄어들어 대용량 데이터 검색 속도가 빨라짐을 의미함.

3) 균형 트리의 개념

균형이란 삽입, 삭제 등의 작업이 발생해도 트리의 높이가 한쪽으로 치우치지 않고 일정하게 유지되는 것을 의미함.
B-Tree는 항상 균형을 유지하여, 어떤 데이터를 검색하든지 루트 노드에서 리프 노드까지의 경로 길이(트리 높이)가 같도록 보장함
이 덕분에 최악의 경우에도 검색 시간 복잡도가 O(log n)으로 안정적임. (BST는 최악의 경우 O(N))

2-2. B-Tree의 계층적 구조

B-Tree의 모든 노드는 기본적으로 같은 구조를 가지지만, 트리의 계층에 따라 역할이 구분됨.

1) 루트 노드 (Root Node)

트리의 가장 위에 있는 유일한 노드이자 모든 탐색의 시작점dla.
트리가 비어있지 않은 한 반드시 존재하며, 다른 노드와 달리 키 개수와 자식 노드 개수에 대한 최소 제한 조건이 완화될 수 있음.

2) 내부(브랜치) 노드 (Internal/Branch Node)

루트 노드와 리프 노드 사이에 위치하며, 탐색 경로를 안내하는 역할을 함.
항상 자식 노드를 가지는 노드
키(Key): 다음 탐색 경롤를 결정하기 위한 기준값
자식 포인터(Pointer): 하위 노드들을 가리키는 주소값

3) 리프 노드 (Leaf Node)

트리의 가장 낮은 레벨에 위치하며, 실제 데이터 또는 데이터의 위치를 담고 있는 노드
자식 노드를 가지지 않으며 B-Tree에서는 모든 리프 노드가 항상 동일한 깊이(Level)에 위치하여 균형을 유지함.

2-3. 키와 포인터

1) B-Tree 차수 (Order)

B-Tree에서 하나의 노드가 가질 수 있는 최대 자식 수를 차수( $M$ ) 또는 Order라고 함
키 개수와의 관계
- 차수가 M인 B-Tree는 하나의 노드에 최대 M-1개의 키(데이터)를 저장할 수 있음.
- 노드의 키 개수가 N개라면, 자식 포인터(자식 노드를 가리키는 포인터)는 N+1개를 가짐.
- 이 차수(M)가 클수록 노드당 담는 키가 많아지므로 트리의 높이는 더욱 낮아져 디스크 I/O에 유리해짐.
- e.g. 4차 B-Tree (M=4) 최대 자식 수: 4개, 최대 키 개수: 4-1 = 3개

2) 노드의 저장 형태

차수가 M인 B-Tree의 한 노드는 $P_1, K_1, P_2, K_2, \dots, P_n, K_n, P_{n+1}$ 로 구성됨.

n : 현재 노드가 가지고 있는 키(데이터)의 개수
$Ki$ : 데이터 (키) 값, 키 값은 정렬된 상태로 저장됨
$Pi$ : 자식 노드를 가리키는 포인터 (주소)

3) 탐색 구조의 원리

키의 역할 (K)
- 노드 내에서 해당 키의 왼쪽에 있는 모든 키는 $Ki$ 보다 작고, 오른쪽에 있는 모든 키는 크거나 같도록 트리를 분할하는 경계 역할을 함.
포인터의 역할 (P)
- $P1$ 은 $K1$ 보다 작은 값을 가진 자식 노드를 가리킴

루트 노드에서 원하는 데이터를 검색할 때 매 노드마다 많은 수의 키를 비교하고 하나의 포인터를 따라 내려가므로, 트리의 높이가 낮아져 디스크 I/O 횟수를 최소화할 수 있음.

3. B+Tree의 기초

3-1. B+Tree란 무엇인가?

B+Tree는 자체 균형(self-balancing)이 가능한 트리 자료구조의 한 종류로, 특히 대용량 데이터를 저장하는 디스크 환경에서 최적화된 구조
범위 검색 최적화
리프 노드가 순차적으로 연결되어 있어, 시작점만 찾으면 리스트를 따라 순차적으로 데이터를 빠르게 탐색할 수 있음.
디스크 I/O 최소화
내부 노드가 키와 자식 노드의 포인터만 저장하여 노드 하나에 더 많은 키를 담을 수 있음.
이는 트리의 높이를 낮춰 데이터를 찾기 위해 디스크에 접근하는 횟수를 획기적으로 줄여줌.

DB에서 레코드를 빠르게 검색, 삽입, 삭제할 수 있도록 돕는 인덱스를 구현하는 데 가장 널리 사용됨.
디스크 접근 횟수를 최소화하여 검색 성능을 향상시키는 것이 주된 목적임.

3-2. B+Tree의 시간 복잡도 및 균형 유지 원리

B+Tree는 대용량 디스크 환경에 최적화된 자료구조로, 모든 주요 연산에서 일관되고 효율적인 로그 시간 복잡도를 제공하며, 이를 노드 분할(Split) & 병합(Merge)을 통해 균형있게 유지함.

1) B+Tree의 시간 복잡도

B+Tree의 시간복잡도는 트리의 높이(h)에 의해 결정됨.

트리의 차수와 전체 데이터 레코드의 개수(n)을 사용할 때, 높이 h는 $O(\log_m n)$ 에 비례함

연산	시간 복잡도	설명
탐색 (Search)	$O(h)$ 또는 $O(\log_m n)$	루트에서 시작해 리프 노드까지 도달하는 경로를 따라 내려가므로, 트리의 높이에 비례함.
삽입 (Insertion)	$O(h)$ 또는 $O(\log_m n)$	리프 노드를 찾는 시간 $O(h)$ 와 노드 분할(Split)이 발생할 경우 상위 노드로 전파되는 시간 $O(h)$ 가 더해져 로그 시간 복잡도를 가짐.
삭제 (Deletion)	$O(h)$ 또는 $O(\log_m n)$	리프 노드를 찾는 시간 $O(h)$ 와 노드 병합(Merge) 또는 재분배(Redistribution)가 발생할 경우 상위 노드로 전파되는 시간 $O(h)$ 가 더해져 로그 시간 복잡도를 가짐.
범위 검색 (Range Search)	$O(h + k)$	$k$ 는 원하는 범위에 속하는 데이터 레코드의 수임.
시작점을 찾는 데 $O(h)$ 가 소요된 후, 리프 노드의 연결 리스트를 따라 $k$ 개의 레코드를 순차적으로 탐색함.

2) B+Tree의 균형 유지 원리 (Self-Balancing Principle)

B+Tree는 데이터의 삽입과 삭제가 빈번하게 일어나더라도 트리의 모든 리프 노드가 항상 같은 깊이에 위치하도록 유지하여 검색 성능의 일관성을 보장함.

이 메커니즘을 통해 B+Tree는 데이터의 동적인 변화에도 불구하고 항상 로그 시간 복잡도를 유지하며 효율적인 인덱스 역할을 수행할 수 있음.

이 균형을 유지하는 주요 매커니즘은 노드 분할과 노드 병합/재분배임.

(1) 삽입 시 균형 유지: 노드 분할 (Node Split)

데이터를 삽입하여 특정 노드의 키 개수가 최대 허용 개수를 초과했을 때 발생함.

꽉 찬 노드를 두 개의 노드로 나눔.
나눠진 두 노드를 구분하는 중간 키(Median Key)를 선택함.
이 중간 키는 부모 노드로 승격되어 인텍스 엔트리로 사용되고, 부모 노드의 키 개수 규칙을 따르면서 분할된 두 자식 노드를 가리키게 됨

[전파, Propagation]

승격된 키로 부모 노드 또한 최대 키 개수를 초과하면, 이 과정은 루트 노드까지 재귀적으로 반복될 수 있음.

루트노드까지 분할되면 트리의 높이가 1 증가함.

(2) 삭제 시 균형 유지: 병합 및 재분배(Merge & Redistribution)

데이터를 삭제하여 특정 노드의 키 개수가 최소 허용 개수 미만이 되었을 때 발생함.

재분배(Redistribution) 형제 노드에게서 키를 빌려와 최소 개수를 충족시키려고 시도함. 이웃 노드가 여유 키를 가지고 있다면, 부모 노드의 키를 포함하여 키를 재분배하고 균형을 맞춤.
병합 (Merge) 형제 노드마저 키가 부족하여 빌려줄 수 없다면, 해당 노드와 형제 노드를 하나로 함침.