🎬 서론

DB Index를 공부하던 중 B+Tree라는 자료구조에 대해서 알게 되었다.

이는 B-Tree에서 확장된 개념이기에, 이번 글을 통해서 B-Tree, B+Tree에 대해 알아보고 그 차이점을 정리해보려고 한다.

---

🌲 B-Tree

B-Tree는 균형 잡힌 다진 검색 트리의 일종으로, 데이터를 정렬된 상태로 유지하면서 빠른 검색 & 삽입 & 삭제가 가능하도록 설계된 구조이다.

Root & Branch & Leaf Nodes

위 이미지에 있는 사각형은 각각 노드라고 부른다.

노드는 아래 3가지 종류가 존재한다.
1. 가장 상단에 위치한 Root 노드
2. 중간에 위치한 Branch 노드들
3. 가장 하단에 위치한 Leaf 노드들

Root 노드의 경우에는 트리의 진입점이자 최상단 노드이기에 무조건 1개만 존재한다.

Binary Search Tree와의 차이점

Binary Search Tree

B-Tree

둘의 핵심적인 동작 원리는 동일하다. 하지만 아래와 같은 차이점이 존재한다.

항목	BST (Binary Search Tree)	B-Tree
노드당 키 수	1개	여러 개
비교 방식	현재 노드의 키 1개와 비교	현재 노드의 배열 형태 키들 중 하나와 비교하여 분기
자식 수	최대 2개	최대 M개 (트리의 차수에 따라 결정됨)
분기 기준	왼쪽 < key < 오른쪽	키 사이 구간에 따라 자식 포인터 선택

B-Tree 동작 원리

B-Tree 동작 원리의 핵심은 하나의 노드에 여러 키를 저장하고, 키 범위에 따라서 자식 노드를 선택하며 탐색을 진행하는 점이다.

여러 키들은 배열로 저장되어 있으며, 이는 항상 정렬된 상태를 유지한다. ex) [30, 70, 95]

위 이미지에서 21이라는 키를 찾는다고 가정해 보자.
루트 노드는 [30, 70]이기에, 자식 포인터는 3개를 가진다.

          [30 | 70]
        /     |     \
      P0     P1     P2

찾고자 하는 키가 30보다 작으므로, P0 즉 첫 번째 자식으로 이동한다. (= [8, 25])

          [8  | 25]
        /     |     \
      P0     P1     P2

8, 25 중에 찾는 값인 21이 없으므로 다시 자식 노드로 탐색을 진행한다. 이를 위해 위와 동일하게 몇 번째 자식으로 이동할지 판단한다.

이번에는 8 < 21 < 25 이므로, 두 번째 자식 노드로 이동한다. (= [15, 21, 23])

해당 노드의 키들 중에서 21이 존재하므로 탐색을 종료한다.

🧑🏻‍💻 이렇듯 3번의 과정만으로 원하는 값을 찾을 수 있었다. 만약 이를 선형적으로 탐색했다면 이미지 상 최악의 경우에는 29번 탐색이 이루어졌을 것이다.

B-Tree는 선형 탐색에 비해 얼마나 빠를까?

그렇다면 위의 경우에서는 B-Tree가 선형 탐색보다 약 10배 빠르다고 말할 수 있을까? 그렇게 단순하게 계산할 수는 없다.

우선 선형 탐색의 경우에는 추가적인 연산 없이 단순히 비교만 계속해서 진행한다. 비교하며 같은 값이 아니면 다음 row로 넘어가고, 같다면 탐색을 종료하는 식이다.

반면 B-Tree 탐색의 경우에는 하나의 노드 내에서 키를 비교한 뒤, 해당 키 범위에 맞는 자식 노드로 내려가며 탐색을 진행한다.

실질적인 성능 차이는 이런 연산 자체보다는, 디스크 접근 횟수에서 발생한다.

RDBMS에서는 데이터를 디스크에 페이지(블록) 단위로 저장하는데, 인덱스는 이를 고려해 "하나의 노드 == 하나의 페이지" 구조로 설계된다.
따라서 B-Tree는 트리의 깊이만큼만 디스크 I/O가 발생하게 된다.

반면 테이블에서 단순히 선형 탐색을 수행하면, row들이 여러 페이지에 나뉘어 저장되어 있기 때문에 최악의 경우 row 수만큼 디스크 I/O가 발생할 수도 있다.
(단, 실제로는 한 페이지가 16KB이므로 여러 row가 담길 수 있어 항상 그렇게 되진 않는다.)

🧑🏻‍💻 정리하자면 디스크 I/O 발생 횟수를 줄이는 것이 DB 성능에 매우 중요하며,
B-Tree는 이러한 I/O 비용을 트리 깊이 수준으로 제한함으로써 큰 성능상의 이점을 제공한다.

B-Tree는 항상 균일한가?

B-Tree는 균형 트리로, 항상 루트 -> 리프 노드로의 거리가 동일하다.

하지만 삽입 & 삭제 연산이 진행됨에 따라 이러한 균형은 깨질 수가 있다. 때문에 B-Tree는 자체적으로 균형을 맞추는 작업을 진행한다.

B-Tree의 구조 조정 과정

B-Tree는 트리의 균형을 맞추기 위해서 삽입 & 삭제 시 아래의 과정을 수행하게 된다.

1. 삽입 : 노드 분할 (Split)

<25 삽입>
[10, 20, 30] + 25
→ [10, 20, 25, 30]
→ 중간값 20을 부모로 올리고 [10], [25, 30]으로 분할

1. 노드가 가득 찬 상태에서 키를 삽입하면, 해당 노드를 두 개로 분할한다.
2. 중간 키를 부모 노드로 올리고, 나머지 키는 좌우 노드에 분배한다.
3. 만약 부모 노드도 가득 차 있다면, 분할은 상위 노드로 전파된다.

🧑🏻‍💻 이 작업은 최악의 경우 루트까지 전파되며, 만약 루트까지 분할되면 트리의 높이가 1 증가하게 된다.

📌 비용: O(log N) (트리 깊이만큼 분할 전파)

2. 삭제 : 병합(Merge) or 키 재분배(Redistribute)

<10 삭제>
[10, 15] - 10
→ [15] → 최소 키 개수 미달 (언더플로우)
→ 형제 노드에서 키를 빌리거나, 병합하여 균형 유지

1. 삭제 후 노드에 남은 키 개수가 최소 개수보다 적다면(언더플로우), 구조 조정이 필요하다.
2. 형제 노드에 여유 키가 있으면, 부모 키와 교환하며 재분배(Redistribute)를 수행한다.
3. 형제도 여유가 없으면, 해당 노드를 병합(Merge)하고 부모 키를 내려보낸다.
4. 이 조정 과정은 상위 노드로 전파될 수 있다.

🧑🏻‍💻 이 작업은 최악의 경우 루트까지 전파되며,
만약 루트 노드가 비게 되면 트리의 높이가 1 감소하게 된다.

📌 비용: O(log N) (재귀적으로 병합/재분배 전파)

최소 키 개수의 기준은?

삭제 연산 과정에서, 최소 키 개수 미달(언더플로우)일 경우에는 재분배나 병합이 필요하다고 하였다.

여기서 최소 키 개수는 어떤 기준으로 정해지는 것일까?

B-Tree는 "루트를 제외한 모든 노드는 자식이 최소 ⌈M / 2⌉개 이상이어야 한다" 는 핵심 제약이 존재한다.
이는 노드가 너무 비어 있으면 트리 높이가 불필요하게 증가하며, 성능 저하를 야기할 수 있기 때문이다.

정리하자면 B-Tree에서 루트를 제외한 모든 노드는 자식 수가 최소 ⌈M / 2⌉개 이상이어야 하며,
이에 따라 키 개수는 ⌈M / 2⌉ - 1개 이상이어야 한다.

B-Tree 연산별 시간 복잡도 요약

연산	시간 복잡도	설명
검색 (Search)	O(log N)	트리 높이만큼 탐색 (균형 유지됨)
삽입 (Insert)	O(log N)	리프 노드까지 내려간 후, 필요 시 분할
삭제 (Delete)	O(log N)	언더플로우 발생 시 병합/재분배 수행

B-Tree는 모든 연산에 대해서 O(log N)이라는 균일한 시간복잡도를 보장한다.

---

🌲 B+Tree

B+Tree와 B-Tree의 가장 큰 차이점은, 실질적인 값 즉 데이터가 리프 노드에만 존재한다는 것이다.

그리고 이러한 데이터들은 Linked List처럼 순차적으로 연결되어 있다.

B+Tree의 장점

1. 리프 노드를 제외하고 데이터를 담아두지 않기 때문에, 브랜치 노드들의 메모리를 더 확보함으로써 더 많은 키들을 수용할 수 있다.

하나의 노드에 수십 ~ 수백 개의 키들을 담을 수 있기에 트리의 높이가 더욱 낮게 유지될 수 있는 것이다.

2. 풀 스캔 시, B+Tree는 리프 노드에 데이터가 모두 있기 때문에 한 번의 선형탐색만 하면 된다.

하지만 B-Tree의 경우에는 중간 노드까지 포함하여 전체 노드를 확인해야 하기 때문에 성능 상 훨씬 느리다.

MySQL InnoDB B+Tree 인덱스 구조

이미지 출처

InnoDB에서의 B+Tree는 위에서 설명한 것보다 훨씬 복잡한 모습을 보인다. (이 또한 매우 단순화된 것이라고 한다)

이에 대해서는 지식이 짧아 추후 학습 후에 다시 정리해보려고 한다. 궁금하다면 해당 블로그 글을 읽어보는 것을 추천한다!

---

🧹 차이점 정리

최종적으로 B-Tree와 B+Tree의 차이점을 정리하자면 아래와 같다.

항목	B-Tree	B+Tree
데이터 저장 위치	내부 노드와 리프 노드 모두에 데이터 저장 가능	리프 노드에만 데이터 저장
내부 노드 역할	데이터도 저장하며 탐색 역할도 수행	탐색(인덱스) 역할만 수행
리프 노드 연결	❌ 없음	✅ 리프 노드끼리 연결 (Linked List 구조)
전체 순회 성능	비효율적 (모든 노드 순회 필요)	효율적 (리프만 순차 탐색)
범위 검색 성능	느림	빠름 (리프 노드 연속 접근 가능)
인덱스 크기	상대적으로 크고 깊이가 더 클 수 있음	내부 노드가 가벼워져 더 낮은 트리 높이 유지 가능
사용 사례	이론 구조 / 일부 탐색 중심 시스템	✅ MySQL InnoDB 인덱스, 파일 시스템 등 실무에서 널리 사용됨

---

참고한 블로그