Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust
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 (ε)
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 ε (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 ± ε 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: gilnett/learned_index_lab
- Crate: crates.io
If you are building storage engines, analytical query tools, or high-throughput systems, functional data structures like learned indexes are well worth exploring.
7 reactions · 2 comments
Mentions
用分段几何模型替掉 B 树，误差可证 纯 Rust 实现 PGM 学习索引，零依赖，把累积分布函数拟合成带 epsilon 上界的分段线性模型。README 注明了原始论文出处。 gilnett/learned_index_lab
Replacing B-Trees with streaming linear models (PGM): cache locality and bounds in practice Traditional B-Trees waste substantial CPU cycles on pointer chasing across node levels, causing avoidable cache misses on modern architectures. The PGM-index approach (Ferragina & Vinciguerra, VLDB 2020: vldb.org) addresses this by modeling key distributions through streaming piecewise linear regression with strict +/- epsilon error bounds. Instead of traversing tree nodes, key rank is predicted directly on the ALU (y = ax + b), bounding the local search window so that it fits entirely within L1 cache. The construction runs in a single O(N) streaming pass with zero external solvers. I built a pure Rust reference implementation (v0.2.0) with zero dependencies to benchmark this against std::collections::BTreeMap across 1M keys: gilnett/learned_index_lab. Benchmarks across uniform and skewed distributions show a 99.9% reduction in index memory (~48 KB vs 45 MB) and 3x to 4.5x lower lookup latency. While transactional engines still rely on B-Trees for in-place page writes, learned models provide significant advantages for read-heavy or immutable storage layouts (such as LSM SSTables and columnar stores) where pointer overhead is pure waste. Has anyone here benchmarked or worked with learned data structures in storage systems? How do you approach optimal epsilon tuning when key distributions are non-uniform or unpredictable?
gilnett/learned_index_lab this is going to be extra cute once fully tested.
“High-perf Piecewise Geometric Model (PGM) learned index…” gilnett/learned_index_lab > [Demo of] the paradigm shift away from traditional comparison-based pointer hierarchies (e.g. B-Trees, LSM block indexes) to approximations of Empirical Cumulative Distribution Functions (CDFs)
“High-performance Piecewise Geometric Model (PGM) learned index implementation…” gilnett/learned_index_lab > [Demo of] paradigm shift away from traditional comparison-based pointer hierarchies (e.g. B-Trees, LSM block indexes) to approximations of Empirical Cumulative Distribution Functions (CDFs)
B-Tree, but with Error Budgeting gilnett/learned_index_lab
こういうの同じことは考えてたんだけど、効率も性能もハッシュマップや最新のBTreeに勝てないんだよね⋯⋯ 昔、NINTENDO64でカオス数列を使った画像圧縮とかあったけど今使われてるという話聞かない gilnett/learned_index_lab
Learned Index Lab: Replacing B-Trees with Streaming Models in Rust (99% RAM, 3x
Why We've Been Indexing Data Wrong for 50 Years: Replacing B-Trees with Math in Rust 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 (ε) 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 ε (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 ± ε 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: gilnett/learned_index_lab - Crate: crates.io If you are building storage engines, analytical query tools, or high-throughput systems, functional data structures like learned indexes are well worth exploring.
Learned Index Lab: Replacing B-Trees with streaming linear models in pure Rust (-99% RAM, 3x faster) Instead of pointer-chasing through B-Tree node hierarchies, this index models the key distribution using streaming piecewise linear regression with strict epsilon error bounds. Lookups compute positions directly on the CPU ALU before a local L1 cache search, reducing memory by 99% and cutting latency by 3x. To clarify the technical phrasing without buzzwords: 1. Baseline: BTreeMap is indeed mutable. PGM indexes target immutable / read-heavy sorted datasets (OLAP engines, columnar storage, and SSTables in LSM trees). Even compared to a flat slice::binary_search (~20 cache line jumps across an 8MB array for 1M keys), PGM drastically reduces memory traffic. 2. ALU computation: Once segment parameters are loaded, the index position is estimated with a single multiply-add instruction in CPU registers: pos = y0 + slope * (key - x0). No pointer chasing or node traversals. 3. L1 cache search: Because error is mathematically bounded to +/- epsilon (e.g. epsilon = 16), the target key is guaranteed to sit within a contiguous 256-byte slice (4 cache lines). The local search hits L1 cache with prefetching rather than jumping across RAM. The implementation and release benchmarks are reproducible here: gilnett/learned_index_lab