B-Tree와 B+Tree
데이터베이스의 기본 인덱스가 이진 탐색 트리(BST)가 아니라 B+Tree인 데에는 명확한 이유가 있습니다. 디스크 I/O를 최소화하도록 설계된 자료구조이기 때문입니다. 디스크 접근은 메모리 접근보다 수만~수십만 배 느리므로, 디스크 접근 횟수를 줄이는 것이 데이터베이스 성능의 핵심입니다.
이진 탐색 트리의 한계
이진 탐색 트리는 메모리에서는 효율적이지만 디스크 기반 데이터베이스에서는 문제가 있습니다.
BST는 노드당 키가 1개이므로 트리가 깊어집니다. 디스크에서는 한 번 읽을 때 하나의 블록(보통 4KB~8KB)을 가져오므로, 한 노드에 여러 키를 넣는 B-Tree가 유리합니다.
디스크 블록 크기: 8KB
BST 한 노드: 키 1개 + 포인터 2개 ≈ 수십 바이트
→ 8KB 블록에 키 1개만 사용 → 대부분 낭비
B-Tree 한 노드: 키 수백 개 + 포인터 수백 개
→ 8KB 블록을 꽉 채워 사용
→ 한 번 디스크 접근으로 수백 개 키 비교 가능
핵심: 디스크 블록 활용률을 최대화하여 I/O 횟수를 최소화B-Tree의 구조
B-Tree는 하나의 노드에 여러 키를 저장하는 균형 탐색 트리입니다. 1972년 Rudolf Bayer와 Edward McCreight가 발명했습니다.
B-Tree 용어
B-Tree 구조 예시
B-Tree의 특성
| 특성 | 설명 |
|---|---|
| 균형 트리 | 모든 리프 노드의 깊이가 같음 |
| 다진 트리 | 한 노드에 여러 키 저장 (차수 m이면 최대 m-1개 키) |
| 정렬 유지 | 키가 정렬된 상태로 저장 |
| 자동 균형 | 삽입·삭제 시 자동으로 균형 유지 (Split, Merge) |
| 데이터 위치 | 모든 노드에 데이터(또는 포인터) 저장 가능 |
| 시간 복잡도 | 검색, 삽입, 삭제 모두 O(log N) |
B-Tree 검색 과정
B+Tree — 데이터베이스의 표준 인덱스
B+Tree는 B-Tree를 개선한 변형으로, 대부분의 RDB가 기본 인덱스로 사용합니다.
B-Tree와의 핵심 차이: 실제 데이터(또는 ROWID)가 리프 노드에만 있고, 리프 노드끼리 연결 리스트로 연결됩니다.
B+Tree의 특성
B-Tree vs B+Tree 상세 비교
| 비교 항목 | B-Tree | B+Tree |
|---|---|---|
| 데이터 위치 | 모든 노드에 가능 | 리프 노드에만 |
| 리프 연결 | 없음 | 이중 연결 리스트 |
| 범위 검색 | 중위 순회 필요 (비효율) | 리프에서 순차 탐색 (효율적) |
| 내부 노드 크기 | 데이터 포함으로 큼 | 키만 저장하므로 작음 |
| 같은 블록에 키 수 | 적음 (데이터 크기 차지) | 많음 (팬아웃 높음) |
| 동일 데이터 검색 | 내부 노드에서 끝날 수 있음 | 항상 리프까지 내려감 |
| 검색 시간 일관성 | 불균일 (키 위치에 따라 다름) | 균일 (항상 같은 깊이) |
| 실제 DBMS 사용 | 거의 없음 | Oracle, MySQL, PostgreSQL 등 표준 |
범위 검색 비교
B+Tree가 RDB의 표준이 된 핵심 이유는 범위 검색(Range Scan) 성능입니다.
B+Tree 삽입과 분할
B+Tree에 새 키를 삽입할 때 리프 노드가 꽉 차면 Split(분할)이 발생합니다.
삽입 과정
1단계: 적절한 리프 노드 찾기 (루트부터 탐색)
2단계: 리프에 키 삽입 (정렬 순서 유지)
3단계-A: 공간이 있으면 완료
3단계-B: 공간이 없으면 리프 분할 (Split)
리프 분할
* 키를 반으로 나누어 두 리프로 분리
* 오른쪽 리프의 첫 키를 부모에 복사 (Copy-up)
* 부모도 꽉 차면 부모도 분할 (이때는 Push-up)
내부 노드 분할
* 키를 반으로 나누고 중간 키를 부모로 올림 (Push-up)
* 리프 분할은 Copy-up, 내부 분할은 Push-up삭제 과정
B+Tree 높이와 저장 용량
DBMS에서의 실제 B+Tree 구현
Oracle
* 인덱스 블록 크기: DB_BLOCK_SIZE (보통 8KB)
* 높이 확인: SELECT blevel FROM dba_indexes WHERE ...
* blevel=0이면 루트만, blevel=2이면 높이 3
MySQL InnoDB
* 페이지 크기: innodb_page_size (기본 16KB)
* 클러스터드 인덱스: PK가 B+Tree 리프에 전체 행 저장
* 세컨더리 인덱스: PK 값을 포인터로 저장
PostgreSQL
* 블록 크기: 8KB (기본)
* B+Tree의 변형: Lehman-Yao B+Tree 사용
* 동시성 제어 최적화: 형제 포인터 + 하이 키(High Key)-- Oracle: B-Tree 높이 확인
SELECT index_name, blevel, leaf_blocks, num_rows
FROM user_indexes
WHERE table_name = 'PRODUCTS';
-- blevel + 1 = B-Tree 높이
-- MySQL: 인덱스 통계
SELECT stat_name, stat_value
FROM mysql.innodb_index_stats
WHERE table_name = 'products'
AND stat_name IN ('size', 'n_leaf_pages');B+Tree 외의 인덱스 자료구조
B+Tree가 범용적이지만 모든 상황에 최적은 아닙니다.
Hash Index 상세
-- Memory 엔진은 Hash 인덱스가 기본
CREATE TABLE sessions (
session_id VARCHAR(64),
user_id INT,
data TEXT,
INDEX USING HASH (session_id)
) ENGINE = MEMORY;
-- InnoDB Adaptive Hash Index
-- 자주 접근되는 인덱스 페이지를 자동으로 해시 인덱스로 구성
-- 별도 설정 없이 InnoDB가 자동 관리
SHOW VARIABLES LIKE 'innodb_adaptive_hash_index';Bitmap Index 상세
LSM-Tree 개요
B+Tree 연습 문제
문제: 차수 200인 B+Tree, 리프 노드당 최대 100개 레코드 저장
총 5000만 건의 데이터를 저장하려면 최소 높이는?
풀이
높이 3: 200 × 200 × 100 = 4,000,000건 (부족)
높이 4: 200 × 200 × 200 × 100 = 800,000,000건 (충분)
답: 높이 4 (디스크 I/O 최대 4회)문제: 다음 중 B+Tree의 특성이 아닌 것은?
A. 모든 리프 노드의 깊이가 같다
B. 내부 노드에도 데이터가 저장된다 ← 정답!
C. 리프 노드끼리 연결 리스트로 연결된다
D. 범위 검색에 효율적이다
해설: B+Tree에서 데이터는 리프 노드에만 저장됩니다.
내부 노드는 검색을 위한 라우팅 키만 저장합니다.
B는 B-Tree의 특성입니다.정리
| 개념 | 설명 |
|---|---|
| B-Tree | 다진 균형 탐색 트리, 모든 노드에 데이터 가능 |
| B+Tree | B-Tree 개선, 데이터는 리프에만, 리프 연결 리스트 |
| 차수(Order) | 한 노드의 최대 자식 수 |
| 팬아웃 | 한 노드에서 나가는 포인터 수, 클수록 트리 낮아짐 |
| Split | 노드 초과 시 분할, 키를 상위로 올림 |
| Merge | 노드 부족 시 형제와 병합 |
| 범위 검색 | B+Tree의 핵심 강점, 리프 순차 탐색 |
| 높이 | 보통 3~4, 수억 건 데이터 처리 가능 |
| Hash Index | 동등 검색 O(1), 범위 검색 불가 |
| Bitmap Index | 비트 연산으로 다중 조건 빠르게 처리 |
| LSM-Tree | 쓰기 최적화, 로그/시계열 데이터에 적합 |
B+Tree는 디스크 I/O를 최소화하도록 설계된 자료구조입니다. 한 노드에 수백 개의 키를 저장하여 트리 높이를 낮추고, 리프 노드의 연결 리스트를 통해 범위 검색을 효율적으로 처리합니다. 대부분의 RDBMS는 B+Tree를 기본 인덱스 구조로 사용하며, InnoDB의 클러스터드 인덱스는 B+Tree의 리프에 전체 행 데이터를 저장하는 특수한 형태입니다.
다음 절에서는 클러스터드 인덱스, 비클러스터드 인덱스 등 인덱스의 종류를 다루겠습니다.