B+트리 (B+-Tree) — Brain Science

핵심 인사이트 3줄

B+트리(B+-Tree)는 B-트리에서 데이터를 리프 노드에만 저장하고, 모든 리프를 연결 리스트로 이어 범위 검색(Range Scan) 성능을 O(k)로 극적으로 개선한 구조다.

내부 노드는 라우팅 키만 보유해 더 많은 키를 담을 수 있어 트리 높이가 낮아지고, MySQL InnoDB·PostgreSQL 등 모든 주요 RDBMS 인덱스의 표준이다.

클러스터 인덱스(Primary Key)는 B+트리 리프에 실제 행 데이터를 저장하고, 세컨더리 인덱스는 PK 값을 저장해 2단계 조회(InnoDB 이중 조회) 구조를 형성한다.

Ⅰ. B+트리 vs B-트리 핵심 차이

특성	B-트리	B+트리
데이터 저장 위치	모든 노드	리프 노드만
내부 노드 용도	라우팅 + 데이터	라우팅 키만
범위 검색	트리 순회 필요 (느림)	리프 체인 스캔 O(k) (빠름)
내부 노드 용량	데이터 포함으로 적음	키만 있어 더 많은 키 보유
삭제 복잡도	복잡 (내부 노드 처리)	리프만 처리, 내부는 더미 키

B+트리 구조:

내부 노드: [ 17 ]  ← 라우팅 키만
           /    \
     [ 5, 12 ]  [ 24, 30 ]

리프 노드 (체인):
[1,3] → [5,9] → [12,15] → [17,20] → [24,27] → [30,35]
  ↑ 실제 데이터(또는 Row Pointer) 저장 + 연결 포인터

📢 섹션 요약 비유: B+트리는 색인 카드 + 실제 파일 분리 시스템이다 — 색인(내부 노드)은 위치만 알려주고, 실제 파일(리프)은 순서대로 서랍에 연결되어 있다.

Ⅱ. 범위 검색 (Range Scan) 최적화

B-트리 범위 검색

SELECT * WHERE age BETWEEN 20 AND 30:
  B-트리: 트리를 중위 순회 → 불연속 디스크 I/O 다수

B+트리 범위 검색

SELECT * WHERE age BETWEEN 20 AND 30:
  1. age=20 리프 노드까지 트리 하강 O(log n)
  2. 리프 체인 → → → age=30까지 순차 스캔 O(k)
  총: O(log n + k)  ← 매우 효율적

def range_search(root, low, high):
    # 1단계: low 값의 리프 찾기
    leaf = find_leaf(root, low)
    # 2단계: 리프 체인으로 high까지 스캔
    result = []
    while leaf:
        for key in leaf.keys:
            if low <= key <= high:
                result.append(key)
            elif key > high:
                return result
        leaf = leaf.next  # 다음 리프로 이동
    return result

📢 섹션 요약 비유: 범위 검색은 사전에서 특정 알파벳 구간 단어 찾기다 — B-트리는 각 단어를 따로 찾고, B+트리는 'A' 페이지 찾은 뒤 'B', 'C'로 쭉 넘기면 된다.

Ⅲ. MySQL InnoDB B+트리 인덱스 구조

클러스터 인덱스 (Primary Key Index)

InnoDB B+트리 리프 노드:
┌──────────────────────────────────────┐
│  PK  │      실제 행 데이터 (Row)      │
│  1   │  name="Alice", age=25, ...    │
│  2   │  name="Bob",   age=30, ...    │
│  3   │  name="Carol", age=28, ...    │
└──────────────────────────────────────┘

세컨더리 인덱스 (Secondary Index)

세컨더리 B+트리 리프 노드:
┌───────────────────────────┐
│  인덱스 키 │  PK 값       │
│  age=25   │  PK=1        │  → 클러스터 인덱스에서 row 찾기
│  age=28   │  PK=3        │
│  age=30   │  PK=2        │
└───────────────────────────┘

이중 조회 (Double Lookup) 문제: 세컨더리 인덱스 탐색 후 PK로 클러스터 인덱스 재탐색 필요

→ 커버링 인덱스 (Covering Index): SELECT 컬럼을 인덱스에 모두 포함해 이중 조회 방지

📢 섹션 요약 비유: 이중 조회는 책에서 목차(세컨더리 인덱스)로 페이지를 찾고, 그 페이지에서 다시 내용을 읽는 것이다. 커버링 인덱스는 목차에 요약이 다 있어 페이지를 안 넘겨도 되는 것이다.

Ⅳ. B+트리 삽입과 삭제

삽입 — 리프에서 분할

리프 노드 가득 찼을 때:
  분할 전: [10, 20, 30, 40, 50] (가득 참)
  삽입 값: 25
  분할 후: [10, 20] | [25, 30, 40, 50]
           부모에 25(복사) 올라감  ← B-트리와 차이: B+트리는 복사(copy), B-트리는 이동(move)

삭제 — 내부 노드 더미 키 유지

B+트리 특성:
  리프의 키를 삭제해도 내부 노드의 더미 키는 유지 가능
  (라우팅 역할만 하므로)
  → B-트리보다 삭제 처리가 단순

📢 섹션 요약 비유: B+트리 삽입 분할에서 키를 복사하는 것은 사원증 복사본을 본사(부모)에 보내는 것이다 — B-트리는 원본을 보내지만 B+트리는 복사본을 보내 리프에도 남겨둔다.

Ⅴ. 성능 최적화와 현대 적용

페이지 크기와 차수 최적화

MySQL InnoDB 페이지: 16KB 기본
  내부 노드 키: ~6 bytes + 포인터 6 bytes = 12 bytes
  → 내부 노드 키 수: 16384 / 12 ≈ 1365개
  → 높이 3 트리에 최대: 1365² × (16384/행크기) ≈ 수천만 행

현대 DB에서의 적용

DB	B+트리 변형	특이사항
MySQL InnoDB	클러스터 B+트리	PK 리프에 실제 데이터 저장
PostgreSQL	힙 기반 + B+트리	세컨더리 인덱스에 힙 포인터
MongoDB WiredTiger	B-트리 변형	LSM 트리와 혼합
SQLite	B-트리	이식성 중시, 단순 구조

📢 섹션 요약 비유: InnoDB 클러스터 인덱스는 전화번호부다 — 이름(PK) 순서대로 모든 정보가 정렬되어 있어 이름만 알면 주소·번호를 즉시 찾는다.

📌 관련 개념 맵

B+트리 (B+-Tree)
├── B-트리와의 차이
│   ├── 데이터: 리프에만
│   └── 리프 연결 리스트 (Range Scan 최적화)
├── 인덱스 유형
│   ├── 클러스터 인덱스 (Clustered)
│   │   └── InnoDB: 리프에 실제 행 저장
│   └── 세컨더리 인덱스
│       └── 리프에 PK 값 저장 → 이중 조회
├── 최적화 기법
│   ├── 커버링 인덱스 (이중 조회 방지)
│   ├── 복합 인덱스 (Composite)
│   └── 인덱스 선두 컬럼 규칙
└── 실제 사용
    ├── MySQL InnoDB
    ├── PostgreSQL
    └── Oracle / DB2

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

┌─────────────────────────────────────────────────────────────────┐
│                   B+트리 발전 흐름                               │
├──────────────┬────────────────────┬─────────────────────────────┤
│ 1976년       │ B+트리 개념 정립   │ Knuth, 리프 체인 아이디어   │
│ 1980년대     │ DB 인덱스 표준화   │ IBM DB2·Oracle 채택         │
│ 2000년대     │ MySQL InnoDB       │ 클러스터 B+트리, 범용화     │
│ 2010년대     │ SSD 최적화         │ 순차 vs 랜덤 I/O 재분석     │
│ 2020년대     │ NVMe·인메모리 DB   │ 페이지 크기 조정, Bε-트리  │
└──────────────┴────────────────────┴─────────────────────────────┘

핵심 키워드 연결:
B-트리 → B+트리(리프 체인) → 범위 스캔 O(k)
  ↓              ↓                   ↓
디스크 최적화  데이터=리프만      ORDER BY 최적화
  ↓
클러스터 인덱스 → 커버링 인덱스 → 쿼리 최적화

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

B+트리는 책에서 목차와 내용이 분리된 구조다 — 목차(내부 노드)는 길만 알려주고, 실제 내용(데이터)은 순서대로 연결된 마지막 페이지(리프)에만 있다.
리프 체인은 연결된 서랍 손잡이다 — 첫 서랍을 열면 다음 서랍 손잡이(포인터)가 달려있어 원하는 범위까지 빠르게 이동할 수 있다.
클러스터 인덱스는 학교 출석부다 — 학번(PK) 순서대로 모든 학생 정보가 정리되어 있어 학번만 알면 모든 정보를 즉시 찾는다.