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/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/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/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/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.