為何我們 50 年來一直錯誤地為數據編製索引：在 Rust 中以數學取代 B-Trees

Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust

For half a century, database engineering has rested on an unspoken consensus: if you need to index sorted data, you use a B-Tree. From relational engines like PostgreSQL and SQLite to modern key-value stores like RocksDB, B-Trees and their variants have been the default choice since the early 1970s.

They are robust, well-understood, and battle-tested. But in the 50 years since their invention, computer architecture has fundamentally transformed.

Processors have become astonishingly fast, while RAM latency has barely kept pace. This divergence—often called the memory wall—means the way B-Trees navigate data is increasingly at odds with how modern silicon actually works.

I spent the past few days implementing and benchmarking a theoretical alternative in pure Rust: a Piecewise Geometric Model (PGM) Learned Index. Here is what I learned about why it works, how it breaks the traditional model, and what it implies for modern software systems.

The Silent Bottleneck: Pointer Chasing

To understand why B-Trees struggle on modern hardware, you have to look at what happens at the CPU cache level during a lookup.

A B-Tree organizes data into hierarchical nodes linked by memory pointers. When searching for a key:

1. The CPU loads the root node from RAM into cache.
2. It scans the node to find the appropriate child branch.
3. It follows a pointer to another memory location in RAM, usually causing a cache miss.
4. It repeats this process four to six times until reaching the target leaf.

On a modern CPU, an arithmetic calculation takes a fraction of a nanosecond. Loading an un-cached line from main memory takes around 50 to 100 nanoseconds.

During a B-Tree search, your processor spends almost none of its time "thinking"—it spends nearly all of its time waiting for memory buses to deliver data across disparate RAM addresses. This phenomenon is known as pointer chasing.

Furthermore, maintaining this tree structure requires substantial metadata: child pointers, node capacities, and balancing flags. In practice, the index metadata alone often takes up more memory than the actual keys being indexed.

The Paradigm Shift: Data is a Function

What is a sorted list of numbers?

Traditionally, we treat sorted data as an opaque collection of distinct items that must be compared one by one. But mathematically, a sorted array is simply a curve: a Cumulative Distribution Function (CDF).

If you have an array of a million sorted items, the position of any item is roughly proportional to its value.

In 2018, researchers at MIT and Google (Kraska et al.) asked a provocative question:

Why are we traversing an artificial tree of pointers when we could simply approximate the curve with a mathematical equation?

If you know the slope of the data, you don't need a tree. You can compute the memory address directly using basic algebra:

$$y = ax + b$$

How a PGM-Index Actually Works

Pure machine learning models like neural networks are often too slow and lack strict precision guarantees—you cannot afford to "guess roughly" where a database record lives.

This is where the Piecewise Geometric Model (PGM) comes in. It does not use neural networks; it uses formal geometry.

1. The Error Corridor ($\epsilon$)

Instead of forcing a single complex curve over the entire dataset, a PGM index draws a series of simple linear segments over the data.

As it scans through the sorted keys in a single pass, it maintains a narrow "corridor" of width $\epsilon$ (for example, 16 or 32 items wide). As long as the incoming data points stay within this corridor, the same straight line continues. The moment the data bends too far, the segment is sealed, and a new straight line begins.

2. Direct ALU Calculation

When you query a key:

1. The CPU checks which segment covers the key (a trivial lookup across a tiny array of segments).
2. It evaluates the linear equation $y = ax + b$ using single-cycle arithmetic instructions on the CPU ALU.
3. The result is guaranteed by construction to be within $\pm \epsilon$ of the true location.
4. The CPU performs a tiny local search within that bounded window.

Because that local window is so small, the entire search window is already loaded in the CPU's L1 cache line. The CPU never has to stall waiting for random memory jumps.

What This Implies in the Real World

Replacing pointer traversal with affine approximations changes the fundamental economics of indexing:

1. Radical Memory Shrinkage

In traditional database architectures, storing an index for a million items requires dozens of megabytes of pointer allocations.

With a PGM index, smooth or predictable data (such as timestamps, auto-increment IDs, or sequential keys) can be modeled by just a few dozen linear equations. An index that previously consumed tens of megabytes shrinks down to a few kilobytes.

The entire index can live permanently inside the CPU cache, leaving your RAM free for actual application data.

2. Predictable Low Latency

Because lookups do not depend on walking an arbitrary tree structure, latency becomes deterministic. The CPU performs an ALU calculation, accesses contiguous memory, and finishes the search in a fraction of the time a traditional tree requires.

3. Lower Infrastructure Costs

Memory is the single most expensive hardware component in large-scale database clusters. Dividing index memory footprints by orders of magnitude allows database nodes to hold significantly more data per machine before needing to scale out or page to disk.

The Trade-offs: Where It Fits (and Where It Doesn't)

Learned indexes are not a silver bullet that replaces B-Trees everywhere:

• Where they shine: Read-heavy workloads, append-only streams, and immutable storage blocks. In modern LSM-Tree storage engines like RocksDB or ClickHouse, data on disk is written once into immutable files (SSTables). Indexing these static blocks with a PGM index provides massive speed and memory benefits without any drawback.
• Where B-Trees still hold ground: Highly dynamic, random-write workloads with frequent in-place insertions and deletions. Updating a geometric segment on every individual insert requires buffering or rebuild strategies that traditional self-balancing trees handle naturally.

Conclusion & Code

Building this in Rust confirmed that modern performance engineering is less about micro-optimizing instructions and more about aligning algorithmic design with the physical realities of memory hierarchies.

I packaged this implementation as an open-source, zero-dependency Rust crate with full reproducibility tests:

• Repository: https://github.com/gilnett/learned_index_lab
• Crate: https://crates.io/crates/learned_index_lab

If you are building storage engines, analytical query tools, or high-throughput systems, functional data structures like learned indexes are well worth exploring.