B+Tree와 LSM-Tree는 데이터베이스 인덱스의 변경을 디스크에 반영하는 방식이 다릅니다. B-tree 계열은 인덱스 변경을 기존 구조에 반영하는 대표적인 비교 대상이고, LSM-Tree는 변경을 메모리 구성요소에 모은 뒤 하나 이상의 디스크 구성요소로 단계적으로 병합합니다. 따라서 어느 쪽이 항상 빠르다고 볼 수 없으며, 삽입·삭제와 조회의 비율, 즉시 응답 요구, 병합 작업의 비용을 함께 판단해야 합니다.

B+Tree의 페이지 인덱스와 LSM-Tree의 메모리·디스크 구성요소 병합을 비교한 개념 이미지

원 논문이 제시한 선택 기준

Patrick O’Neil, Edward Cheng, Dieter Gawlick, Elizabeth O’Neil의 논문은 이 구조를 고속으로 증가하는 이력 테이블의 인덱싱 문제에서 설명합니다. 논문 초록은 B-tree 같은 전통적 디스크 인덱스를 실시간 유지할 때 삽입마다 발생하는 I/O 비용을 문제로 제시하고, LSM-Tree는 인덱스 변경을 지연하고 묶어 메모리 구성요소에서 디스크 구성요소로 전달한다고 설명합니다. 이 방식의 목적은 높은 삽입·삭제량에서 디스크 탐색 비용을 줄이는 것입니다.

그 설명은 쓰기 경로가 공짜라는 뜻은 아닙니다. LSM-Tree는 새 항목을 먼저 작은 메모리 상주 구성요소에 넣고, 그 내용을 더 큰 디스크 구성요소와 병합합니다. 논문은 병합 중에도 검색 가능한 인덱스 값을 구성요소 중 하나에서 찾을 수 있다고 설명하지만, 즉시 결과를 요구하는 일부 인덱스 조회는 I/O 효율을 잃을 수 있다고 명시합니다. 그러므로 “항상 빠른 쓰기”나 “조회 지연이 없다”로 요약해서는 안 됩니다.

변경을 모으는 LSM-Tree와 비교 대상인 B-tree

LSM-Tree의 핵심은 특정 제품의 고정된 파일 배치가 아니라 변경을 단계적으로 반영하는 원리입니다. 원 논문의 2구성요소 설명에서 새 이력 행의 인덱스 항목은 메모리 구성요소에 들어가고, 이후 디스크 구성요소로 옮겨집니다. 검색은 메모리와 디스크 구성요소를 확인할 수 있습니다. 논문은 구성요소 간 병합이 정렬 병합을 닮은 방식으로 진행된다고 설명하며, 한 번의 변경을 즉시 최종 디스크 위치에 쓰는 대신 이동을 늦추고 묶는 설계를 다룹니다.

B-tree는 논문에서 이력 인덱스의 전통적 대안으로 등장합니다. 논문은 특정 벤치마크 조건에서 무작위 키 삽입을 유지하는 B-tree 인덱스의 읽기·쓰기 I/O 부담을 계산하고 이를 LSM 접근법의 동기로 삼습니다. 이 계산을 오늘날 모든 B-tree 구현, 장치, 캐시, 데이터 분포에 그대로 적용할 수는 없습니다. 또한 자료는 모든 B-tree의 페이지 크기나 고정된 트리 높이, 업데이트 때마다 반드시 전체 페이지를 다시 쓰는 동작을 보편 규칙으로 정하지 않습니다. 제품별 엔진이 제공하는 구현 문서와 실제 측정치가 필요합니다.

RocksDB 문서가 보여 주는 compaction의 절충

RocksDB의 “Leveled Compaction” 문서는 LSM 계열 설계에서 읽기와 쓰기 비용이 어떻게 맞바뀔 수 있는지 구체적인 사례를 제공합니다. 문서는 L0 파일이 너무 많으면 여러 질의의 읽기 성능을 해칠 수 있다고 설명합니다. RocksDB는 일부 L0 파일을 더 큰 파일로 compaction할 수 있으며, 문서의 설명대로라면 이 선택은 L0 읽기 증폭을 줄일 수 있는 대신 추가 쓰기 증폭을 발생시킵니다. 해당 페이지는 이 추가 비용과 일반적인 leveled compaction의 비용도 구분해 설명합니다.

이것은 모든 LSM 구현에 그대로 적용되는 수치나 운영 보장이 아니라 RocksDB 문서의 정책과 설명입니다. 여기서 도출할 수 있는 실무적 결론은 “compaction을 켜면 읽기가 무조건 빨라진다”가 아닙니다. 읽기 경로의 파일 수를 줄이는 작업은 쓰기와 백그라운드 I/O를 사용하므로, 지연 시간과 쓰기 여유를 함께 살펴야 합니다. 문서가 소개하는 L0 병합 옵션을 검토할 때도 사용하는 RocksDB 버전, 설정, 부하에서 실제 효과를 확인해야 합니다.

전문가 관점: 워크로드로 선택을 검증하기

원 논문 저자들이 제시한 핵심 적용 조건은 조회보다 인덱스 삽입이 더 흔한 이력 테이블과 로그 같은 환경입니다. 이를 현재 시스템에 적용할 때는 이름만으로 구조를 선택하지 말고 실제 키 분포와 연산 비율을 기록하세요. 삽입·삭제량이 높고 조회가 상대적으로 드문지, 즉시 결과를 요구하는 점 조회가 중요한지, 범위 조회가 어느 정도인지 확인하면 논문의 조건과 자신의 부하가 얼마나 가까운지 판단할 수 있습니다.

그 다음에는 후보 엔진에서 같은 데이터와 보존 기간을 사용해 쓰기 처리량, 점 조회 및 범위 조회 지연, 저장 공간, 병합 중 백그라운드 I/O를 측정합니다. LSM 계열이라면 compaction이 실행될 때의 지연 분포와 쓰기 증폭도 살펴야 합니다. B-tree 계열이라면 인덱스 유지 비용과 페이지 캐시가 실제 장치 I/O에 미치는 영향을 함께 측정해야 합니다. 이 항목들은 측정 계획이지, 두 출처가 모든 제품에서 같은 결과를 보장한다는 주장이 아닙니다.

자료의 한계도 선택에 반영해야 합니다. LSM 논문은 1990년대의 디스크 비용과 특정 이력 테이블 모델을 분석한 원고이며 PDF에는 “To be published”라고 표시되어 있어 이 사본만으로 발행일을 단정하지 않았습니다. RocksDB 페이지 역시 특정 구현의 leveled compaction 설명입니다. 따라서 논문의 비용 계산을 최신 SSD나 다른 엔진의 성능 수치로 인용하지 말고, 원리와 가설을 세우는 근거로 사용한 뒤 현재 환경에서 검증하는 편이 타당합니다.

참고 자료