Answers · Where the data lives

Why is a log-structured store faster for writes than a B-tree?

In shortBecause a B-tree finds a page and then rewrites it in place for every insert, while a log-structured store only appends, and appending in order is far cheaper than jumping about the disk.

A B-tree insert has to find the page holding the key, change a few bytes of it, and write that whole page back to the place it already occupies. A log-structured store never writes in place: it appends the change to a journal and puts the row into a sorted buffer in memory, so the disk only ever sees long sequential writes. The same change costs the tree a random page write and the log a sequential append, and that difference, not the shape of the tree, is the whole of the gap.

The insert the tree has to do

Start with the granularity. A page is 8 KB and a row is 80 bytes, so a leaf page holds about a hundred rows.

\frac{8192\ \text{bytes}}{80\ \text{bytes per row}} = 102.4\ \text{rows per page}

Changing one 80-byte row therefore moves 8,192 bytes, which is 102 times the data that actually changed. That alone would be tolerable if the page stayed in memory, and often it does: it is read once, modified, and the buffer pool holds it dirty. The problem is the eviction. Under a random insert stream the pages being dirtied are spread across the whole file, so the buffer pool cannot hold them all, and each one has to be written back to a position fixed by the key's place in the sort order. That is a random write. And one insert in every hundred or so arrives at a page that is full, at which point the tree allocates a new page, moves half the entries across, writes both pages, and updates the parent, so a single-row insert became three page writes. The balance of the tree is an invariant somebody is paying to maintain, on every write, forever.

What the log does instead

The log-structured store refuses the premise. A write is appended to a sequential journal, which is the only thing that must reach the disk before the write is acknowledged, and then inserted into a sorted structure held in memory. No disk page is touched at all. When that in-memory buffer fills, the whole thing is written out as one sorted run, in one long sequential write, and that run is never modified again. Merging happens in the background: when enough runs accumulate, a few are combined into a larger one and the old ones are deleted whole.

Nothing is free, so count what the merges cost. Take 10,000 rows and a level ratio of four, meaning each level of runs is four times the size of the one above it. The number of runs a lookup might have to consult is the number of levels.

\frac{\ln 10000}{\ln 4} = \frac{9.2103}{1.3863} = 6.6\ \text{runs}

Each time a run of one level is merged into the level below, every row in it is rewritten. So a row that lives long enough to sink through all 6.6 levels is rewritten about 6.6 times four, because the level it lands in is four times bigger and that merge rewrites 4 rows for every one it moves.

80 \times (1 + 6.6 \times 4) = 80 \times 27.4 = 2192\ \text{bytes}

That is 2,192 bytes of sequential writing per row over its whole life, against 8,192 bytes of random writing for a single B-tree insert. Divide one by the other and the log moves less than a third of the data: 8192 / 2192 is about 3.7. So even after paying for every merge it will ever cause, the row still costs less in bytes, and every one of those bytes goes down in a long contiguous stream rather than to a page chosen by a key. Fewer bytes, and the cheap kind of write. That is the entire advantage.

FIG 1

reads for an exact lookup	reads for the first row of a range	reads for a range of ten rows	cost of an insert, tree equals 100	space used, tree equals 100
2	1	11	100	100
1	1	11	95	110
5	3	5	25	170

The natural guess is that the tree is slow because it is a tree, that the log must be winning by avoiding the descent. It is not. The in-memory buffer of a log-structured store is itself a sorted structure, a balanced tree or a skip list, and inserting into it costs the same logarithmic walk the B-tree's descent costs. The descent was never the expensive part: two or three page reads at the top of a tree are almost always cached, and the table above puts the whole exact lookup at roughly two reads either way once the filters are counted. The expensive part is the last step of a B-tree insert, the one where the modified page must go back to a location chosen by the key rather than to the end of the file. The log does not search less. It writes differently. The second half of the same mistake is assuming the balanced shape costs nothing to hold: it is repaired on every insert, by page rewrites and by splits, and that repair is the write cost you are trying to explain.

Where the advantage goes

All of this assumes the tree's working set does not fit in memory. Give the buffer pool enough room that the dirty pages stay resident and the writeback gets batched anyway, and the gap narrows sharply, because the random writes become one flush of many pages at once. It also assumes the merges keep up. When writes arrive faster than the background merging can consume runs, the count of 6.6 runs grows and reads get slower with nothing about the reads having changed. A delete makes it worse in the same direction: there is no page to modify, so a delete is a write too, a marker laid down beside the old entry until a merge removes both, and a workload of updates and deletes inflates everything the log writes while the tree just overwrites in place.

And the read column is where the bill actually arrives. A lookup must check the memory buffer and then each run in turn, which is 6.6 binary searches instead of two page reads, and it is only tolerable because a probabilistic filter per run can answer that this run certainly does not hold the key and skip most of them. Space is worse too, 170 against 100 on the table, since obsolete versions sit on disk until a merge clears them. If the workload needs ranges over old data, or reads that outnumber writes, the tree is the right shape and no amount of cheap writing changes that.

Worth keeping

The balanced shape of a B-tree is maintained rather than given: every insert reads a page, changes it, and writes it back to a location fixed by the key.
A log-structured store writes each row several times over its life, but every one of those writes is sequential and the total bytes can still be less than one B-tree page rewrite.
A lookup in a log-structured store checks one sorted run per level, so the cheap writes are paid for at read time and in disk space.

Where this goes next

This question is one step of How an Index Actually Works, a course that works through its subject from the beginning. The page that teaches this part of it is The Other Two Shapes, and it reads the whole way through whether or not you have an account.

What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.

Read that page The whole course