📚 B-Tree 완벽 정리 - 디스크 기반 탐색을 위한 균형 트리
✅ B-Tree란?
B-Tree는 다중 분기(multi-way branching)를 허용하는 균형 잡힌 탐색 트리로, 디스크나 외부 저장 장치에 저장된 데이터를 빠르게 탐색하기 위해 설계된 트리이다.
일반적인 이진 탐색 트리는 메모리 기반으로 작동하지만, B-Tree는 블록 단위로 데이터를 다루는 환경에 최적화되어 있다.
데이터베이스, 파일시스템, 인덱싱 시스템 등에서 광범위하게 사용된다.
실전 구현은 상당히 복잡하므로, 일반적으로는 라이브러리나 DB 시스템 내부에 구현되어 있다.
이 포스팅에서 구현은 생략하겠다.
✅ 특징
- 노드 하나에 여러 개의 키와 자식 포인터를 가질 수 있다.
- 트리의 높이가 낮고, 균형이 항상 유지된다.
- 중간에서 삽입/삭제가 가능하다.
- 디스크 I/O를 줄이기 위해 노드가 디스크 블록 단위로 매핑된다.
- Inorder 순회 시 오름차순 정렬된 결과를 얻을 수 있다.
✅ 기본 구조
- 각 노드는 최대
2t - 1개의 키를 저장할 수 있다. (t: 최소 차수) - 각 노드는 최소
t - 1개의 키를 가져야 한다. (단, 루트 제외) - 노드에
n개의 키가 있다면,n + 1개의 자식 포인터를 가진다. - 키는 오름차순 정렬 상태로 유지된다.
✅ 삽입
- 항상 리프 노드에 삽입된다.
- 삽입 시 노드가 가득 찼다면 → 노드를 분할(split) 해야 한다.
- 중간 키가 위로 올라가고, 좌우는 분리되어 새로운 자식이 된다.
- 이 과정이 재귀적으로 루트까지 전파될 수 있다.
✅ 삭제
삭제는 다음의 세 가지 경우로 나뉜다.
- 리프 노드에서 직접 삭제 가능할 경우 → 그냥 제거
- 내부 노드 삭제:
- 왼쪽 자식에서 최대값 or 오른쪽 자식에서 최소값으로 교체
- 교체 후 해당 서브트리에서 다시 삭제
- 삭제로 인해 키 개수가 부족해진 경우:
- 형제에게 빌려오거나
- 형제와 병합하여 부모에서 키를 내려받는다
→ 이 과정에서도 재귀적 구조 복구가 일어날 수 있다.
✅ 시간복잡도
| 연산 | 시간복잡도 |
|---|---|
| 탐색 | O(log n) |
| 삽입 | O(log n) |
| 삭제 | O(log n) |
노드 하나 안에서는 이진 탐색을 통해 키를 찾기 때문에 각 노드 안의 탐색은 O(log m), 트리 높이는 O(log n)이다.
🎯 마무리 요약
- B-Tree는 디스크 기반 탐색을 위해 설계된 균형 잡힌 트리이다.
- 하나의 노드가 여러 개의 키와 자식을 가질 수 있어 트리의 높이를 줄인다.
- 삽입과 삭제 시 노드 분할/병합을 통해 항상 균형을 유지한다.
- 파일시스템, 데이터베이스 인덱스 등 실전 환경에서 매우 중요하게 사용된다.
멋있는 사람이 되는 게 꿈입니다