B-트리 (B-Tree)

핵심 인사이트 3줄

1. B-트리(B-Tree)는 디스크 I/O를 최소화하기 위해 설계된 자기 균형 m-원 탐색 트리로, 루트에서 리프까지 모든 경로의 길이가 동일하다.
2. 노드 하나가 여러 키와 자식을 가져(최소 차수 t), 한 번의 디스크 읽기로 많은 데이터를 처리해 대용량 DB·파일시스템 인덱스의 핵심 자료구조다.
3. 삽입·삭제 시 노드 분할(Split)·병합(Merge)·재분배(Redistribution)로 균형을 유지하며, 모든 연산의 시간 복잡도는 O(log n)이다.

Ⅰ. B-트리의 정의와 속성

B-트리(B-Tree)는 **Rudolf Bayer와 Edward McCreight(1972)**가 대용량 디스크 저장소를 위해 설계한 자기 균형 탐색 트리다.

B-트리 성질 (최소 차수 t 기준)

1. 루트가 아닌 노드: 최소 t-1개, 최대 2t-1개 키
2. 루트: 최소 1개 키 (비어있지 않으면)
3. 내부 노드: 키 수 + 1개의 자식
4. 모든 리프 노드: 같은 깊이 (완전 균형)
5. 노드 내 키는 오름차순 정렬

B-트리 (t=2, 최대 3키/노드) 예시:

          [17]
        /      \
   [5, 12]    [24, 30]
   /  |  \    /  |   \
 [1,3][7,9][15,16][20,22][27,28][35]

📢 섹션 요약 비유: B-트리 노드는 책장 칸이다 — 각 칸(노드)에 여러 권의 책(키)을 꽂고, 칸마다 서브섹션(자식 포인터)이 있어 어느 칸에서도 같은 거리로 원하는 책을 찾을 수 있다.

Ⅱ. B-트리 탐색과 삽입

탐색 (Search)

def search(node, k):
    i = 0
    while i < len(node.keys) and k > node.keys[i]:
        i += 1
    if i < len(node.keys) and k == node.keys[i]:
        return (node, i)  # 키 발견
    if node.is_leaf:
        return None       # 없음
    return search(node.children[i], k)  # 자식으로 내려감

삽입 (Insert) — 노드 분할

삽입 위치 리프가 가득 찼을 때 (2t-1개 키):

분할 전:  [1, 5, 9, 13, 17]  (t=3이면 max 5키)
            ↓ 중간 키(9) 부모로 올라감
분할 후:  부모에 9 추가
          왼쪽 [1, 5] | 오른쪽 [13, 17]

📢 섹션 요약 비유: 노드 분할은 책장이 꽉 찼을 때 책을 반으로 나눠 새 책장을 만드는 것과 같다 — 가운데 책을 윗 칸으로 올리고 양쪽으로 분리한다.

Ⅲ. B-트리 삭제 — 병합과 재분배

삭제 3가지 케이스

언더플로우 처리:
  형제에 여유 있음 → 재분배 (부모 키 내려오고 형제 키 올라감)
  형제도 최소 → 병합 (두 노드 + 부모 키 합체)

📢 섹션 요약 비유: B-트리 삭제는 학급 합반 규칙이다 — 한 반 학생이 너무 적어지면(언더플로우) 옆 반에서 한 명 빌리거나(재분배), 아예 두 반을 합반(병합)한다.

Ⅳ. 시간 복잡도와 실제 활용

시간 복잡도

실제 적용

• 파일시스템: NTFS·HFS+·ext4 모두 B-트리 변형 사용
• DBMS 인덱스: InnoDB (B+ 트리), Oracle (B-트리)
• t 값 선택: 페이지 크기 4KB 기준 → t ≈ 50~100

디스크 페이지 크기 4096 bytes
키 + 포인터 = 20 bytes
t ≈ 4096 / (2 × 20) ≈ 100
→ 높이 2의 B-트리에 최대 100³ = 백만 개 키 저장

📢 섹션 요약 비유: t가 크면 나무가 납작해진다 — 층수가 낮은 (높이가 작은) 쇼핑몰은 엘리베이터(디스크 I/O) 이용 횟수가 줄어 쇼핑이 빨라진다.

Ⅴ. B-트리 vs 이진 탐색 트리 비교

이진 탐색 트리 (BST) vs B-트리 (t=100):

BST 높이: log₂(1,000,000) ≈ 20
B-트리 높이: log₁₀₀(1,000,000) ≈ 3

디스크 I/O: BST 20회 vs B-트리 3회 → B-트리가 7배 빠름

B-트리 계열 비교

�� 섹션 요약 비유: B-트리 계열은 도서관 분류 체계다 — BST가 1권짜리 칸마다 책 1권을 꽂는다면, B-트리는 한 칸에 100권을 꽂아 검색 효율이 훨씬 높다.

📌 관련 개념 맵

B-트리 (B-Tree)
├── 설계 목적
│   └── 디스크 I/O 최소화
├── 핵심 연산
│   ├── 탐색 O(log n)
│   ├── 삽입 (노드 분할)
│   └── 삭제 (병합·재분배)
├── 변형
│   ├── B+-트리 (리프 체인, DB 인덱스 표준)
│   └── B*-트리 (공간 효율화)
└── 실제 사용
    ├── DBMS 인덱스 (InnoDB B+ 트리)
    ├── 파일시스템 (NTFS, HFS+)
    └── 키-값 스토어 (RocksDB)

📈 관련 키워드 및 발전 흐름도

┌─────────────────────────────────────────────────────────────────┐
│                   B-트리 발전 흐름                               │
├──────────────┬────────────────────┬─────────────────────────────┤
│ 1972년       │ B-트리 논문        │ Bayer & McCreight, Boeing    │
│ 1976년       │ B+-트리 제안       │ Knuth TAOCP, 리프 체인 추가  │
│ 1980년대     │ DBMS 인덱스 표준화 │ Oracle·DB2 B+-트리 채택     │
│ 2000년대     │ InnoDB B+-트리     │ MySQL InnoDB 클러스터 인덱스 │
│ 2010년대     │ Fractal Tree·LSM  │ B-트리 대안 구조 등장        │
│ 2020년대     │ NVMe 최적화 B-트리 │ SSD 특성 고려 설계           │
└──────────────┴────────────────────┴─────────────────────────────┘

핵심 키워드 연결:
이진 탐색 트리 → B-트리(디스크 최적화) → B+-트리(리프 체인)
      ↓                   ↓                       ↓
  메모리 최적        디스크 페이지 단위      범위 스캔 O(k)
      ↓
  DBMS 인덱스 표준 → 클러스터 인덱스 → 실행 계획 최적화

👶 어린이를 위한 3줄 비유 설명

1. B-트리는 넓고 낮은 나무다 — 높이가 낮을수록 꼭대기에서 잎까지 거리가 짧아 원하는 잎(데이터)을 빨리 찾는다.
2. 노드 분할은 꽉 찬 책가방을 반으로 나누는 것이다 — 가운데 책(중간 키)을 선생님(부모 노드)에게 전달하고 가방 두 개로 나눈다.
3. 디스크 I/O가 적다는 것은 서랍을 덜 열어도 된다는 뜻이다 — 서랍 하나에 많은 것을 넣어두면 몇 개만 열어도 원하는 걸 찾을 수 있다.