B* Tree로 인덱스 분열과 공간 낭비 줄이기
B* Tree의 형제 노드 재배치와 2→3 분할 원리를 통해 인덱스 공간활용도, 분열 빈도, 운영상 트레이드오프를 정리한다.
2026-08-14 · 최초 발행 2024-04-29
대용량 인덱스에서 노드 분열이 잦아지면 부모 갱신과 상향 분열까지 연쇄적으로 발생한다. B* Tree(B-star Tree)는 B Tree의 균형성과 탐색 복잡도를 유지하면서, 형제 노드 재배치와 2→3 분할로 이 비용을 줄이기 위해 제안된 구조다. 랜덤 삽입이 이어지는 온디스크 인덱스에서 페이지 밀도와 쓰기 효율을 함께 다루는 데 초점이 있다.
가득 찬 노드를 다루는 방식
B* Tree는 B Tree를 변형한 균형 트리다. 노드의 최소 점유율을 2/3 이상으로 보장하며, 삽입 대상 노드가 가득 차면 곧바로 분열하지 않는다. 먼저 좌우 형제의 빈 공간으로 키를 재배치한다. 형제도 가득 찬 경우에만 현재 노드와 형제, 부모의 분리키를 모아 3개 노드로 나눈다.
내부 노드는 키와 자식 포인터를 보유하고, 리프 노드는 키와 레코드 또는 레코드 포인터를 담는다. B+ Tree처럼 키를 리프에만 둘 필요는 없지만, 구현에 따라 리프 전용 데이터 저장 방식을 함께 쓸 수 있다.
검색·삽입·삭제의 평균 복잡도는 O(log_m N)를 유지한다. 분열 빈도를 낮추고 페이지 밀도를 높여 I/O 효율을 개선하는 것이 이 구조의 의도다.
재배치가 먼저 일어나는 이유
B Tree가 최소 1/2 점유를 보장하는 것과 달리, B* Tree는 최소 2/3 점유를 목표로 한다. 페이지 단위 저장에서는 유효 데이터 밀도가 높아질수록 캐시와 디스크 I/O 효율에도 영향을 준다.
삽입 대상 노드가 가득 찼을 때 좌우 형제 중 빈 공간이 있다면 키를 재분배하고 부모의 분리키를 조정한다. 이 과정은 즉시 분열하는 상황을 피하게 해 부모 갱신과 상향 분열 같은 보조연산을 줄인다.
형제 역시 가득 찬 경우에는 현재 노드, 형제 노드, 부모 분리키를 함께 정렬한 뒤 3개 노드로 균등하게 분할한다. 이때 새 노드는 1개만 추가되며, 각 노드는 약 2/3 밀도로 채워진다. 다음 삽입을 받을 여지가 생기므로 분열 사이의 간격도 늘어난다.
트리의 높이는 여전히 logarithmic하게 유지되고, 높이가 증가하는 시점은 루트 확장뿐이다. 상위 노드로 분열이 전파되는 빈도가 줄어들면 경로 갱신과 잠금 유지 시간도 단축되는 경향이 있다.
삽입 경로에서 확인할 것
키 K와 값 V를 루트 R에서 삽입할 때는 리프까지 내려간 뒤 여유 공간을 확인한다. 리프에 공간이 있으면 키를 삽입하고 정렬한다. 가득 찼다면 형제의 여유를 먼저 확인하고, 재배치가 불가능할 때 부모 분리키를 포함한 2→3 분할을 수행한다. 부모가 이를 수용하지 못하면 상향 분열이나 루트 확장으로 이어진다.
재배치에는 형제와 부모를 함께 다루는 작업이 포함된다. 부모(읽기) → 자식(쓰기) → 형제(쓰기) 순으로 보수적으로 잠금을 적용하고, 재배치 전에 형제의 존재와 상태를 확인한 뒤 래치를 승격하는 방식이 권장된다. 래치 커플링(latch coupling) 또는 SMO(Structure Modification Operation) 프로토콜도 필요하다.
루트가 가득 찼거나 부모 분열이 연쇄되는 경우에는 원자성도 보장해야 한다. 온디스크 구현이라면 WAL/저널링으로 이를 확보한다. 분열 자체는 줄어들지만 재배치 과정에서 형제 페이지 쓰기가 늘어날 수 있으므로, 쓰기 패턴과 저널링 비용의 트레이드오프를 함께 봐야 한다.
페이지 밀도가 중요한 환경
온디스크 인덱스를 사용하는 임베디드 KV 스토어에서는 높은 공간 밀도가 필요하다. 페이지 단위 저장에서 쓰기 I/O 절감을 기대할 수 있고, 랜덤 키 분포의 삽입 워크로드에서는 분열 빈도가 줄어 레이턴시 안정화에 유리하다.
파일시스템의 메타데이터와 디렉터리 인덱스도 같은 성격을 가진다. 디렉터리 엔트리가 급증하는 상황에서는 분열을 최소화하는 일이 중요하며, 형제 재배치로 밀도를 균일하게 유지하고 리밸런싱 비용을 낮출 수 있다.
인메모리 캐시 인덱스에서는 메모리 단편화와 리밸런싱 비용을 줄이는 데 활용할 수 있다. 다만 동시성 제어가 복잡해져 구현 난이도가 높아진다는 점은 별도로 고려해야 한다.
B Tree와 달라지는 운영 특성
| 항목 | B Tree | B* Tree |
|---|---|---|
| 공간활용도 | 최소 50% 점유 보장 | 최소 66.7% 점유 보장, 평균 밀도 증가 |
| 분열 빈도 | 가득 찬 노드에서 즉시 분열 빈번 | 형제 재배치 우선, 불가 시 2→3 분할로 빈도 감소 |
| 높이 안정성 | 평균 안정, 상향 분열 전파 가능 | 상향 분열 전파 감소 경향, 높이 증가 지연 |
| 쓰기 증폭 | 분열 시 부모·조상 갱신 빈번 | 재배치로 형제 쓰기 증가 가능, 총 분열·전파 감소 |
| 운영 편의/복잡도 | 구현 단순 | 재배치·동시성 처리 복잡, 래치/로그 설계 중요 |
페이지 평균 점유율은 50%에서 66.7% 수준으로 높아지고, 동일 데이터량을 기준으로 페이지 수는 25% 내외 감소할 수 있다. 랜덤 삽입 워크로드에서는 분열 횟수가 2040% 감소할 것으로 추정되며, 이 값은 워크로드와 차수에 따라 달라진다. 경로 갱신과 상향 분열 전파가 줄면 쓰기 IOPS 요구량이 낮아지고 P99 레이턴시의 변동성 완화도 기대할 수 있다.
I/O 캐시 효율과 히트율은 높아질 수 있으며, 분열 스톨과 장기 잠금이 줄어 동시성 처리율도 안정화될 수 있다.
형제 재배치와 2→3 분할을 담은 예시
아래 코드는 Python 3.10+를 전제로 한 교육용 단일 파일 예시다. 내구성과 동시성은 포함하지 않고, 리프에 값을 저장한다고 가정한다. 형제 재배치와 2→3 분할 로직을 보여주는 데 목적이 있다.
# Python 3.10+
from bisect import bisect_left
class Node:
def __init__(self, order: int, leaf: bool):
self.order = order # 최대 키 개수 기준 간단화
self.leaf = leaf
self.keys: list = []
self.values: list = [] # 리프일 때만 사용
self.children: list[Node] = []
def is_full(self) -> bool:
return len(self.keys) >= self.order
def min_fill(self) -> int:
# B* Tree 최소 점유율: ceil(2/3 * order)
return (2 * self.order + 2) // 3
class BStarTree:
def __init__(self, order: int = 6):
assert order >= 4 # 데모 제한
self.order = order
self.root = Node(order, True)
def search(self, key):
n = self.root
while True:
i = bisect_left(n.keys, key)
if n.leaf:
if i < len(n.keys) and n.keys[i] == key:
return n.values[i]
return None
n = n.children[i]
def insert(self, key, value):
r = self.root
if r.is_full():
new_root = Node(self.order, False)
new_root.children.append(r)
self.root = new_root
self._split_child_bstar(new_root, 0) # 루트 확장
self._insert_nonfull(self.root, key, value)
def _insert_nonfull(self, node: Node, key, value):
i = bisect_left(node.keys, key)
if node.leaf:
if i < len(node.keys) and node.keys[i] == key:
node.values[i] = value
return
node.keys.insert(i, key)
node.values.insert(i, value)
return
# 내부 노드
child = node.children[i]
if child.is_full():
# 형제 재배치 시도
if self._try_redistribute(node, i):
# 재배치 후 적절한 자식 선택 재계산
i = bisect_left(node.keys, key)
else:
# 2→3 분할
self._split_two_to_three(node, i)
# 분할 후 다시 자식 선택
i = bisect_left(node.keys, key)
self._insert_nonfull(node.children[i], key, value)
def _try_redistribute(self, parent: Node, idx: int) -> bool:
child = parent.children[idx]
# 좌측 형제
if idx > 0:
left = parent.children[idx - 1]
if len(left.keys) < self.order:
# 왼쪽에 여유 → parent key 하향, child 최소 키 상향
parent_key = parent.keys[idx - 1]
move_key = child.keys.pop(0)
if child.leaf:
move_val = child.values.pop(0)
left.keys.append(parent_key)
left.values.append(self.search(parent_key))
parent.keys[idx - 1] = move_key
left.keys[-1] = move_key
left.values[-1] = move_val
else:
left.keys.append(parent_key)
parent.keys[idx - 1] = move_key
return True
# 우측 형제
if idx + 1 < len(parent.children):
right = parent.children[idx + 1]
if len(right.keys) < self.order:
parent_key = parent.keys[idx]
move_key = child.keys.pop()
if child.leaf:
move_val = child.values.pop()
right.keys.insert(0, parent_key)
right.values.insert(0, self.search(parent_key))
parent.keys[idx] = move_key
right.keys[0] = move_key
right.values[0] = move_val
else:
right.keys.insert(0, parent_key)
parent.keys[idx] = move_key
return True
return False
def _split_child_bstar(self, parent: Node, idx: int):
# 일반 B-Tree식 분할(루트 초기 확장용), 간소화
full = parent.children[idx]
mid = len(full.keys) // 2
sep = full.keys[mid]
right = Node(self.order, full.leaf)
right.keys = full.keys[mid+1:]
full.keys = full.keys[:mid]
if full.leaf:
right.values = full.values[mid+1:]
full.values = full.values[:mid+1] # B+ 유사 처리 예시
else:
right.children = full.children[mid+1:]
full.children = full.children[:mid+1]
parent.keys.insert(idx, sep)
parent.children.insert(idx+1, right)
def _split_two_to_three(self, parent: Node, idx: int):
# child(가득 참)와 오른쪽 형제를 묶어 2→3 분할(우선 오른쪽 형제 사용)
left = parent.children[idx]
if idx + 1 < len(parent.children):
right = parent.children[idx + 1]
else:
# 오른쪽 형제 없으면 왼쪽 형제 사용
right = left
left = parent.children[idx - 1]
idx = idx - 1
# 두 노드와 부모 분리키 수집
sep = parent.keys[idx]
pool_keys = left.keys + [sep] + right.keys
pool_keys.sort()
# 균등 분배
k = len(pool_keys)
t = k // 3
a_keys = pool_keys[:t]
b_keys = pool_keys[t:2*t]
c_keys = pool_keys[2*t:]
# 새로운 중간 노드 생성
mid_node = Node(self.order, left.leaf)
left.keys = a_keys
right.keys = c_keys
mid_node.keys = b_keys
# 부모 키/포인터 갱신
parent.keys[idx] = mid_node.keys.pop(0)
parent.children.insert(idx + 1, mid_node)
# 간단 사용 예시
if __name__ == "__main__":
bt = BStarTree(order=6)
for x in [10, 20, 5, 6, 12, 30, 7, 17, 3, 25, 40, 1, 2, 4, 8, 9]:
bt.insert(x, str(x))
print("search(12) =", bt.search(12))이 구현은 교육용으로 단순화되어 있다. 포인터와 값의 재배치, 내부 노드와 리프의 일관성 처리, 경계 조건은 실제 구현보다 축약되어 있다. 프로덕션에서는 동시성, 내구성, 정확한 분리키 처리, 리프/내부 분리 정책을 별도로 설계해야 한다.