B-Tree와 B+ Tree로 설계하는 데이터베이스 인덱스
B-Tree와 B+ Tree의 페이지 기반 구조, 탐색·분할·병합 흐름, 범위 조회와 인덱스 튜닝 관점을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
페이지 접근 횟수를 줄이는 인덱스 구조
B-Tree와 B+ Tree는 데이터베이스 인덱싱에서 널리 쓰이는 다분기 균형 탐색 트리다. 노드 크기를 디스크 페이지 크기에 맞추고 한 노드가 많은 자식 포인터를 갖게 해, 대량의 키를 낮은 높이로 관리한다. 이 구조는 랜덤 I/O를 줄이면서 OLTP의 포인트 조회와 OLAP의 범위 스캔에 모두 대응한다.
B-Tree에서는 내부 노드와 리프 노드가 모두 키와 레코드 또는 포인터를 보관한다. B+ Tree는 실제 레코드를 리프 노드에만 두고, 내부 노드는 키와 자식 포인터로 탐색 경로를 구성한다. 리프 노드는 연결 리스트로 이어져 있어 키 범위를 따라 읽을 때 순차 접근을 유도할 수 있다. 대부분의 상용 DBMS가 기본 인덱스 구조로 B+ Tree를 채택하는 배경이다.
차수, 즉 팬아웃은 노드가 보유할 수 있는 최대 자식 수다. 팬아웃이 커질수록 트리 높이 h는 낮아지고 I/O 횟수도 줄어든다. 높이는 h ≈ O(log_f N)으로 표현하며, f는 팬아웃, N은 키 수다. 수백만수억 건에서도 h가 35 수준으로 유지된다. 채움률(fill factor)은 분할과 병합 빈도, 쓰기 증폭을 조절하기 위해 노드에 남겨 두는 여유 공간 비율이다.
탐색 경로와 구조 변경이 만나는 지점
검색, 삽입, 삭제는 키 k와 연산 유형을 받은 뒤 루트에서 리프까지 내려가는 흐름을 공유한다. 내부 노드에서 키를 찾고 자식 포인터를 선택해 리프에 도달한 다음, 검색 결과를 반환하거나 삽입·삭제 결과를 처리한다. 장애가 발생하면 로그와 리커버리 경로가 이어진다.
삽입 시 리프에 공간이 없으면 페이지를 분할하고 상위 키를 승격한다. 상위 노드까지 연쇄 분할될 수 있다. 삭제로 언더플로가 생기면 인접 노드와 재분배하거나 병합하며, 경우에 따라 루트 높이가 줄어든다. 동시성 제어에는 래치 커플링(latch coupling)을 사용해 경합을 줄이고 데드락을 방지하며, W-A-L(Write-Ahead Logging)로 크래시 세이프티를 확보한다.
레코드 락과 페이지 래치는 분리해서 운용한다. MVCC 환경에서는 방문 중인 노드를 래치로 잠시 보호하고, 커밋 일관성은 트랜잭션 락 또는 스냅샷으로 보장한다. 분할과 병합이 발생하면 로그 기록, 더티 페이지 플러시, 체크포인트 동기화가 뒤따른다.
버퍼 매니저는 루트와 상위 내부 노드 같은 핫셋을 상주시켜 탐색 I/O를 상수화한다. 범위 스캔에서는 리프를 따라 프리페치와 리드어헤드를 적용해 순차 I/O를 유도한다. 프리픽스 압축과 중복 키 제거는 키 공간을 줄여 팬아웃을 높이고 I/O를 낮춘다.
B+ Tree가 범위 조회에 강한 이유
디스크 페이지에 맞춘 노드 레이아웃은 키와 포인터 배치를 효율화한다. 프리픽스와 바라이트(Varint) 인코딩으로 키가 차지하는 공간을 줄이면 하나의 노드에 더 많은 항목을 담을 수 있다.
팬아웃을 수백 단위로 확보하면 트리 높이는 34 수준으로 유지된다. 콜드 캐시에서도 34회 랜덤 I/O 내 응답을 보장하고, 핫 캐시에서는 메모리 접근으로 상수 시간에 가까워진다.
B+ Tree의 리프 레벨 연결 리스트는 범위 조회를 리프 간 순차 접근으로 바꾼다. 커버링 인덱스를 구성하면 테이블 접근 자체를 없애 레이턴시를 최소화할 수 있다. 분할과 병합은 국소적으로 처리되므로 전체 구조를 다시 만들 필요가 없으며, WAL, 체크포인트, 페일리스트(freelist)가 장애 내구성을 뒷받침한다.
운영에서는 채움률, 페이지 크기, 키 정렬과 콜레이션, 전용 버퍼 풀과 핀ning 전략을 함께 살펴야 한다. 선택도와 히스토그램 같은 통계를 비용 모델에 반영하는 일도 올바른 인덱스 선택과 연결된다.
B-Tree와 B+ Tree의 접근 특성
| 항목 | B-Tree | B+ Tree | 실무 관점 주석 |
|---|---|---|---|
| 성능(포인트 조회) | 내부/리프 모두 데이터 보유, 약간 유리할 수 있음 | 대부분의 DB 최적화 대상, 차이 미미 | 캐시 적중 시 차이 축소 |
| 성능(범위 조회) | 내부/리프 혼재로 다소 비효율 | 리프 연속 연결로 매우 효율 | 스캔·정렬 비용 절감 |
| 확장성 | 유사 | 유사하나 실구현 최적화 풍부 | B+ Tree가 산업 표준 |
| 일관성/복구 | WAL/체크포인트 필요 | 동일 | 구현 품질이 좌우 |
| 운영 편의 | 구현 다양성 | 구현·도구 생태계 우수 | RDBMS 기본 인덱스 구조 |
DBMS 인덱스 설계에서 보는 지점
MySQL InnoDB의 프라이머리 키는 클러스터드 B+ Tree이며, 리프에 실제 레코드를 저장한다. 보조 인덱스는 리프에 PK를 포함하므로 보조 인덱스에서 PK를 다시 찾는 루크업 더블탭이 가능하다. 이 때문에 PK 길이 최적화가 필요하다.
PostgreSQL은 기본 B-Tree 인덱스를 제공하며 deduplication과 HOT 업데이트로 쓰기 비용을 줄인다. FILLFACTOR는 분할 빈도 제어에 사용하고, REINDEX와 CLUSTER로 파편화를 관리한다. Oracle과 SQL Server 같은 상용 DBMS도 B+ Tree 기반으로 동작하며, INCLUDE 컬럼을 이용한 커버링과 파티셔닝을 조합해 대용량 범위 스캔을 최적화한다.
커버링 인덱스는 SELECT 컬럼을 인덱스에 포함해 테이블 접근을 없앤다. 읽기 경로가 인덱스 스캔으로 끝나므로 레이턴시와 I/O를 줄일 수 있다. 복합 인덱스에서는 선택도가 높은 조건 컬럼을 선두에 두고 정렬·그룹핑 컬럼을 포함한다. 엔진이 지원한다면 문자열에 프리픽스 인덱스를 적용해 크기와 팬아웃을 개선할 수 있다.
PostgreSQL에서는 WHERE 조건에 맞춘 부분 인덱스로 인덱스 크기와 유지비를 줄일 수 있으며, 표현식 기반 B-Tree는 계산 컬럼 최적화에 사용된다.
인덱스 운영 시에는 키 길이와 카디널리티를 관리해야 한다. 키 길이가 줄면 팬아웃은 늘고 높이는 낮아진다. 쓰기 중심 워크로드에서는 채움률을 낮게 설정해 분할 스톨을 완화한다. 페이지 분할률, 리프 체인 길이, 인덱스 크기와 블로트 지표로 파편화를 점검하고, 선택도와 히스토그램을 최신화해 옵티마이저가 적절한 인덱스를 고르게 해야 한다.
예시 SQL
-- PostgreSQL 15+
CREATE INDEX idx_orders_ux
ON orders USING btree (customer_id, order_date DESC)
WITH (fillfactor = 85);
-- MySQL 8.0 (InnoDB)
CREATE INDEX idx_user_email ON users(email);
-- 대체: 긴 문자열은 접두 인덱스
CREATE INDEX idx_doc_title_prefix ON docs(title(100));전제조건: 대상 DBMS 버전 기능 지원 여부 확인 필요.
페이지 크기와 팬아웃이 만드는 효과
페이지가 8KB이고 키와 포인터 평균이 32바이트라고 가정하면 팬아웃은 f ≈ 8KB/32B ≈ 256이다. N=1천만 건일 때 높이는 h ≈ log_256(10^7) ≈ 3.0~4.0이며, 콜드 캐시에서도 3~4 랜덤 I/O 내 조회가 가능하다.
핫셋이 상주한 경우 포인트 조회 P99 레이턴시는 수 ms에서 수백 μs 수준을 기대할 수 있다. 범위 스캔은 순차 프리페치로 스루풋이 수배 향상된다. 채움률과 배치 삽입을 활용하면 분할·병합에 따른 쓰기 증폭을 1.11.5배 수준으로 관리할 수 있고, Dedup과 압축을 적용하면 인덱스 크기를 2060% 축소하면서 캐시 히트율을 높일 수 있다.
클러스터드·보조 인덱스 전략, 커버링·복합 인덱스 설계, 분할·병합 튜닝은 서로 분리된 선택이 아니다. 페이지 구조와 워크로드를 함께 보면서 키 길이, 채움률, 통계를 관리할 때 B-Tree와 B+ Tree의 I/O 절감 효과가 실제 운영 경로로 이어진다.