Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Lsm tree — where it appears

A structure that accumulates writes in memory, flushes them as sorted runs, and merges runs into larger ones as they collect. Nothing is ever written in place, so each key is written once per level it passes through rather than costing a whole block of its own.

Named by 4 essays across one field — each of them below, with the objects they name alongside it.

elements of block written per key insertedB-tree, in place49.3Log-structured, T = 23.0 · 16× less than the treeLog-structured, T = 42.0 · 25× less than the treeLog-structured, T = 81.0 · 49× less than the treeLog-structured, T = 161.0 · 49× less than the treeB = 64, M = 4,096 (M/B = 64)25× between the two structures at T = 4

The writes nobody counted

Sixteen thousand keys inserted into a B-tree write 49.3 elements' worth of blocks for every key stored. The same keys into a log-structured store write 2.0. Every operation counter reports the two as the same work — the same insertions, the same comparisons, the same number of updates — and the factor of 24 decides which structure a storage engine is built from.

applied · Transfer 1100ε — the exponent the fanout is B toelements written per key33445679ε = 1 — the B-tree ·fanout 256 · 3transfers a queryε = 0.5 · fanout 16 · 5a querythe number above eachpoint is what a querycostsB = 256, M = 16,384 (M/B = 64)131,072 random keys

One dial between two structures

A B-tree writes 226 elements of block for every key stored and a log-structured store writes two. They are presented as rival designs. They are one design at two settings of an exponent that nothing in either description mentions, and every setting between them is available.

applied · Transfer 0.020.050.10.20.5121235810filter bits a keywasted reads per absent lookupno filters: all 3 levelssame rate every levelrates sized to levelsn = 65,536, size ratio 4, first run 1,024 keysthe same memory at every point

The filter each run carries

A log-structured store turns every lookup for a missing key into a read of every level, and a Bloom filter on each run buys those reads back with memory. Spread five bits a key evenly across three levels and a missing key still wastes 0.279 reads. Give the small levels more bits and the large one fewer — the same memory — and it wastes 0.201. At four levels the gap is 0.382 against 0.209, because sized filters stop the waste growing with the number of levels.

applied · Transfer 234681016110size ratioblock transfers · levelsa range of 100 keyslevelsan absent point lookup1,048,576 keys, 5 bits a keyfilters answer one of these two

The read a filter has no key for

A Bloom filter on every run of a log-structured store turns a lookup for a missing key from a read of every level into a fraction of one — 0.72 transfers across eight levels at five bits a key, and 0.00027 at twenty. A range query over the same store reads nine transfers at five bits and nine at twenty, because a filter answers whether one named key is in a run and a range has no key to name.

applied · Transfer

Named alongside it

The objects these essays reach for when they reach for this one.

Write amplificationBlock transferTrade offB-treeBloom filterExternal-memory modelMemory hierarchyAmortised analysisBlock sizeBuffered treeCompactionData movement

All concepts