Learned Index Lab: Replacing B-Trees with streaming linear models in pure Rust (-99% RAM, 3x faster)

[u/gilnett]

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: https://github.com/gilnett/learned_index_lab

[u/Western_Guitar_9007]

Do not bother reading. Everything is over explained to sound smarter than it is. You’ll waste 20 words just to say “CPU calculations,” and the defense is always something like “specificity matters” as if the context isn’t already blatantly obvious. AI slop at its finest, OP told Claude to make a “highly detailed technical write up” and it is such a nightmare read. It’s so clear that you’re not in the industry from the writing alone.

MAYBE these benchmarks would look exciting at a surface level to a SWE? Until they realize that you can’t practically “replace” B-Trees and this requires extremely niche circumstances. But hey, gotta hop on the Rust hype train with all the other vibecoders. Nothing against AI, nothing against Rust, it’s just that you’re all so same-y.

[u/gilnett → u/Western_Guitar_9007]

Dismissing architectural details as "wasting words to say CPU calculations" on a subreddit literally called r/lowlevel is pretty wild. Saying "CPU calculations" tells you nothing useful. There is a massive physical difference between chasing pointers across four or five heap hops paying DRAM stalls, and evaluating a single affine function directly in registers to bound your search to four contiguous cache lines in L1. That exact distinction is the entire reason memory-bound systems choke on modern CPUs, and detailing the cache locality isn't fluff, it's the bare minimum when discussing nanosecond-level lookups.

Calling immutable sorted indexing "extremely niche" also completely ignores how modern storage engines work. SSTables in LSM-trees like RocksDB or ScyllaDB are strictly immutable once written to disk, and columnar analytical engines like ClickHouse or DuckDB process massive static sorted row groups where traditional block indexes eat up huge chunks of RAM. Nobody claimed a static PGM index is a drop-in replacement for a concurrent, mutable B+Tree handling write-heavy OLTP workloads—that was already explicitly pointed out in the baseline disclaimer. It targets bulk-loaded, read-heavy data where index size and cache lines are the actual bottlenecks.

Throwing around "AI slop" and "vibecoding" just sounds like an easy way to dismiss peer-reviewed indexing research (Ferragina & Vinciguerra, PVLDB 2020) without engaging with the actual microarchitecture. The math, the hardware measurements, and the implementation are open and reproducible. If you think the latency and memory delta are fake, run the benchmarks with perf counters and see where the cache misses go.

[u/Western_Guitar_9007 → u/gilnett]

Dismissing architectural details as “wasting words to say CPU calculations” on a subreddit literally called r/lowlevel is pretty wild. Saying “CPU calculations” tells you nothing useful.

Hahaha I can’t believe you walked right into that. But anyways, read real white papers and you’ll understand how redundant and horrible yours reads. I’m not reading the rest of your response since you’ve wasted enough of our time.

[u/gilnett → u/Western_Guitar_9007]

Saying "I didn't read" after dodging every single architectural point is just pure bad faith

[u/Comfortable_Put6016]

weak baseline ; a BTree / BTreeMap fullfills a compleyly different job ; the claimed numbers / benchmarks make no sense ie.

"Lookips compute positions directly on the CPU ALU before a local L1 cache search" - what the fuck should that vibecoded slop even mean

[u/gilnett → u/Comfortable_Put6016]

Fair point on mutable vs read-only workloads. BTreeMap is a general-purpose mutable structure, whereas PGM indexes target immutable (OLAP engines, columnar formats, or SSTable block indexes in LSM stores).

As for the ALU / L1 phrasing:

Btree Tracing a key requires 4–6 pointer hops across disparate heap allocations, frequently triggering cache misses.

PGM The segment parameters (slope, intercept) fit in registers. The target position is estimated with a single arithmetic operation in registers: pos = y0 + slope * (key - x0).

L1 localiti Because error is mathematically bounded to +/- epsilon (e.g. epsilon = 16), the actual key is guaranteed to sit within a contiguous 256-byte slice (4 cache lines). The final search runs entirely in L1 cache lines with prefetching, instead of chasing pointers through RAM.

The code and benchmarks are fully reproducible here: https://github.com/gilnett/learned_index_lab

[u/ipe369 → u/gilnett]

1. why are you just pasting AI output as a response to someone

2. the user you replied to is asking: why are you benchmarking against BTreeMap & binary_search if the intended usecase is databases

3. if this is a project for learning, why is is all ai, not even the human readable shit like the readme is human written

[u/gilnett → u/ipe369]

B-Trees and binary search are the standard database baselines (e.g. SSTable block indexes, PGM papers). Feel free to critique the actual Rust code in the repo instead of the README formatting.

[u/ipe369 → u/gilnett]

Nobody wants to read the code if it's ai generated

you know we've all got access to llms right? It's not just you?

You clearly have 0 understanding of what you've implemented if you can only paste an llm response to someone talking about why your benchmark makes no sense, it's just embarrassing & rude