---
title: "The Log-Structured Merge-Tree (LSM-Tree)"
description: "How can a database keep scattered incoming records searchable without paying for a separate disk-page update on every insert? The original LSM-tree batches sorted entries in memory and rolls them into larger disk trees. Read it to understand the merge, its amortized cost, and the read and recovery obligations that remain."
canonical_url: "https://fanout.sh/daily/2026-10-03-log-structured-merge-tree"
md_url: "https://fanout.sh/daily/2026-10-03-log-structured-merge-tree.md"
last_updated: "2026-10-03"
access: "public"
---

# The Log-Structured Merge-Tree (LSM-Tree)

How can a database keep scattered incoming records searchable without paying for a separate disk-page update on every insert? The original LSM-tree batches sorted entries in memory and rolls them into larger disk trees. Read it to understand the merge, its amortized cost, and the read and recovery obligations that remain.

## Paper details

- Authors: Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil

- Venue: Acta Informatica 1996

- Track: Systems

- Difficulty: Easy

- Reading time: 32 min

- Original paper: https://doi.org/10.1007/s002360050048

## What you will learn

- How a separately searchable memory component postpones disk placement without hiding recent entries.

- How a rolling merge shares page-transfer work across new entries, and why a small memory buffer can erase the advantage.

- Why component searches, deletion markers, recovery, and historical cost assumptions limit a simple faster-writes claim.

## Continue exploring

[Follow a modern LSM storage engine](https://fanout.sh/system/archive/lsm-tree-storage-engine): Connect the original rolling merge to memory tables, sorted files, version resolution, and compaction.

---
This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included.

Browse the public content map: https://fanout.sh/sitemap.md