B-트리 변형과 LSM 트리

B-Tree 변형들과 LSM Tree는 하나의 공통 질문에서 출발해 — 제자리 수정의 비용을 어떻게 줄일 것인가, 그리고 읽기·쓰기·공간 중 무엇을 우선할 것인가.

기본 B-Tree는 매 수정마다 노드를 제자리에서 업데이트하거든. 랜덤 쓰기라서 비싸고 동시성 제어도 까다로워. 그래서 다양한 변형들이 각자의 방식으로 이 문제를 우회하지. Copy-on-Write B-Tree는 수정할 노드를 복사해서 복사본에 변경을 적용하고, 루트까지 경로 전체를 새로 만든 다음 루트 포인터를 원자적으로 교체해. 락 없이 읽기가 가능하고 WAL도 필요 없어. LMDB가 이 방식인데, 대가는 루트까지의 쓰기 증폭이지.

Lazy B-Tree(WiredTiger, 즉 MongoDB 엔진)는 수정을 바로 적용하지 않고 업데이트 버퍼에 모았다가 한꺼번에 반영해. 여러 수정을 모아서 쓰니까 I/O가 줄어들고 SSD 쓰기 증폭도 완화돼. LA-Tree나 Fractal Tree도 비슷하게 각 노드에 작은 버퍼를 둬서 업데이트를 흡수하는 방식이야. Bw-Tree는 Microsoft Research가 만든 건데 아예 래치 없이 동작해. 매핑 테이블로 논리적 페이지 ID를 물리적 주소에 매핑하면서 CAS로 원자적 업데이트를 하고, 변경을 델타 체인으로 기존 페이지에 연결하지. 동시성이 극대화되지만 델타가 길어지면 읽기가 느려져서 주기적으로 통합해야 해.

FD-Tree는 SSD의 erase-before-write 특성에 맞춰 순차 쓰기를 극대화하고, Cache-Oblivious B-Tree는 캐시 크기를 몰라도 모든 메모리 계층에서 좋은 지역성을 가지게 해. 결국 각 변형은 쓰기 증폭 vs 읽기 증폭, 구현 복잡도 vs 동시성, 범용성 vs 하드웨어 최적화에서 다른 지점을 선택한 거야.

이런 트레이드오프를 정면으로 다루는 게 RUM Conjecture야. 읽기·쓰기·공간을 동시에 최적화하는 건 불가능하다는 건데, LSM Tree는 그 트레이드오프에서 쓰기를 선택한 자료구조지. 핵심 아이디어는 단순해 — 랜덤 쓰기를 순차 쓰기로 바꾸는 거야. 모든 쓰기를 메모리의 Memtable(보통 스킵리스트)에 먼저 버퍼링하고, 가득 차면 디스크에 SSTable로 통째로 순차 쓰기해. 디스크 데이터는 절대 직접 수정하지 않는 불변 방식이거든. Memtable은 메모리에만 있으니까 WAL로 내구성을 보장하고, 조회할 때는 Memtable → 최근 SSTable → 오래된 SSTable 순서로 찾아가.

업데이트와 삭제가 특이해. 기존 데이터를 찾아서 고치지 않아. 업데이트는 같은 키에 새 값을 그냥 삽입하고, 삭제는 톰스톤이라는 특수 마커를 넣지. 오래된 버전과 톰스톤은 컴팩션 때 정리되는데, 이 전략이 성능 특성을 결정해. Size-Tiered는 비슷한 크기 SSTable을 모아 병합해서 쓰기에 유리하고, Leveled는 각 레벨에 크기 제한을 두고 키 범위가 안 겹치게 유지해서 읽기와 공간에 유리하지. Cassandra vs RocksDB의 기본 전략 차이가 바로 이거야.

LSM Tree의 읽기 약점을 보완하는 핵심이 블룸 필터야. "이 키가 이 SSTable에 있는가?"를 확률적으로 빠르게 판단해서, "없다"고 하면 확실히 없거든. 대부분의 SSTable을 건너뛸 수 있으니까 존재하지 않는 키에 대한 조회가 극적으로 빨라져.

---

정리

4장 읽고 기억할 거 세 가지:

1. B-Tree 변형들은 "제자리 수정을 피하자"는 공통 철학을 공유한다. Copy-on-Write는 락 없는 읽기를, Bw-Tree는 래치 없는 동시성을, Lazy B-Tree는 버퍼링으로 I/O 절감을 달성한다.
2. LSM Tree는 Memtable → WAL → SSTable로 모든 쓰기를 순차 append로 처리하며, 컴팩션 전략(Size-Tiered vs Leveled)이 읽기/쓰기/공간 성능을 결정한다.
3. RUM Conjecture에 따라 읽기·쓰기·공간을 동시에 최적화하는 건 불가능하며, 블룸 필터가 LSM Tree 읽기의 핵심 보조 도구로 불필요한 SSTable 탐색을 걸러낸다.