Storage Engines: LSM-Trees, B-Trees, and Column-Oriented Storage

The previous post chose the data model. This one drills to the very bottom: how does a database actually put data on disk, and get it back? DDIA opens the chapter with a two-line bash “world’s simplest database” — db_set appends a line to the end of a file, db_get greps the whole file and takes the last match. Writes are as fast as they get (sequential append); reads are hopelessly slow (an O(n) full scan). And the whole chapter — really every storage engine — answers the same question: to make reads a bit faster, how much organising cost are you willing to pay on writes? An index is the name of that trade-off — it spends extra work at write time to buy speed at read time; indexes aren’t free, and this chapter shows you exactly how the bill is paid.

Two schools: LSM tidies up later, B-trees update in place

Push the “how do you pay the organising fee” question all the way down and there are really only two schools of storage engine:

LSM-tree (log-structured): writes go first into an in-memory memtable; when it fills, the batch is flushed sequentially into an immutable SSTable file that is never modified again — old values are cleared by background compaction. Writes are always the sequential appends disks love, so they fly; the price is that reading one key may mean searching several levels from newest to oldest (a bloom filter lets you skip levels that don't have it). B-tree: data lives in a tree of fixed-size (say 4KB) pages; a write finds the page and overwrites it in place; a read walks three or four levels and it's there — fast and steady. The price is that in-place updates are random I/O, and to survive "crashed halfway through", every write first goes to a WAL. Same organising fee — LSM chooses to owe it and pay later (compaction), B-tree pays on the spot (random writes + WAL)

The trade-off compresses to one line: LSM treats the disk as a log — writes are extremely fast, but the organising debt has to be paid back slowly by compaction (which also amplifies the write volume); B-trees put each write in its place immediately, so the read path is short and stable — that’s been the skeleton of relational databases for decades. You’ve met both already: Redis’s AOF is a pure append log, a Kafka partition is an append-only log (sequential writes are the secret behind its “disk is king”), and behind every SQL you run, that index is very nearly a B-tree.

OLTP vs OLAP: same data, two layouts

The second big theme: when the shape of the read differs, even whether data should be laid across or down differs. Transactional (OLTP) reads and writes are “fetch a few complete records” — look up an order, edit a member; analytical (OLAP) is “scan hundreds of millions of rows but only two or three columns each” — daily revenue totals for last quarter. Serve both read shapes with one layout and one side is guaranteed to hurt:

Row-oriented lays all fields of one record contiguously — one order is one read, OLTP is blazing; but when analytics only wants the amount column, you're forced to scan every field of every row. Column-oriented flips it, laying values of the same column contiguously — scanning a billion rows reads only that one run, I/O drops an order of magnitude, and same-typed values sit next to each other, so compression is extreme (a run of repeated dates squashes to almost nothing). That's why the analytics world is all columnar: warehouses, and Parquet in the Spark ecosystem, all use this layout. The split between databases and data warehouses comes down to "different read shapes → you can only pick one layout"

So the everyday DE question “why can’t we just run analytics on the Production DB” is already answered at the storage layer: the DBA isn’t being stingy — a row layout is inherently unable to serve full-table-scan reads (and vice versa). Copying data out of OLTP into a columnar warehouse before analysing it — that’s the underlying reason layered data architectures and the entire data-engineering pipeline exist.

Reflections

”Append-only to please the disk” is a hidden thread through modern data systems

Only after this chapter did the scattered dots join up: LSM’s SSTables, the B-tree’s WAL, Redis’s AOF, Kafka’s partition log — all the same trick: sequential append. Disks (even SSDs) hate random writes and love sequential ones, so decades of storage design have all, at heart, been doing one thing: rewriting random write demand as a sequential log. Even the most “update-in-place” structure, the B-tree, doesn’t dare touch a page without an append-only WAL. Once you see that thread, your first question about any new storage system becomes: where does it turn random writes into sequential ones? Nearly every time there’s an answer — that’s the power of a good principle, one line stringing ten tools together.

Choosing an engine is choosing when to pay the organising fee

LSM vs B-tree has been argued for years over which is faster, but the cleanest understanding this chapter gave me is: both pay the same “organise for reads” fee; the only difference is when. B-trees pay on the spot (every write goes to its place: random I/O + WAL), so the read path is always short and stable; LSM runs a tab (writes just append) and leaves the organising debt to background compaction — lovely during write spikes, but the debt compounds (write amplification) and the compaction that repays it can fight the foreground for I/O. Neither is faster — one moves the cost to a moment you can better afford. I use this ruler everywhere now: write-heavy, read-light, can tolerate occasional read jitter → the LSM family (Cassandra, RocksDB); balanced, need stable query latency → the B-tree family (relational). When a selection argument breaks out, translate the question into “when do you want to pay the organising fee” and the argument usually ends.

The OLTP/OLAP split taught me: no single layout serves every read shape

The column-storage section explained the reason my profession exists, right down to the root. The same order data — the transactional system wants “one record at a time, the whole record”, analytics wants “a billion rows, two columns” — different read shapes mean different optimal physical layouts, and one copy of data can only have one layout at a time. So the data has to be copied out of OLTP, turned columnar, and fed to analytics — ETL, warehouses, Medallion, right through to Part III of DDIA on “derived data”, are all downstream consequences of this physical constraint. It also keeps me sober about “one system does OLTP + OLAP” marketing: not impossible, but underneath there’s necessarily some “two layouts, kept in sync” mechanism, and that sync is new complexity. Much of data engineering is, in essence, maintaining a “second layout” of the same data — see that, and you’ll know much better which physics problem your daily work is actually solving.