CS학습2026.10.066 min read

B+Tree: 리프 노드에 데이터를 모으는 디스크 친화적 균형 트리

B+Tree는 내부 노드에는 탐색용 키만, 리프 노드에는 모든 키와 데이터(또는 포인터)를 저장하는 다진 균형 트리(multiway balanced tree)다. 노드 하나를 디스크 페이지 크기에 맞춰 높이를 매우 낮게 유지하므로 탐색이 O(log N) 페이지 접근으로 끝나고, 리프끼리 연결 리스트로 이어져 범위 조회에 강하다. 대부분의 관계형 DB 인덱스

By 송민성

1. 개념

B+Tree는 B-Tree의 변형으로, 다음 성질을 가진 균형 다진 탐색 트리다.

내부 노드(internal node): 자식으로 가는 경계 키(separator key)와 자식 포인터만 가진다. 실제 데이터(레코드 또는 레코드 위치)는 없다.
리프 노드(leaf node): 모든 키와 해당 값(레코드 또는 레코드 위치)을 저장한다. 키는 정렬되어 있다.
리프 연결: 리프 노드끼리 다음(필요하면 이전) 리프를 가리키는 포인터로 연결된다.
균형(balanced): 루트에서 모든 리프까지의 깊이가 같다.
차수(order/fanout): 노드 하나가 가질 수 있는 자식 수. 루트를 제외한 노드는 보통 절반 이상 채워져야 한다는 최소 채움 조건을 유지한다.

B-Tree는 내부 노드에도 데이터를 저장할 수 있지만, B+Tree는 데이터를 리프에만 둔다는 점이 가장 큰 차이다.

2. 왜 사용하는가

디스크 기반 저장소에서 비용은 CPU 연산보다 페이지(page) 단위 I/O 횟수가 지배한다. 이진 탐색 트리는 노드당 키가 1개라 높이가 크고, 탐색마다 I/O가 여러 번 발생한다.

B+Tree는 이 문제를 다음과 같이 해결한다.

높은 팬아웃(fanout): 내부 노드에 데이터가 없어 키를 더 많이 담을 수 있다. 노드 하나를 페이지 하나(예: 8KB)에 맞추면 팬아웃이 수백 단위가 되고, 수백만~수억 건도 높이 3~4 정도로 표현된다.
효율적인 범위 조회: 시작 키를 찾은 뒤 리프 연결을 따라 순차적으로 읽으면 된다.
안정적인 탐색 비용: 모든 조회가 루트에서 리프까지 같은 깊이를 지나므로 성능 편차가 작다.
전체 순회 용이: 내부 노드를 거치지 않고 리프만 따라가면 정렬된 전체 스캔이 가능하다.

3. 동작 원리

탐색(search)

루트에서 시작해 각 내부 노드에서 경계 키와 비교해 알맞은 자식으로 내려가고, 리프에서 키를 찾는다. 내부 노드에 같은 키가 있어도 데이터는 리프에만 있으므로 항상 리프까지 내려간다.

삽입(insert)

탐색으로 키가 들어갈 리프를 찾는다.
리프에 공간이 있으면 정렬 위치에 삽입한다.
가득 찼다면 분할(split) 한다. 리프를 두 개로 나누고, 오른쪽 리프의 첫 키를 부모에 올린다. (리프 분할은 키를 부모로 "복사"하며 리프에도 남는다.)
부모도 가득 차면 같은 방식으로 분할이 위로 전파된다. 내부 노드 분할 시 가운데 키는 부모로 "이동"한다.
루트가 분할되면 새 루트가 생기고 높이가 1 증가한다. 트리는 항상 위로 자라므로 균형이 유지된다.

삭제(delete)

리프에서 키를 제거한다.
최소 채움 조건을 어기면 형제 노드에서 키를 빌려오거나(재분배, redistribution), 형제와 병합(merge) 한다.
병합으로 부모의 키가 줄어 부모도 조건을 어기면 위로 전파된다. 루트의 자식이 하나만 남으면 높이가 1 줄어든다.

범위 조회(range scan)

하한 키가 속한 리프를 탐색으로 찾은 뒤, 상한 키를 넘을 때까지 리프 연결을 따라 읽는다.

4. 코드 예제

메모리 위에서 동작하는 단순화된 B+Tree 구현이다(삽입, 탐색, 범위 조회). 삭제는 생략했다.

python

from __future__ import annotations
from bisect import bisect_left, bisect_right


class Node:
    def __init__(self, leaf: bool):
        self.leaf = leaf
        self.keys: list[int] = []
        self.children: list[Node] = []   # 내부 노드: 자식 포인터
        self.values: list[str] = []      # 리프 노드: 값
        self.next: Node | None = None    # 리프 연결


class BPlusTree:
    def __init__(self, max_keys: int = 4):
        self.max_keys = max_keys
        self.root = Node(leaf=True)

    def _find_leaf(self, key: int) -> Node:
        node = self.root
        while not node.leaf:
            # key == 경계 키이면 오른쪽 자식으로 내려간다
            node = node.children[bisect_right(node.keys, key)]
        return node

    def search(self, key: int) -> str | None:
        leaf = self._find_leaf(key)
        i = bisect_left(leaf.keys, key)
        if i < len(leaf.keys) and leaf.keys[i] == key:
            return leaf.values[i]
        return None

    def range(self, lo: int, hi: int) -> list[tuple[int, str]]:
        result = []
        leaf: Node | None = self._find_leaf(lo)
        while leaf is not None:
            for k, v in zip(leaf.keys, leaf.values):
                if k > hi:
                    return result
                if k >= lo:
                    result.append((k, v))
            leaf = leaf.next
        return result

    def insert(self, key: int, value: str) -> None:
        split = self._insert(self.root, key, value)
        if split is not None:
            sep, right = split
            new_root = Node(leaf=False)
            new_root.keys = [sep]
            new_root.children = [self.root, right]
            self.root = new_root

    def _insert(self, node: Node, key: int, value: str):
        if node.leaf:
            i = bisect_left(node.keys, key)
            if i < len(node.keys) and node.keys[i] == key:
                node.values[i] = value  # 중복 키는 갱신
                return None
            node.keys.insert(i, key)
            node.values.insert(i, value)
            if len(node.keys) <= self.max_keys:
                return None
            # 리프 분할: 오른쪽 첫 키를 부모로 복사
            mid = len(node.keys) // 2
            right = Node(leaf=True)
            right.keys = node.keys[mid:]
            right.values = node.values[mid:]
            node.keys = node.keys[:mid]
            node.values = node.values[:mid]
            right.next = node.next
            node.next = right
            return right.keys[0], right

        idx = bisect_right(node.keys, key)
        split = self._insert(node.children[idx], key, value)
        if split is None:
            return None
        sep, right_child = split
        node.keys.insert(idx, sep)
        node.children.insert(idx + 1, right_child)
        if len(node.keys) <= self.max_keys:
            return None
        # 내부 노드 분할: 가운데 키는 부모로 이동
        mid = len(node.keys) // 2
        up = node.keys[mid]
        right = Node(leaf=False)
        right.keys = node.keys[mid + 1:]
        right.children = node.children[mid + 1:]
        node.keys = node.keys[:mid]
        node.children = node.children[:mid + 1]
        return up, right


if __name__ == "__main__":
    tree = BPlusTree(max_keys=3)
    for k in [10, 20, 5, 6, 12, 30, 7, 17, 25, 1]:
        tree.insert(k, f"row-{k}")

    print(tree.search(12))      # row-12
    print(tree.search(99))      # None
    print(tree.range(6, 20))    # [(6, 'row-6'), (7, 'row-7'), (10, 'row-10'), (12, 'row-12'), (17, 'row-17'), (20, 'row-20')]

PostgreSQL에서 인덱스가 B-Tree(구현상 B+Tree 계열)로 쓰이는 모습은 실행 계획으로 확인할 수 있다.

sql

CREATE TABLE orders (
    id         bigserial PRIMARY KEY,
    user_id    bigint NOT NULL,
    created_at timestamptz NOT NULL
);

CREATE INDEX idx_orders_user_created ON orders (user_id, created_at);

-- 등치 + 범위 조건: 인덱스 범위 스캔 기대
EXPLAIN
SELECT * FROM orders
WHERE user_id = 42
  AND created_at >= now() - interval '7 days'
ORDER BY created_at;

5. 시간 복잡도 또는 성능 특성

N을 키 개수, B를 노드당 평균 키 수(팬아웃)라 하자.

연산	시간 복잡도(노드 접근 수 기준)
탐색	O(log_B N)
삽입	O(log_B N)
삭제	O(log_B N)
범위 조회(결과 K개)	O(log_B N + K/B)

노드 내부 키 탐색은 이진 탐색을 쓰면 O(log B)이며, 전체 비교 횟수는 O(log N) 수준이다. 다만 디스크 기반 시스템에서는 I/O 횟수가 지배적이므로 O(log_B N)이 실질적 지표다.
높이는 팬아웃이 클수록 낮아진다. 팬아웃이 수백이면 수억 건도 보통 높이 몇 단계로 충분하다. 상위 노드는 자주 접근되어 버퍼 캐시에 남기 쉬워 실제 디스크 읽기는 더 적다.
분할과 병합은 최악의 경우 루트까지 전파되지만, 일반적으로 드물게 발생하며 상각(amortized)하면 비용이 낮다.

6. 실무 사용 사례

관계형 DB의 기본 인덱스: PostgreSQL(btree 인덱스), MySQL InnoDB(클러스터드 인덱스와 보조 인덱스), Oracle, SQL Server 등이 B-Tree 계열 인덱스를 기본으로 쓴다. 이 중 InnoDB는 B+Tree 구조로, 기본 키 인덱스의 리프에 행 데이터가 저장된다.
파일 시스템: NTFS, ext4(HTree 디렉터리 인덱스), XFS, Btrfs 등이 메타데이터 관리에 B-Tree 계열 구조를 사용한다.
정렬 조건과 범위 조건: BETWEEN, <, >, ORDER BY, LIKE 'abc%'(접두어 검색) 같은 질의에 효과적이다.
복합 인덱스(composite index): (user_id, created_at)처럼 앞 컬럼 등치 + 뒤 컬럼 범위/정렬 패턴을 한 번의 인덱스 스캔으로 처리한다.

7. 주의할 점

쓰기 비용: 삽입/삭제마다 인덱스 갱신과 분할/병합이 일어난다. 인덱스가 많을수록 쓰기 성능이 떨어진다.
무작위 키의 단편화: UUID v4처럼 무작위 키를 기본 키로 쓰면 삽입 위치가 흩어져 페이지 분할과 캐시 미스가 늘어난다. 순차적 성격의 키(예: 시간 정렬 가능한 UUID)가 유리한 경우가 많다.
복합 인덱스의 컬럼 순서: 선두 컬럼 조건이 없으면 인덱스를 효율적으로 쓰기 어렵다(leftmost prefix 원칙).
인덱스 컬럼 가공: WHERE date(created_at) = ...처럼 컬럼에 함수를 적용하면 일반 인덱스를 못 쓴다. 표현식 인덱스나 조건 재작성이 필요하다.
선택도가 낮은 컬럼: 값 종류가 적은 컬럼은 옵티마이저가 인덱스 대신 순차 스캔을 택할 수 있다.
쓰기 중심 워크로드: 쓰기가 압도적으로 많다면 LSM-Tree 계열 저장소가 더 적합할 수 있다. 워크로드를 측정해 판단해야 한다.
위 구현 코드는 학습용이다. 실제 DB는 동시성 제어(latch/lock), 로그 기반 복구(WAL), 가변 길이 키, 페이지 레이아웃 등을 추가로 다룬다.

8. 핵심 정리

B+Tree는 내부 노드에는 경계 키, 리프 노드에는 모든 데이터를 두는 균형 다진 트리다.
노드를 페이지 크기에 맞춰 팬아웃을 키우고, 그 결과 높이가 낮아 탐색 시 I/O가 O(log_B N)으로 억제된다.
리프가 연결 리스트로 이어져 범위 조회와 정렬 순회가 빠르다.
삽입은 분할(split), 삭제는 재분배/병합으로 균형을 유지하며, 루트 분할/병합으로 높이가 변한다.
실무에서는 쓰기 비용, 키 설계, 복합 인덱스 컬럼 순서를 함께 고려해야 한다.