How Databases Store Data: Pages, the Log, B-Trees and LSM-Trees

Pages, write-ahead logs, B-trees and LSM-trees, with write, read and space amplification measured on a page store and a miniature LSM, and PostgreSQL 18 measured on page layout, HOT updates, bloat and WAL bytes.

Underneath every database is a program that turns rows into bytes on a disk and finds them again. It has two classic shapes, the B-tree and the LSM-tree, and both are answers to the same physical fact: storage moves in blocks, and a write that lands in the wrong place costs far more than one that lands in the right one.

This part measures the trade-off rather than describing it. We build a miniature LSM and a page-based store, run the same workload through both, and count the bytes each writes, the files each reads and the space each wastes. Then we measure the real thing: PostgreSQL 18 in a container, on page layout, heap-only updates, bloat and write-ahead log volume.

Try this first

You have a table of 20,000 small rows, about 900 kB on disk. You update every row, ten times over: 200,000 updates, and not one new row.

How many bytes does the database write to disk? And how big is the table when you finish? Write down a multiple of the starting size for each.

Pages: the unit that decides everything

A database doesn’t read rows, it reads pages. Bayer and McCreight’s B-tree paper defines the page before it defines the tree. Their index is organised in fixed-size pages, each holding up to a set number of keys and needing only to be partly filled, and those pages are “the blocks of information transferred between main store and backup store”. (We are reading an optical scan of the 1970 Boeing report, so that is a paraphrase around one quoted phrase, not a transcription.)

That constraint hasn’t moved in fifty-six years. PostgreSQL’s page is 8 kB, and everything else follows from it: how many rows fit, what an update costs, and why a big value is stored somewhere else.

Our lab asks PostgreSQL what’s actually in a page:

PostgreSQL 18.6, block size 8192 bytes
table of 20,000 rows (id int, tag text, counter int)
tuples in page 0:            185
tuple size, smallest:        40 bytes
tuple size, largest:         40 bytes
heap:                        109 pages, so 892,928 bytes
on disk (pg_table_size):     933,888 bytes, heap plus its maps

Those tuples are 40 bytes each, and 185 of them fit in 8,192 bytes, leaving room for the page header, the line pointers and a little free space. Note the two sizes: relpages counts the heap, and pg_table_size adds the free-space and visibility maps that PostgreSQL keeps beside it. Neither includes the indexes, which is what pg_total_relation_size is for, and which is why “how big is this table” is three questions. A row that doesn’t fit in a page is a problem, so PostgreSQL doesn’t allow one. TOAST is triggered, in the manual’s words, “only when a row value to be stored in a table is wider than TOAST_TUPLE_THRESHOLD bytes (normally 2 kB)”, and then, in the same page’s words, it will “compress and/or move field values out-of-line until the row value is shorter than TOAST_TUPLE_TARGET bytes (also normally 2 kB, adjustable) or no more gains can be had”. Note that the threshold is on the whole row: three 800-byte columns will TOAST although no single value is close to 2 kB.

The famous B-tree property, that pages are at least half full, is the paper’s own floor, not a typical value: “Storage utilization is at least 50% but generally much higher.”

Fill factor is a different number, and the two get conflated constantly. Occupancy is a floor the tree guarantees after a split; fill factor is a ceiling asked for when pages are filled, so that there is room left over. They also mean different things on either side of the table. On the heap, fill factor is what leaves room for an updated row to stay in its own page, and it defaults to 100. On a B-tree index, it applies to an initial index build and to pages added at the right-hand end, defaults to 90, and has nothing to do with updates, because index entries are never updated in place.

And PostgreSQL’s B-tree has no floor at all. It never merges two half-empty pages back together, which is why an index that has had a lot deleted from it stays big until it is rebuilt.

The write-ahead log: one sequential write instead of many random ones

If a crash can happen between two page writes, a database that writes pages in place can be left with half an update. The answer, in every engine here, is to write the change to a log first, sequentially, and only then update the pages.

PostgreSQL’s manual is blunt about why this is faster and not just safer: the log turns many random writes into one sequential one, so only the log has to be flushed to disk at commit time.

Two things people get wrong about the log:

It’s bigger than you think, because it contains whole pages. With full_page_writes on, which is the default, the first change to a page after each checkpoint copies the entire 8 kB page into the WAL. That’s the defence against a torn page, where the operating system writes half a block. Our lab measures the effect: the same update batch costs more WAL right after a checkpoint than it does later.

20,000 rows updated (id primary key), full_page_writes = on
WAL for the batch straight after a CHECKPOINT: 5,916,896 bytes
WAL for the same batch with no checkpoint:    4,528,208 bytes
ratio:                                        1.31x
(for scale, inserting 20,000 fresh rows:      2,795,960 bytes)

The insert is there for scale and not as a fair comparison: it goes into a brand-new table, so almost nothing it touches is a page being changed for the first time since a checkpoint, and it writes few full-page images.

Durability is a dial, not a switch. LevelDB’s documentation states the extreme case: “By default, each write to leveldb is asynchronous: it returns after pushing the write from the process into the operating system”, and “Asynchronous writes are often more than a thousand times as fast as synchronous writes.” A default RocksDB or LevelDB write survives your process crashing and not the machine losing power. A default PostgreSQL commit survives both.

SQLite splits the same question in three: corruption, durability of the last transaction, and durability across a process crash. In WAL mode with synchronous=NORMAL it is “safe from corruption” but “does lose durability”, while “Transactions are durable across application crashes regardless of the synchronous setting”.

And one uncomfortable fact from the same documentation: the disk may lie. SQLite’s atomic commit document says that “often the IDE disk control lies and says that data has reached oxide while it is still held only in the volatile control cache.”

That has bitten the databases themselves. In 2018 PostgreSQL discovered that its assumption about fsync was wrong: after a failed fsync, the kernel could report success on the next call while the data was gone. The fix, backpatched, was to stop trying to recover: PostgreSQL now panics and replays from the log instead.

B-tree or LSM: the same data, two shapes

A B-tree keeps its pages in sorted order and updates them in place. A read follows a few pointers to one page. A write eventually rewrites that page, wherever it sits on disk.

An LSM-tree never updates in place. Writes land in a memtable, which is flushed as a sorted run, and background compaction merges runs. A read may have to look in several runs.

Here is the whole LSM cycle, which is three moves and no fourth:

The LSM-tree paper, by O’Neil, Cheng, Gawlick and O’Neil, is worth reading for what it doesn’t say. It frames the design as an insert-optimised index, it expected that “three components are probably the most that will be seen in practice”, and it has no Bloom filters: the word appears once in the whole paper, describing somebody else’s design in the related work. LevelDB shipped seven levels at a size ratio of ten, and Bloom filters arrived with that generation. The theorem survived, which is that equal ratios between components minimise merge I/O; the constants didn’t.

The three amplifications

RocksDB defines them with unambiguous wording. Write amplification “is the ratio of bytes written to storage versus bytes written to the database”. Read amplification is the number of disk reads per query, and space amplification is the ratio of storage used to the data’s real size.

Our lab measures all three on one workload: 200,000 writes over 20,000 distinct keys, into a page store that flushes its dirty pages at checkpoints, and into a small LSM.

	Bytes written	Write amplification	Space amplification
Page store, 8 kB pages, checkpoint every 1,000 writes	94,789,632	18.23×	1.01×
LSM, 2,000-row memtable, size-tiered, fanout 4	11,638,354	2.24×	3.04×

The user wrote 5,200,000 bytes in all: 200,000 writes of 26 bytes each. Only 520,000 bytes of that is live data, because the 200,000 writes land on 20,000 distinct keys. Write amplification compares what each engine wrote to the first number; space amplification compares what it left on disk to the second. The page store ended at 524,288 bytes (64 pages) and the LSM at 1,582,412 bytes across 7 runs, after 29 compactions.

Read that table before repeating “LSM is write-optimised, B-tree is read-optimised”, because the interesting part is the third column. The LSM wrote far less and kept about three copies of the data waiting for compaction; the page store wrote far more and kept almost exactly one.

Three things this lab is not, before you carry its numbers anywhere. The page store is a flat array of pages, not a B-tree: no splits, no key order, no page header, and a free in-memory index. So its 1.01× is a floor no real engine reaches — and the LSM’s 2.24× is a floor too, since its runs count only keys and values, not the Bloom filter and index blocks a real SST file carries — the PostgreSQL heap measured earlier is already at 8,192 bytes per 7,400 of rows before a single update. And neither engine writes a log. A minimal record-per-write log would add about another 1× of the user’s bytes here; a real one costs much more, as the WAL section above measured — 4.5 MB for one pass of 20,000 rows whose changed column is 80,000 bytes. And a point lookup here is one page against 0.96 runs, which flatters the LSM twice over. 8.4% of our lookups are answered by the memtable without opening a run at all, and the Bloom filters turn away most of the rest before one is opened: 51,659 rejections against 19,234 runs actually searched. A real B-tree, meanwhile, reads the pages on the way down the tree as well as the leaf.

The number you are really measuring

That 18.23× is not a fact about page stores. It is a fact about checkpointing every 1,000 writes. The same rows, with the pages flushed more or less often:

checkpoint every    bytes written   write amplification
         100        751,337,472               144.49x
       1,000         94,789,632                18.23x
      10,000          9,699,328                 1.87x
     100,000          1,048,576                 0.20x

That is a factor of more than 700 from one setting, and it is the same trade a real database makes with checkpoint_timeout: flush often and write more, flush rarely and lose more time to replay after a crash.

The bottom row lands under 1× because a page touched a thousand times between checkpoints is still written once, and with 200,000 writes over 20,000 keys most of them are overwrites that never reach disk. Don’t take that home: it is under 1× only because this store writes no log. A real engine writes every change to its WAL whatever the checkpoint interval, so its total write amplification has a floor of about 1× that no amount of batching goes below.

Whenever you meet an amplification number, ask which knob it is measuring.

RocksDB’s own wiki refuses the simple version too. Classic leveled compaction, the one from the paper, “minimizes space amplification at the cost of read and write amplification”, with leveled write amplification “often larger than 10”. Tiered compaction is the one that minimises writes, and it pays in reads and space. An LSM gives you a dial. A B-tree doesn’t offer one.

A naming trap while we’re here: RocksDB’s option called “Level” is Tiered+Leveled, and the one called “Universal” is tiered. The API names and the literature’s names don’t line up.

What a Bloom filter is worth

An LSM read has to check every run that might hold the key, which is why a miss is the expensive case. A Bloom filter per run turns most of those checks into arithmetic.

20,000 lookups for keys that were never written, against 7 runs
runs searched, no filter:    140,000
runs searched, 10 bits/key:    2,617
runs rejected by the filter: 137,383

That’s read amplification collapsing on misses, and it’s why Bloom filters are in every shipping LSM despite not being in the paper.

Three caveats. RocksDB states the first flatly: “Bloom filters are not useful for range scans, so the read amplification is number_of_level0_files + number_of_non_empty_levels.” A range has no single key to test. The second is that the false-positive rate is an implementation property and not just a formula: RocksDB’s original full filter “could not get an FP rate better than about 0.1%, even at 100 bits/key”. The third is that the Bloom filter is no longer the only choice. RocksDB ships a Ribbon filter, where NewRibbonFilterPolicy(9.9) “has the same 1% FP rate as Bloom but only uses around 7 bits per key”, trading CPU for memory.

What updates really cost: PostgreSQL measured

PostgreSQL never overwrites a row. An update writes a new version and leaves the old one for VACUUM, which is the design the manual states plainly: an update “does not immediately remove the old version of the row”, and the space “must then be reclaimed for reuse by new rows”.

There’s an optimisation that avoids most of the cost, and it depends on the page. A heap-only tuple update writes the new version into the same page and skips the index entirely. The conditions, from the documentation: “The update does not modify any columns referenced by the table’s indexes, not including summarizing indexes” and “There is sufficient free space on the page containing the old row for the updated row”. The exception in the first one is why a BRIN index over a column doesn’t stop that column’s updates being heap-only.

That second condition is what fill factor is for. Our lab runs ten rounds of updating every row, three ways:

Table	Updates	Heap-only	Share	Table grew	With its indexes
Fill factor 100, updating an unindexed column	200,000	1,033	0.5%	10.43×	7.93×
Fill factor 90, updating an unindexed column	200,000	85,859	42.9%	6.47×	5.07×
Fill factor 90, updating an indexed column	200,000	0	0.0%	6.96×	6.25×

Three lessons in one table. Leaving no free space in the page (fill factor 100) means almost no update can stay on its page. Leaving 10% free lets a large share of them stay. And indexing the column you update takes the optimisation away completely.

The last column is there because the table is not the whole bill. A non-HOT update writes an index entry for every index on the table, and those bytes sit outside pg_table_size. In the first two rows, where only the primary key is indexed, the indexes are 7.6% and 9.3% of the bytes added. In the third, where the updated column is indexed too, they are 29.5%. (The first two are as small as they are because PostgreSQL’s B-tree deduplicates repeated keys into posting lists, so 199,000 new entries for the same 20,000 ids cost about four and a half bytes each rather than twenty.)

A caution on the growth columns themselves: the fill-factor-90 tables start 9.6% larger by construction, so their ratios are measured against a bigger starting size. The heap-only share is the clean comparison, and it carries the lesson on its own.

Bloat, and what VACUUM gives back

Old row versions accumulate, and that’s where a table’s real size comes from:

20,000 rows, autovacuum off, fill factor 100
every round updates one fixed-width column, so no row ever gets longer
at the start:                       933,888 bytes
after 10 rounds of updates:       9,740,288 bytes   (10.43x)
after VACUUM:                     9,740,288 bytes   (unchanged)
after 10 more rounds of updates:  9,740,288 bytes   (still unchanged)
after VACUUM FULL:                  901,120 bytes

That answers the question this part opened with. Two hundred thousand updates to 20,000 rows, not one new row, and the table is ten times its starting size; the write-ahead log for those ten rounds is another 45 MB or so on top, at the 4.5 MB a round the WAL section measured.

Now note which numbers don’t move. VACUUM marks the dead space reusable and the file stays the same size: the manual says it “will not return the space to the operating system”, “except in the special case where one or more pages at the end of a table become entirely free and an exclusive table lock can be easily obtained”. A later update reuses that space instead of growing the file. Only VACUUM FULL, which rewrites the whole table and takes an exclusive lock, gives the disk back.

That’s PostgreSQL’s space amplification, and the manual frames it as intentional: “the idea is not to keep tables at their minimum size, but to maintain steady-state usage of disk space”.

The third line is the one worth staring at. Ten more rounds of updates, 200,000 more row versions, and the file did not grow by a byte: they went into the space VACUUM had marked reusable. That is the steady state the manual is describing, reached.

(Our lab turns autovacuum off to make the first ten rounds visible in seconds. With it on, a table that churns like this settles instead of growing tenfold first.)

Explain it like I’m ten

Two ways to keep a diary.

• The tidy way: one book, entries in alphabetical order by whatever you look things up by, and you rub out and rewrite whenever something changes. Finding an entry is quick, because everything is in its place. Changing one word means finding the page, rubbing out, rewriting.
• The fast way: a fresh sticky note for every change, stuck on top of the pile. Writing is instant. Finding something means checking the newest notes first, then older ones. Every so often you tidy the pile into a new book, which takes a while, and until you do, the same fact exists on several notes.

The tidy way is a B-tree. The sticky notes are an LSM.

The precise version

• Rubbing out and rewriting a page is update in place, and the whole page is rewritten even for one word: that’s write amplification.
• Checking several notes for one fact is read amplification, and the Bloom filter is a label you hold a word up against: the note either definitely doesn’t have it, or might.
• Several copies of the same fact until you tidy up is space amplification, and tidying is compaction (or VACUUM).
• Where the analogy breaks: a real database also writes a log before touching anything, so that a fire halfway through tidying doesn’t lose the diary.

Across the engines

	PostgreSQL 18	InnoDB	RocksDB / LevelDB	SQLite
Shape	B-tree (Lehman & Yao), heap tables	clustered B-tree	LSM-tree	B-tree
Page or block	8 kB	16 kB	SST data blocks, configurable	4 kB default
Update	new row version, old one vacuumed	update in place	new entry, compaction later	update in place
Torn-page defence	full page images in the WAL	doublewrite buffer	SST files are immutable once written	journal or WAL
Durability default	commit is durable	tunable, durable by default	write is not power-cut durable by default	durable, tunable
Reclaiming space	VACUUM marks reusable; VACUUM FULL rewrites	purged in the background	compaction	VACUUM

Trade-offs

• Read, update, memory: you only get to pick two. The RUM paper’s framing is that optimising two of those three overheads costs you the third, and read, write and space amplification are how you measure them. It’s explicitly a conjecture in a “visionary paper”, and its own table concludes “there is no single winner”.
• Write-heavy and space-constrained pull in opposite directions. Tiered compaction writes least and wastes most; leveled wastes least and writes most. Choose by which resource is scarce.
• Random reads favour a B-tree; sequential ingest favours an LSM. A point lookup in a B-tree is a fixed, small number of page reads. An LSM’s cost depends on how far behind compaction is.
• Bloom filters help misses, not ranges. If your workload scans ranges, budget for the runs.
• Fill factor trades space for update cost, and our measurements show how sharply: the same ten rounds of updates were 0.5% heap-only at fill factor 100 and 42.9% at 90. (We measured the heap’s fill factor, which is the one that decides HOT; an index has its own.)
• Durability defaults differ by orders of magnitude in speed. LevelDB puts its own async-versus-sync gap at “more than a thousand times”. Know which setting you have before comparing two databases’ write throughput.

Common mistakes

• Quoting “LSM is write-optimised” without the compaction bill. The writes you avoid at insert time come back during compaction.
• Comparing benchmarks with different durability settings. An async LevelDB write against a synchronous PostgreSQL commit is not a comparison.
• Indexing the column you update most. It removes heap-only updates, as our lab shows: 42.9% of updates stayed on their page without the index, and none with it.
• Treating bloat as a bug. It’s the documented design of MVCC. Monitor it, vacuum it, and leave fill factor room on tables you update.
• Reaching for VACUUM FULL routinely. It rewrites the table under an exclusive lock, and the manual prefers “moderately-frequent standard VACUUM runs”.
• Assuming fsync means what you think. It didn’t, for years, on Linux. That’s why PostgreSQL panics rather than retrying.
• Storing big blobs in rows. Once the row passes about 2 kB PostgreSQL moves the widest fields out of line anyway; you may as well decide where they go yourself.
• Believing “Postgres has no buffer pool”. It has shared_buffers and relies on the operating system cache, and the manual admits “some data might exist in both places”.

Interview questions

Try to answer each one before opening the model answer.

1. Explain the difference between a B-tree and an LSM-tree.

Show a strong answer

• B-tree: sorted pages updated in place, a read is a small fixed number of page reads, a write eventually rewrites a page. In an engine that really updates in place, space amplification stays near 1; under MVCC it doesn’t, as the PostgreSQL half of this part measures.
• LSM-tree: writes go to a memtable, flush as sorted runs, and compaction merges them. Writes are sequential and cheap; reads may touch several runs; space holds several versions until compaction catches up.
• Measured on one workload: our page store wrote 18 times the user bytes with 1.01× space; the LSM wrote 2.2 times with 3.04× space. Say what the numbers depend on, though: the page store’s figure is mostly its checkpoint interval, which moved it from 144× to 0.2× across the sweep.
• The dial: an LSM’s compaction strategy chooses which amplification to pay. Tiered minimises writes, leveled minimises space.
• Reads: Bloom filters make misses cheap but do nothing for range scans.

Likely follow-up: “Which would you choose for a write-heavy log?” An LSM, with tiered compaction and enough disk for the space amplification, or a plain append-only file if you never update.

2. What is a write-ahead log for, and why is it faster as well as safer?

Show a strong answer

• Safety: the change is durable in the log before the pages change, so a crash mid-update can be replayed or rolled back.
• Speed: one sequential write and one flush replace many random page writes at commit time. The pages can be written later, in batches.
• Cost: the log is extra bytes. In PostgreSQL the first change to a page after each checkpoint writes the whole 8 kB page into the WAL, to survive torn pages.
• Measured: the same update batch cost noticeably more WAL immediately after a checkpoint than it did later.
• Alternatives: InnoDB solves the torn-page problem with a doublewrite buffer instead, which it argues isn’t twice the I/O because it’s sequential and one fsync.

Likely follow-up: “What’s checkpointing?” Flushing dirty pages so the log before that point is no longer needed. It bounds recovery time and lets the log be recycled.

3. Why does an update in PostgreSQL make the table grow?

Show a strong answer

• MVCC: an update writes a new row version; the old one stays visible to older transactions until VACUUM reclaims it.
• HOT updates avoid part of the cost: if no indexed column changed and the page has room, the new version goes in the same page and no index entry is written.
• Fill factor is how you leave that room. Our lab: 0.5% heap-only updates at fill factor 100, 42.9% at 90, and 0% when the updated column was indexed.
• VACUUM reclaims for reuse, not for the filesystem. The file stays the same size and new rows fill the gaps.
• Steady state, not minimum size: the manual’s own framing of the goal.

Likely follow-up: “When would you use VACUUM FULL?” Rarely: after a one-off bulk delete, accepting an exclusive lock, because it rewrites the table.

4. What do write, read and space amplification mean, and how do you reduce each?

Show a strong answer

• Write: bytes written to storage per byte written by the user. Reduce with bigger memtables, tiered compaction, and, in PostgreSQL, a longer checkpoint interval or wal_compression rather than turning full-page writes off.
• Read: disk reads per query. Reduce with Bloom filters, fewer runs (more aggressive compaction), bigger caches, and covering indexes.
• Space: bytes on disk per byte of live data. Reduce with leveled compaction, compression, and vacuuming.
• They fight: the RUM conjecture’s point is that you optimise two and pay in the third.
• Measure yours: bytes written and disk usage are both observable; guessing which one dominates is how people pick the wrong engine.

Likely follow-up: “Where does compression sit?” It cuts space and read bytes, costs CPU, and can cut write amplification in the log too.

5. How would you decide between PostgreSQL and an LSM store for a new service?

Show a strong answer

• Start with the query shapes: joins, transactions and ad-hoc queries point at a relational engine; a high-volume append with key lookups points at an LSM.
• Then the write rate and the durability you need. An LSM’s default write may not be power-cut durable; a relational commit is.
• Then operational reality: backups, replication, schema changes, and who on the team has run it before.
• The boring answer is usually right: PostgreSQL handles a lot more write volume than people assume, especially with fill factor and vacuum tuned.
• Don’t choose on a benchmark with mismatched settings.

Likely follow-up: “What if you need both?” That’s common: a relational store of record plus an LSM-backed store for the high-volume stream, with one of them the source of truth.

6. What happens on a crash, exactly?

Show a strong answer

• On restart the engine replays its log from the last checkpoint: committed transactions are reapplied, uncommitted ones discarded.
• Torn pages are repaired from full page images (PostgreSQL) or the doublewrite buffer (InnoDB).
• What’s lost depends on the durability setting: nothing at all with a synchronous commit; the last few writes with an async one.
• Process crash versus machine crash are different: LevelDB’s async write survives the first and not the second.
• And the disk may still lie, which is why the engines’ own documentation talks about caches that claim to have persisted data they haven’t.

Likely follow-up: “How do you test it?” Kill the process, then kill the machine, ideally with fault injection, and verify the data your application believes it committed.

7. What does a Bloom filter do for an LSM, and when doesn’t it help?

Show a strong answer

• It answers “definitely not here” cheaply for each run, so a key that doesn’t exist doesn’t cost a read per run. In our lab, 20,000 missing-key lookups fell from 140,000 run searches to 2,617.
• False positives cost a wasted read, and the rate is a function of bits per key, hash count and implementation quality.
• It doesn’t help range scans at all, because there is no single key to test.
• It costs memory, typically about 10 bits per key, which competes with the block cache.
• It wasn’t in the original paper: it comes from the LevelDB and Bigtable generation.

Likely follow-up: “What else reduces read amplification?” Fewer runs through compaction, partitioned indexes, and caching the index and filter blocks.

8. Your database’s disk usage doubled overnight without more data. What do you look at?

Show a strong answer

• In PostgreSQL: dead tuples and whether vacuum is keeping up, long-running transactions or replication slots holding the oldest snapshot, and index bloat.
• In an LSM: whether compaction has fallen behind, which shows up as level-0 files piling up and read latency rising.
• In both: the write-ahead log itself, if archiving or a replica has stalled and the log can’t be recycled.
• Then look at the workload: a new index, a changed update pattern that broke heap-only updates, or a bulk job.
• Fix the cause, not the symptom: more aggressive vacuum or compaction, fill factor changes, or removing the index that broke HOT.

Likely follow-up: “Why can a long-running transaction cause bloat?” Vacuum can’t remove row versions still visible to it, so churn accumulates for as long as it runs.

Sources

• Labs: system-design/checks/part16_storage/ (a miniature LSM and a page store measuring the three amplifications, and postgres.py, which measures page contents, HOT updates, bloat and WAL bytes against PostgreSQL 18 in a container)
• R. Bayer and E. McCreight, “Organization and Maintenance of Large Ordered Indices” (Boeing Scientific Research Laboratories report, July 1970; later published in Acta Informatica); P. O’Neil, E. Cheng, D. Gawlick, E. O’Neil, The Log-Structured Merge-Tree; M. Athanassoulis et al., Designing Access Methods: The RUM Conjecture, EDBT 2016
• PostgreSQL 18: database page layout, TOAST, heap-only tuples, routine vacuuming, write-ahead logging, WAL configuration
• RocksDB: MemTable, compaction, Bloom filters; LevelDB: implementation notes and documentation
• SQLite: write-ahead logging, atomic commit; MySQL: InnoDB architecture

What to remember

• The page is the unit. Row size, update cost and caching all follow from it.
• The log exists so that a crash is recoverable, and it makes commits faster by turning random writes into one sequential one. It is not free: PostgreSQL writes whole pages into it after each checkpoint.
• A B-tree updates in place and an LSM appends and compacts, so the first tends to spend space cheaply and writes dearly, and the second the other way round. Both are settings as much as shapes.
• Every amplification number is a number about a setting. Ours moved by three orders of magnitude on the checkpoint interval alone.
• Bloom filters make LSM misses cheap and do nothing for ranges.
• In PostgreSQL, updates create row versions. Fill factor and un-indexed columns are what keep them on the same page.
• Vacuum reclaims space for reuse, not for the filesystem. Steady-state size is the design, not a bug.
• Durability is a setting. Compare two databases only when it matches.

Every storage engine is a bet about which is scarcer: your disk’s bandwidth, its space, or your patience on a read.