B-Tree와 B+Tree — 데이터베이스 인덱스가 이 구조를 쓰는 이유
수억 개의 레코드가 있는 테이블에서
WHERE id = 12345가 왜 이렇게 빠른 걸까요?
비밀은 **노드 하나에 키와 포인터를 수백 개씩 담아 트리 높이를 극단적으로 낮추는 구조 **, B-Tree와 B+Tree에 있습니다. 공부하다 보니 "키만 나열된" 설명으로는 실제 인덱스 페이지가 어떻게 생겼는지 감이 안 오더라고요. 이 글에서는 ** 포인터(p)와 키(key)가 번갈아 나오는 실제 노드 구조 **로 설명합니다.
시각화 도구를 함께 켜놓고 따라가면 이해가 훨씬 빠릅니다.
왜 B-Tree인가 — 디스크 I/O가 핵심
메모리 접근은 ~100ns, 디스크 접근은 ~10ms입니다. 10만 배 차이입니다. 트리 높이 = 디스크 접근 횟수이므로, 높이를 줄이는 것이 성능의 전부입니다.
BST: 10억 개 → 높이 약 30 → 디스크 30번 접근
B-Tree: 10억 개 → 높이 약 3 → 디스크 3번 접근
디스크는 한 번에 ** 페이지(보통 16KB)**를 읽습니다. B-Tree 노드 하나를 하나의 페이지에 맞추면, 한 번의 디스크 I/O로 수백 개의 키를 한꺼번에 비교할 수 있습니다.
B-Tree의 노드 구조 — 포인터와 키가 번갈아 나온다
B-Tree의 핵심을 한 문장으로 요약하면: "포인터 | 키 | 포인터 | 키 | 포인터"가 번갈아 나오는 구조 입니다.
내부 노드 (Internal Node)
차수(order) m인 B-Tree에서, 한 노드는 최대 m-1개의 키 와 m개의 자식 포인터 를 가집니다.
차수 4인 B-Tree 내부 노드:
p0 | 30 | p1 | 60 | p2 | 90 | p3
│ │ │ │
▼ ▼ ▼ ▼
<30 30~60 60~90 >90
(자식) (자식) (자식) (자식)
p0→ 키 30보다 작은 값들이 있는 자식 노드를 가리킴p1→ 키 30 이상, 60 미만인 값들의 자식 노드p2→ 키 60 이상, 90 미만p3→ 키 90 이상
B-Tree에서는 내부 노드에도 데이터 포인터가 붙을 수 있습니다. 즉, 키 30을 찾으러 왔는데 루트 노드에서 바로 발견할 수도 있습니다.
B-Tree 내부 노드 (키 + 데이터 포인터):
p0 | (30, dataPtr₃₀) | p1 | (60, dataPtr₆₀) | p2
↑ ↑
키 30의 실제 레코드 키 60의 실제 레코드
리프 노드 (Leaf Node)
B-Tree의 리프 노드도 ** 키 + 데이터 포인터** 쌍을 가집니다. 자식 포인터는 NULL입니다.
B-Tree 리프 노드:
∅ | (10, rowPtrA) | ∅ | (20, rowPtrB) | ∅ | (25, rowPtrC) | ∅
↑
자식이 없으므로 포인터는 NULL
rowPtrA→ 키 10에 해당하는 실제 행 데이터의 디스크 위치rowPtrB→ 키 20에 해당하는 행rowPtrC→ 키 25에 해당하는 행
전체 B-Tree 예시 (차수 3)
10, 20, 30, 40, 50, 60, 70을 삽입한 차수 3 B-Tree입니다.
루트 (내부 노드)
p0 | (30, dataPtr₃₀) | p1 | (50, dataPtr₅₀) | p2
│ │ │
▼ ▼ ▼
┌───────────┐ ┌────────────┐ ┌──────────────┐
│(10,rowA) │ │(40,rowD) │ │(60,rowF) │
│(20,rowB) │ │ │ │(70,rowG) │
└───────────┘ └────────────┘ └──────────────┘
리프 노드 리프 노드 리프 노드
※ B-Tree: 내부 노드(30, 50)에도 데이터 포인터가 있다!
면접에서 "B-Tree에서 키 30을 검색하면?"이라는 질문이 나오면, "루트 노드에서 바로 찾을 수 있습니다. 내부 노드에도 데이터가 있기 때문입니다" 라고 답할 수 있습니다.
B-Tree의 삽입과 분할
분할(Split) — 노드가 가득 차면
차수 3인 B-Tree에 순서대로 10, 20, 30을 삽입하는 과정입니다.
Step 1: 10 삽입
(10, rowA)
Step 2: 20 삽입
(10, rowA) | (20, rowB)
Step 3: 30 삽입 → 노드 가득 참! (차수 3이면 최대 키 2개)
(10, rowA) | (20, rowB) | (30, rowC) ← 오버플로!
→ 중간 키 20이 부모로 올라가고 노드가 분할됩니다:
(20, dataPtr₂₀)
/ \
(10, rowA) (30, rowC)
- 중간 키
20은 부모 노드로 승격 (부모가 없으면 새 루트가 됨) - 왼쪽 자식: 20보다 작은 키들
- 오른쪽 자식: 20보다 큰 키들
40, 50 추가 삽입
40 삽입 → 오른쪽 리프에 추가:
(20, dataPtr₂₀)
/ \
(10, rowA) (30, rowC) | (40, rowD)
50 삽입 → 오른쪽 리프 오버플로! → 분할:
p0 | (20, dataPtr₂₀) | p1 | (40, dataPtr₄₀) | p2
│ │ │
▼ ▼ ▼
(10, rowA) (30, rowC) (50, rowE)
이렇게 분할이 반복되면서 트리가 아래에서 위로 자랍니다. 모든 리프의 깊이가 항상 같으므로 ** 완전 균형 **이 유지됩니다.
B+Tree — B-Tree의 진화
B+Tree 는 대부분의 RDBMS(MySQL InnoDB, PostgreSQL, Oracle)가 사용하는 구조입니다. B-Tree와 결정적인 차이 두 가지:
- 내부 노드는 키 + 자식 포인터만 가진다 (데이터 포인터 없음)
- ** 리프 노드가 연결 리스트 **로 이어져 있다
B+Tree 내부 노드 — 인덱싱 전용
B+Tree 내부 노드 (데이터 없음, 라우팅만):
p0 | 20 | p1 | 40 | p2
│ │ │
▼ ▼ ▼
<20 20~40 ≥40
B-Tree 내부 노드와 비교하면:
B-Tree 내부 노드: p0 | (30, dataPtr₃₀) | p1 ← 키에 데이터 포인터가 붙음
B+Tree 내부 노드: p0 | 30 | p1 ← 키만! 데이터 없음!
** 데이터 포인터가 없으니 같은 16KB 페이지에 키를 훨씬 더 많이 넣을 수 있습니다.** → 팬아웃(fan-out)이 커지고 → 트리 높이가 더 낮아집니다.
B+Tree 리프 노드 — 데이터 + 링크드 리스트
B+Tree 리프 노드:
[(10, rowPtrA), (15, rowPtrB)] → [(20, rowPtrC), (25, rowPtrD)] → [(40, rowPtrE), (50, rowPtrF)]
리프 1 → 리프 2 → 리프 3
↑ ↑
리프 간 링크드 리스트로 연결
- 각 리프는
(키, 레코드 포인터)쌍의 목록 - 리프끼리 ** 오른쪽 형제 포인터(→)**로 연결
WHERE price BETWEEN 20 AND 50같은 범위 검색 시, 키 20이 있는 리프를 찾고 → 링크를 따라 50까지 쭉 훑으면 끝
B+Tree 전체 구조 예시
루트 (내부)
p0 | 30 | p1 | 60 | p2
│ │ │
▼ ▼ ▼
┌──────────┐ ┌──────────────┐ ┌──────────────┐
│ 내부 노드 │ │ 내부 노드 │ │ 내부 노드 │
│p0|15|p1 │ │p0|40|p1|50|p2│ │p0|70|p1|80|p2│
└──┬──┬────┘ └─┬──┬──┬──────┘ └─┬──┬──┬──────┘
│ │ │ │ │ │ │ │
▼ ▼ ▼ ▼ ▼ ▼ ▼ ▼
리프: [(10,rA),(12,rB)] → [(15,rC),(20,rD)] → [(30,rE),(35,rF)] → [(40,rG),(45,rH)] → ...
→ → →
리프 간 링크드 리스트
** 핵심 포인트:**
- 내부 노드의 키
30,60은 ** 라우팅용 **일 뿐, 실제 데이터는 리프에만 있음 - 내부 노드
30이 있어도 리프에(30, rE)가 또 있음 — ** 키가 중복 존재** - 리프만 순회하면 전체 데이터를 정렬된 순서로 읽을 수 있음
B-Tree vs B+Tree — 한눈에 비교
| 구분 | B-Tree | B+Tree |
|---|---|---|
| 내부 노드 | p0 | (key, dataPtr) | p1 | p0 | key | p1 (키만) |
| 리프 노드 | (key, dataPtr) | (key, dataPtr) + 형제 링크 |
| 데이터 위치 | ** 모든 노드 **에 있을 수 있음 | ** 리프 노드에만** 있음 |
| 리프 연결 | 없음 | 연결 리스트로 연결 |
| 팬아웃 | 상대적으로 작음 | 큼 (같은 페이지에 키를 더 넣음) |
| 점 검색 | 운 좋으면 내부 노드에서 바로 끝 | 항상 리프까지 내려감 |
| 범위 검색 | 트리 오르내리며 중위 순회 | 리프에서 링크 따라가기 (빠름) |
면접 포인트: "B-Tree는 내부 노드에도
(key, data pointer)가 있어 운 좋으면 검색이 빨리 끝날 수 있지만, B+Tree는 내부 노드에 키만 두어 팬아웃을 극대화하고, 리프의 연결 리스트로 범위 검색이 압도적으로 빠릅니다. 그래서 대부분의 RDBMS가 B+Tree를 씁니다."
MySQL InnoDB와 B+Tree
페이지 구조
InnoDB 페이지 (16KB):
┌────────────────────────────────────────────┐
│ Page Header (38 bytes) │
├────────────────────────────────────────────┤
│ p0 | key₁ | p1 | key₂ | p2 | ... | pₙ │ ← 내부 노드면 키+자식 포인터
│ 또는 │
│ (key₁, row₁) | (key₂, row₂) | ... │ ← 리프 노드면 키+행 데이터
├────────────────────────────────────────────┤
│ Page Directory │
│ FIL Trailer │
└────────────────────────────────────────────┘
INT(4B) 키 + 포인터(6B) = 약 10B per 엔트리
→ 한 페이지에 약 16KB / 10B ≈ 1,600개 키 저장 가능
높이와 레코드 수
높이 3인 B+Tree (팬아웃 ~1,000 기준):
- 루트(1개 페이지): ~1,000개 자식 포인터
- 레벨 1(1,000개 페이지): ~1,000,000개 자식 포인터
- 리프(1,000,000개 페이지): 페이지당 ~100 레코드
→ 약 1억 레코드를 디스크 3번 읽기로 검색!
높이 4면 약 1,000억 레코드까지 커버합니다.
클러스터드 인덱스 vs 세컨더리 인덱스
Primary Key (클러스터드 인덱스):
내부: p0 | PK₁ | p1 | PK₂ | p2
리프: [(PK₁, 행 데이터 전체), (PK₂, 행 데이터 전체), ...]
↑ 리프에 실제 row가 통째로 저장됨!
Secondary Index (넌클러스터드):
내부: p0 | email₁ | p1 | email₂ | p2
리프: [(email₁, PK값), (email₂, PK값), ...]
↑ 리프에 PK 값만 저장 → PK 인덱스에서 다시 검색 (더블 룩업)
세컨더리 인덱스로 검색하면 리프에서 PK 값을 얻고, PK 클러스터드 인덱스를 다시 타야 합니다. 이걸 ** 더블 룩업(Double Lookup)**이라고 합니다.
검색 과정 따라가기
WHERE id = 45를 B+Tree에서 검색하는 과정입니다.
Step 1: 루트 노드 읽기 (디스크 I/O 1회)
p0 | 30 | p1 | 60 | p2
45 > 30, 45 < 60 → p1로 이동
Step 2: 내부 노드 읽기 (디스크 I/O 2회)
p0 | 40 | p1 | 50 | p2
45 > 40, 45 < 50 → p1로 이동
Step 3: 리프 노드 읽기 (디스크 I/O 3회)
[(41, row₄₁), (43, row₄₃), (45, row₄₅), (48, row₄₈)]
45 발견! → row₄₅ 반환
총 디스크 I/O: 3회
시간 복잡도
| 연산 | 시간 복잡도 | 디스크 I/O |
|---|---|---|
| 검색 | O(log_m N) | O(log_m N) |
| 삽입 | O(log_m N) | O(log_m N) |
| 삭제 | O(log_m N) | O(log_m N) |
| 범위 검색 | O(log_m N + K) | O(log_m N + K/F) |
m: 차수(팬아웃), N: 전체 키 수, K: 결과 수, F: 페이지당 키 수
주의할 점
인덱스가 항상 빠른 건 아니다
인덱스는 읽기를 빠르게 하지만 쓰기(INSERT, UPDATE, DELETE)마다 인덱스 유지 비용(분할, 병합, 재정렬)이 추가됩니다. 쓰기가 빈번한 테이블에 인덱스를 과도하게 추가하면 오히려 느려집니다.
AUTO_INCREMENT PK와 페이지 분할
랜덤 UUID를 PK로 쓰면 리프 중간에 삽입이 일어나 페이지 분할이 빈번합니다. AUTO_INCREMENT PK를 쓰면 항상 오른쪽 끝에 삽입되어 분할이 최소화됩니다.
정리
- B-Tree 노드는
p0 | (key, dataPtr) | p1 | (key, dataPtr) | p2구조로, 내부 노드에도 데이터가 있을 수 있습니다 - B+Tree 내부 노드는
p0 | key | p1 | key | p2로 키만 가지고 (라우팅용), 실제 데이터 포인터는 리프에만 저장합니다 - B+Tree 리프는
[(key, rowPtr), ...] →형태로, 리프끼리 연결 리스트로 이어져 범위 검색에 강합니다 - MySQL InnoDB는 B+Tree 기반이며, 높이 3~4로 수억 레코드를 검색합니다
- 클러스터드 인덱스 리프에는 행 데이터 전체가, 세컨더리 인덱스 리프에는 PK 값이 저장됩니다
References
- B-Tree Visualization (USF) — B-Tree 삽입/삭제 과정을 시각적으로 확인
- B+Tree Visualization (USF) — B+Tree 구조와 리프 연결 리스트 시각화
- MySQL InnoDB Physical Structure — InnoDB 페이지 구조 공식 문서