B-Tree
이진 탐색 트리는 메모리 안에서 탐색을 보장합니다. 그런데 데이터가 디스크에 있는 순간, 그 보장은 사실상 무의미해집니다. B-Tree는 디스크라는 물리적 제약 위에서 탄생한 자료구조이며, 그 구조의 모든 결정이 하나의 원칙을 따릅니다.
B-Tree란
B-Tree는 자기-균형 다진 탐색 트리(self-balancing m-way search tree)입니다. 이진 탐색 트리(BST)가 노드당 자식을 최대 2개 갖는 것과 달리, B-Tree는 노드 하나가 수십에서 수백 개의 키를 담고 그보다 하나 더 많은 자식 포인터를 가집니다.
| 성질 | 설명 |
|---|---|
| 차수(order) | 한 노드가 가질 수 있는 최대 자식 수. 노드당 최대 개 키 |
| 노드 내 정렬 | 키는 항상 오름차순. 노드 안에서도 이진 탐색 가능 |
| 균형 보장 | 모든 리프가 같은 깊이. 분할(split)과 병합(merge)이 자동 유지 |
| 최소 점유율 | 루트 제외 모든 노드는 최소 개 자식 보유 |
왜 필요한가
BST는 메모리 안에서는 훌륭합니다. 하지만 데이터가 메모리에 다 들어가지 않아 디스크에 저장해야 하는 순간, 구조적 약점이 드러납니다.
BST는 노드 하나에 키 하나만 담고, 탐색할 때 트리 높이만큼 노드를 방문합니다. 100만 건이면 높이가 약 20입니다. 노드가 디스크의 서로 다른 위치에 흩어져 있다면, 20번의 디스크 랜덤 I/O가 발생합니다.
디스크 랜덤 I/O의 비용은 메모리 접근과 비교할 수 없을 정도로 큽니다.
| 저장 매체 | 랜덤 I/O 지연 | 메모리 대비 |
|---|---|---|
| HDD | ~10ms | 약 100,000배 |
| SSD | ~0.1ms | 약 1,000배 |
| 메모리 | ~100ns | 기준 |
B-Tree는 이 격차를 세 가지 전략으로 해결합니다.
1. 노드 = 디스크 블록
하나의 노드를 디스크 페이지(4KB – 16KB)에 맞춥니다. 디스크는 어차피 블록 단위로 읽으므로, 한 번의 I/O로 수백 개의 키를 가져옵니다.
2. 트리 높이 감소
차수가 1,000인 B-Tree(16KB 페이지에 약 1,000개 키)라면, 10억 건의 데이터도 높이가 3–4입니다. BST의 30번 I/O가 B-Tree에서는 3–4번으로 줄어듭니다.
3. 노드 내부 정렬
노드 안의 키들이 정렬되어 있으므로, 한 번 노드를 읽으면 그 안에서의 탐색은 메모리 내 이진 탐색입니다. 추가 I/O가 발생하지 않습니다.
동작 원리
탐색
차수 5인 B-Tree에서 키 42를 찾는 과정을 따라갑니다.
루트 노드를 읽습니다. 키 [20, 40, 60, 80]이 있습니다. 42는 40보다 크고 60보다 작으므로 40과 60 사이의 자식 포인터를 따라갑니다. 해당 자식 노드를 읽습니다. [41, 43, 45, 47]이 있습니다. 42는 41과 43 사이이므로 다시 자식 포인터를 따라갑니다. 리프 노드에서 42를 발견하면 탐색 성공, 없으면 실패입니다.
매 단계에서 한 번의 디스크 I/O + 노드 내 이진 탐색이 일어납니다. 트리 높이가 면 정확히 번의 I/O로 어떤 키든 찾을 수 있습니다.
삽입과 분할
삽입은 두 단계로 나뉩니다. 적절한 리프 찾기, 그리고 키 삽입입니다.
리프에 빈 공간이 있으면 정렬 순서에 맞게 삽입하고 끝납니다. 문제는 리프가 이미 가득 찬 경우입니다. 이때 **분할(split)**이 발생합니다.
차수 4인 B-Tree(노드당 최대 3개 키)에서 분할 과정을 봅니다.
리프 [25, 30, 35]에 28을 삽입하면 임시로 [25, 28, 30, 35]가 됩니다. 키가 4개로 최대를 초과했으므로 분할이 필요합니다. 중간 키 30을 선택하고, 왼쪽 [25, 28]과 오른쪽 [35]로 나눕니다. 중간 키 30은 부모 노드로 올라갑니다(promote). 부모도 가득 차 있으면 부모에서도 분할이 발생하며, 이 과정이 루트까지 전파될 수 있습니다.
아래 시각화에서 이 과정을 단계별로 확인할 수 있습니다.
B-Tree 삽입과 분할
키 28을 삽입할 때 노드 분할이 발생하는 과정을 단계별로 확인하세요.
삭제
삭제는 삽입의 역방향이지만 더 복잡합니다.
리프에서 키를 제거한 후 최소 점유율(개 키)을 만족하면 끝납니다. 만족하지 못하면 언더플로우가 발생합니다. 이때 형제 노드에서 키를 빌려오거나(재분배), 형제와 **병합(merge)**합니다. 병합이 부모까지 전파되면 트리 높이가 1 감소합니다. 분할의 역과정입니다.
적합한 상황
써야 할 때
| 상황 | 이유 |
|---|---|
| 디스크 기반 대량 데이터 | 노드 = 디스크 블록 대응으로 I/O 최소화 |
| 범위 쿼리 빈번 | 키 정렬 → BETWEEN, >, < 효율적 처리 |
| 정렬 결과 필요 | ORDER BY를 인덱스 순서 그대로 반환 |
| 파일시스템 메타데이터 | NTFS, HFS+, ext4(htree) 등이 채택 |
피해야 할 때
| 상황 | 대안 |
|---|---|
| 데이터가 전부 메모리 | 해시 테이블, Red-Black Tree, Skip List |
| 등호 검색만 필요 | 해시 인덱스 |
| 쓰기가 극단적으로 많음 | LSM Tree (순차 I/O로 쓰기 처리량 우세) |
| 긴 가변 텍스트 키 | 역인덱스(inverted index) |
트레이드오프
B-Tree vs B+Tree
B+Tree는 B-Tree의 변형이며, 실무에서는 거의 B+Tree를 씁니다. 차이는 두 가지입니다.
데이터 위치: B-Tree는 내부 노드에도 데이터를 저장합니다. B+Tree는 리프에만 저장하고, 내부 노드는 키와 자식 포인터만 담습니다. 덕분에 같은 페이지 크기에 더 많은 키를 넣을 수 있어 팬-아웃이 높아지고, 트리 높이가 낮아집니다.
리프 연결: B+Tree의 리프 노드들은 Linked List로 연결되어 있습니다. 범위 쿼리 시 시작점을 찾고 리프를 순차 순회하면 됩니다. B-Tree에서는 중위 순회로 내부 노드를 오르내려야 합니다.
| 비교 항목 | B-Tree | B+Tree |
|---|---|---|
| 데이터 위치 | 내부 + 리프 | 리프만 |
| 내부 노드 팬-아웃 | 상대적으로 낮음 | 더 높음 |
| 범위 쿼리 | 중위 순회 필요 | 리프 Linked List 순회 |
| 단건 검색 | 내부에서 일찍 발견 가능 | 항상 리프까지 |
| 실무 채택 | 드묾 | MySQL, PostgreSQL, Oracle |
DB 워크로드는 범위 쿼리와 정렬이 압도적으로 많기 때문에 B+Tree가 사실상 표준이 되었습니다.
B-Tree vs 해시 인덱스
| 비교 항목 | B-Tree | 해시 인덱스 |
|---|---|---|
| 등호 검색 | ||
| 범위 쿼리 | 지원 | 불가 |
| 정렬 | 지원 | 불가 |
| 디스크 친화성 | 높음 | 낮음 |
해시 인덱스가 등호 검색에서 빠르지만, 범위 쿼리와 정렬을 지원하지 못하는 것이 결정적 약점입니다. 대부분의 DB 워크로드가 범위 쿼리를 필요로 하기 때문에 B-Tree 계열이 기본 인덱스로 채택됩니다.
B-Tree 계열의 근본적 트레이드오프는 읽기 성능 vs 쓰기 비용입니다. 높이 3–4로 어떤 키든 빠르게 읽을 수 있지만, 삽입 시 분할과 삭제 시 병합이 발생하고 랜덤 페이지 갱신이 필요합니다. 이 쓰기 증폭(write amplification)이 LSM Tree 같은 쓰기 최적화 구조가 등장한 배경입니다.
함께 읽으면 좋은 글
Database Index (데이터베이스 인덱스)
B+Tree 기반 인덱스의 내부 동작 원리를 이해하고, 복합 인덱스의 리프 노드 배치부터 등호 먼저·정렬 마지막 원칙, 인덱스 개수 결정까지 실전 설계 기준을 얻습니다.
마무리
B-Tree는 자료구조의 미학이 아니라 디스크 I/O 경제학의 산물입니다. 디스크 블록 단위 I/O라는 물리적 제약이 높은 팬-아웃을 강제했고, 그 결과 10억 건의 데이터도 3–4번의 I/O로 탐색할 수 있는 구조가 탄생했습니다. B+Tree와 해시 인덱스를 비교할 때도, 이 근본 제약에서 출발하면 각각의 트레이드오프가 자연스럽게 이해됩니다.