길리랩blog

B+ Tree로 디스크 인덱스와 범위 조회를 설계하는 법

B+ Tree의 리프 체인, 분할·병합, 래치 커플링과 WAL 복구를 바탕으로 디스크 기반 인덱스의 범위 조회와 운영 설계 기준을 정리합니다.

2026-08-14 · 최초 발행 2024-04-29

리프까지 내려간 뒤 옆으로 읽는 인덱스

B+ Tree는 대용량 데이터를 디스크에서 다룰 때 I/O를 줄이고 범위 질의를 효율적으로 처리하기 위해 쓰이는 균형 다분기 트리다. 데이터베이스 인덱스와 파일 시스템 메타데이터에서 널리 사용된다.

내부 노드는 탐색에 필요한 키와 자식 포인터를 보유하고, 실제 레코드는 리프 노드에만 둔다. 모든 리프는 같은 깊이에 있으며 좌우 형제 포인터로 이어진다. 단일 키 조회는 루트에서 리프까지 내려가 처리하고, 범위 조회는 시작 리프를 찾은 뒤 연결된 리프를 따라간다.

B-Tree는 내부 노드에도 값 또는 레코드 포인터를 둘 수 있다. 반면 B+ Tree는 값을 리프에 집중시켜 범위 스캔, 캐시·페이지 적중률, 접근 비용의 일관성 측면에서 유리하다. 고정 크기 페이지(예: 8~16 KiB)에 저장하고 높은 분기도(Fan-out)를 확보하므로 트리 높이를 낮게 유지할 수 있으며, 탐색·삽입·삭제는 O(log_f N) 복잡도를 따른다.

페이지 안에서 나뉘는 탐색 경로와 데이터 저장

내부 노드는 키 개수와 포인터 등을 담은 헤더, 정렬된 키 배열, 자식 포인터 배열로 구성된다. 페이지 크기와 키·포인터 크기가 분기도를 결정한다.

리프 노드는 키와 레코드 식별자(RID) 또는 포인터를 저장한다. 좌우 형제 포인터가 리프를 연결하므로 순차 스캔과 범위 질의에서 선형 접근을 활용할 수 있다.

내부 노드의 키를 압축하거나 정규화하면 한 페이지의 분기도를 높이고 캐시 효율을 개선할 수 있다. 리프 체인은 시작 키를 찾은 뒤 연속 읽기로 이어지는 경로를 만든다.

구조 변경은 분할과 병합으로 전파된다

삽입은 하향 탐색으로 대상 리프를 찾은 뒤 시작한다. 리프에 공간이 없으면 노드를 분할하고, 구분 키를 부모에 올린다. 상위 노드에도 공간이 없으면 분할이 계속 전파될 수 있으며, 루트가 분할되면 트리 높이가 증가한다.

삭제 후에는 언더플로우를 확인한다. 형제 노드와 항목을 재분배하거나 병합하고, 이에 맞춰 상위 키를 조정한다. 과도한 재구조화를 피하기 위해 하한(merge threshold)을 적용할 수 있다.

동시성 제어에서는 상위 노드의 래치를 잡은 뒤 하위 래치를 확보하고 상위 래치를 해제하는 래치 커플링을 사용한다. 짧은 임계구역을 유지하면서 데드락을 예방하기 위한 방식이다. B-link 변형은 우측 링크와 고수준 키 범위를 유지해 분할 중에도 검색 선형화를 보장하며, WAL(Write-Ahead Logging) 기반 저널링은 장애 후 일관성 확보에 사용된다.

인덱스와 스토리지에서의 선택 기준

클러스터드 인덱스에서는 리프가 실제 데이터 페이지를 가리키거나 포함하므로 범위 스캔과 정렬 질의에 적합하다. 논클러스터드 인덱스는 RID를 통해 원본 테이블을 조회하며, 커버링 인덱스는 테이블 접근을 줄이는 설계가 된다.

파일 시스템과 스토리지 엔진에서는 디렉터리 엔트리, inode 맵 같은 메타데이터 관리에 활용할 수 있다. 대용량 디렉터리에서도 로그-스케일 접근 비용을 유지할 수 있다. KV 스토어의 온디스크 인덱스에서도 쓰기 증폭과 압축 정책을 고려한 하이브리드 구조로 병행 운용할 수 있다.

페이지 크기와 정렬 키는 키 분포 및 접근 패턴에 맞춰 정한다. 프리픽스·서픽스 압축을 적용할 수 있으며, 핫 스팟 키에는 파티셔닝이나 샤딩을 함께 고려한다. 초기 적재를 70~90%로 설정하면 분할 빈도를 억제할 수 있다.

탐색과 삽입에서 래치가 이동하는 경로

⤢✕NoYes & SearchYesNoYes & InsertYesNoYesNoStart: Search/Insert(k)Fix root with S-latchNode is Leaf?Choose child by key rangeFix child S-latchUnlatch parentBinary search in leafFound?Return RID/recordReturn Not FoundUpgrade to X-latch on leafHas free space?Insert (key,RID) keepingorderWAL log + Unlatch +CommitSplit leaf: allocate newleafDistribute keys, set siblingpointersPromote separator key toparentParent has space?Insert separator into parentRecursively split parent(B-link safe)WAL log all changesUnlatch nodes bottom-up +Commit

경합이 있으면 하향식 S-래치를 사용하고, 리프에서 X-래치로 전환한 뒤 필요하면 재탐색(retry)한다. 분할 중 검색은 B-link의 우측 링크와 고정 상한 키를 통해 선형화를 유지한다. WAL은 페이지 이미지 또는 레코드 로그 기록, 디스크 플러시, 래치 해제 순서로 처리한다.

트랜잭션 처리의 입력은 키 k, 트랜잭션 TX, 격리수준(예: RR/RC)이다. 탐색은 상향 의도 잠금(IS)부터 루트 S-래치, 하향 래치 커플링, 리프 탐색으로 이어진다. 삽입과 삭제는 리프 X-래치, 여유 공간 판단, 분할·병합 시 부모 SMO 처리, WAL 기록을 거친다. 결과는 RID 또는 레코드 핸들, 성공·실패 결과와 필요 시 재시도 플래그다.

분할 경합이나 래치 업그레이드에 실패하면 재탐색 루프를 수행한다. WAL fsync 후 구조 변경을 커밋하고, 크래시 리커버리에서는 redo/undo를 적용한다. 공정 큐잉 또는 타임아웃 기반 재시도 정책은 기아를 막는 방법이다.

B-Tree, B+ Tree, 해시 인덱스의 운영상 차이

구조 성능(포인트/범위) 확장성(높이) 일관성(경합) 안정성(장애 복구) 운영 편의
B-Tree 포인트 양호, 범위 보통 낮은 높이 래치 커플링 보통 WAL로 보장 범위 스캔 효율 제한
B+-Tree 포인트/범위 모두 우수 매우 낮은 높이 B-link로 우수 WAL+SMO 안전성 높음 커버링·압축 최적화 용이
Hash Index 포인트 매우 우수, 범위 취약 높이 개념 없음 버킷 경합 이슈 재해시 중 비용 큼 범위·정렬 부적합

순차 쓰기가 주도하는 워크로드에서는 LSM-Tree를 고려할 수 있지만, 읽기 증폭과 Compaction 비용이 수반된다. 포인트 조회만 주로 수행하는 경우에는 해시 인덱스가 선택지가 될 수 있으나, 범위 및 정렬 질의에는 불리하다.

페이지 크기에서 트리 높이를 가늠해 보기

페이지 16 KiB(16384B), 내부노드 키 16B, 포인터 8B, 오버헤드 128B를 가정하면 내부 분기도 Fi는 다음과 같이 계산된다.

  • Fi ≈ floor((16384 - 128) / (16 + 8)) = floor(16256 / 24) = 677
  • 슬롯·정렬·조각을 포함한 실무 보수치는 Fi ≈ 300~600이다.
  • 키 16B와 RID 8B를 가정한 리프 용량 Cl은 ≈ floor(16256 / 24) ≈ 677이며, 보수치는 250~500이다.
  • N=100,000,000 레코드, Fi=400, Cl=300일 때 h=3(root→internal→leaf)의 용량은 400×400×300=48,000,000으로 100,000,000보다 작다.
  • h=4의 용량은 400×400×400×300=19,200,000,000으로 100,000,000 이상이므로 필요 높이는 4다.

실행 가능한 계산 코드(Python 3.10+):

# fanout_height.py
import math

def fanout(page=16384, hdr=128, key=16, ptr=8, rid=8, leaf=False):
    unit = (key + (rid if leaf else ptr))
    return (page - hdr) // unit

def height(n_records, Fi, Cl):
    # capacity with height h (including leaf) = Fi^(h-2) * Fi * Cl, for h>=2
    # h=2: root->leaf = Fi*Cl
    if n_records <= Fi * Cl:
        return 2
    h = 3
    cap = Fi * Fi * Cl
    while n_records > cap:
        h += 1
        cap *= Fi
    return h

Fi_raw = fanout(leaf=False)
Cl_raw = fanout(leaf=True)
Fi = 400  # conservative practical fanout
Cl = 300  # conservative practical leaf capacity

print("Raw Fi/Cl:", Fi_raw, Cl_raw)
print("Conservative Fi/Cl:", Fi, Cl)
for n in [120_000, 48_000_000, 100_000_000]:
    print(n, "records -> height", height(n, Fi, Cl))

이 계산은 균일 키 길이와 고정 페이지 크기를 전제로 한다. 실제 시스템에서는 가변 길이 키, 슬롯 디렉터리, 압축, 조각 때문에 Fi와 Cl이 감소할 수 있다.

공간 효율과 쓰기 비용 사이의 균형

초기 빌드에서 70~90%를 채우면 분할 빈도와 단편화를 줄일 수 있다. 다만 채움률을 낮추면 공간 오버헤드가 커지고, 높이면 쓰기 증폭이 증가한다.

키는 정렬 특성을 활용하고 프리픽스 또는 덴스 키를 적용해 범위 스캔에 맞출 수 있다. 압축을 과도하게 적용하면 CPU 비용이 늘고 재분배 시 복잡성이 커진다.

B-link, leaf-first X-래치, 짧은 임계구역은 동시성 정책의 선택지다. 우측 링크와 상한 키는 메모리 오버헤드를 더하고 구현 복잡성도 높인다.

트리 높이를 3~4 수준으로 유지하면 랜덤 I/O를 로그-스케일로 줄일 수 있다. 리프 체인을 따라 순차 읽기를 수행하면 MB/s 단위의 스캔 성능을 달성할 수 있다. SMO와 WAL 조합은 장애 시 인덱스 일관성을 유지하며, 키 확장·복합 인덱스·압축 기법을 도입할 때도 유연성을 제공한다.

B+ Tree데이터베이스 인덱스범위 질의WAL래치 커플링