CS학습2026.10.056 min read

B-Tree: 디스크 접근 횟수를 줄이는 다진 균형 탐색 트리

B-Tree는 한 노드에 여러 개의 키를 저장하고 모든 리프의 깊이를 같게 유지하는 다진(multiway) 균형 탐색 트리다. 노드 크기를 디스크 페이지 크기에 맞춰 트리 높이를 낮추고, 검색·삽입·삭제를 O(log n)에 처리한다. 이 글에서는 최소 차수 t 기준의 불변 조건, 분할(split) 기반 삽입, Python 구현, 그리고 PostgreSQL

By 송민성

1. 개념

B-Tree는 한 노드가 여러 개의 키(key)와 자식(child) 포인터를 가질 수 있는 균형 탐색 트리(balanced search tree)다. 이진 탐색 트리(BST)가 노드당 키 1개, 자식 최대 2개인 것과 달리, B-Tree는 노드당 수십~수천 개의 키를 담을 수 있다.

최소 차수(minimum degree) t (t ≥ 2)를 기준으로 하는 CLRS 정의의 불변 조건은 다음과 같다.

루트를 제외한 모든 노드는 최소 t-1개, 최대 2t-1개의 키를 가진다.
루트는 최소 1개(트리가 비어 있지 않을 때), 최대 2t-1개의 키를 가진다.
키가 k개인 내부 노드(internal node)는 자식을 k+1개 가진다.
노드 안의 키는 정렬되어 있고, i번째 자식 서브트리의 모든 키는 (i-1)번째 키와 i번째 키 사이에 있다.
모든 리프(leaf)는 같은 깊이에 있다.

예를 들어 t = 2이면 노드당 키가 1~3개이고 자식이 2~4개이므로 2-3-4 트리와 같다.

2. 왜 사용하는가

디스크 기반 저장소에서 비용을 지배하는 것은 CPU 비교 횟수가 아니라 페이지(page) 읽기 횟수다. 키 100만 개를 담은 균형 BST의 높이는 약 20이므로 검색 한 번에 노드를 최대 20번 따라가야 하고, 각 노드가 서로 다른 페이지에 있으면 I/O가 그만큼 발생한다.

B-Tree는 노드 하나를 디스크 페이지 하나(예: 8KB)에 대응시켜 분기 수(fan-out)를 크게 만든다. 분기 수가 수백이면 키 수십억 개도 높이 3~4 정도의 트리에 담을 수 있다. 상위 노드는 자주 접근되므로 메모리 캐시에 남기 쉽다는 점도 이점이다.

또한 키가 정렬된 상태로 유지되므로 등치 검색뿐 아니라 범위 검색(range scan), 정렬 순회, 접두사 검색을 지원한다. 해시 인덱스는 등치 검색만 가능하다.

3. 동작 원리

검색

루트에서 시작해 노드 안의 키를 이진 탐색 또는 선형 탐색으로 비교한다. 키를 찾으면 종료하고, 못 찾으면 해당 구간의 자식으로 내려간다. 리프까지 내려가도 없으면 해당 키는 존재하지 않는다.

삽입과 분할(split)

삽입은 항상 리프에서 일어난다. 리프가 가득 차 있으면(키 2t-1개) 중간 키를 부모로 올리고 노드를 둘로 나눈다. 이 분할이 루트까지 전파되면 루트가 분할되어 트리 높이가 1 증가한다. 따라서 B-Tree는 BST와 달리 위쪽(루트)으로 자라고, 이 덕분에 모든 리프의 깊이가 항상 같게 유지된다.

아래 구현은 내려가는 도중 가득 찬 노드를 미리 분할하는 단일 패스(single-pass) 방식이다. 이 방식은 부모에 항상 빈 자리가 있음을 보장하므로 위로 되돌아갈 필요가 없다.

삭제와 병합(merge)

삭제는 노드의 키 수가 t-1 미만이 되지 않도록 처리한다. 부족해질 경우 형제 노드에서 키를 빌려오거나(재분배, redistribution), 형제와 부모의 키 하나를 합쳐 병합한다. 병합이 루트까지 전파되면 높이가 1 감소한다. 삭제 로직은 경우의 수가 많아 아래 예제에서는 다루지 않는다.

4. 코드 예제

검색과 삽입을 지원하는 B-Tree(최소 차수 t)의 Python 구현이다.

python

class Node:
    def __init__(self, leaf: bool):
        self.keys: list[int] = []
        self.children: list["Node"] = []
        self.leaf = leaf


class BTree:
    def __init__(self, t: int = 2):
        assert t >= 2
        self.t = t
        self.root = Node(leaf=True)

    def search(self, key: int, node: Node | None = None):
        node = node or self.root
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        if i < len(node.keys) and node.keys[i] == key:
            return node, i
        if node.leaf:
            return None
        return self.search(key, node.children[i])

    def _split_child(self, parent: Node, i: int) -> None:
        t = self.t
        full = parent.children[i]
        right = Node(leaf=full.leaf)
        mid_key = full.keys[t - 1]

        right.keys = full.keys[t:]
        full.keys = full.keys[: t - 1]
        if not full.leaf:
            right.children = full.children[t:]
            full.children = full.children[:t]

        parent.keys.insert(i, mid_key)
        parent.children.insert(i + 1, right)

    def insert(self, key: int) -> None:
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            new_root = Node(leaf=False)
            new_root.children.append(root)
            self.root = new_root
            self._split_child(new_root, 0)
        self._insert_non_full(self.root, key)

    def _insert_non_full(self, node: Node, key: int) -> None:
        i = len(node.keys) - 1
        if node.leaf:
            node.keys.append(key)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
            return

        while i >= 0 and key < node.keys[i]:
            i -= 1
        i += 1
        if len(node.children[i].keys) == 2 * self.t - 1:
            self._split_child(node, i)
            if key > node.keys[i]:
                i += 1
        self._insert_non_full(node.children[i], key)

    def inorder(self, node: Node | None = None):
        node = node or self.root
        for i, k in enumerate(node.keys):
            if not node.leaf:
                yield from self.inorder(node.children[i])
            yield k
        if not node.leaf:
            yield from self.inorder(node.children[-1])

    def height(self) -> int:
        h, node = 1, self.root
        while not node.leaf:
            node = node.children[0]
            h += 1
        return h


if __name__ == "__main__":
    tree = BTree(t=2)
    for k in range(1, 21):
        tree.insert(k)

    print("정렬 순회:", list(tree.inorder()))
    print("높이:", tree.height())
    print("검색(7):", "발견" if tree.search(7) else "없음")
    print("검색(42):", "발견" if tree.search(42) else "없음")

PostgreSQL에서 B-Tree 인덱스가 범위 검색에 쓰이는지 확인하는 예제다.

sql

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

INSERT INTO orders (user_id, created_at)
SELECT (random() * 10000)::int,
       now() - (random() * interval '365 days')
FROM generate_series(1, 1000000);

-- PostgreSQL의 기본 인덱스 유형은 B-Tree다.
CREATE INDEX idx_orders_user_created ON orders (user_id, created_at);
ANALYZE orders;

EXPLAIN (ANALYZE, BUFFERS)
SELECT * FROM orders
WHERE user_id = 42
  AND created_at >= now() - interval '30 days';

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

n개의 키, 최소 차수 t일 때 다음과 같다.

연산	시간 복잡도	비고
검색	O(log n)	디스크 접근(페이지 읽기)은 O(log_t n)
삽입	O(log n)	분할이 루트까지 전파될 수 있음
삭제	O(log n)	재분배 또는 병합
범위 검색	O(log n + m)	m은 결과 개수(B+Tree 기준 리프 연결 리스트 순회)

높이 h는 h ≤ log_t((n+1)/2)로 제한된다. 노드 안에서 키를 탐색하는 비용까지 포함하면 CPU 비교는 노드당 O(log t) 또는 O(t)이지만, 전체 비교 횟수는 O(log n) 수준을 유지한다.

6. 실무 사용 사례

관계형 DB 인덱스: PostgreSQL, MySQL(InnoDB) 등은 기본 인덱스로 B-Tree 계열을 사용한다. PostgreSQL의 CREATE INDEX 기본값이 B-Tree이며, =, <, >, BETWEEN, ORDER BY를 지원한다.
B+Tree 변형: 대부분의 DB는 실제로 B+Tree를 쓴다. B+Tree는 값(레코드 또는 포인터)을 리프에만 두고 리프끼리 연결해 범위 스캔을 효율적으로 만든다. 내부 노드에는 키만 있어 분기 수가 더 커진다. InnoDB의 클러스터드 인덱스(clustered index)가 대표적이다.
파일 시스템: Btrfs, NTFS 등이 디렉터리나 메타데이터 구조에 B-Tree 계열을 사용한다.
복합 인덱스 설계: (user_id, created_at) 인덱스는 user_id 등치 + created_at 범위 조건에 효과적이지만, created_at만 조건인 쿼리는 선두 컬럼이 없어 효율이 떨어진다.

7. 주의할 점

선두 컬럼 규칙: 복합 인덱스는 왼쪽 컬럼부터 순서대로 사용된다. 컬럼 순서를 쿼리 패턴에 맞춰야 한다.
쓰기 비용: 행을 삽입·수정·삭제할 때마다 인덱스도 갱신되므로 인덱스가 많을수록 쓰기가 느려지고 저장 공간이 늘어난다.
랜덤 키와 분할: UUIDv4처럼 무작위 키는 삽입 위치가 트리 전체에 흩어져 페이지 분할과 캐시 미스가 늘어난다. 시간순 정렬이 가능한 키(예: UUIDv7, 시퀀스)가 유리한 경우가 많다.
인덱스 부풀림(bloat): 삭제와 갱신이 반복되면 페이지 사용률이 떨어질 수 있다. PostgreSQL에서는 REINDEX나 VACUUM으로 관리한다.
함수 적용 조건: WHERE lower(email) = ...처럼 컬럼에 함수를 적용하면 일반 인덱스를 쓰지 못한다. 표현식 인덱스(expression index)가 필요하다.
선택도가 낮은 컬럼: 값의 종류가 적은 컬럼은 옵티마이저가 인덱스 대신 순차 스캔을 선택할 수 있다.

8. 핵심 정리

B-Tree는 노드당 여러 키를 담고 모든 리프의 깊이를 같게 유지하는 다진 균형 탐색 트리다.
노드를 디스크 페이지 크기에 맞춰 분기 수를 키우면 높이가 낮아져 페이지 읽기 횟수가 줄어든다.
삽입은 분할(split), 삭제는 재분배와 병합(merge)으로 균형을 유지하며, 루트가 분할·병합될 때만 높이가 바뀐다.
검색·삽입·삭제는 O(log n)이고, 범위 검색은 O(log n + m)이다.
실제 DB 인덱스는 대부분 B+Tree 변형이며, 복합 인덱스의 컬럼 순서와 쓰기 비용을 함께 고려해 설계해야 한다.