B-Tree와 B+Tree

데이터 100만 건 기준

BST (이진 탐색 트리)
  깊이 ≈ log₂(1,000,000) ≈ 20
  → 최악 20번 디스크 I/O

B-Tree (차수 100)
  깊이 ≈ log₁₀₀(1,000,000) ≈ 3
  → 최대 3번 디스크 I/O

디스크 I/O 1회 ≈ 10ms (SSD: ~0.1ms)
BST: 20 × 10ms = 200ms
B-Tree: 3 × 10ms = 30ms
→ 동일한 검색에 6배 이상 성능 차이!

디스크 블록 크기: 8KB

BST 한 노드: 키 1개 + 포인터 2개 ≈ 수십 바이트
  → 8KB 블록에 키 1개만 사용 → 대부분 낭비

B-Tree 한 노드: 키 수백 개 + 포인터 수백 개
  → 8KB 블록을 꽉 채워 사용
  → 한 번 디스크 접근으로 수백 개 키 비교 가능

핵심: 디스크 블록 활용률을 최대화하여 I/O 횟수를 최소화

차수(Order, m): 한 노드가 가질 수 있는 최대 자식 수
  → 차수 m인 B-Tree
     * 루트: 최소 2개 자식 (또는 리프)
     * 내부 노드: 최소 ⌈m/2⌉개 자식, 최대 m개 자식
     * 각 노드: 최소 ⌈m/2⌉-1개 키, 최대 m-1개 키
     * 모든 리프는 같은 깊이

팬아웃(Fan-out): 한 노드에서 나가는 포인터(자식) 수
  → 팬아웃이 클수록 트리가 낮아짐 → 디스크 I/O 감소

노드 종류
  * 루트 노드: 트리의 최상위, 최소 2개 자식
  * 내부 노드(Internal): 루트와 리프 사이의 중간 노드
  * 리프 노드(Leaf): 최하위 노드, 자식 없음

                    [30, 60]                ← 루트
                  /     |    \
          [10, 20]   [40, 50]   [70, 80, 90]  ← 리프

키 30의 왼쪽: 30보다 작은 키들 (10, 20)
키 30과 60 사이: 30~60 사이의 키들 (40, 50)  
키 60의 오른쪽: 60보다 큰 키들 (70, 80, 90)

                    [30, 60]               ← 1단계: 30 < 45 < 60
                  /     |     \
          [10, 20]   [40, 50]   [70, 80]   ← 2단계: 40 < 45 < 50

1단계: 루트 [30, 60] 확인 → 45는 30과 60 사이 → 가운데 자식으로
2단계: [40, 50] 확인 → 40 < 45 < 50 → 45가 이 노드에 없음

결과: 45는 트리에 없음 (검색 실패)
디스크 I/O: 2회 (루트 1번 + 내부 1번)

내부 노드 (키만 저장, 가이드 역할)
                    [30]
                   /    \
              [10, 20]  [30, 40, 50]    ← 내부 노드 (키만)

리프 노드 (키 + 데이터 포인터, 연결 리스트)
  [10,ptr]─→[20,ptr]─→[30,ptr]─→[40,ptr]─→[50,ptr]
        ←──── 이중 연결 리스트 ────→

ptr = 실제 데이터 행을 가리키는 ROWID/포인터

1. 데이터는 리프 노드에만 저장
   → 내부 노드는 키만 저장 (라우팅 역할)
   → 내부 노드에 더 많은 키를 넣을 수 있음 → 팬아웃 증가

2. 리프 노드끼리 연결 리스트
   → 범위 검색 시 트리를 다시 올라갈 필요 없음
   → 리프에서 좌→우 순차 탐색만으로 범위 결과 획득

3. 내부 노드의 키는 리프에도 존재
   → 내부 노드의 키는 "라우팅 키"
   → 같은 키 값이 내부 노드와 리프 노드에 모두 나타남

4. 리프 노드의 키는 항상 정렬 상태
   → ORDER BY 최적화에 유리

8KB 블록, 키 크기 8바이트, 포인터 8바이트, 데이터 100바이트:

B-Tree
  한 노드 키 수 ≈ 8192 / (8 + 8 + 100) ≈ 70개
  → 팬아웃 ≈ 71

B+Tree (내부 노드)
  한 노드 키 수 ≈ 8192 / (8 + 8) ≈ 512개
  → 팬아웃 ≈ 513

B+Tree가 약 7배 더 넓은 트리!
  → B-Tree 깊이 4인 곳에서 B+Tree는 깊이 3
  → 디스크 I/O 1회 절약

SELECT * FROM products WHERE price BETWEEN 100 AND 500;

B+Tree
  1. 루트에서 100을 찾아 리프까지 내려감 (2~3번 I/O)
  2. 리프의 연결 리스트를 따라 500까지 순차 읽기
  3. 데이터가 연속된 블록에 저장되어 시퀀셜 I/O 활용
  → 매우 효율적!

B-Tree
  1. 100을 찾은 뒤 중위 순회(In-order Traversal)
  2. 부모→자식→부모→형제를 왔다 갔다
  3. 랜덤 I/O가 발생하여 성능 저하
  → 비효율적

실제 쿼리에서 범위 검색은 매우 빈번
  WHERE date BETWEEN '2024-01-01' AND '2024-12-31'
  WHERE salary >= 3000000
  WHERE name LIKE '김%'  (인덱스 범위 스캔)

차수 3 (리프 최대 2개 키, 내부 최대 2개 키):

1. 초기 상태
         [30]
        /    \
  [10, 20] [30, 40]

2. 35 삽입 → 리프 [30, 40]에 35 추가 → [30, 35, 40] 초과!

3. 리프 분할
   [30, 35, 40] → [30] | [35, 40]
   오른쪽 첫 키 35를 부모에 Copy-up

4. 분할 후
         [30, 35]
        /    |    \
    [10, 20] [30] [35, 40]
    ← 리프 연결 리스트 →

1단계: 키가 있는 리프 노드 찾기
2단계: 리프에서 키 삭제
3단계-A: 최소 키 수를 만족하면 완료
3단계-B: 최소 키 수 미달 → 재분배 또는 병합

재분배 (Redistribution)
  * 형제 노드에서 키를 빌려옴
  * 부모 노드의 구분 키도 갱신

병합 (Merge)
  * 형제 노드와 합침
  * 부모 노드에서 구분 키 삭제
  * 부모도 최소 키 수 미달이면 연쇄 병합

차수 3 (리프 최소 1개 키)

1. 초기
         [30, 35]
        /    |    \
  [10, 20] [30] [35, 40]

2. 30 삭제 → 리프 [30]에서 삭제 → [] 비어짐!

3. 형제 [10, 20]에서 20을 빌려옴 (재분배)
         [20, 35]
        /    |    \
    [10]   [20]  [35, 40]

또는 형제와 병합
         [35]
        /    \
  [10, 20] [35, 40]

차수 200 (한 노드에 최대 199개 키), 리프에 100개 레코드

높이 1 (루트만):          199개 키
높이 2 (루트+리프):       200 × 100 = 20,000건
높이 3:                   200 × 200 × 100 = 4,000,000건 (400만)
높이 4:                   200³ × 100 = 800,000,000건 (8억)

핵심: 높이 3~4면 수억 건의 데이터를 처리 가능!
  → 검색 시 디스크 I/O는 3~4회면 충분
  → 루트와 상위 내부 노드는 보통 버퍼 캐시에 상주
  → 실제 디스크 I/O는 1~2회로 감소

┌───────────────┬───────────────────┬─────────────────────┐
│   자료구조    │       장점        │ 적합한 상황         │
├───────────────┼───────────────────┼─────────────────────┤
│ B+Tree        │ 범용, 범위 검색   │ 대부분의 인덱스     │
│ Hash Index    │ 동등 검색 O(1)    │ = 조건 검색         │
│ Bitmap Index  │ 낮은 카디널리티   │ 성별, 상태 (OLAP)   │
│ R-Tree        │ 공간 검색         │ 위치/지도 (GIS)     │
│ GIN/GiST      │ 전문 검색, 배열   │ PostgreSQL 텍스트   │
│ LSM-Tree      │ 쓰기 최적화       │ 로그, 시계열 DB     │
└───────────────┴───────────────────┴─────────────────────┘

Hash Index
  * 동등 검색(=)에 O(1)이지만 범위 검색 불가
  * MySQL Memory 엔진에서 지원, InnoDB는 Adaptive Hash Index

Bitmap Index
  * 각 값에 비트맵 할당, AND/OR 연산이 빠름
  * Oracle에서 OLAP용으로 활용
  * 값의 종류가 적은 컬럼(성별, 상태)에 적합

해시 함수: h(key) → 버킷 번호

검색: key=100
  1. h(100) = 3 → 버킷 3으로 바로 접근
  2. 버킷 3에서 key=100인 행 포인터 반환
  → O(1) 검색!

그러나
  WHERE price > 100  → 해시 값으로 대소 비교 불가
  WHERE name LIKE 'A%' → 해시 값이 원래 순서와 무관
  ORDER BY price → 해시 인덱스는 정렬 순서 제공 불가

employees 테이블의 gender 컬럼
  M: [1, 0, 1, 1, 0, 1, 0, 0, 1, 1]  ← 비트맵
  F: [0, 1, 0, 0, 1, 0, 1, 1, 0, 0]

WHERE gender = 'M' AND dept = 'IT'
  gender_M:  [1, 0, 1, 1, 0, 1, 0, 0, 1, 1]
  dept_IT:   [1, 1, 0, 0, 1, 0, 0, 1, 0, 0]
  AND 연산:  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0]  ← 1번 행만 해당!

장점: 비트 연산으로 여러 조건의 AND/OR를 매우 빠르게 처리
단점: DML이 빈번하면 비트맵 갱신 비용이 큼 → OLTP에 부적합

쓰기 최적화 자료구조
  1. 쓰기 → 메모리의 MemTable에 먼저 기록 (매우 빠름)
  2. MemTable이 꽉 차면 → 디스크에 SSTable로 Flush
  3. SSTable들이 쌓이면 → 백그라운드에서 Compaction (병합 정렬)

읽기
  MemTable → 최신 SSTable → 오래된 SSTable 순서로 검색
  → 읽기는 B+Tree보다 느릴 수 있음

사용처
  * RocksDB (MySQL MyRocks 엔진)
  * LevelDB (Google)
  * Cassandra, HBase
  * 로그 수집, 시계열 데이터 등 쓰기 비중이 높은 시스템

B+Tree vs LSM-Tree
  ┌────────────┬──────────┬──────────┐
  │    항목    │ B+Tree   │ LSM-Tree │
  ├────────────┼──────────┼──────────┤
  │ 읽기 성능  │   우수   │   보통   │
  │ 쓰기 성능  │   보통   │   우수   │
  │ 공간 효율  │   보통   │   우수   │
  │ 쓰기 증폭  │   높음   │   낮음   │
  │ 읽기 증폭  │   낮음   │   높음   │
  │ 사용 사례  │   OLTP   │ 로그/IoT │
  └────────────┴──────────┴──────────┘

상황별 적합한 인덱스

1. WHERE user_id = 12345 (동등 검색, PK)
   → B+Tree (기본) 또는 Hash Index

2. WHERE created_at BETWEEN '2024-01-01' AND '2024-12-31'
   → B+Tree (범위 검색)

3. WHERE gender = 'M' AND status = 'ACTIVE' AND grade = 'VIP'
   → Bitmap Index (낮은 카디널리티, 다중 조건)

4. WHERE ST_Distance(location, POINT(37.5, 127)) < 1000
   → R-Tree (공간 검색)

5. IoT 센서 데이터 실시간 저장
   → LSM-Tree (쓰기 위주)