B-Tree & B+Tree

02 Apr 2025 in Blog / 알고리즘

• B-Tree란?
• B-Tree 핵심 개념
• B-Tree의 규칙
• B-Tree 예시 (차수 t=2)
• B-Tree 작동 방식
  • 검색(Search)
  • 삽입(Insert)
  • 삭제(Delete)
• 어디서 쓰이나?
• B-Tree 기본 삽입 구현 (Python)
• B-Tree vs B+Tree
• B+Tree란?
• B+Tree의 구조 (차수 M 기준)
• B+Tree의 예시 (차수 M=4)
• B+Tree 삽입 & 삭제
• B+Tree의 장점
• 한 줄 요약

이진 트리(Binary Tree)보다 더 많은 데이터를 한 노드에 저장할 수 있는 B-Tree에 대해서 알아볼거야. B-Tree는 데이터베이스나 파일 시스템 등에서 자주 사용되는 균형 잡힌 트리 구조이고 디스크 접근 횟수를 최소화하는 데에 특화되어 있어. B-Tree의 삽입/삭제/탐색의 시간복잡도는 모두 O(log n)이야, 높이는 log base t(n)

B-Tree란?

B-Tree(Balanced Tree)는 일반적인 이진 탐색 트리보다 더 많은 자식을 가질 수 있는 트리 구조야. 그래서 다진 탐색 트리(Multi-way Search Tree) : 하나의 노드가 M개의 자식을 가질 수 있는 것, 으로도 불려. 트리의 높이를 줄이고, 디스크 접근을 줄여서 성능을 높이는 데 목적이 있어. 디스크 접근을 줄이는게, 디스크 I/O를 최소화하도록 설계했기 때문이고 이게 디스크 기반 구조에 매우 효율적이야.

B-Tree 핵심 개념

• 각 노드는 여러 개의 키(key)와 자식 포인터를 가짐

• 모든 리프 노드는 같은 깊이에 있음 → 균형 트리

• 내부 노드와 리프 노드 구분

• 트리의 차수(order) M에 따라 아래와 같은 규칙 있음

B-Tree의 규칙

B-Tree의 규칙 (차수 t일 때)
1. 최대 키 개수: 하나의 노드에 최대 2t-1개의 키를 가질 수 있음
2. 최소 키 개수: 하나의 노드에 최소 t-1개의 키를 가져야 함(root 제외)
3. 정렬: 키는 항상 오름차순으로 정렬되어 있다
4. 자녀의 개수: 내부 노드가 k개의 키를 가지면, k+1개의 자식을 갖는다
5. 리프 노드를 제외한 모든 노드는 자식을 가진다
6. 자식 분기 기준: 키 값에 따라 자식 노드로 분기 (이진 탐색처럼)
7. 모든 리프 노드는 같은 깊이에 있다 -> 균형 트리

B-Tree 예시 (차수 t=2)

[10, 20]
 /   |   \
[5] [15] [25, 30]

• 루트 노드에 2개의 키가 있음 (10, 20)

• 세 개의 자식 노드르 가짐

– 왼쪽 자식은 5, 중간은 15, 오른쪽은 25,30

B-Tree 작동 방식

검색(Search)

• 각 노드의 키들을 이진 탐색으로 찾음

• 작으면 왼쪽, 크면 오른쪽 자식으로 내려감

• 평균적으로 O(log n) 성능

삽입(Insert)

• 항상 리프 노드에 삽입

• 만약 삽입하려는 리프 노드가 가득 찼다면(= 2t-1개의 키가 있다면), split(분할)함

• 분할은 중앙 키를 부모로 올리고 양쪽을 나눔 → 트리 전체를 균형 있게 유지

삭제(Delete)

• 리프 노드에서 삭제는 비교적 간단

• 내부 노드에서 삭제하려면 대체할 키(전위/후위 순회에서 가장 가까운 값)를 찾아 교체

• 자식 노드에 키가 부족하면 merge 또는 borrow해서 균형 유지

어디서 쓰이나?

• 데이터베이스 인덱스(PostgreSQL, MySQL의 InnoDB도 B+Tree 기반)

• 파일 시스템 (NTFS, EXT4, HFS+ 등)

• 디스크 기반 구조에 적합(한 번의 디스크 접근으로 여러 키 확인 가능)

• 대용량 데이터를 디스크에 저장하면서 효율적인 검색이 필요할 때

B-Tree 기본 삽입 구현 (Python)

class BTreeNode:
    def __init__(self, t, leaf=False):
        self.t = t                      # 최소 차수 t
        self.leaf = leaf                # 리프 노드 여부
        self.keys = []                  # 키 리스트
        self.children = []             # 자식 노드 리스트

    def insert_non_full(self, key):
        i = len(self.keys) - 1

        if self.leaf:
            # 리프 노드인 경우: 키를 삽입할 위치를 찾아 삽입, 이진 검색트리와 비슷
            self.keys.append(None)
            while i >= 0 and key < self.keys[i]:    # i(tree 크기-1)가 0이상이고 key가 tree가장 마지막 key보다 작으면
                self.keys[i + 1] = self.keys[i]     # 가장 마지막 key를 한칸 뒤에 복사한다
                i -= 1                              # i를 1감소
            self.keys[i + 1] = key    # i가 -1일수도 있고 자기보다 작은 key값 다음 index 일수도 있는데, 찾고 그 다음에 본인 key를 넣는다
        else:
            # 내부 노드: 자식 노드로 내려감
            while i >= 0 and key < self.keys[i]:    # i(tree 크기-1)가 0이상이고 key가 tree가장 마지막 key보다 작으면
                i -= 1                              # 자기보다 작은 key값 찾을때까지 i 감소
            i += 1                                  # i + 1 하면서 while문 마무리

            if len(self.children[i].keys) == 2 * self.t - 1:  # 현재 i의 자식노드리스트의 키들의 길이가 최소 차수 tx2 -1가 같을때때
                self.split_child(i)                           # i노드에 대해서 split_child 함수 실행

                if key > self.keys[i]:
                    i += 1
            self.children[i].insert_non_full(key)

    def split_child(self, i):
        t = self.t                              # t에 최소 차수 저장
        y = self.children[i]                    # y에 i의 자식노드리스트 저장
        z = BTreeNode(t, y.leaf)                # z에 최소 차수와 y의 leaf 여부에 따라 z도 동일하게 leaf를 따라감
                                                # 아직 z는 keys와 children 없음
        # 중간 키를 부모로 올림
        self.children.insert(i + 1, z)          # 리스트 자식노드리스트에 z insert
        self.keys.insert(i, y.keys[t - 1])      # 리스트 키리스트에 y중간 키를 insert

        z.keys = y.keys[t:]      # 오른쪽 절반
        y.keys = y.keys[:t - 1]  # 왼쪽 절반

        if not y.leaf: # y가 leaf가 아니라면
            z.children = y.children[t:] # z의 자식노드리스트에 y 자식노드리스트의 오른쪽 절반 저장
            y.children = y.children[:t] # y 자식노드리스트에 본인의 왼쪽 절반 저장

class BTree:
    def __init__(self, t):
        self.root = BTreeNode(t, True)
        self.t = t

    def insert(self, key):
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            new_root = BTreeNode(self.t, False)
            new_root.children.insert(0, self.root)
            new_root.split_child(0)
            i = 0
            if key > new_root.keys[0]:
                i += 1
            new_root.children[i].insert_non_full(key)
            self.root = new_root
        else:
            root.insert_non_full(key)

    def print_tree(self, node=None, level=0):
        if node is None:
            node = self.root
        print("Level", level, "Keys:", node.keys)
        if not node.leaf:
            for child in node.children:
                self.print_tree(child, level + 1) 

B-Tree vs B+Tree

항목	B-Tree	B+Tree
키 저장	모든 노드	리프 노드만 저장
내부 노드	(key, value) 쌍	key만 존재 (value 없음)
탐색 속도	상대적으로도 느릴 수 있음	빠름 (리프 노드에만 키 존재)
범위 탐색	비효율적일 수 있음	연결 리스트 구조로 효율적

위 표를 보면 B+Tree가 효율적인거 같지? 그러면 B+Tree에 대해서도 배워보자

B+Tree란?

B-Tree에서 범위 검색을 더 빠르게 하기 위해 개선한 자료구조야. 특히 데이터베이스 인덱스에서 자주 사용되고, MySQL InnoDB 같은 엔진에서도 핵심 구조로 쓰여

B+Tree는 B-Tree의 확장 버전으로, 다음과 같은 특징이 있어:

• 데이터는 모두 리프 노드에만 저장됨

• 내부 노드는 오직 탐색을 위한 키만 존재

• 리프 노드들은 연결 리스트로 연결되어 있음 → 범위 검색에 특화

B+Tree의 구조 (차수 M 기준)

• 내부 노드: 최대 M - 1개의 키, 최대 M개의 자식 포인터

• 리프 노드: 최대 M - 1개의 (key, value) 쌍

• 리프 노드들은 왼쪽 → 오른쪽으로 연결 리스트처럼 연결

B+Tree의 예시 (차수 M=4)

       [20 | 40]
       /   |   \
     A     B    C

리프 노드들:
A: [5, 10, 15] →  
B: [20, 25, 30] →  
C: [40, 45, 50]

• 내부 노드는 분기 기준만 저장 (데이터 없음)

• 리프 노드들은 정렬된 순서 + 연결 리스트 구조

B+Tree 삽입 & 삭제

• 삽입: 리프 노드에 key/value 삽입 → 오버플로우 시 분할, 부모에 key 전파

• 삭제: 리프 노드에서 제거 → 언더플로우 시 병합 또는 차용

※ 내부 노드는 여전히 분기 기준만 저장하기 때문에 삽입/삭제 시에도 데이터 재배치는 리프에서만 발생

B+Tree의 장점

• 범위 검색이 빠르다 → 리프 노드에서 오른쪽으로 쭉 읽으면 됨

• 디스크 I/O 효율적 → 한 번 로딩에 여러 key 처리

• 인덱스 스캔 최적 → WHERE age BETWEEN 20 AND 40 같은 쿼리에 특화

한 줄 요약

B+Tree는 검색과 범위 조회가 빠르고 효율적인 B-Tree의 실전 버전이다