An index is a bet that the next lookup is close to the last one. B-tree indexes keep that bet in sorted pages, one pointer per key, and pay a page fault or two to find it. Learned index structures replace the pages with a model that predicts a key's position from its value, so the index stores a function instead of a list. The pitch is an order of magnitude less memory and one cache miss instead of three. The catch is that a function fitted to yesterday's data is a liability the moment the distribution moves.
A B-tree spends 16 to 32 bytes per key and three or four cache misses per lookup, while a learned index stores a few bytes per key and predicts the position in one step.
Part One: What is being compared
The headline number is the wrong unit: a budget records cost before the first result, per operation, and on bad days.
Both map a key to a location, both handle duplicates and variable-length keys, and both sit under the same buffer pool and write-ahead log.
Part Two: The arithmetic
The arithmetic is about bytes per key. A B-tree entry costs a key plus a pointer plus fill-factor slack, commonly 16 to 32 bytes, and a lookup walks three or four levels, each a potential cache miss. A learned index stores a small model plus a bounded error, often a few bytes per key, predicts the position in one step, then scans a short range to find the exact entry. On read-heavy keys the memory saving can be tenfold.
The mechanism is about information: one design makes part of the problem observable, and someone must still calibrate the instrument.
Part Three: Where the model breaks
Writes are where the model breaks. B-tree indexes absorb an insert by splitting a page, a local operation with bounded cost. Learned index structures assume a distribution, so an insert outside the fitted range forces a retrain or lands in a delta buffer searched separately. Skewed or adversarial keys, the ones a multi-tenant system sees every day, are exactly where the error bound stops holding and the lookup degrades to a scan.
Inserts outside the fitted distribution force a retrain or a delta buffer, which is why learned indexes win on append-only data and struggle with multi-tenant skew.
Part Four: The later cost
The constant factors are unglamorous. Model inference costs a few SIMD operations, cheap next to a cache miss and expensive next to two comparisons in a hot node. That is why learned indexes win on large, cold indexes and lose on small, hot ones, and why the results cluster around read-only datasets. The engine must also keep the model consistent across compaction, replication and crash recovery.
Expect a split by scale: large operators amortise the fixed side, smaller ones stay because their load is spiky.
Part Five: Outside the team
For the team running a multi-tenant database, the difference is whether one tenant's key pattern can blow up everyone's tail latency. For the user, it is a query that returns in ten milliseconds or two hundred. The daily-life version is a librarian who memorised the shelving plan versus one who reads the labels.
Outside engineering the consequence is access: a system that needs less of the scarce resource can be replicated more widely.
A fair comparison fixes the workload mix, including insert rate and key skew, and prices memory, cache misses and retraining. A lookup benchmark on a static dataset measures the easy half of the problem.
Market sizing check
If learned indexes stay inside specialised engines rather than general databases by 2030, the addressable market is small, perhaps $300M to $1.5B a year embedded in storage products. The deciding factor is write-heavy multi-tenant workloads, not read benchmarks.
All figures are a synthesis of published ranges and a stated model, not a measurement of a shipped system.
The comparison that matters
The comparison that matters is between an index that stores a function and one that stores a sorted list. Learned indexes win on memory and cold-read latency for stable, large keyspaces; B-trees win on inserts, skew, recovery and predictability. Adopt the model where data is append-only.
The ranking assumes the workload keeps its shape; shift the mix and the result changes with no technology changing.
Use a learned index for large, cold, read-mostly keyspaces and keep the B-tree wherever writes, recovery and worst-case bounds are part of the contract.
SOL: HCqPmPJM3NVtS6YrmVaTZYnuP8XZ2PFgQZKT94VK1LkS
If this saved you time, a tip is appreciated.




