Introduction

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)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 rr keys live, you know roughly where any new key lands.

Try It

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 — ⌈log⁡232⌉=5\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.

<!-- Demo: compare a learned linear model lookup vs a binary-search B-tree on 32 sorted keys -->
<div class="controls">
  <label for="searchKey">Key:</label>
  <input id="searchKey" type="number" min="1" max="999" placeholder="e.g. 85" />
  <button id="btnSearch" type="button">Search</button>
  <button id="btnRandom" type="button" class="ghost">Random</button>
</div>
<div class="results" id="results" aria-live="polite"></div>
<div class="array-wrap">
  <div id="arrayViz" class="array-viz" aria-label="Sorted key array visualization"></div>
</div>
<div class="legend">
  <span class="leg-item"><span class="dot dot-target"></span>Target key</span>
  <span class="leg-item"><span class="dot dot-learned"></span>Learned scan window</span>
  <span class="leg-item"><span class="dot dot-btree"></span>B-tree steps</span>
</div>

/* Demo styles for learned-indexes comparison */
* { 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; }

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// 32 sorted integer keys — roughly evenly spaced to simulate a learnable distribution
// (gap ~6-8 on average, with slight noise — a near-linear CDF)
const KEYS = [3,7,12,18,24,31,37,43,50,56,63,70,78,85,91,98,
              106,113,120,128,135,143,150,158,165,172,180,187,195,202,210,218];
const N = KEYS.length;

// Linear learned model: fits a line through (min_key, 0) and (max_key, N-1)
// predicted_rank = round((key - min) / (max - min) * (N-1))
function learnedPredict(key) {
  const minK = KEYS[0], maxK = KEYS[N - 1];
  const raw = ((key - minK) / (maxK - minK)) * (N - 1);
  return Math.max(0, Math.min(N - 1, Math.round(raw)));
}

// B-tree simulation: standard binary search, each midpoint is one node visited
// Binary search on sorted array = equivalent to a perfectly balanced B-tree traversal
function btreeLookup(key) {
  const visited = [];
  let lo = 0, hi = N - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    visited.push(mid);
    if (KEYS[mid] === key) return { idx: mid, visited };
    if (KEYS[mid] < key) lo = mid + 1;
    else hi = mid - 1;
  }
  return { idx: -1, visited };
}

// Learned lookup: predict position, then scan a small window of +/- ERROR cells
const ERROR = 1; // max error budget in cells (covers the model's residual on this near-linear dataset)
function learnedLookup(key) {
  const pred = learnedPredict(key);
  const lo = Math.max(0, pred - ERROR);
  const hi = Math.min(N - 1, pred + ERROR);
  const scanned = [];
  for (let i = lo; i <= hi; i++) {
    scanned.push(i);
    if (KEYS[i] === key) return { idx: i, pred, scanned };
  }
  return { idx: -1, pred, scanned };
}

function renderArray(target, learnedScanned, btreeVisited) {
  const viz = document.getElementById('arrayViz');
  viz.innerHTML = '';
  const lSet = new Set(learnedScanned);
  const bSet = new Set(btreeVisited);
  KEYS.forEach((k, i) => {
    const d = document.createElement('div');
    const isTarget = i === target;
    const inL = lSet.has(i);
    const inB = bSet.has(i);
    let cls = 'cell';
    if (isTarget) cls += ' target';
    else if (inL && inB) cls += ' both';
    else if (inL) cls += ' learned-scan';
    else if (inB) cls += ' btree-visited';
    d.className = cls;
    d.textContent = k;
    viz.appendChild(d);
  });
}

function search() {
  const raw = document.getElementById('searchKey').value.trim();
  const key = parseInt(raw, 10);
  const res = document.getElementById('results');
  if (isNaN(key)) {
    res.innerHTML = '<div class="result-row notfound"><span class="label">Please enter a key from the array.</span></div>';
    renderArray(-1, [], []);
    return;
  }
  const lr = learnedLookup(key);
  const br = btreeLookup(key);
  if (lr.idx === -1) {
    res.innerHTML = '<div class="result-row notfound"><span class="label">Key not found in the array. Try a key shown in the array.</span></div>';
    renderArray(-1, lr.scanned, br.visited);
    return;
  }
  const lSteps = lr.scanned.length;
  const bSteps = br.visited.length;
  res.innerHTML =
    '<div class="result-row learned"><span class="label">Learned model:</span> ' +
    i18nFmt('%steps% step(s) — predicted position %pred%', { steps: lSteps, pred: lr.pred }) + '</div>' +
    '<div class="result-row btree"><span class="label">B-tree:</span> ' +
    i18nFmt('%steps% step(s) (binary search)', { steps: bSteps }) + '</div>';
  renderArray(lr.idx, lr.scanned, br.visited);
}

document.getElementById('btnSearch').addEventListener('click', search);
document.getElementById('searchKey').addEventListener('keydown', (e) => {
  if (e.key === 'Enter') search();
});
document.getElementById('btnRandom').addEventListener('click', () => {
  const k = KEYS[Math.floor(Math.random() * N)];
  document.getElementById('searchKey').value = k;
  search();
});
renderArray(-1, [], []);
Result
Console

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.

The Real Complexity

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

  • The CDF view. Sort the nn keys as k1≤k2≤⋯≤knk_1 \le k_2 \le \dots \le k_n. A lookup for key xx is equivalent to finding its rank rr in this sorted list. If a model predicts r^\hat{r} with error at most ε\varepsilon, a scan of the window [r^−ε,r^+ε][\hat{r} - \varepsilon, \hat{r} + \varepsilon] is guaranteed to find xx — or confirm it is absent. Total cost: one model inference + O(ε)O(\varepsilon) scan.
  • Error budget. A simple linear model achieves ε=O(n)\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)O(1), giving O(1)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.

Where It Matters

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][0,1]).

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/learned-indexes/Content licensed under CC BY-NC 4.0.