study › DDIA › Chapter 4 · Storage and Retrieval

The Same Rows Cost 4× More in Random Order

Load 10 million rows into an indexed B-tree in ascending key order and it takes ~10 s; load the same rows with keys scattered across the key space and it takes ~40 s — and leaves an index 31% bigger, its leaves a third emptier (69% vs 90% full). This is the random-write penalty LSM-trees exist to avoid.

Concept

A B-tree keeps keys sorted in fixed-size pages, so where a new key lands depends on its value. Feed it keys in ascending order and every insert appends to the same rightmost leaf — fast and tightly packed. Feed it the same keys scattered across the key space and each insert lands in a different page all over the disk — the "random writes" the book warns about. You will load 10 million rows two ways, differing only in key order, and watch the random order take 4× longer and leave an index 31% bigger and a third emptier. This is why LSM-trees, which only ever write sequentially, sustain higher write throughput.

Provenance

Designing Data-Intensive Applications, 2nd ed. (Kleppmann & Riccomini, 2025), Chapter 4 — Storage and Retrieval, §"Sequential versus random writes":

With a B-tree, if the application writes keys that are scattered all over the key space, the resulting disk operations are also scattered randomly … Disks generally have higher sequential write throughput than random write throughput.

The book contrasts the B-tree's scattered small writes with the LSM's large sequential ones. Here you produce the B-tree penalty and measure it.

Prerequisites

The surprise is about how a B-tree places keys on pages. These help; each line notes where it shows up.

B-tree layout — keys are held in sorted order across fixed-size pages (8 KB in Postgres); a lookup walks from the root down to a leaf.
Insertion and page splits — a new key goes into the leaf that owns its value; if that leaf is full, it splits into two half-full pages. Where the key lands is set by its value, not by when it arrives.
Sequential vs. random insertion — always-increasing keys land in the current rightmost leaf (append); scattered keys land in leaves all over the tree (random).
Page fill factor — how full leaf pages are on average. Append-heavy loads pack pages tight; split-heavy loads leave them partly empty, so the index takes more space.

Where to learn the prerequisites B-tree inserts and splits (#1–#2): DDIA §"B-Trees"; any DB-internals reference on B-tree page splits. The random-fill result (#4): the average fill of a randomly-built B-tree tends to ln 2 ≈ 69% — a classic result (Knuth, TAOCP Vol. 3); you'll see it land almost exactly. Why LSM avoids it: DDIA §"Sequential versus random writes" and §"Comparing B-Trees and LSM-Trees." If only one is new, make it #2 — page splits are why random order costs more.

Environment these numbers came from Timings depend on your hardware and will differ; the index sizes and fill factors are structural and reproduce closely. Captured on macOS 26.5.2 (Darwin 25.5.0), arm64, with Docker 29.6.2 running the official postgres:16 image (PostgreSQL 16.14). Two tables of 10,000,000 rows, each with a B-tree index present during load.

Mental model

Two tables, each with a B-tree index on column k, built before the rows are inserted so the index is maintained on every insert:

Sequential — k = 1, 2, 3, …, 10,000,000, inserted in order. Each new key is the largest so far, so it always goes into the current rightmost leaf.
Random — the same count of rows, but k is scattered across the key space (a hash of the row number). Consecutive inserts land in unrelated leaves all over the tree.

Same table shape, same number of rows, same index — only the order the keys arrive in differs. We measure load time, index size, and how full the leaf pages end up. The whole exercise is one script, code/random_vs_sequential_writes.sql.

Setup

docker run -d --name ddia-ch4 -e POSTGRES_PASSWORD=study -e POSTGRES_DB=study postgres:16
sleep 3
docker exec ddia-ch4 psql -U postgres -d study -c "CREATE EXTENSION pgstattuple;"
docker cp random_vs_sequential_writes.sql ddia-ch4:/tmp/
docker exec ddia-ch4 psql -U postgres -d study -f /tmp/random_vs_sequential_writes.sql

Do not read the output yet — make each prediction first.

Step 1 · load time (the surprise)

Predict. Both loads insert exactly 10,000,000 rows into an identical table with an identical index. The only difference is the order the keys arrive in. How different can the load times be? (The instinct: "same rows, same work — maybe a little slower for random.")

How much does key order change the load time?

=== sequential insert: keys 1..10,000,000 in ascending order === INSERT 0 10000000 Time: 9979.232 ms (00:09.979) === random insert: same 10,000,000 rows, keys scattered across the key space === INSERT 0 10000000 Time: 39840.081 ms (00:39.840)

~4× slower for random order — ~10 s vs ~40 s — for the identical set of rows. Every scattered insert dirties a different, cold index page; the sequential load keeps hammering the same hot rightmost page.

Step 2 · the index is bigger, too

Predict. The two indexes hold the same 10M keys. Are they the same size?

Same keys — same index size?

=== index sizes: same key count, different insertion order === seq_index | rnd_index | ratio -----------+-----------+------- 214 MB | 282 MB | 1.31

The randomly-built index is 31% larger — for the same keys. Random inserts split pages in the middle and leave the halves partly empty; the extra space is real bytes on disk (and in the cache) forever.

Step 3 · why: page fill

Predict. What is the average leaf-page fill of each index? (Sequential append should pack pages nearly full.)

How full are the leaf pages in each case?

=== avg leaf fill (%): how densely packed the B-tree leaves are === insert_order | avg_leaf_density_pct --------------+---------------------- sequential | 90.1 random | 68.6

Sequential fills leaves to 90%; random settles at 68.6% — essentially ln 2 ≈ 69%, the textbook average fill of a B-tree built from random keys. That 90-vs-69 gap is exactly the 31% size difference from Step 2.

What you should see

Random-order load is ~4× slower than sequential (~40 s vs ~10 s) for the same rows.
The random index is ~31% larger (282 vs 214 MB).
Leaf fill: ~90% sequential vs ~69% random (the classic ln 2).

Why

A B-tree stores keys in sorted order across fixed-size pages, so a key's value decides which leaf it belongs in. Ascending keys are always the new maximum, so they land in the current rightmost leaf: the load touches one hot page until it fills, splits it once, and moves on. That page is already in memory, the writes coalesce, and each leaf ends up ~90% full. The disk sees, in effect, a sequential append.

Scattered keys defeat all of that. Each insert targets a different leaf somewhere in the tree — very likely a cold page that must be read in, modified, and written back, with a write-ahead log entry each time. That is the pattern of "many small, scattered writes" the book names, and disks (even SSDs) do it slower than sequential writes: ~4× here. Worse, an insert into a full interior leaf splits it into two ~half-full pages, and with random arrivals that keeps happening everywhere at once, so the average fill converges to ln 2 ≈ 69% — which is both the wasted space (a 31% bigger index) and more pages to write, compounding the slowdown.

The boundary — sequential keys are the happy path; that's the whole point of LSM A B-tree loves monotonic keys: auto-increment IDs, timestamps, ULIDs. It suffers on random keys: UUIDv4, hashes, natural keys spread across a domain — which is exactly why time-ordered UUIDs (UUIDv7) were designed, to turn random inserts back into appends. An LSM-tree sidesteps the question entirely: it buffers writes in memory and flushes whole sorted segments at once, and compaction rewrites whole segments — so every write to disk is sequential regardless of key order. That is the write-throughput advantage the book attributes to log-structured storage, and this exercise is the B-tree cost it is measured against.

Go deeper

Rebuild and re-measure. REINDEX the random index and check its size and fill. Predict whether a clean rebuild recovers the 90% packing — it sorts the keys first, so it should. (This is why periodic index maintenance exists.)
fillfactor. Create the sequential index with WITH (fillfactor=70) and compare. Predict how leaving room in each page changes size now vs. how it would help a later update-heavy workload.
Count the WAL. Wrap each load in a check of pg_current_wal_lsn() before and after. Predict which order generates more write-ahead log, and by roughly how much.

Sources: DDIA 2e, Ch. 4, §"Sequential versus random writes" and §"Comparing B-Trees and LSM-Trees" · the ln 2 average fill of a random B-tree is a classic result (Knuth, TAOCP Vol. 3).