B*-Tree의 재분배와 2:3 분할 색인 전략

노드 공간을 먼저 재분배하는 균형 트리

B*-Tree는 대규모 데이터베이스와 스토리지 엔진에서 색인 성능과 공간 효율을 함께 다루기 위한 B/B+Tree 변형이다. 삽입 시 노드가 가득 찼다고 즉시 분할하지 않고 인접 형제와의 재분배를 먼저 시도한다. 형제도 가득 찬 경우에는 두 노드를 세 노드로 재배치하는 2:3 분할을 적용한다.

이 정책은 최소 2/3 충전율을 보장한다. 일반적으로 데이터는 리프에 두고 내부 노드에는 키와 포인터만 두는 B+Tree 계열로 적용한다. B-Tree나 B+Tree의 1:1 분할과 달리, 재분배와 2:3 분할을 통해 공간 활용도를 높인다. 평균 팬아웃이 커지면 같은 N에서 트리 높이가 낮아지고 I/O도 줄어든다.

탐색·삽입·삭제의 평균·최악 복잡도는 O(log_f N)이며, f는 팬아웃이다. 높은 충전율은 f를 높여 동등한 N에서의 트리 높이를 낮춘다.

리프 연결과 충전율이 색인 동작에 미치는 영향

내부 노드는 정렬된 키와 자식 포인터를 보유하며, 리프에는 키-값과 좌·우 형제 포인터를 둔다. 리프 연결은 범위 스캔에 사용된다.

충전율은 최소 2/3이며 최대 1.0에 근접한다. 키 수는 페이지 크기와 레코드 포맷에 따라 달라지며, 예를 들어 16KB 페이지를 사용할 수 있다. 평균 팬아웃이 높아지므로 동일 데이터셋에서는 B+-Tree보다 트리 높이가 낮아지는 경향이 있다.

삽입 중 발생하는 재분배와 2:3 분할

삽입은 루트에서 리프까지 내려가며 진행한다. 이때 latch coupling으로 부모에서 자식 순서로 단기 락을 획득한다.

대상 리프가 가득 차면 우선 형제 노드의 공간을 확인한다. 일반적으로 우형제에 여유가 있으면 키를 두 노드에 다시 균등하게 나누고 부모 경계 키를 갱신한다. 형제까지 가득 찼다면 새 노드를 하나 추가한 뒤 기존 두 노드를 세 노드로 재배치한다. 각 노드는 2/3 이상 충전되며, 분할 키는 부모에 다시 삽입된다. 부모도 가득 찬 경우 동일한 규칙이 상위로 전파된다.

⤢✕

처리는 탐색, 삽입, 재분배 또는 2:3 분할, 상향 전파, WAL 기록 순으로 이어진다. 결과는 성공이거나, I/O 또는 공간 부족 시 재시도다.

삭제 시에는 차용 후 병합을 선택한다

삭제 뒤 노드 충전율이 2/3 미만으로 내려가면 먼저 형제 노드에서 키를 차용해 균형을 되돌린다. 차용할 수 없을 때만 두 노드를 병합하고 부모 키를 조정한다. 이 과정에서 루트 축소가 발생할 수 있으며, 최소 충전율을 맞추기 위한 처리는 상위 노드까지 반복된다.

B-Tree 계열의 정책 차이

지표	B-Tree	B+-Tree	B*-Tree
성능(랜덤 조회)	내부/리프 모두 데이터, 경로 짧음	내부는 키만, 리프 집중	B+ 기반, 높이 더 낮아 I/O 감소
확장성(팬아웃)	중간	높음	매우 높음(2/3 충전율)
일관성(균형 유지)	1/2 충전 보장	1/2 충전 보장	2/3 충전 보장, 높이 안정
안정성(분할/병합 비용)	낮음	중간	재분배+2:3로 비용↑, 빈도↓
운영 편의(범위 스캔)	보통	리프 체인 우수	리프 체인+낮은 높이로 우수

색인과 메타데이터에 적용할 수 있는 위치

OLTP의 기본 키와 보조 키 인덱스에서는 16KB 페이지 기준으로 2/3 충전율을 유지해 높이를 1단계 줄일 수 있다. 쓰기가 많은 워크로드에서는 분할 빈도가 줄고, 체크포인트 사이의 쓰기량도 안정화된다.

스토리지와 파일시스템에서는 디렉터리 엔트리 또는 블록 매핑 색인에 적용할 수 있다. 공간 활용이 좋아지면 캐시 적중률 향상에도 연결된다. 임베디드 및 키-값 스토어에서는 SSD 최적화 변형과 결합해 Log-structured merge를 대체하거나 보완할 수 있으며, read-heavy 환경에서 일관된 지연 시간을 확보하는 용도에 맞는다.

충전율이 만드는 효과와 비용

B+-Tree와 비교한 평균 공간 활용도는 워크로드와 키 분포에 따라 1020%p 개선될 수 있다. 트리 높이가 1단계 낮아지면 랜덤 조회와 삽입 I/O를 525% 절감할 수 있다. 재분배를 먼저 수행하면 분할 빈도는 20~40% 감소하며, 로그와 쓰기 증폭 완화에도 영향을 준다.

높은 충전율은 경로 길이의 분산을 줄여 지연 시간을 안정화한다. 리프 체인과 높은 팬아웃은 범위 스캔의 선형 접근 성능을 개선하고, 공간 계획 및 리밸런싱 비용의 변동성도 낮춘다.

반면 삽입 경로의 CPU 비용과 구현 복잡도는 증가한다. 페이지 크기와 키 정렬, 분할 정책, 동시성 제어, 복구 로그를 함께 선택해야 하는 이유다.

페이지·래치·로그를 함께 설계하기

페이지 크기는 8~16KB를 권장하며, 가변 길이 키에는 prefix compression을 적용할 수 있다. 팬아웃은 늘지만 CPU 압축 비용이 따른다.

재분배 허용 폭은 예를 들어 60~80%로 두고 2:3 분할의 트리거 임계치를 조정한다. 분할을 줄일 수 있는 대신 삽입 경로의 CPU 사용량은 늘어난다.

동시성 제어에는 래치 커플링과 B-link 포인터를 적용할 수 있다. B-link는 우형제 포인터와 상한 키를 사용하며 데드락과 팬텀 감소에 도움이 되지만 코드 복잡성이 커진다. 구조 변경에는 SML(Structural Modification Latch)을 적용한다.

WAL은 필수다. 로그 선기록(LSN)과 체크포인트로 크래시 복구를 보장하고, 분할과 병합은 로그를 통해 원자성을 유지한다. I/O 실패나 공간 부족이 발생하면 롤백 또는 리트라이를 수행하며, 배치 재시도 정책을 둘 수 있다. 분할·병합 단계를 미세 로그로 남기면 크래시 일관성을 유지할 수 있지만 로그량은 증가한다.

워크로드에 맞춰 검증하는 과정

먼저 키 분포, 레코드 길이, 읽기·쓰기 비율을 수집하고 인덱스 높이와 페이지 충전율의 베이스라인을 측정한다. 그 뒤 페이지 크기, 타깃 충전율(예: 70~85%), 재분배 폭을 정하고 리프 링크, B-link, latch 정책을 결정한다.

파일 포맷에서는 LSN, sibling, high key를 포함한 페이지 헤더를 정의한다. 분할·병합 WAL 시퀀스와 재시도 정책도 이 단계에서 구현한다. 랜덤·순차·핫스폿이 섞인 벤치마크로 검증하고, P95/P99 지연, 분할률, 쓰기 증폭을 모니터링하면서 점진적으로 배포한다.