B+ Tree 인덱스가 범위 조회를 처리하는 방식
B+ Tree의 내부 노드와 리프 체인 구조, 범위 스캔·분할·병합 과정과 인덱스 설계 시 고려할 트레이드오프를 정리합니다.
2026-08-14 · 최초 발행 2024-04-29
내부는 길을 찾고, 리프는 데이터를 이어 붙인다
B+ Tree는 데이터베이스와 파일시스템에서 널리 쓰이는 다분기 균형 검색 트리다. 내부 노드에는 key와 하위 노드 pointer만 두고, 실제 데이터 또는 레코드 pointer는 리프 노드에만 저장한다.
리프는 key 오름차순으로 정렬되며 단방향 또는 양방향 연결리스트로 이어진다. 특정 key를 찾을 때는 루트에서 리프까지 내려가고, 범위를 읽을 때는 시작 리프를 찾은 뒤 연결된 리프 체인을 계속 따라간다. 범위 조회 중에 트리를 반복해서 다시 탐색하지 않아도 되는 이유다.
노드 분할과 병합은 트리 높이를 제어한다. 이 균형 유지 방식 덕분에 탐색·삽입·삭제는 O(log_f N) 복잡도를 보장한다. 여기서 f는 fan-out이다.
Index Set과 Sequence Set의 역할 분리
내부 노드인 Index Set은 (key, pointer) 쌍으로 하위 노드를 가리킨다. 실제 데이터를 담지 않으므로 한 페이지에 더 많은 항목을 넣을 수 있고, fan-out이 커져 트리 높이와 랜덤 조회 I/O 수를 줄일 수 있다.
Sequence Set인 리프 노드는 실제 데이터 또는 데이터 레코드 pointer를 key 순서대로 보관한다. 모든 리프가 연결되어 있으므로, 범위 스캔과 순차 접근에서 캐시와 프리페치 효율을 높이기 좋다.
페이지 단위 접근도 이 구조와 맞물린다. 예를 들어 8~16KB 페이지에서 리프를 연속으로 읽으면 순차 I/O를 유도할 수 있다. 자주 경유하는 내부 노드는 버퍼 캐시에 남을 가능성이 높다.
동시성 제어에서는 노드 단위 latch를 커플링(crabbing)해 이동 경로를 일시적으로 보호한다. DBMS는 여기에 레코드·갭 락을 더해 트랜잭션 격리 수준을 보장하며, InnoDB의 range-lock이 그 예다.
리프 체인을 따라가는 조회 경로
단건 탐색은 루트부터 하향 이동해 해당 리프에 도달한 뒤 이진 검색으로 레코드를 찾는다. 복잡도는 O(log_f N)이며, 내부 노드가 캐시에 적중하면 접근 비용은 더 작아진다.
범위 스캔은 [a,b]에서 a가 있는 리프를 먼저 찾고, b를 넘을 때까지 리프 연결리스트를 순회한다. 반환 개수를 k라고 하면 복잡도는 O(log_f N + k)다. 리프 체인만 따라가므로 디스크 선형 읽기에도 유리하다.
분할과 병합이 균형을 지키는 방식
삽입은 대상 리프에서 시작한다. 페이지 용량을 초과하면 리프를 분할(split)하고, 구분자 key를 상위 노드로 전파한다. 분할은 연쇄될 수 있으며, 루트까지 분할되면 트리 높이는 +1 증가한다. DBMS에서는 이 과정에 로그 기록과 크래시 리커버리 전략이 필요하다.
삭제는 리프에서만 수행한다. 삭제 후 underflow가 발생하면 형제 노드에서 항목을 재분배하거나 병합(merge)한다. 상위 키를 조정하거나 삭제해야 할 수 있고, 경우에 따라 루트가 축소된다. 삭제와 병합 중에는 일시적 불균형이 생길 수 있어 latch로 단기 보호한다.
인덱스와 스토리지에서 만나는 B+ Tree
InnoDB의 클러스터드·보조 인덱스, PostgreSQL BTREE, SQL Server의 B-tree 기반 인덱스는 B+ Tree 파생 구현을 사용한다. 시간 구간 조회, 사용자 ID 범위 페이징, 리더보드 상위 N, 프리픽스 검색처럼 정렬된 범위를 자주 읽는 작업에 특히 맞는다.
파일시스템과 스토리지에서도 디렉터리 엔트리 정렬과 메타데이터 인덱싱에 쓰인다. HFS+, XFS 등이 해당하며, 캐시·스토리지 엔진에서는 페이지 크기와 키 크기를 조정해 fan-out을 높이고 트리 높이를 낮춘다.
다음은 MySQL 8.0/InnoDB에서 기본 B+ Tree 인덱스를 가정한 범위 스캔 예시다.
-- 전제조건: MySQL 8.0+, InnoDB, innodb_page_size=16KB
CREATE TABLE t (
id BIGINT PRIMARY KEY, -- 클러스터드 B+ Tree (리프에 전체 행)
created_at DATETIME,
val VARCHAR(100),
KEY idx_created (created_at) -- 보조 B+ Tree (리프에 PK 포함)
) ENGINE=InnoDB;
-- 범위 스캔: 리프 체인을 연속 순회
SELECT id, val
FROM t
WHERE created_at BETWEEN '2025-01-01' AND '2025-01-31'
ORDER BY created_at, id
LIMIT 1000;idx_created에서 시작 리프를 찾은 뒤 리프 연결리스트를 따라 순차 읽기를 수행한다. ORDER BY가 인덱스 정렬과 일치하면 파일 정렬 없이 순차 I/O를 활용할 수 있다.
페이지 구조가 성능에 미치는 영향
페이지 16KB, key+ptr 24B를 가정하면 내부 노드는 수백 수준의 fan-out을 확보할 수 있다. 1억 행에서는 높이가 ≈ 4이고, 랜덤 조회는 3~4 페이지 접근으로 처리된다.
리프 체인을 이용한 순차 접근은 SSD/HDD의 선형 읽기에 유리하고 CPU 캐시·프리페치 효율도 높인다. 워크로드가 변해도 분할과 병합으로 균형을 유지해 O(log_f N) 성능을 보장한다. 페이지 크기, fill factor, 키 크기를 페이지 단위로 조정하며 지속적으로 성능을 관리할 수 있다.
B-Tree와 비교할 때 달라지는 지점
| 지표 | B-Tree | B+ Tree |
|---|---|---|
| 성능(랜덤 조회) | 내부/리프에 데이터 혼재, fan-out 상대적으로 낮음 | 데이터가 리프에만 존재해 fan-out 증가, 높이 감소 |
| 성능(범위 스캔) | 트리 재탐색 빈번, 순차성 제한 | 리프 연결리스트 기반 선형 스캔 최적화 |
| 확장성 | 대용량에서 높이 증가 가능성 다소 큼 | 높은 fan-out로 대용량에서도 낮은 높이 유지 |
| 일관성/균형 | 분할/병합 필요 | 동일하나 리프 집중 모델로 관리 용이 |
| 운영 편의 | 구현 단순 | 리프 체인 관리 필요하나 운영 이점 큼 |
키 분포와 쓰기 비용을 함께 본다
범위 스캔을 고려한다면 시간·숫자처럼 정렬 친화적인 컬럼을 키로 설계하고, 복합키에서는 선택적인 선두 컬럼 배치를 검토한다. fill factor는 70~90%로 두어 초기 분할 빈도를 완화할 수 있다. 페이지 크기를 스토리지 블록과 정렬하고 리프 프리페치를 활성화하는 것도 I/O 경로에 영향을 준다.
반대로 분할과 병합은 상위 노드까지 다중 페이지 갱신을 전파해 쓰기 증폭을 일으킬 수 있다. 단조 증가 키는 우측 분할을 한곳에 집중시키므로 페이지 예열·패딩 또는 인공 랜덤화를 고려해야 한다. 키가 커지면 fan-out이 줄어 트리 높이가 늘어나므로 해시·서브키 전략을 병행 검토한다.