B-Tree (Balanced Tree) - 데이터베이스 인덱스 구조
1. 정의
- B-Tree는 균형 이진트리를 일반화한 **다진 균형 검색 트리(M-ary Balanced Search Tree)**이다.
- 모든 리프 노드는 동일한 깊이를 가지며, 트리의 높이를 최소화하여 디스크 접근 횟수를 줄인다.
- 노드 하나에 여러 개의 키와 자식 포인터를 저장하여 디스크 I/O 비용을 줄이고 대용량 데이터 처리에 최적화된 구조이다.
2. 구조
- 차수(m): 하나의 노드가 가질 수 있는 최대 자식 수.
- 각 노드는 최대 m-1개의 키와 최대 m개의 포인터를 가진다.
- 키는 오름차순으로 정렬되어 저장되며, 키의 구간에 따라 포인터가 자식 노드를 가리킨다.
- 리프 노드에는 데이터의 실제 위치 또는 포인터가 존재한다.
노드 구성 예시 (차수 m = 4):
[10 | 20 | 30]
↓ ↓ ↓ ↓- 자식은 4개, 키는 3개. 각 키 사이에 포인터가 배치됨.
3. 연산
3.1 검색 (Search)
- 루트 노드에서 시작해 키를 비교하며 자식 포인터를 따라 내려간다.
- 리프 노드에 도달하면 해당 키 존재 여부 확인.
- 시간 복잡도: O(logₘ N)
3.2 삽입 (Insert)
- 적절한 리프 노드 탐색.
- 키 삽입.
- 삽입 후 키 개수가 m 이상이면 노드 분할(Split) 발생.
- 중간 키가 부모로 **승격(Promotion)**됨.
- 루트까지 전파되면 트리의 높이 증가 가능.
3.3 삭제 (Delete)
-
삭제할 키 탐색 후 제거.
-
키 개수가 최소값(m/2 - 1) 미만이면,
- 형제 노드로부터 **차용(Redistribution)**하거나
- 형제와 **병합(Merge)**하여 균형 유지.
-
루트가 비면 트리 높이 감소.
4. B-Tree의 특징
- 모든 리프는 같은 깊이.
- 한 노드에 여러 키/포인터 → 트리 높이 낮음.
- 디스크 블록 단위로 노드 구성 → I/O 최소화.
- 검색, 삽입, 삭제 모두 로그 시간 복잡도.
5. B-Tree vs B+Tree
| 항목 | B-Tree | B+Tree |
|---|---|---|
| 데이터 저장 위치 | 모든 노드 | 리프 노드만 |
| 범위 검색 성능 | 낮음 | 높음 (리프 간 연결) |
| 인덱스 용도 | 제한적 | 대부분의 DBMS 기본 구조 |
- 대부분의 상용 DBMS는 B+Tree를 인덱스 구조로 사용한다.
6. DBMS에서의 활용
| DBMS | 인덱스 구조 |
|---|---|
| Oracle | B*-Tree (B+Tree 기반에 노드 분할 최적화) |
| MySQL (InnoDB) | B+Tree 인덱스 (클러스터형 포함) |
| PostgreSQL | B+Tree 기본, GiST, GIN도 지원 |
- B+Tree 인덱스는 클러스터형 인덱스로 사용될 때, 리프 노드에 실제 데이터 레코드를 포함한다.
7. 성능 및 설계 고려사항
7.1 인덱스 성능 영향 요소
- 트리 깊이: 깊을수록 디스크 접근 횟수 증가.
- 노드 크기: 디스크 블록 크기에 맞춰 최적화 필요.
- 중복 키: 특정 리프에 부하 집중 → Hot Spot 발생.
- 삽입/삭제 빈도: 리밸런싱 비용 고려.
7.2 인덱스 튜닝 포인트
- 자주 사용하는 컬럼에 인덱스 생성.
- 읽기 위주 시스템: 범위 검색 최적화된 B+Tree 적합.
- 쓰기 많은 테이블: 인덱스 수 최소화, 재구성 주기 관리.
8. 확장된 형태
| 구조 | 설명 |
|---|---|
| B*-Tree | B-Tree의 노드 분할 비율을 최적화하여 공간 효율 증가 |
| LSM Tree | 쓰기 성능을 극대화하기 위한 구조 (NoSQL 계열 사용) |
| Fractal Tree | 비동기식 노드 분산으로 쓰기 병목 해소 |
9. 요약
- B-Tree는 균형 잡힌 검색 트리로 디스크 최적화된 인덱스 구조이다.
- 검색/삽입/삭제 연산에서 성능 예측이 용이하고 안정적이다.
- 범위 질의와 대용량 데이터 처리를 고려할 경우, B+Tree를 사용하는 것이 일반적이다.
- 데이터베이스 성능을 위해 B-Tree 구조에 대한 이해는 인덱스 설계와 튜닝의 핵심 요소이다.
B-Tree vs B+Tree에서의 데이터 저장 위치 차이
| 항목 | B-Tree | B+Tree |
|---|---|---|
| 데이터 저장 위치 | 내부 노드와 리프 노드 모두에 저장 가능 | 리프 노드에만 저장 |
| 내부 노드 | 일부 실제 데이터를 포함 | 오직 인덱스(키 값)만 저장 |
| 리프 노드 | 일부 또는 전부 저장 | 모든 데이터 저장 |
B-Tree
- 키와 함께 **실제 데이터 포인터(또는 값)**를 내부 노드와 리프 노드 모두에 저장할 수 있음.
- 검색 시 중간 노드에서 바로 원하는 데이터를 찾는 경우도 있음.
B+Tree
- 내부 노드는 오직 키 값과 포인터만 저장.
- 모든 실제 데이터(레코드 포인터 또는 데이터 값)는 리프 노드에만 저장됨.
- 리프 노드는 순차 검색을 위한 연결 포인터를 포함 → 범위 검색 최적화.
예시:
B+Tree 구조 예시
내부 노드: [10 | 20 | 30]
↓ ↓ ↓ ↓
리프 노드: [1, 2, 3] - [10, 12, 15] - [21, 25, 29] - [31, 32]- 내부 노드: 데이터 없음, 키 값만 있음
- 리프 노드: 데이터 저장, 리프 간 포인터 연결
정리
- "데이터는 리프 노드에만 저장된다"는 표현은 B+Tree의 특징입니다.
- B-Tree는 내부와 리프 모두에 저장 가능.
- 대부분의 DBMS는 B+Tree 기반 인덱스를 사용하므로, 이 표현이 흔히 언급됩니다.
DevSecOps Pentest🚩