B-Tree

 

B-Tree (균형 트리)

핵심 요약

• 정의: B-Tree는 다진(m-way) 균형 탐색 트리이다.
• 균형 유지: 모든 리프 노드가 같은 깊이에 위치하도록 강제하여 검색 성능의 일관성을 보장한다. 키가 노드 용량을 초과하면 분할(Split)하고, 최소치보다 부족해지면 병합(Merge) 또는 재분배(Borrow)한다.
• I/O 효율화: 하나의 노드에 여러 개의 키를 저장하여 디스크 접근 횟수를 최소화한다. 이는 트리의 전체 높이를 낮추는 효과로 이어진다.
• 설계: 노드의 크기를 디스크 블록(페이지) 크기에 맞추는 것이 일반적이다. 이 특징 때문에 데이터베이스나 파일 시스템과 같이 디스크 기반의 대용량 데이터를 다루는 시스템에 매우 적합하다.

---

B-Tree의 구조

노드 구성

• 내부 노드 (Internal Node): 여러 개의 정렬된 키와 자식 포인터 배열로 구성된다. 각 키는 자식 노드가 담당하는 키의 구간(범위)을 구분하는 역할을 한다.
• 리프 노드 (Leaf Node): 실제 데이터 또는 데이터에 대한 포인터를 저장한다. 모든 리프 노드는 동일한 깊이에 위치한다.

동적 조정 메커니즘

• 노드 분할 (Split): 삽입 시 한 노드의 키 개수가 최대치를 초과하면, 중간 값 키를 기준으로 노드를 두 개로 분할한다. 이때 중간 키는 부모 노드로 올라간다.
• 노드 병합 및 재분배 (Merge/Redistribute): 삭제 후 한 노드의 키 수가 최소치 미만이 되면, 인접한 형제 노드에서 키를 빌려오거나(재분배) 형제 노드와 합쳐(병합) 최소 키 수 조건을 만족시킨다.

---

B-Tree의 형식적 정의

차수(degree) m인 B-Tree는 다음 조건을 만족하는 균형 잡힌 m-진 검색 트리다.

1. 모든 노드는 최대 m-1개의 키를 가진다.
2. 루트를 제외한 모든 노드는 최소 ⌈m/2⌉ - 1개의 키를 가진다.
3. 내부 노드의 자식 수는 (키의 수 + 1)이다.
4. 모든 리프 노드는 같은 깊이에 존재한다.
5. 노드 내의 키는 정렬된 상태를 유지한다.

항목	표현식 (최소 차수 t 기반)	표현식 (최대 자식 수 m 기반)
최소 자식 수	t	⌈m / 2⌉
최대 자식 수	2t	m
최소 키 수	t - 1	⌈m / 2⌉ - 1
최대 키 수	2t - 1	m - 1

• 두 표현식에서 m = 2t 관계가 성립한다.

B-Tree의 높이
높이(h)는 디스크 접근 횟수와 직결되므로 매우 중요한 성능 지표다. 높이는 최악의 경우에도 다음 식을 만족한다.

• t는 최소 차수 (minimum degree), n은 전체 키의 수

---

 

삽입 연산

1. 키가 삽입될 리프 노드를 탐색한다.
2. Case 1: 리프 노드에 여유 공간이 있는 경우
   • 해당 노드에 키를 정렬된 위치에 삽입하고 종료한다.
3. Case 2: 리프 노드가 꽉 찬 경우 (Overflow)
   • 일단 키를 노드에 삽입한다.
   • 노드의 중간 키를 부모 노드로 올린다.
   • 중간 키를 기준으로 노드를 두 개로 분할(Split)한다.
   • 부모 노드에서도 Overflow가 발생하면 이 과정을 재귀적으로 반복한다. 이 과정에서 트리의 높이가 증가할 수 있다.

삭제 연산

1. Case 1: 삭제할 키가 리프 노드에 있는 경우
   • 키를 삭제한다. 삭제 후에도 노드의 최소 키 수 조건을 만족하면 종료한다.
   • 만약 최소 키 수보다 적어지면(Underflow), 아래 Case 3을 진행한다.
2. Case 2: 삭제할 키가 내부 노드에 있는 경우
   • 해당 키의 직전 키(predecessor)나 직후 키(successor)를 리프 노드에서 찾아와 값을 교체한다.
   • 이후 리프 노드에 있는 직전/직후 키를 삭제 대상으로 변경하고 Case 1 또는 3을 진행한다.
3. Case 3: 삭제 후 노드에 Underflow가 발생한 경우
   • 재분배(Borrow): 인접한 형제 노드의 키가 충분하면, 부모 노드의 키를 하나 가져오고 형제 노드의 키를 부모 노드로 올린다.
   • 병합(Merge): 형제 노드도 최소한의 키만 가지고 있다면, 부모 노드에서 키를 하나 내리고 두 노드를 하나로 합친다. 이 과정은 부모 노드까지 전파될 수 있다.

동작	상황	처리 방식
삽입	노드에 여유 공간 있음	정렬 위치에 삽입
삽입	노드 오버플로우 (Overflow)	분할(Split) 후 중간 키를 부모로 올림
삭제	노드 언더플로우 (Underflow) 없음	단순 삭제 또는 키 교체
삭제	노드 언더플로우 (Underflow) 발생	형제 노드에서 재분배(Borrow) 또는 병합(Merge)

---

장단점 및 활용

• 장점:
  • 높은 I/O 효율성: 디스크 블록 크기에 맞춘 노드 설계로 I/O 호출 수를 줄인다.
  • 균형 잡힌 검색 성능: 모든 리프가 동일 깊이에 있어 최악의 경우에도 O(log n)을 보장한다.
  • 범위 검색에 유리: 노드 내 키들이 정렬되어 있어 순차 접근이 효율적이다.
• 단점:
  • 구현의 복잡성: 분할, 병합, 재분배 로직이 복잡하다.
  • 메모리 오버헤드: 노드 내 여유 공간 유지를 위해 일부 메모리가 낭비될 수 있다.
  • 동시성 제어의 어려움: 다중 스레드 환경에서 잠금(Lock) 구현이 복잡하다.
• 활용 분야:
  • 데이터베이스 인덱스: 대용량 데이터의 빠른 CRUD를 보장하기 위해 표준적으로 사용된다.
  • 파일 시스템: 디렉토리 구조 및 메타데이터 인덱싱에 사용된다.

---

B+ Tree (B-Tree의 확장판)

B-Tree의 발전된 형태로, 데이터베이스 인덱스와 파일 시스템에서 사실상의 표준으로 사용된다. (MySQL InnoDB, Oracle DB, PostgreSQL 등)

B-Tree와 B+ Tree의 핵심 차이

항목	B-Tree	B+ Tree
데이터 저장 위치	모든 노드 (내부 + 리프)	리프 노드에만 저장
리프 노드 구조	독립적	서로 연결된 연결 리스트(Linked List) 구조
내부 노드의 역할	키 저장 + 데이터 포인터	인덱스 역할만 수행 (경로 탐색용 키)
범위 쿼리 성능	비효율적 (여러 노드 순회 필요)	매우 효율적 (리프 노드만 순차 스캔)

B+ Tree의 구조적 특징

1. 데이터는 리프 노드에만 존재: 내부 노드는 오직 리프 노드로 가는 경로를 안내하는 인덱스 역할만 수행한다. 이 덕분에 내부 노드는 더 많은 키(인덱스)를 저장할 수 있어 트리의 높이가 더 낮게 유지될 수 있다.
2. 리프 노드의 연결 리스트: 모든 리프 노드가 서로를 가리키는 포인터로 연결되어 있다. 이는 BETWEEN, ORDER BY 같은 범위 검색 시 매우 빠른 순차 스캔(Sequential Scan)을 가능하게 한다.

B+ Tree가 널리 사용되는 이유

• 디스크 I/O 최소화: 내부 노드에는 인덱스만 있어 더 많은 키를 한 블록에 담을 수 있고, 트리의 높이가 낮아져 디스크 접근이 줄어든다.
• 범위 검색 최적화: 리프 노드가 연결 리스트로 되어 있어 특정 범위의 데이터를 조회할 때 매우 빠르다.
• 단순한 구조: 인덱스(내부 노드)와 데이터(리프 노드)가 명확히 분리되어 관리가 용이하다.

비유로 이해하기

• B-Tree: 책의 각 챕터(내부 노드)마다 내용의 일부가 있고, 더 상세한 내용은 다른 페이지(자식 노드)로 가라고 안내하는 방식. 특정 내용을 찾으려면 여러 챕터를 넘나들어야 할 수 있다.
• B+ Tree: 책의 맨 앞에는 '목차(내부 노드)'만 있고, 모든 '실제 내용(데이터)'은 본문(리프 노드)에 순서대로 정리되어 있다. 또한, 각 페이지 하단에는 다음 페이지로 바로 넘어갈 수 있는 쪽수가 적혀있다(연결 리스트). 목차를 통해 원하는 시작 페이지로 한 번에 간 뒤, 그 뒤로는 페이지만 넘기면 되므로 순차적으로 읽기 매우 편하다.