# 인덱스 내부 구조 — B-Tree vs LSM-Tree

> **한 줄 요지**: 인덱스 선택의 진짜 결정 변수는 "읽기냐 쓰기냐"가 아니라 **"쓰기 부담이 B-Tree의 random I/O를 아프게 할 만큼 있느냐"**다. B-Tree는 정렬을 *제자리에* 유지(읽기 강점, random 쓰기 대가), LSM은 정렬을 *메모리에서* 하고 순차로 flush(쓰기 강점, write/read amplification 대가).

**메타**
- 분류: `백엔드 > DB & 스토리지 > 인덱스 내부 구조 (B-Tree vs LSM-Tree)`
- 날짜: 2026-07-16
- 깊이: 실무/딥-다이브 (내부 구조·1차 원리 유도)
- 방식: `[소크라테스 + 실무 드릴]` — 힌트만으로 LSM을 밑바닥부터 재발명 → 함정 시나리오 3개로 판단 훈련

---

## 1. 배경 — 왜 이 논의가 필요한가

"인덱스"는 그냥 빠른 조회 장치가 아니다. 디스크의 물리적 성질(순차 vs 랜덤 I/O) 위에 세워진 **타협의 산물**이다. 같은 "정렬된 조회"라는 목표를 두고 B-Tree와 LSM-Tree는 정반대 지점에서 타협한다. 이 둘의 내부 동작을 이해해야:
- 워크로드에 맞는 스토리지 엔진/DB를 고를 수 있고,
- Cassandra 툼스톤 지옥·컴팩션 폭주 같은 실전 사고를 예방하며,
- "증상이 나쁘다"고 엔진을 갈아엎는 대신 **튜닝으로 풀 지점**을 안다.

---

## 2. 쟁점 요약

- **디스크 토대**: append(순차)는 싸고, random in-place(제자리 수정)는 비싸다 — HDD(seek)든 SSD(read-modify-write = write amplification)든.
- **B-Tree**: 정렬을 디스크에 제자리로 유지 → 삽입 시 페이지 분할(random 쓰기). 팬아웃이 커서 얕음(3~4단) → 단건 조회 강점.
- **LSM-Tree**: 메모리(memtable)에 정렬 → SSTable로 순차 flush → 컴팩션으로 병합. 쓰기 폭주 강점, 대신 write/read amplification.
- **선택 기준**: 표면의 "읽기/쓰기 비율"이 아니라 **쓰기 부담이 LSM을 정당화하는가**.
- **운영 함정**: 대량 삭제(툼스톤), 컴팩션 전략 오선택(STCS vs LCS), 오버엔지니어링.

---

## 3. 입장별 정리

### 🌳 B-Tree 옹호 (전통 RDB DBA 관점)
- 데이터를 **key 순 정렬 상태로 디스크에 유지**. 정렬은 물리적 인접이 아니라 **부모 노드의 구분키(포인터)**로 유지 → 새 페이지는 디스크 아무 데나 쓰고 포인터만 꽂음.
- **B+Tree**: 내부 노드는 이정표(key+포인터)만, **데이터는 리프에만**. 리프끼리 **링크드리스트**로 연결 → 범위 스캔은 "한 번 하강 + 옆으로 훑기".
- 팬아웃 ≈ 800 → 높이 3~4단으로 수십억 행 → **단건 조회 = 디스크 read 3~4번(상위는 캐시), 예측 가능한 낮은 지연.**
- 약점: 쓰기가 **random in-place**(페이지 분할·포인터 수정·위로 전파) → 쓰기 폭주에 취약. 시간 지나면 단편화로 범위스캔 저하.
- 클러스터형(PK) 인덱스 = 리프에 행 전체 / 보조 인덱스 = 리프에 PK → 2단 조회.

### 🪵 LSM-Tree 옹호 (쓰기 폭주 서비스 관점)
- **"절대 제자리 수정 안 한다. append만 한다."** → 쓰기 폭발적으로 빠름.
- 조회를 위해 **정렬은 메모리(memtable, 스킵리스트/균형트리)에서** 유지 → 차면 **SSTable(정렬 파일)로 순차 flush** 후 메모리 비움. 내구성은 **WAL**이 보강.
- SSTable = **블룸필터 + sparse index(블록당 첫 key) + 정렬 데이터 블록**. → 조회: 블룸필터로 없는 파일 스킵 → sparse index로 블록 1개 특정 → 이진탐색.
- 갱신 = 새로 쌓기(최신 우선), 삭제 = **툼스톤(마커+타임스탬프)**. 누적은 **컴팩션(병합정렬)**으로 정리.
- 약점: **write amplification**(컴팩션마다 재기록), **read amplification**(한 파티션이 여러 SSTable에 흩어짐 → point read가 여러 파일 확인).

### 🙋 질문자 (초심자)가 드러낸 전제
- "페이지 = 디스크 개념?" → 그렇다(4~16KB 블록, 메모리 페이지와 별개).
- "논리적 포인터 정렬이면 HDD에서 그 주소 찾아가는 오버헤드는?" → 맞다. B-Tree도 읽기가 공짜는 아니고 random I/O를 치른다. 단 트리가 얕아 단건은 3~4홉으로 상한.
- "SSTable ⟷ 파티션은 1:1?" → 아니다. **다대다**(한 파일에 여러 파티션, 한 파티션이 여러 파일에 흩어짐).

---

## 4. 트레이드오프 표

### 4-1. B-Tree vs LSM-Tree

| 축 | B-Tree | LSM-Tree |
|---|---|---|
| 쓰기 패턴 | random in-place (페이지 분할) | 순차 append (flush) |
| 쓰기 양(amplification) | 적음 | 많음 (컴팩션 재기록) |
| 읽기(단건) | 얕은 트리 3~4홉, **예측가능·낮은 지연** | 여러 SSTable 확인 가능 → **read amp, 꼬리(p99) 취약** |
| 범위 스캔 | 리프 링크 훑기(단편화 시 저하) | 정렬 파일 병합 |
| 공간 | 조밀 | 죽은 버전·툼스톤 누적(전략 따라) |
| 강점 워크로드 | 읽기·point read·지연 민감, 쓰기 희박 | 쓰기 폭주(로그/이벤트/잦은 갱신) |
| 대표 | MySQL InnoDB, PostgreSQL | RocksDB, LevelDB, Cassandra, HBase, ScyllaDB, MyRocks |

### 4-2. LSM 컴팩션 전략 (셋 다 못 가진다 — write/read/space amp)

| 전략 | write amp | read amp | space amp | 적합 |
|---|---|---|---|---|
| **STCS** (size-tiered) | 낮음 | 높음 | 높음 | 쓰기 폭주, 갱신 적음 (로그/이벤트) |
| **LCS** (leveled) | 높음 | 낮음 | 낮음 | 읽기·갱신 잦고 지연 민감 (프로필/세션) |
| **TWCS** (time-window) | 낮음 | 낮음(시간범위) | 낮음 | 시계열 + TTL 만료 |

---

## 5. 결론 / 의사결정 가이드

**엔진 선택 (그린필드):**
- 읽기·point read 위주 + **쓰기 희박** + 중간 규모 + 빡센 p99 → **B-Tree RDB.** (LSM은 오버엔지니어링 + p99 리스크)
- **쓰기 부담이 큼**(초당 수십만, 잦은 갱신) → **LSM.** 읽기는 LCS로 감내 수준까지.
- ⚠️ 결정 변수는 "읽기 많음"이 아니라 **"쓰기가 B-Tree의 random I/O를 아프게 하는가."** 쓰기가 희박하면 읽기 많아도 B-Tree.

**이미 LSM 위에 있는데 읽기/디스크가 나쁠 때:**
- 엔진 갈아엎지 말고 **컴팩션 전략부터** 점검. 갱신 잦은데 STCS면 → **LCS로 전환**(read/space amp 급감, 대가는 write amp). 노드 추가는 구조 문제를 하드웨어로 덮는 헛발질.

**대량 삭제 (LSM):**
- row 단위 `DELETE` 수십만 번 = 툼스톤 지옥(읽기 경로가 툼스톤 스캔 → `tombstone_failure_threshold` 초과 시 쿼리 실패, `gc_grace_seconds` 동안 잔존).
- 회원 단위 삭제 → **삭제 단위를 파티션 키로** 모델링(`member_id`) → 파티션 툼스톤 몇 개. 삭제된 파티션은 읽기 경로도 안 때림.
- 시간 만료 → **TTL + TWCS** → 창 만료 시 SSTable 통째 drop, 툼스톤 0.
- 핵심: **"누구를 지우나(파티션 키)"와 "언제 만료하나(TTL/TWCS)"는 독립된 두 축.** 삭제를 row 연산으로 맞서지 말고 모델링/만료로 흡수.

**실패 모드 체크리스트:**
- 툼스톤 부활(좀비): 툼스톤을 옛 값과 병합 전에 버리면 삭제된 key가 되살아남 → `gc_grace_seconds` 존재 이유.
- 컴팩션 스파이크: 백그라운드 컴팩션이 IO/CPU 튀게 함 → 지연 민감 서비스의 p99 위협.
- 읽기 증폭: 존재하지 않는/드문 key 조회가 여러 파일을 다 뒤짐 → p99 꼬리.

---

## 6. 추가 학습 키워드

- WAL(commit log) / 체크포인트 / 크래시 복구(replay)
- 스킵리스트 vs red-black tree (memtable 자료구조)
- 블룸 필터 FP 비대칭 (→ 0003)
- fractal tree / B-epsilon tree (B-Tree와 LSM 사이 절충)
- write/read/space amplification 정량 분석 (RUM conjecture)
- leveled vs size-tiered vs time-window compaction 내부
- Cassandra 데이터 모델(파티션 키·클러스터링 키), gc_grace_seconds
- CDC / change data capture (인덱스·검색 동기화)

---

*관련 노트: [[bloom-filter-note]] (SSTable의 블룸필터 부품), [[transaction-isolation-note]] (스토리지 엔진 위의 격리).*