LSM 트리(Log-Structured Merge Tree), 효율적인 데이터 저장 방식
LSM 트리(Log-Structured Merge Tree)는 쓰기 성능(Write Performance)에 특화된 저장 엔진으로, NoSQL DB 및 관계형 DB에서 널리 사용됨
B+ 트리(B+ Tree) 대비 단일 랜덤 블록 접근(Single Random Block Access)으로 인덱스 업데이트가 가능하여 쓰기 성능을 향상시킴
MemTable, SSTable, Compaction 등 핵심 구성 요소와 레벨 기반 압축(Level-Based Compaction) 방식을 통해 저장 공간 효율성을 높임
짧은 설명(Thin Article)에 대한 비판과 함께, LSM 트리 시각화 자료에 대한 긍정적 평가가 존재함
LSM 트리의 핵심 구성 요소
LSM 트리는 MemTable, SSTable, Compaction 등 세 가지 주요 구성 요소로 이루어져 있다. MemTable은 메모리 내 데이터 구조로, 일반적으로 균형 이진 탐색 트리(Balanced Binary Search Tree)로 구현되어 O(logN) 시간 복잡도(Time Complexity)를 보장한다. SSTable은 정렬된 문자열 테이블로, 디스크에 저장되는 불변의 데이터 파일이다. Compaction은 여러 SSTable을 병합하여 저장 공간을 최적화하고 읽기 성능을 향상시키는 역할을 한다.
B+ 트리(B+ Tree)와의 성능 비교
LSM 트리는 B+ 트리와 비교하여 쓰기 성능에 강점을 가진다. B+ 트리는 인덱스 업데이트 시 여러 번의 랜덤 블록 접근이 필요하지만, LSM 트리는 단일 접근만으로 가능하다. 이는 LSM 트리가 로그 구조(Log Structure)를 사용하여 데이터를 순차적으로 기록하기 때문이다. 하지만 읽기 성능은 Compaction 과정에서 여러 SSTable을 검색해야 하므로 B+ 트리보다 느릴 수 있다. 따라서 LSM 트리는 쓰기 중심(Write-Intensive) 워크로드에 적합하다.
레벨 기반 압축(Level-Based Compaction)과 공간 증폭
LSM 트리는 레벨 기반 압축 방식을 사용하여 저장 공간 효율성을 높인다. 각 레벨마다 데이터 압축이 트리거되는 임계값이 존재하며, 이 값은 레벨이 증가함에 따라 기하급수적으로 증가한다. 이러한 동적 임계값 설정은 공간 증폭(Space Amplification)을 가능하게 하여, 저장 공간 사용량을 효율적으로 관리한다. L0 레벨의 정렬되지 않은 파일(Unsorted Files)은 다른 레벨과 다른 방식으로 압축된다는 점에 유의해야 한다.
