[학습] B-tree와 UUID4 성능 저하 — 클러스터드 인덱스의 함정
TL;DR — UUID4는 랜덤 분포라 B-tree에 삽입 시 페이지 분할(page split)이 폭발적으로 발생한다. SQLite rowid(정수) 기준 초당 100만 건 vs UUID4는 수십 배 느림. PostgreSQL·MySQL도 동일 원리 적용.
학습 배경
GeekNews 큐레이션 아티클 (2026-06-07): SQLite에서 UUID4를 clustered index로 사용할 때 B-tree 재균형으로 인한 성능 저하 분석.
개념 맵 (7 레이어)
[B-tree 구조]
└─ [Clustered index] ─── 데이터가 인덱스 순서로 물리 정렬됨
└─ [Sequential vs Random insert]
└─ [UUID4 문제] ─── 랜덤 분포 → page split 폭발
└─ [SQLite rowid 특수성]
└─ [대안: UUID7 / ULID / auto-increment]
개념 설명
1. B-tree 구조
B-tree(Balanced Tree)는 데이터베이스 인덱스의 가장 보편적인 자료구조다.
- 노드: 루트 → 내부 노드 → 리프 노드 구조
- 정렬 보장: 모든 노드는 키 순서로 정렬됨
- 삽입 규칙: 새 키는 정렬된 위치에 삽입. 노드가 가득 차면 분할(split)
- 페이지 단위: 디스크에서 페이지(SQLite 기본 4KB) 단위로 읽고 씀
새 키 삽입 시 B-tree 내부 동작:
1. 루트부터 리프까지 트리 탐색 (O(log n))
2. 리프 노드에서 정렬 위치 찾기
3. 공간 있으면 삽입 완료
4. 공간 없으면 페이지 분할 → 부모 노드에도 키 삽입 → 연쇄 분할 가능
2. Clustered Index
인덱스의 리프 노드에 실제 행 데이터가 함께 저장되는 구조.
- 데이터가 인덱스 키 순서로 물리적으로 정렬됨
- 이점: 범위 쿼리 빠름, 인덱스 탐색 = 데이터 접근
- SQLite: 기본적으로
rowid(정수) 기반 clustered index.WITHOUT ROWID테이블은 PRIMARY KEY가 clustered index. - MySQL InnoDB: PRIMARY KEY가 항상 clustered index
3. Sequential vs Random Insert
| 특성 | Sequential (auto-increment, rowid) | Random (UUID4) |
|---|---|---|
| 삽입 위치 | 항상 마지막 리프 페이지 | 트리 전체 랜덤 |
| 페이지 분할 | 최소화 (마지막만 분할) | 모든 기존 페이지가 후보 |
| 캐시 효율 | 높음 (최근 페이지 재사용) | 낮음 (랜덤 페이지 접근) |
| 쓰기 증폭 | 낮음 | 높음 |
4. UUID4 문제 — Page Split 폭발
UUID4는 완전 랜덤 128비트 값이다.
- 삽입 시 기존 트리의 랜덤한 위치에 끼어들어야 함
- 해당 리프 페이지가 메모리에 없으면 디스크에서 로드 (I/O)
- 페이지가 가득 차면 분할 → 부모 노드 업데이트 → 연쇄 발생
- 대규모에서: 거의 모든 삽입이 페이지 분할 + 랜덤 I/O 유발
성능 수치 (SQLite 기준, 아티클 수치):
- rowid(정수): ~100만 건/초
- UUID4: 수십 배 감소
5. SQLite rowid 특수성
SQLite의 모든 일반 테이블은 암묵적 rowid(64비트 정수)를 가진다.
rowid는 단조 증가 → sequential insert → page split 최소화INTEGER PRIMARY KEY선언 시rowid의 alias가 됨 (별도 인덱스 없음, 가장 효율적)- UUID를
TEXT로 저장하면 clustered index가 UUID 순서로 정렬 → 문제 발생 WITHOUT ROWID로 UUID를 PK 삼으면 더 심각해짐
6. 대안
| 대안 | 특성 | UUID 호환성 |
|---|---|---|
| Auto-increment / rowid | 완전 sequential, 가장 빠름 | X (분산 시스템 어려움) |
| UUID7 | timestamp prefix → 단조 증가 경향 | O (UUID 포맷 유지) |
| ULID | timestamp(ms) + 랜덤 26자 | O (정렬 가능) |
| NanoID (custom) | 사용자 정의 길이 | 설계에 따라 |
UUID7: timestamp_ms + random 구조라 같은 밀리초 내에서만 랜덤. 대규모에서도 sequential에 가까운 삽입 패턴 유지.
실전 적용
우리 시스템(Pantheon, nhl-backend)에서:
- Pantheon: SQLite 사용 여부 확인 필요. 만약 UUID PK 사용 중이면 UUID7/ULID 검토 대상
- nhl-backend (FastAPI + SQLAlchemy): MySQL 기준이면 InnoDB clustered index 동일 문제. UUID PK 지양, surrogate key + unique UUID 컬럼 패턴 고려
- PostgreSQL:
gen_random_uuid()(UUID4) PK →uuid_generate_v7()(UUID7) 마이그레이션 패턴 존재
예시 — SQLite에서 UUID4 vs rowid 비교
-- 느린 패턴: UUID4 TEXT PK
CREATE TABLE events_bad (
id TEXT PRIMARY KEY, -- UUID4, 랜덤 → B-tree 분할 폭발
payload TEXT
);
-- 빠른 패턴: rowid + unique UUID
CREATE TABLE events_good (
id INTEGER PRIMARY KEY, -- rowid alias, sequential
uuid TEXT UNIQUE, -- UUID는 참조용 별도 컬럼
payload TEXT
);
-- UUID7 사용 시 (분산 환경에서 UUID 필요할 때)
-- UUID7 = timestamp_ms(48bit) + version(4bit) + random(76bit)
-- 시간순 정렬 가능 → clustered index 친화적함정 / 주의점
- AUTO_INCREMENT != UUID: 분산 환경에서 auto-increment는 충돌 위험. UUID7/ULID가 현실적 대안
- PostgreSQL TOAST: 큰 값은 별도 저장소로 분리되어 UUID 영향 다름
- 쓰기 vs 읽기 트레이드오프: UUID4는 분산 생성·무충돌 이점 있음. 쓰기 빈도 낮으면 선택 가능
- 기존 시스템 마이그레이션: UUID4→UUID7 전환은 PK 변경 = 대규모 마이그레이션
내 언어로 설명하기 (Feynman Summary)
항승씨가 직접 작성해주세요. B-tree에서 UUID4가 왜 느린지, 친구에게 설명하듯 2-3문장으로.
복습 일정
| 단계 | 날짜 | 완료 |
|---|---|---|
| Day 0 (Feynman 첫 작성일) | 미정 | ☐ |
| Day 7 | 미정 | ☐ |
| Day 37 | 미정 | ☐ |
| Day 127 | 미정 | ☐ |
Day 0는 Feynman summary 직접 작성한 날 기준으로 갱신됩니다.
참고
- GeekNews: SQLite에서 UUID4 클러스터드 인덱스 성능 분석 (2026-06-07 큐레이션)
- 연결 개념: B-tree, Clustered Index, Page Split, Write Amplification