Portfolio

개념

DB가 10억 건 중 특정 키 하나를 찾아야 한다. 전수 스캔은 논외고, 정렬된 자료구조가 필요하다. 그런데 RAM이 아니라 디스크 위에 있는 정렬 구조여야 한다. 일반 이진 탐색 트리(BST)를 그대로 디스크에 올리면 깊이가 30단계 쯤 되고, 그 30번의 디스크 I/O가 그대로 쿼리 비용이 된다. 여기서 출발해 나온 두 갈래가 B-tree 계열과 LSM-tree다.

B-tree — 디스크에 맞춘 트리

발상은 단순하다.

디스크는 어차피 블록 단위로 읽으니, 노드 하나를 페이지 하나 크기로 키워서 한 노드에 키를 잔뜩 담자.

한 노드에 키가 수백 개면 자식(branch)도 수백 개, 즉 fan-out이 수백이 된다. 트리 깊이는 log(fan-out) 스케일이라 fan-out이 커질수록 트리가 얕아진다.

이진 트리: log₂(10억) ≈ 30단계
B-tree:   log₂₀₀(10억) ≈ 4단계

I/O 30번이 I/O 4번으로 줄어드는 게 B-tree의 전부다. 구조의 핵심 규칙:

한 노드 = 한 페이지 (8KB)
값은 정렬되어 있고 노드마다 여러 개
자가 균형 — 삽입/삭제로 한쪽이 깊어지면 노드를 분할·병합해서 모든 리프 깊이를 같게 유지

B+tree — 실제 DB가 쓰는 것

"DB 인덱스는 B-tree"라고들 하지만 거의 모든 RDB(Postgres, MySQL, Oracle)가 실제로 쓰는 건 B+tree다.

차이는 하나다.

B-tree: 모든 노드에 실제 데이터 있음
B+tree: 리프 노드에만 데이터. 내부 노드는 키만 (이정표 역할)

           [100 | 500]              ← 키만 (이정표)
          /     |     \
       [50]  [300]   [700]          ← 키만
       / \    / \     / \
      ◀리프──리프──리프▶             ← 데이터 + 양방향 링크
      1~49  51~99 ... 901~999

왜 B-tree보다 나은가

트리가 더 얕다. 내부 노드에 데이터가 없으니 한 노드에 키를 더 많이 담을 수 있다. 8KB 페이지 기준:

B-tree  내부 노드: 키 + 데이터 → 한 항목 ~200B → 노드당 ~38개
B+tree 내부 노드: 키 + 포인터만 → 한 항목 ~16B → 노드당 ~500개

10억 개 데이터의 깊이: B-tree ~6단계, B+tree ~4단계. 읽기에서 손해는 없고 오히려 I/O가 줄어든다.

리프가 연결 리스트로 이어져 있다. 범위 조회가 공짜.

SELECT * WHERE id BETWEEN 100 AND 500;

B-tree: 100 찾고 → 101 찾으려고 다시 루트부터 → 반복
B+tree: 100 찾고 → 리프 링크 타고 쭉

Clustered index가 "테이블 자체가 B+tree"인 것도 이 구조 덕이다. 리프 순회 = 테이블 순차 스캔.

LSM-tree — 쓰기 중심 전략

여기서 발상이 뒤집힌다.

B+tree의 약점은 랜덤 쓰기다. INSERT 한 번에 해당 키가 들어갈 페이지를 찾아가서 그 페이지를 수정해야 하는데, 10억 건 규모면 그 페이지는 디스크 어딘가 랜덤한 위치에 있다. 매 쓰기마다 랜덤 I/O. 로그 수집·시계열처럼 쓰기가 폭주하는 워크로드엔 부적합하다.

LSM의 전략:

쓰기는 무조건 순차 I/O로만. 정렬은 나중에 몰아서.

동작 방식

쓰기 → MemTable (RAM의 정렬된 구조) + WAL에 append
         ↓ 꽉 차면 flush
       [SSTable 1] ← 디스크, 불변, 정렬된 파일
       [SSTable 2]
       [SSTable 3]
         ↓ 백그라운드
       Compaction: 여러 SSTable을 합쳐 큰 SSTable로

MemTable: RAM의 정렬 구조(보통 skip list). 쓰기는 여기로만
WAL: durability 확보용 순차 로그. MemTable 내용을 append
SSTable (Sorted String Table): 정렬된 불변 파일. MemTable을 디스크로 덤프한 결과
Compaction: 여러 SSTable을 병합하며 중복·삭제 표시 정리

읽기는 어떻게

데이터가 여러 SSTable + MemTable에 흩어질 수 있으니 읽기는 원칙적으로 느리다. 이를 완화하는 장치들:

Bloom filter — SSTable마다 "이 파일에 이 키가 없음"을 빠르게 판별. 대부분 SSTable은 실제로 열지 않고 스킵
Leveled compaction — SSTable을 레벨별로 정리해 한 키가 한두 SSTable에만 존재하도록 보장 (LevelDB, RocksDB 방식)
블록 캐시 — 최근 읽은 블록을 RAM에 캐싱

B+tree vs LSM-tree

축	B+tree	LSM-tree
쓰기 속도	보통 (랜덤 I/O)	매우 빠름 (순차 I/O)
읽기 속도	일관되게 빠름	보통 (여러 SSTable 확인 가능성)
쓰기 증폭	낮음	높음 (compaction으로 같은 데이터 수 회 재기록)
공간 증폭	낮음	높음 (tombstone, 중복 버전)
레이턴시 예측성	좋음	나쁨 (compaction 스파이크)
트랜잭션/JOIN	자연스러움	어색함

"LSM이 쓰기 빠르면 그냥 더 좋은 거 아닌가"에 대한 답

아니다. LSM은 비용을 다른 곳에 떠넘겼을 뿐이다.

쓰기 증폭 — 논리적 쓰기 1번이 compaction 거치며 10~30번 물리 쓰기로 증폭. SSD 수명과 대역폭에 부담
공간 증폭 — 삭제가 tombstone만 남기고 실제 제거는 compaction 때. 같은 키의 오래된 버전도 한동안 공존. 실제 데이터의 2~3배 공간을 쓰기도 함
지연 스파이크 — compaction이 돌 때 디스크·CPU를 잡아먹어 p99 레이턴시가 튐
복잡한 쿼리 불리 — ACID 다중 행 트랜잭션, JOIN, secondary index가 전부 어색

Postgres·MySQL이 LSM으로 갈아타지 않은 이유가 이거다. OLTP는 예측 가능한 레이턴시와 트랜잭션이 핵심이라 B+tree가 여전히 맞는 선택이다.

언제 뭘 쓰나

B+tree (RDB)

일반 OLTP — 읽기·쓰기 섞여 있고 트랜잭션이 중요
범위 조회, JOIN 등 복잡한 쿼리 패턴
레이턴시 예측 가능성이 중요

LSM-tree

쓰기 폭주 워크로드 — 로그 수집, 메트릭, IoT, 시계열
Key-Value 단건 읽기 위주
대량 append, 수정은 거의 없음

채택 사례

B+tree: Postgres, MySQL/InnoDB, Oracle, SQL Server
LSM-tree: Cassandra, HBase, RocksDB, LevelDB, ScyllaDB, InfluxDB 일부

한 줄로

B+tree — 정렬을 항상 유지하고 쓰기 비용을 지불 LSM-tree — 정렬을 미뤘다가 나중에 몰아서. 읽기 비용을 지불

"더 좋은 구조"는 없다. 쓰기와 읽기의 트레이드오프를 어디로 떠넘길 것인가의 선택이다.

B-tree와 LSM-tree

개념