B+ Tree
B+ Tree는 데이터베이스와 파일 시스템에서 널리 사용되는 균형 탐색 트리(Balanced Search Tree) 이다. 특히 디스크 기반 저장장치에서 데이터 검색 성능을 높이기 위해 설계되었으며, 대부분의 DBMS 인덱스 구조로 사용된다.
왜 B+ Tree를 사용할까?
배열에서 데이터를 찾는 경우 이진 탐색을 이용하면 다음과 같은 시간 복잡도를 가진다.
O(log N)
하지만 데이터베이스에서는 데이터가 메모리가 아닌 디스크에 저장되어 있다.
디스크 접근은 CPU 연산보다 훨씬 느리기 때문에, 단순히 연산 횟수를 줄이는 것보다 디스크 I/O 횟수를 최소화하는 것이 중요하다.
B+ Tree는 하나의 노드에 많은 키를 저장하여 트리의 높이를 낮춤으로써 디스크 접근 횟수를 줄인다.
B+ Tree의 구조
예를 들어 차수(Order)가 4인 B+ Tree를 생각해보자.
[30 | 60]
/ | \
/ | \
[10 20] [30 40 50] [60 70 80]
트리는 크게 두 종류의 노드로 구성된다.
- Internal Node (내부 노드)
- Leaf Node (리프 노드)
Internal Node
내부 노드는 실제 데이터를 저장하지 않는다.
[30 | 60]
내부 노드의 역할은 검색 경로를 결정하는 것이다.
예를 들어
30 미만 → 왼쪽
30 이상 60 미만 → 가운데
60 이상 → 오른쪽
과 같이 탐색 방향을 안내한다.
Leaf Node
리프 노드는 실제 데이터 또는 데이터가 저장된 위치(포인터)를 저장한다.
[10 20]
[30 40 50]
[60 70 80]
B+ Tree에서는 모든 실제 데이터가 리프 노드에만 존재한다.
B-Tree와 B+ Tree 비교
B-Tree
[30]
/ \
[10 20] [40 50]
내부 노드와 리프 노드 모두 데이터를 저장한다.
B+ Tree
[30]
/ \
[10 20] [30 40 50]
내부 노드는 검색용 키만 저장하고 실제 데이터는 리프 노드에만 저장한다.
| 항목 | B-Tree | B+ Tree |
|---|---|---|
| 실제 데이터 저장 | 모든 노드 | 리프 노드만 |
| 범위 검색 | 비효율적 | 효율적 |
| 구현 복잡도 | 상대적으로 복잡 | 상대적으로 단순 |
| DB 인덱스 활용 | 적음 | 매우 많음 |
Leaf Node 연결
B+ Tree의 가장 큰 특징은 모든 리프 노드가 연결 리스트 형태로 연결된다는 점이다.
[10 20]
↓
[30 40 50]
↓
[60 70 80]
실제로는 양방향 연결 리스트로 구현되는 경우가 많다.
[10 20] ↔ [30 40 50] ↔ [60 70 80]
Point Query
특정 값을 찾는 연산이다.
예시:
SELECT *
FROM Student
WHERE id = 40;
탐색 과정:
[30 | 60]
↓
[30 40 50]
↓
40
시간 복잡도
트리의 높이를 h라고 하면
O(h)
B+ Tree의 높이는
h ≈ log_B N
이므로
O(log_B N)
이다.
여기서
- N : 데이터 개수
- B : 한 노드가 가질 수 있는 최대 자식 수(Fan-out)
Range Query
특정 구간의 데이터를 찾는 연산이다.
예시:
SELECT *
FROM Student
WHERE id BETWEEN 35 AND 75;
먼저 35가 포함된 리프 노드를 찾는다.
[30 40 50]
이후 리프 노드 연결을 따라가면서 범위 내 데이터를 순차적으로 읽는다.
[30 40 50]
↓
[60 70 80]
시간 복잡도
첫 번째 리프 탐색
O(log_B N)
범위 내 데이터 K개 순회
O(K)
따라서
O(log_B N + K)
삽입 (Insertion)
예를 들어
[30 40 50]
에 45를 삽입하면
[30 40 45 50]
이 된다.
Split
노드가 가득 찬 경우 분할한다.
[30 40 45 50]
↓
[30 40] [45 50]
그리고 부모 노드에 분할 기준 키를 삽입한다.
[45]
/ \
[30 40] [45 50]
시간 복잡도
최악의 경우 루트까지 분할이 전파될 수 있다.
따라서
O(log_B N)
이다.
삭제 (Deletion)
데이터를 삭제한 후 노드의 키 개수가 최소 개수보다 적어질 수 있다.
Redistribution
형제 노드에서 키를 빌려온다.
[10]
[20 30 40]
↓
[10 20]
[30 40]
Merge
빌려올 수 없다면 병합한다.
[10]
[20]
↓
[10 20]
그리고 부모 노드의 키도 제거한다.
시간 복잡도
최악의 경우 루트까지 병합이 전파될 수 있으므로
O(log_B N)
이다.
B+ Tree의 시간 복잡도 정리
| 연산 | 시간 복잡도 |
|---|---|
| Search (Point Query) | O(log_B N) |
| Range Query | O(log_B N + K) |
| Insertion | O(log_B N) |
| Deletion | O(log_B N) |
B+ Tree가 DB에서 사용되는 이유
- 트리 높이가 매우 낮다.
- 디스크 I/O 횟수를 줄일 수 있다.
- 범위 검색이 매우 빠르다.
- 삽입과 삭제 후에도 균형이 유지된다.
- 대용량 데이터에 적합하다.
실제 데이터베이스에서는 하나의 노드가 디스크 블록(예: 4KB, 8KB)에 대응되며, 한 노드에 수백 개 이상의 키를 저장할 수 있다.
예를 들어 Fan-out이 100이라면,
높이 1 → 100개
높이 2 → 10,000개
높이 3 → 1,000,000개
높이 4 → 100,000,000개
의 데이터를 관리할 수 있다.
따라서 수천만 건의 데이터가 있어도 보통 트리 높이는 3~4 정도에 불과하며, 몇 번의 디스크 접근만으로 원하는 데이터를 찾을 수 있다.
핵심 요약
B+ Tree는 실제 데이터를 리프 노드에만 저장하고, 모든 리프 노드를 연결 리스트로 연결한 균형 탐색 트리이다. Point Query는
O(log_B N), Range Query는O(log_B N + K)의 시간 복잡도를 가지며, 디스크 I/O를 최소화할 수 있어 대부분의 데이터베이스 인덱스 구조로 사용된다.