B-Tree로 설계하는 대용량 인덱스와 범위 질의
B-Tree의 페이지 기반 균형 구조, 분할·병합, 범위 질의와 PostgreSQL 인덱스 설계 활용을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
페이지 접근을 줄이기 위해 높이를 낮춘다
B-Tree는 대규모 데이터 집합에서 탐색·삽입·삭제를 수행하기 위한 균형 다진 탐색 트리다. 관계형 데이터베이스, 키-값 스토어, 파일시스템의 메타데이터 인덱싱에서 널리 쓰인다. 핵심은 정렬된 키를 페이지에 담고, 트리의 높이를 낮춰 랜덤 디스크 I/O를 줄이는 데 있다.
내부 노드는 정렬된 키 집합과 하위 노드 포인터를 보유하며, 모든 리프는 같은 깊이를 유지한다. 차수(order, branching factor), 페이지 크기(page size), 키와 포인터의 크기가 팬아웃(fan-out)을 결정한다. 루트를 제외한 내부 노드는 키 개수의 하한과 상한을 지켜야 하고, 삽입 시에는 분할(split), 삭제 시에는 병합 또는 재분배(rebalance)로 이 규칙을 유지한다.
노드 안의 키와 포인터가 만드는 탐색 경로
내부 노드는 키 K1..Kn과 자식 포인터 P0..Pn으로 이루어진 다진 검색 구조다. 실제 페이지에는 페이지 헤더와 슬롯 디렉터리 같은 메타데이터도 함께 들어간다.
리프에는 B-Tree의 경우 레코드 자체를, B+Tree의 경우 레코드 포인터를 둘 수 있다. 리프를 양방향으로 연결하면 첫 리프를 찾은 뒤 순차 스캔을 이어가기 좋다.
4–16KB 페이지에서는 수백 단위의 팬아웃을 만들 수 있고, 트리 높이를 3–4 레벨로 유지할 수 있다. 점 탐색은 O(log_f N) 페이지 접근 패턴을 따른다. 범위 질의는 첫 리프를 찾은 뒤 연속 페이지를 스캔하므로 대역폭을 활용할 수 있다.
키가 정렬돼 있으므로 BETWEEN, ORDER BY, prefix 매칭처럼 범위 또는 순차 접근이 필요한 질의에 적합하다. 복합키에서는 컬럼 순서에 따라 정렬과 필터 성능이 달라지며, 선택 컬럼을 포함한 커버링 인덱스는 테이블 접근을 줄일 수 있다.
| 구조 | 성능(점/범위) | 확장성(높이) | 일관성/복구 | 안정성/파편화 | 운영 편의 |
|---|---|---|---|---|---|
| B-Tree | 점/범위 모두 우수, 분할 시 약간의 쓰기 증폭 | 수백 팬아웃로 3–4 레벨 유지 용이 | WAL/체크포인트로 안정 | 분할·병합으로 장기 균형 유지 | 범용 기본값으로 운영 단순 |
| B+Tree | 리프만 데이터, 순차 스캔 최적 | 유사 | 유사 | 리프 체인으로 스캔 효율 우수 | 대다수 DBMS 기본 |
| Hash Index | 점 탐색 특화, 범위 비효율 | 버킷 재해시 비용 고려 | 재해시·크래시 복구 구현 난도 | 버킷 편향 시 성능 저하 | 특정 워크로드 한정 유용 |
삽입과 삭제에서 균형을 보존하는 방식
삽입은 리프에 여유 공간이 있으면 해당 위치에 엔트리를 추가하는 것으로 끝난다. 공간이 부족하면 리프를 분할하고 분할 키를 상위 노드로 승격(promotion)한다. 상위 노드 역시 가득 차 있다면 분할은 연쇄될 수 있다.
삭제 후 점유율이 하한 아래로 떨어지면 형제 노드에서 엔트리를 재분배하거나 병합한다. 이 과정에서 트리의 높이가 줄어들 수도 있다.
동시성 제어에서는 래치 커플링(latch coupling)으로 상향·하향 잠금을 전파해 구조 변경을 안전하게 처리한다. 레코드 잠금과 구조 래치는 분리해 운용한다. WAL(Write-Ahead Logging)은 로그를 먼저 기록한 뒤 페이지를 수정해 충돌 복구와 일관성을 보장한다.
중복 키를 허용하는 경우에는 다중 엔트리 체인으로 처리할 수 있고, 허용하지 않으면 고유 제약 위반을 반환한다. 공간 부족은 분할 연쇄로 이어질 수 있으며 트리 높이도 증가할 수 있다. 동시 갱신 충돌에서는 레코드 잠금 대기 또는 타임아웃을 처리하고, 래치 보유 시간은 짧게 유지한다.
인덱스 설계와 스토리지에서의 선택
고빈도 점·범위 질의가 발생하는 테이블에서는 B-Tree 계열을 기본 인덱스 구조로 쓸 수 있다. 복합키는 선택도가 높은 컬럼을 앞에 배치하고, 정렬 요구가 있는 쿼리에는 인덱스의 정렬 순서를 활용한다. DESC/ASC 혼합, 부분 인덱스, 표현식 인덱스도 적용할 수 있다.
InnoDB, PostgreSQL, SQLite 등의 B+Tree 기반 스토리지 엔진은 클러스터형 인덱스와 보조 인덱스를 구현한다. HFS+/APFS와 NTFS는 디렉터리 및 메타데이터 인덱싱에 이 구조를 사용한다.
로그·타임시리즈·멀티테넌시 환경에서는 시간 컬럼을 후행키로 두어 테넌트별 최신 N개 조회를 최적화할 수 있다. Prefix 압축과 커버링 인덱스는 I/O 절감과 캐시 효율 향상에 활용된다.
-- 최신 주문 조회 최적화: 사용자별 + 최신순
CREATE INDEX CONCURRENTLY ix_orders_user_created_at
ON orders USING btree (user_id, created_at DESC)
INCLUDE (status, total_amount); -- 커버링 컬럼
-- 쿼리 예시: 인덱스 순차 스캔과 LIMIT 적용
SELECT order_id, created_at, status, total_amount
FROM orders
WHERE user_id = $1
ORDER BY created_at DESC
LIMIT 50;페이지 크기와 팬아웃으로 보는 탐색 비용
탐색 높이를 근사하면 8KB 페이지에서 오버헤드를 제외한 유효 공간은 8,064B다. 내부 키 16B와 포인터 8B를 사용하면 팬아웃 f는 약 8,064 / 24, 즉 약 336이 된다.
N=100,000,000 레코드에서는 log_f(N) ≈ ln(1e8)/ln(336) ≈ 18.42/5.82 ≈ 3.16이므로 높이는 약 4 레벨이다. 점 탐색에는 약 4 페이지의 랜덤 I/O가 필요하고, 범위 스캔은 최초 4 페이지 접근 뒤 리프 연속 스캔 비용이 더해진다.
무작위 삽입에서는 평균 페이지 점유율이 2/3 수준을 유지하는 경향이 있으며, 리프 분할 확률은 O(1/엔트리수) 수준이다. 분할과 병합은 쓰기 증폭을 만들지만 로그·체크포인트 I/O의 예측 가능성을 높이는 효과도 있다.
범용 워크로드에서는 일관된 지연시간 특성을 확보할 수 있고, OLTP/OLAP 혼합 환경에서도 안정적으로 처리할 수 있다. 정렬과 범위 중심 쿼리는 계획을 단순하게 만들며 튜닝 비용을 줄인다. 운영 관점에서는 기본값 인덱스를 선택할 때 안전한 선택지가 된다.