Learned Indexes

Every database you have ever used hides a B-tree beneath the surface. A B-tree is a balanced tree of sorted nodes; to find a key you walk from the root through a chain of comparisons until you reach the right page. It is elegant, general, and optimal in a worst-case sense — roughly $O(\log n)$ comparisons per lookup.

But "general" hides a cost. A B-tree knows nothing about the data it indexes. It treats user IDs that arrive almost sequentially the same as random cryptographic hashes. It cannot exploit the fact that timestamps cluster by day, or that URLs follow a predictable lexicographic pattern.

In 2018 Tim Kraska and colleagues asked a deceptively simple question: what if the index were a model trained on the actual data? If the keys follow any learnable pattern, a model can predict the approximate position of a key in a sorted array in a single forward pass — then a tiny linear scan finishes the job. The result: smaller memory footprint, fewer cache misses, and lookups that can beat a B-tree by an order of magnitude on real-world workloads.

The idea reframes an index as a learned approximation of the cumulative distribution function (CDF) of the keys. If you know roughly where rank $r$ keys live, you know roughly where any new key lands.

The array below holds 32 sorted keys. A linear learned model is fitted to their positions (it approximates the CDF with a maximum prediction error of 1 slot). A classic B-tree (binary search) is built over the same data — $\lceil \log_2 32 \rceil = 5$ comparisons per lookup.

Type a key and press Search — or hit Random to pick one from the array. The demo shows how many steps each approach needs to reach the answer.

<!-- {{c_demo_desc}} -->
<div class="controls">
  <label for="searchKey">{{lbl_search}}</label>
  <input id="searchKey" type="number" min="1" max="999" placeholder="{{ph_key}}" />
  <button id="btnSearch" type="button">{{btn_search}}</button>
  <button id="btnRandom" type="button" class="ghost">{{btn_random}}</button>
</div>
<div class="results" id="results" aria-live="polite"></div>
<div class="array-wrap">
  <div id="arrayViz" class="array-viz" aria-label="{{aria_array}}"></div>
</div>
<div class="legend">
  <span class="leg-item"><span class="dot dot-target"></span>{{leg_target}}</span>
  <span class="leg-item"><span class="dot dot-learned"></span>{{leg_learned}}</span>
  <span class="leg-item"><span class="dot dot-btree"></span>{{leg_btree}}</span>
</div>

/* {{c_style_desc}} */
* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.controls { display: flex; flex-wrap: wrap; gap: .5rem; align-items: center; margin-bottom: .8rem; }
label { font-size: .85rem; font-weight: 600; }
input[type=number] { width: 90px; padding: .38rem .5rem; border: 1px solid #aaa; border-radius: 6px;
                     font-size: .95rem; }
button { font: 600 14px system-ui; padding: .4rem .85rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
.results { min-height: 3.4em; margin-bottom: .8rem; }
.result-row { font-size: .9rem; margin: .18rem 0; }
.result-row .label { font-weight: 700; }
.result-row.learned .label { color: #0a7d33; }
.result-row.btree .label { color: #c14b00; }
.result-row.notfound .label { color: #c92f3c; }
.array-wrap { overflow-x: auto; margin-bottom: .5rem; }
.array-viz { display: flex; gap: 3px; padding: 4px 2px; min-width: max-content; }
.cell { width: 34px; height: 34px; display: flex; align-items: center; justify-content: center;
        font-size: .72rem; font-weight: 600; border-radius: 5px; border: 1px solid #c8d0d8;
        background: #eef1f5; transition: background .2s; flex-shrink: 0; }
.cell.target { background: #1d3557; color: #fff; border-color: #1d3557; }
.cell.learned-scan { background: #b7e4c7; border-color: #2d6a4f; }
.cell.btree-visited { background: #ffd6ae; border-color: #c14b00; }
.cell.both { background: #d4d4fa; border-color: #555; }
.legend { display: flex; gap: 1rem; flex-wrap: wrap; font-size: .8rem; margin-top: .3rem; }
.leg-item { display: flex; align-items: center; gap: .3rem; }
.dot { display: inline-block; width: 12px; height: 12px; border-radius: 3px; }
.dot-target { background: #1d3557; }
.dot-learned { background: #b7e4c7; border: 1px solid #2d6a4f; }
.dot-btree { background: #ffd6ae; border: 1px solid #c14b00; }

// Code not found

Notice that the learned model predicts the position within 1 slot of the truth, so it only scans 3 cells — versus 5 comparisons for binary search. On highly patterned data the model wins decisively; on random data the error budget grows and a deeper hierarchy of models (the Recursive Model Index) is needed.

Classical indexes give worst-case guarantees: a B-tree on $n$ keys always finds any key in $O(\log n)$ comparisons. A learned index gives something different: a prediction with a bounded error.

• The CDF view. Sort the $n$ keys as $k_1 \le k_2 \le \dots \le k_n$. A lookup for key $x$ is equivalent to finding its rank $r$ in this sorted list. If a model predicts $\hat{r}$ with error at most $\varepsilon$, a scan of the window $[\hat{r} - \varepsilon, \hat{r} + \varepsilon]$ is guaranteed to find $x$ — or confirm it is absent. Total cost: one model inference + $O(\varepsilon)$ scan.
• Error budget. A simple linear model achieves $\varepsilon = O(\sqrt{n})$ on uniform data — worse than a B-tree. But on data with low CDF complexity (e.g., timestamps, user IDs, IP addresses) the error can be $O(1)$, giving $O(1)$ lookup.
• Recursive Model Index (RMI). Kraska et al. stack models in a hierarchy: a top-level model picks a sub-model, which narrows the range further. The RMI achieves sub-millisecond lookups on hundreds of millions of keys with memory 10–100× smaller than an equivalent B-tree.
• The trade-off. Learned indexes are read-optimized: inserting new keys may invalidate the model. Hybrid approaches (e.g., ALEX or PGM-Index) handle inserts by combining learned prediction with small local buffers.

The deeper point is philosophical: a learned index is not just a faster B-tree — it is a data structure that encodes knowledge about the distribution of its own keys. The more structured the data, the larger the gain.

Anywhere a sorted dataset is queried many times and updates are infrequent, a learned index is worth considering:

• OLAP and analytics databases: read-heavy workloads on time-series or sequential IDs are ideal — the CDF of timestamps is nearly linear, and a simple model fits almost perfectly.
• In-memory key-value stores: replacing a B-tree index with an RMI can halve lookup latency and reduce the index's memory footprint, freeing RAM for data.
• Genomics and bioinformatics: suffix arrays over DNA sequences follow surprisingly learnable patterns; learned indexes over them cut query time dramatically.
• Embedded and IoT devices: a tiny trained model can replace a bulky tree structure, making indexes feasible on microcontrollers with kilobytes of RAM.
• Cache-conscious design: B-tree nodes are sized to fill a disk page; a learned index's scan window can be sized to fill a CPU cache line — a hardware-level win.

The technique connects to broader ideas about data compression (the model implicitly compresses the key distribution) and dimensionality reduction (the CDF projects any key distribution onto $[0,1]$).

The B-tree has been the workhorse of database indexing for fifty years. It works because it makes no assumptions — and pays a price for that generality on every query. Learned indexes flip this trade-off: they invest training time upfront to earn faster lookups on data that has structure.

The key insight is that an index is secretly an approximation of a CDF. Once you see that, machine learning is a natural tool — models approximate functions, and a CDF is just a function. The more the data follows a pattern, the better the approximation and the smaller the error budget.

This does not mean B-trees are obsolete. They still win on arbitrary, adversarial, or rapidly-changing data. But learned indexes signal a broader shift: algorithms and learned models are not separate disciplines — they are two ends of the same spectrum, and the best data systems of the future will slide freely between them.