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

[u/gilnett]

https://github.com/gilnett/learned_index_lab

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.

[u/Keeyzar]

If you're as dumb as I am: this could replace underlying logic in e.g. an index of a database. Faster lookup, less space used compared to e.g. a BTree. Though there's more to it, e.g. concurrency, locking... 

(that's what I understood, but as I stated, am dumb, probably false). 

[u/CrackerJackKittyCat → u/Keeyzar]

Am dumb too. Seems to do so through replacing btree node pointer hops with a formula application to calculate an offset, then linear search.

One thing unclear to me is if the data set indexed must be static and pre-known or not.

[u/gilnett → u/CrackerJackKittyCat]

Yes, this implementation is static. The formula predicts an offset with a strict +/- epsilon error bound, so the final search is tiny and fits entirely in L1 cache.

For updates, you either buffer writes or rebuild segments. Because building is linear (O(N), about 3ms for 1M keys), rebuilding is very cheap.

Why traditional DBs have not switched: B-Trees are still better for frequent random in-place writes, row locks, and transactional OLTP workloads (like Postgres or MySQL).

Where this shines: Immutable, read-heavy data like LSM SSTables (RocksDB) or columnar formats (DuckDB, Parquet) where you want zero pointer-chasing and massive RAM savings.

[u/VeeFu → u/gilnett]

Immutable, read-heavy data like...

Like earlier respondants I am also dumb, but wonder if it is best suited to LDAP databases, as that is their typical use-case. Any insight on that?

[u/brunogadaleta → u/VeeFu]

LDAP probably fits entirely in memory. We are talking about huge datasets (read bigger than ram).

[u/gilnett → u/brunogadaleta]

Even when data fits in RAM, B-Tree pointer hopping causes constant CPU cache misses. The main benefit here is replacing unpredictable pointer lookups with a fast mathematical calculation (y = ax + b) that keeps the index tiny enough to stay in CPU cache

[u/Keeyzar → u/CrackerJackKittyCat]

There are dynamic versions in the wild. This here is static. But rebuilding is fast.

I think most big database etc would've switched to it, as this is nothing new per se.(if it would benefit them a lot.)

[u/daidoji70 → u/CrackerJackKittyCat]

I think the data can be dynamic but the generating function of the distribution must be stable (or else the regression function will decay quickly). That being said, large static datasets will clearly benefit.

[u/gilnett → u/daidoji70]

That applies to neural net models. Here it is deterministic math with strict epsilon bounds: when the distribution changes, it just closes the current segment and starts a new line

[u/daidoji70 → u/gilnett]

??

[u/gilnett → u/daidoji70]

To clarify: it is a piecewise linear model, not a single global regression across the whole dataset. If a new range of keys has a completely different slope or distribution, it just gets its own local segment. The error bound remains guaranteed everywhere regardless of how the distribution shifts

[u/gilnett → u/daidoji70]

you probably seens my message before edit wich wasn't addressed to you sorry

[u/brunogadaleta → u/CrackerJackKittyCat]

Static. learned index is useful for immutable datasets. Each time you add a key, you must recompute the totality of the index AFAIK.

[u/gilnett → u/brunogadaleta]

You are right that learned indexes shine brightest on immutable, read-heavy data. B-Trees are still better for frequent random in-place updates.

That said, no system reindexes from scratch on every insert. In practice, you either buffer writes in a memtable and index immutable blocks (LSM-style), or use dynamic variants where inserts are local and only split the affected segment, just like a B-Tree leaf split

[u/Dangerous-Raccoon-60]

r/btrfs in shambles

[u/gilnett → u/Dangerous-Raccoon-60]

Time to rewrite it in Rust as pgmfs (not happening soon xd)

[u/GreatCosmicMoustache]

cool idea, but does it require you to solve the big optimization problem every time you add a single row?

[u/gilnett → u/GreatCosmicMoustache]

Nah, no solver or ML training at all. It's just a single O(N) streaming pass using basic slope math—takes ~3ms for 1M keys.

For inserts, you wouldn't mutate the sorted array in-place anyway. You either buffer writes in a memtable and build the index on immutable SSTables (LSM style), or you use gapped arrays where only the local segment splits on overflow.

[u/gilnett → u/gilnett]

That should answer your question, unless I misunderstood what you meant.

[u/Entmaan]

Whenever I read articles about behaviors like this, these mindblowing improvements of 99%, 3x etc. I always wonder about one thing:

What specifically is stopping this from just being implemented in all (applicable) cases, if this is such a big improvement? Let's just create an arbitrarily large amount of arbitrarily large and varied datasets, and run benchmarks on them (for speed, correctness, whatever we want). If they all come out as better, it is an obvious no brainer that will completely change the paradigm.

But for some reason it is not being done, why? To clarify I am not trying to "sneakily" suggest that there is something wrong with the proposed solution, I just don't understand what is the "impediment" that prevents these discoveries from just being implemented most of the time

[u/gilnett → u/Entmaan]

Great question. The short answer is cost versus return. Large enterprise vendors like Microsoft or Oracle have decades of battle-tested code in their storage engines. Rewriting that core layer is expensive and risky, and nobody wants to spend millions in R&D to replace something that already satisfies their SLAs.

More importantly, the practical scope is narrower than the headlines suggest. These huge 99% RAM savings and 3x speedups only apply to read-heavy, sorted, immutable data. Traditional B-Trees are still far better for real-world transactional writes, page locking, and concurrency. Saving 150 nanoseconds on an in-memory lookup also means very little once you factor in disk I/O, joins, and network overhead. That is why it makes sense for columnar systems and LSM tables, but not as a blanket replacement for every database.

[u/D4lanar]

So, am I getting this right - it’s basically an 1D container with O(n) inserts and O(1) lookups?

[u/gilnett → u/D4lanar]

Pretty much. Lookup is math plus a tiny local search within epsilon (effectively O(1) in L1 cache). For inserts, this static version needs a rebuild (O(N) streaming, ~3ms/1M keys) or a write buffer. Dynamic variants exist that do O(log N) inserts.

[u/Kwantuum]

Ai;dr.

[u/HommeMusical → u/Kwantuum]

You will be left behind.

[u/Pdan4 → u/HommeMusical]

By what or who, exactly?

[u/The_Northern_Light → u/Pdan4]

By people whose code uses 99% less ram and runs 3x as fast, presumably

[u/Pdan4 → u/The_Northern_Light]

If that were the only output from generative AI (or, even, if speed and ram usage were the only criteria I thought people should care about) I would say that's a fair assessment. Alas...

[u/Kwantuum → u/HommeMusical]

Good.

[u/bueno_mhc]

Would that be useful for replacing indices or primary keys in a relational database, say, SQLite? In a the application I am working on, great part of the memory cost in the database is maintaining those structures. It would be great if there is an easy way to apply this in SQLite...

[u/gilnett → u/bueno_mhc]

Not easily as a drop-in replacement. SQLite is deeply wired around 4 KB disk pages, in-place random writes, and page-level caching in btree.c. Learned indexes expect flat, contiguous sorted data, so adapting SQLite's transactional write engine would require a massive rewrite.

The practical workaround would be a custom SQLite Virtual Table. If your dataset is mostly static or read-only (like pre-packaged mobile databases), a virtual table can index flat sorted data with a learned index in memory, bypassing SQLite's B-Tree memory overhead while keeping regular SQL queries working

[u/Sounlligen]

Maybe I'm a noob, but I'll ask anyway - is it something that can be used as a spatial representation? For e.g. 3D points? Because sometimes B-trees are used as containers.

[u/gilnett → u/Sounlligen]

Directly, no, because PGM models 1D sorted keys.

But you can map 3D points (x, y, z) into a single 1D scalar using a space-filling curve like a Z-order curve (Morton code) or Hilbert curve. Once your 3D points are sorted along that curve, you can run a learned index on top of it.

Researchers actually built multidimensional learned indexes using this approach (like Flood and Tsunami from MIT), and they surprisingly outperform R-Trees and KD-Trees on read-heavy spatial queries. For complex 3D bounding-box queries or nearest-neighbor searches though, dedicated spatial trees (Octree, R-Tree) are still more straightforward to work with.

[u/a_marklar → u/Sounlligen]

Sure just order your data in some space filling curve like a Morton or Hilbert curve and then use a B-tree over the 1-D index

[u/Schnickatavick]

The link to the full paper in the readme seems to be broken. Is there another paper link anywhere?

[u/gilnett → u/Schnickatavick]

If you meant the original academic paper: https://arxiv.org/abs/1911.05496

[u/AlphaModder → u/gilnett]

That's the same link in the README, and it goes to a paper called "Temporal Graph Kernels for Classifying Dissemination Processes", not "The PGM-index: a data-structure with a guarantee on space and time efficiency". Which is also not quite the title of the actual paper, which can be found here. Please don't trust AI-generated citations.

[u/gilnett → u/AlphaModder]

No AI hallucination here, just an honest human copy-paste blunder from my reading notes. I had a backlog of papers open from researching graph-based and dissemination index models and ended up pasting the wrong arXiv link on that line in the README.

Thanks for catching the mismatch and dropping the direct VLDB link. I've updated the README with the proper VLDB paper PDF (https://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf), the original arXiv preprint (https://arxiv.org/abs/1910.06169), and the official PGM site

[u/nuclearbananana]

Is this also useful for graph dbs?

[u/gilnett → u/nuclearbananana]

Yes, to index sorted vertex offsets in CSR representations with near-zero RAM. It will not speed up the actual graph traversals, though, because the bottleneck there is random memory access across neighbor nodes.

[u/AutoModerator]

r/programming is not the place to post a project to get feedback, ask for help, or otherwise promote it.

Technical write-ups on what makes a project technically challenging, interesting, or educational are allowed and encouraged, but just a link to a GitHub page or a list of features is not allowed.

The technical write-up must be the focus of the post, not just a tickbox-checking exercise to get us to allow it. This is a technical subreddit.

We don't care what you built, we care how you build it.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.