Learned Indexes: Replacing a B-Tree With a Model

An index is really a function: the CDF insight

Ask what a range index does and the answer is deceptively simple: given a lookup key, return the position of that key's record inside a sorted collection. That is a function from key to position. Sort N keys into an array and, for each key, plot the fraction of keys less than or equal to it — you have traced the cumulative distribution function (CDF) of the data. Multiply that fraction by N and you get the record's index. The position of a key is exactly F(key)·N, where F is the empirical CDF.

So an index is a model of the CDF. A B-tree is one such model — a very general, distribution-agnostic one that assumes nothing about the data and pays O(log N) comparisons to narrow the position. But if the keys carry an exploitable shape — timestamps that climb steadily, auto-increment IDs, clustered geographic coordinates — that shape is information the B-tree throws away. Kraska, Beutel, Chi, Dean, and Polyzotis made this explicit in their 2018 SIGMOD paper The Case for Learned Index Structures: if you can approximate the CDF cheaply, the model is the index, and the tree becomes unnecessary.

The recursive model index: a hierarchy of tiny models

A single model that maps millions of keys to exact positions is hard to fit. Getting the coarse shape right is easy; shrinking the error from "somewhere in a million rows" to "row 4,412,077" — the last-mile problem — demands enormous capacity. The paper's answer is the Recursive Model Index (RMI): a shallow hierarchy, usually two or three stages, where each stage's prediction selects which model runs in the next stage.

Stage 1 is a single model over the whole key range. Its output is not the final position but an index into an array of stage-2 models; the chosen stage-2 model, responsible for a narrow slice of the key space, produces the position estimate (or picks a stage-3 model). Crucially, the internal stages do no comparisons and no branching — each is a multiply–add that indexes directly into the next stage's model array. The leaf models are typically simple linear regressions, piecewise-linear pieces of the CDF, so the whole structure is a few hundred bytes to a few megabytes of floating-point coefficients. An RMI is a directed staged function, not a search tree: there is no traversal to backtrack, no rebalancing, and no pointer chasing between levels.

The last mile: error bounds and correct answers

A model only predicts a position; it can be wrong. What makes a learned index a correct index rather than an approximate one is the error bound. At build time the system evaluates the model on every key and records the maximum over- and under-shoot: err = max |predicted − actual|. A lookup then computes the prediction p̂ and performs a local search over the guaranteed window [p̂ − err, p̂ + err] using binary or exponential (galloping) search. Because the true position is provably inside that window, the answer is exact — learned indexes are not probabilistic for point and range lookups; the model only shrinks the haystack.

This is where the cost model lives. Model inference is a constant number of multiply–adds. The local search is O(log₂ ε), where ε is the error window — not O(log N). If the CDF is well approximated so ε stays small and roughly independent of N, a lookup is effectively constant time in the data size, touching only a couple of cache lines. That is the whole game: trade a logarithmic tree walk for a constant model plus a tiny bounded search.

Why it can beat a B-tree: cache, space, and distribution

Three advantages stack up. Complexity: a cache-optimized B+-tree does O(log_B N) node visits, each a likely cache miss as it chases pointers; the RMI does a fixed handful of arithmetic operations and then searches a contiguous ε-sized window that often fits in one or two 64-byte cache lines. Space: a B-tree stores O(N/B) separator keys and pointers across its internal levels, while a piecewise-linear learned index stores only two coefficients per segment, and the segment count depends on how linear the CDF is, not rigidly on N. Distribution: the B-tree treats every dataset as if adversarial and pays the same price for smooth timestamps as for random hashes; the learned index converts real structure into fewer segments and smaller error.

The original paper reported learned indexes up to ~70% faster than a read-optimized B-tree while using an order of magnitude less memory on real datasets (web-server logs, map coordinates, a lognormal synthetic set). Later gap-aware and concurrent variants pushed read speedups further. This is the same instinct behind interpolation search — guess the position assuming a uniform distribution — except a learned index learns the real distribution instead of assuming one, so it degrades gracefully on skew where naive interpolation search collapses to O(N).

Building it: piecewise-linear approximation and the PGM-index

How do you fit the segments? The influential PGM-index (Ferragina and Vinciguerra, PVLDB 2020) makes construction rigorous. Given a target error ε, it computes the optimal piecewise-linear approximation — the minimum number of line segments such that every key's predicted position is within ε of the truth — in a single O(N) streaming pass using an incremental convex-hull construction. Each segment absorbs as many consecutive keys as one line can hold inside the ε corridor; when the next key would break the bound, a new segment begins.

The segments' first keys form a smaller sorted set, so the PGM-index recursively indexes the segments the same way, building a shallow hierarchy until the top layer fits in a cache line. The payoff is a provable worst-case bound: lookups are O(log N) in the worst case like a B-tree, but with far smaller constants and space often orders of magnitude less. That is the key contrast with the RMI — the RMI is a fast heuristic with no worst-case guarantee (a bad model just means a big error window), whereas the PGM-index guarantees the bound by construction. Related designs — FITing-tree (SIGMOD 2019) and RadixSpline — trade differently between build speed, error, and shape.

The hard part: inserts, updates, and ALEX

A sorted array plus a fixed model is beautiful until you insert. Adding a key shifts the positions of everything after it, invalidating the model's predictions and, in the naive case, forcing an O(N) shift. This is the central weakness, and the fixes borrow from decades of storage engineering. Gapped arrays leave deliberate empty slots so a model-based insert usually lands in a nearby gap in O(1) amortized time; delta buffers stage recent writes in a small side structure that is periodically merged and the model retrained — exactly the log-structured merge pattern behind LSM-trees.

ALEX (Ding et al., SIGMOD 2020, Microsoft) combines these: an adaptive RMI whose data nodes are gapped arrays, model-based inserts, exponential search from the predicted slot, and node splitting when a node fills or its error grows too large. It matches or beats B-trees on read-write workloads, not just read-only. The PGM-index handles updates with a logarithmic method — a hierarchy of geometrically growing PGM indexes merged like LSM levels — giving O(log N) amortized inserts. All of these pay a retraining cost and must manage concurrency, which is far better understood for B-link trees than for models.

Failure modes, benchmarks, and where the idea is heading

Learned indexes are not free. Adversarial or spiky distributions — a CDF no small set of lines can track — drive the segment count and error window up until the index is no smaller or faster than a B-tree; a hash-like key set is the worst case. Correctness hinges entirely on the max-error bound being computed honestly: an unaccounted key or a stale bound after an update corrupts lookups, so the invariant “the true position lies within [p̂−err, p̂+err]” must be maintained on every mutation. Updating workloads, concurrency, and variable-length keys remain the sharp edges.

The community measures all this with the SOSD benchmark (“Search On Sorted Data,” Kipf et al.), which pits RMI, PGM-index, and RadixSpline against B-trees, ART, and cache-optimized layouts on real datasets (OpenStreetMap, Wikipedia edits, Amazon books, Facebook IDs). The same 2018 paper also proposed learned Bloom filters — a classifier that predicts membership, backed by a small Bloom filter to eliminate false negatives — showing the “replace a data structure with a model” idea generalizes. Kraska's SageDB vision extends it to sorting, joins, and query planning. Today learned indexes are largely research-grade with open-source libraries (the PGM-index C++ library) and growing production interest, compelling when data is read-heavy, sorted, and structured — and unremarkable when it is none of those.

Finding a key in N sorted records: four mechanisms for the same key→position job

Mechanism	Lookup cost	Space (internal)	Updates & guarantees
B+-tree (cache-optimized)	O(log_B N) node visits, ~1 cache miss each	O(N/B) keys + pointers	Well-understood latching; distribution-agnostic worst case
Interpolation search	O(log log N) on uniform, O(N) on skew	O(1) — no structure stored	Assumes uniform CDF; collapses on non-uniform data
Learned RMI	O(1) model + O(log ε) search, few cache lines	Coefficients only (KB–MB)	Hard inserts; heuristic, no worst-case bound
PGM-index	O(log N) worst case, small constants	O(#segments), often ≪ B-tree	Dynamic via LSM-style merge; provable ε bound