# LSM Trees and SSTables

## 1. A Different Trade-off: Optimize Writes, Not Reads

`02-b_tree/` covered the structure behind most relational-database indexes — a structure that updates itself **in place** on every write, which means every insert/update potentially touches random locations on disk. A **Log-Structured Merge-tree (LSM tree)** makes the opposite bet: never modify data in place, only ever append — turning random writes into sequential ones — and pay the cost back later, on reads and in the background. This is the structure behind write-heavy NoSQL and wide-column stores: Cassandra, RocksDB, LevelDB, and (as a storage engine option) InfluxDB and ScyllaDB.

## 2. The Memtable: Writes Land in Memory First

```
WRITE path:
  client write -> append to an in-memory sorted structure (the "memtable")
              -> (also appended to an on-disk write-ahead log, for crash safety)
```

Every write — insert, update, even delete (recorded as a special "tombstone" marker, not an in-place removal) — is first appended to an in-memory **memtable**, typically a balanced tree or skip list kept sorted by key. Because this is a pure append to memory, writes are extremely fast: no disk seek, no in-place page rewrite, no B-tree rebalancing.

## 3. Flushing to SSTables: Immutable, Sorted Files on Disk

```
memtable fills up ------> flushed to disk as a new SSTable (Sorted String Table)
                           (memtable is now empty again, ready for new writes)

Disk ends up with MANY SSTables, from successive flushes:
  SSTable_1 (oldest)   SSTable_2   SSTable_3   SSTable_4 (newest)
```

Once the memtable reaches a size threshold, it's flushed to disk as an **SSTable** — a file holding sorted key-value pairs, written once and never modified again (hence "immutable"). A fresh, empty memtable takes over for new writes. Over time this produces many SSTable files on disk, each representing a batch of writes from some point in the past.

## 4. Reads: Check the Memtable, Then Search SSTables (Newest First)

A read for a given key has to check the memtable first (the newest data, not yet flushed), then fall back to searching SSTables on disk, from newest to oldest, until it finds the key — since the same key can appear in multiple SSTables (a later write superseding an earlier one), the *first* match found (searching newest-first) is the current value. This is fundamentally more work than a B-tree's single-structure descent, and each SSTable's own internal index (often itself a small B-tree or a sparse index + Bloom filter) is what keeps that per-file search fast rather than a full file scan.

```
GET "user:42":
  1. check memtable -> not found
  2. check SSTable_4 (newest) -> not found
  3. check SSTable_3          -> FOUND, return this value, stop
     (an older value for "user:42" might still exist in SSTable_1 -- irrelevant, it's stale)
```

## 5. Compaction: Merging SSTables in the Background

Left unchecked, the number of SSTables would grow without bound, and every read would get slower as it had more files to check. A background process called **compaction** periodically merges multiple SSTables into fewer, larger ones — discarding superseded values (an old value hidden by a newer write to the same key) and physically removing tombstoned (deleted) keys once it's safe to do so. Compaction is what keeps read amplification bounded over the structure's lifetime; it's a continuous background cost, paid asynchronously, in exchange for the write path never having to do this work synchronously.

![Writes append to a WAL and land in an in-memory memtable that flushes to sorted SSTables, which compaction merges into larger levels; reads check memtable then SSTables newest first](diagrams/01-lsm-write-read-path.svg)

## 6. Write Amplification vs. Read Amplification vs. Space Amplification

| Factor | B-tree | LSM tree |
|---|---|---|
| **Write cost** | In-place update: read-modify-write a page, possible node split — random I/O | Pure sequential append to memtable/log — cheap, but the *same logical write* gets re-written again later during compaction (this re-write is "write amplification") |
| **Read cost** | Single descent through one structure | Potentially check memtable + several SSTables until a match is found ("read amplification") — mitigated by Bloom filters and compaction |
| **Space cost** | Roughly proportional to live data | Stale/superseded values and tombstones linger until compaction reclaims them ("space amplification") |

Neither structure wins on all three axes simultaneously — this is a fundamental trade-off, not an implementation detail one engine got wrong. LSM trees deliberately shift cost away from the write path (fast, sequential) onto the read path and a background process (compaction), which is exactly backwards from a B-tree's in-place-update, single-structure-read design.

## 7. When LSM Beats B-tree

Write-heavy workloads with high ingest rates (time-series data, event logs, metrics, IoT sensor streams) are where LSM trees shine — turning what would be constant random-I/O B-tree page rewrites into sequential appends is a large, measurable win at high write volume. Read-heavy or read-latency-sensitive workloads, or workloads needing strong range-query performance with minimal per-read overhead, tend to still favor B-trees — which is exactly why relational databases (PostgreSQL, MySQL's InnoDB) default to B-tree indexes, and why the systems that pick LSM trees (Cassandra, RocksDB) are typically built for ingest-heavy use cases from the start.

## 8. Common Pitfalls

1. **Assuming LSM trees are "just generally faster" than B-trees** — they trade write speed for read complexity; a read-heavy workload with modest write volume is usually *worse* off on an LSM-backed store.
2. **Forgetting that deletes are tombstones, not immediate removal** — a deleted key's old value(s) physically remain on disk, taking up space and potentially slowing reads, until compaction actually removes them.
3. **Not accounting for compaction as a real, ongoing resource cost** — compaction consumes CPU and I/O in the background; under-provisioning for it is a common cause of an LSM-backed store's performance degrading under sustained high write load.
4. **Expecting range queries to be as cheap as on a B-tree** — a range scan on an LSM tree may need to merge results across the memtable and multiple SSTables in sorted order, more work than a single B-tree's linked-leaf traversal (`02-b_tree/` section 4).

## 9. Quick Reference

```
LSM tree: writes -> memtable (in-memory, sorted) -> flushed to immutable SSTables on disk
Read: check memtable, then SSTables newest-to-oldest, until a match is found
Compaction: background merge of SSTables -> bounds read amplification & reclaims space
Delete = tombstone marker, not in-place removal -- reclaimed later by compaction

B-tree:  optimizes READS (single structure, in-place updates)   -- relational DB default
LSM tree: optimizes WRITES (sequential append, deferred merge)  -- Cassandra, RocksDB, LevelDB

Trade-off axes: write amplification vs read amplification vs space amplification
  -- no structure wins all three; pick based on the workload's write:read ratio
```