How modern databases store and scan data fast

1 LSM trees — write-optimized storage

An LSM tree (Log-Structured Merge-tree) is a way of organising data on disk that is built to make writes extremely fast. The name has three parts: log-structured (new data is appended like a log, never overwritten in place), merge (sorted pieces get merged together over time), and tree (the merged pieces form layers, loosely like a tree of levels). It is the storage engine behind RocksDB, Cassandra, LevelDB, ScyllaDB, and many others.

The three moving parts

An LSM engine has three core components. Let's define each.

• MemTable — an in-memory, sorted structure (often a skip list or balanced tree) that absorbs all incoming writes. It's fast because RAM is fast and it stays sorted so it can be flushed in order.
• SSTable (Sorted String Table) — an immutable file on disk holding key→value pairs in sorted order. "Immutable" means once written it is never edited — only replaced by a later merge. This is the on-disk home of your data.
• Compaction — a background job that merges several SSTables into fewer, larger, still-sorted SSTables, throwing away stale/overwritten entries. This is the "tidy up later" step (covered in depth in Topic 4).

The write path, step by step

The magic is that every write is just an append: into the WAL (sequential disk write) and into the MemTable (in-memory). There is no hunting around the disk to find the exact spot to overwrite. Sequential writes are dramatically faster than random writes on both spinning disks and SSDs, which is why LSM engines shine at write-heavy workloads (logging, time-series, messaging, metrics).

The read path — and why it's harder

Reading is the trade-off. A key might live in the MemTable, or in any of several SSTables across several levels. A read must check them newest-first until it finds the key:

1. Check the MemTable (RAM — fast).
2. Check each SSTable, newest to oldest, until found.

To avoid touching every file, LSM engines use two tricks. A Bloom filter per SSTable — a tiny probabilistic structure that can say "this key is definitely not here" (so you skip the file entirely) or "maybe here." And a sparse index / block index that maps key ranges to file offsets so a lookup reads only one small block. Because each SSTable is sorted, a binary search inside the right block finishes the job.

# Writes arrive (each is just an append):
PUT user:42 = "Ann"      # goes to MemTable
PUT user:99 = "Bo"       # goes to MemTable
# MemTable fills up → flushed to disk as SSTable-1 (sorted):
SSTable-1 = { user:42 -> "Ann", user:99 -> "Bo" }

PUT user:42 = "Annie"    # NEW value, just appended to MemTable
DELETE user:99           # writes a tombstone, not an erase
# MemTable flushed again → SSTable-2 (newer):
SSTable-2 = { user:42 -> "Annie", user:99 -> <tombstone> }

# READ user:42  → check MemTable (miss), then SSTable-2 (newest)
#   → finds "Annie". Stops. Never even looks at SSTable-1.
# READ user:99  → SSTable-2 has a tombstone → returns "not found".

# Later, COMPACTION merges SSTable-1 + SSTable-2 into one:
SSTable-3 = { user:42 -> "Annie" }   # old "Ann" & the tombstone are dropped

LSM vs B+ tree — write-optimized vs read-optimized

Recall the B+ tree from our indexing session: a balanced tree kept sorted and updated in place. It's the classic engine behind PostgreSQL, MySQL/InnoDB, and most traditional databases. Here's the fundamental contrast:

2 Row vs columnar storage

How a database physically lays bytes on disk decides what it's good at. There are two layouts.

• Row storage (row-oriented) — all the columns of one row are stored together, then the next row, and so on. Great when you want whole records.
• Columnar storage (column-oriented) — all the values of one column are stored together, then the next column. Great when you want one column across many rows.

OLTP vs OLAP — two different jobs

This connects to two workload types you should know cold:

Why analytics scans favour columnar — the picture

Imagine a sales table with columns id, customer, region, amount and millions of rows. Here's how the two layouts store the same first three rows on disk:

# ROW layout — fields of a row are adjacent:
[ 1, "Ann", "EU", 50 ] [ 2, "Bo", "US", 80 ] [ 3, "Cy", "EU", 20 ] ...

# COLUMNAR layout — same field across rows is adjacent:
id:       [ 1, 2, 3, ... ]
customer: [ "Ann", "Bo", "Cy", ... ]
region:   [ "EU", "US", "EU", ... ]
amount:   [ 50, 80, 20, ... ]

Now run SELECT SUM(amount) FROM sales;. The database reads data off disk in fixed-size blocks. In the row layout, every block you read is stuffed with id, customer, and region bytes you don't care about — you drag the whole row in just to grab one number. In the columnar layout, the amount values sit packed together, so you read only that column and nothing else. On a billion-row table that's the difference between reading 4 columns' worth of bytes and reading 1 — often a 5–50× reduction in I/O.

Bonus 1: compression gets way better

When values of the same type and meaning sit next to each other, they compress spectacularly — far better than a jumble of mixed-type row data. Two classic schemes:

• Run-Length Encoding (RLE) — replace a run of repeated values with (value, count). A region column that's sorted into long stretches of "EU" becomes ("EU", 1_000_000) instead of a million copies.
• Dictionary encoding — build a small dictionary of distinct values and store cheap integer codes instead of the full values. Great for low-cardinality columns (few distinct values) like region, status, or country codes.

# Raw region column (lots of repetition):
["EU","EU","EU","US","US","EU","EU","EU","EU","ASIA"]

# Step 1 — Dictionary encoding (map strings → small ints):
dict   = { 0: "EU", 1: "US", 2: "ASIA" }
codes  = [0,0,0,1,1,0,0,0,0,2]      # tiny ints instead of strings

# Step 2 — Run-Length Encode the codes:
rle    = [(0,3), (1,2), (0,4), (2,1)]   # (value, run-length)

# 10 strings  →  4 little pairs. And a filter like
# WHERE region = 'EU' becomes "where code == 0" — integer compares, fast.

Bonus 2: vectorized execution

The second columnar superpower is how the data gets processed. Traditional row engines use the Volcano / tuple-at-a-time model: ask for one row, process it, ask for the next — one row through the whole pipeline at a time, with a function call per row. That's a lot of overhead per value.

Columnar engines instead use vectorized execution: process data in batches (vectors) of a few thousand values from one column at a time. One tight loop runs over a whole batch. This is cache-friendly, branch-predictor-friendly, and lets the CPU use SIMD (Single Instruction, Multiple Data — one CPU instruction adds many numbers at once). The overhead per row collapses.

3 DuckDB internals — the "SQLite for analytics"

DuckDB is an open-source analytical database often described as "SQLite for analytics." SQLite proved you don't always need a big client–server database — sometimes you want a fast database that just runs inside your application as a library. SQLite is row-oriented and aimed at transactional, embedded use. DuckDB takes the same embedded idea but builds it for analytics instead. Three design pillars define it:

Pillar 1 — In-process (embedded)

DuckDB runs in the same process as your application — there is no separate server to install, configure, start, or connect to over a network. You just import duckdb (or link the C++ library) and go. Because there's no client–server boundary, query results don't have to be serialised and shipped over a socket — DuckDB can hand data straight to your program's memory. For data scientists this is huge: it reads directly from Pandas/Polars DataFrames, Parquet, and CSV files with almost zero copying.

Pillar 2 — Columnar storage

From Topic 2, you already know why this matters: analytical queries scan a few columns over many rows, and columnar layout reads only those columns and compresses them well. DuckDB stores data column-by-column (and reads Parquet, itself a columnar file format, natively).

Pillar 3 — Vectorized execution

Also from Topic 2: DuckDB processes data in vectors (batches of ~1–2 thousand values) rather than one row at a time, keeping the CPU cache hot and enabling SIMD. This is what makes its big GROUP BY and aggregation queries fly on a single laptop.

import duckdb

# No server, no setup, no loading step — query a file in place:
result = duckdb.sql("""
    SELECT region, SUM(amount) AS revenue
    FROM 'sales.parquet'      -- read the columnar file directly
    WHERE year = 2025
    GROUP BY region
    ORDER BY revenue DESC
""")
result.show()

# It scans ONLY the region, amount, and year columns (columnar),
# skipping every other column in the file, and processes them in
# vectorized batches — all inside your Python process.

4 RocksDB & compaction

RocksDB is Facebook/Meta's high-performance embedded key-value store, built on the LSM tree from Topic 1 (it grew out of Google's LevelDB). It's a library embedded in your app — much like DuckDB is embedded, but RocksDB is a transactional key-value engine, not an analytics engine. It powers the storage layer of countless systems (Kafka Streams, CockroachDB, TiKV, MySQL's MyRocks, and more). The single most important thing to tune in an LSM engine is compaction, so let's go deep.

Why compaction exists

Every MemTable flush creates a new SSTable. Without cleanup you'd accumulate thousands of small, overlapping files — reads would have to check too many of them, and stale values/tombstones would waste space forever. Compaction merges SSTables into fewer, larger, sorted files and drops obsolete entries. The strategy for doing this is a fundamental trade-off.

Leveled compaction

Leveled compaction (LevelDB's and RocksDB's default) organises SSTables into levels L0, L1, L2, … Each level is roughly 10× larger than the one above. Crucially, within each level (from L1 down) the key ranges of SSTables do not overlap — each level is effectively one sorted run split into files. When a level gets too big, some of its data is merged down into the next level.

• Reads are good: below L0, a given key can be in at most one file per level, so a point lookup checks few files.
• Space is good: aggressive merging keeps duplicates/tombstones from piling up, so wasted space is low.
• Writes cost more: moving data down a level rewrites overlapping data repeatedly → higher write amplification.

Tiered compaction

Tiered compaction (also called size-tiered, the default in Cassandra) instead lets several SSTables of similar size accumulate in a tier, and only merges them once you have enough — producing one bigger file that joins the next tier. It rewrites data far less often.

• Writes are cheap: data is merged fewer times → low write amplification.
• Reads cost more: several overlapping files can hold the same key range, so a lookup may check more files → higher read amplification.
• Space costs more: multiple un-merged copies of overlapping data coexist → higher space amplification.

The three amplifications — the core trade-off

You cannot optimize all three at once; this is the famous RUM trade-off of LSM tuning. Define them precisely:

# LEVELED compaction (RocksDB default)
write_amp  = HIGH    # data rewritten as it cascades L0→L1→L2…
read_amp   = LOW     # ≤1 file per level below L0 for a key
space_amp  = LOW     # duplicates aggressively merged away
# → choose for READ-heavy & space-sensitive workloads

# TIERED (size-tiered) compaction (Cassandra default)
write_amp  = LOW     # data merged far fewer times
read_amp   = HIGH    # several overlapping files may hold the key
space_amp  = HIGH    # un-merged copies coexist
# → choose for WRITE-heavy / high-ingest workloads

Tuning knobs you'll actually meet

• Compaction style — leveled vs tiered (RocksDB calls the latter "universal"), the biggest lever, set by your read/write ratio.
• MemTable size & count — bigger MemTables = fewer, larger flushes = less compaction churn, at the cost of more RAM and longer recovery.
• Level size multiplier (default ~10) and L0 file trigger — control how aggressively data cascades down.
• Bloom filter bits per key — more bits = fewer wasted file reads (lower read amplification) for a little extra memory.
• Block size & compression (e.g. LZ4, Zstd per level) — trade CPU for disk I/O and space.

Comparison of engines

Pulling this session together, here's how the engines we've discussed line up:

★ Putting it all together

Every topic this session was really one lesson seen from different angles: the right data structure depends entirely on the workload. Here's the one-paragraph story tying it together:

Quick self-check

📚 References & Further Reading

Class material

• 📄 Original course notes / handout (source sheet) — open the shared class material for this session.
• 📘 Class handout: "DBMS Session 15 — Modern Architectures".

Papers, docs & deep dives

• CMU 15-445 Database Systems — the gold-standard course; its storage-models and modern-systems lectures cover row vs columnar, LSM trees, and vectorized execution in depth.
• The Design and Implementation of Modern Column-Oriented Database Systems (Abadi et al.) — the definitive survey of columnar storage, compression, and vectorized execution.
• DuckDB Documentation — official docs for the in-process analytical database; great for the DuckDB-vs-PostgreSQL assignment.
• RocksDB Wiki — the authoritative reference on LSM internals, compaction styles (leveled/universal), and tuning.
• The Log-Structured Merge-Tree (O'Neil et al., 1996) — the original LSM tree paper that started it all.
• Querying Parquet with Precision using DuckDB — official write-up showing column/row-group pushdown in action.