이번 포스팅에서는 Patric O'Neil의 "The Log-Structured Merge-Tree" 논문을 읽고 LSM Tree가 등장한 이유, 특징, 그리고 동작 원리에 대해 살펴보겠습니다. Abstract 해당 논문이 발표된 시기에는 "activity flow management system application"의 수요가 증가하고 있었습니다. 이 시스템은 일련의 활동을 관리하고 최적화하기 위해 사용되며 대표적인 기능으로는 task tracking, workflow automation 가 있습니다. 이러한 시스템은 애플리케이션 레벨에서 히스토리성 데이터를 저장하는 동시에 데이터베이스에서 시스템 복구를 위해 해당 데이터가 저장되는 시점에 로그성 데이터를 추가로 저장합니다(Write ahead log)..

이번 챕터에서는 데이터베이스에 저장되는 데이터의 형태와 저장 방식에 따른 장단점에 대해 살펴보겠습니다. 데이터베이스는 데이터를 효율적으로 저장하고 찾기 위해 인덱스를 활용합니다. 이러한 인덱스를 저장하는 방식을 크게 분류하면 log-structured 형태와 page-oriented 형태의 저장방식으로 구분됩니다. Log Structured Indexes Hash Table 가장 기초적인 데이터 저장 및 조회 방법으로는 해시 테이블을 사용할 수 있습니다. 이 방법은 Key-value 형태의 데이터를 메모리 상에 유지하면서 주기적으로 디스크로 플러시합니다. 데이터는 append 형식으로 디스크 파일 끝에 추가됩니다. 디스크에 저장된 데이터는 segment 단위로 구분하며, 더 이상 쓰기 작업이 없는 seg..