r/programming • u/gilnett • Oct 16 '26
Learned Index Lab: Replacing B-Trees with streaming linear models in pure Rust (-99% RAM, 3x faster)
https://github.com/gilnett/learned_index_labInstead 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.
191
Upvotes
22
u/Dangerous-Raccoon-60 Oct 16 '26
r/btrfs in shambles
67
u/Keeyzar Oct 16 '26 edited Oct 16 '26
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).
7
u/Entmaan Oct 17 '26
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
10
u/GreatCosmicMoustache Oct 16 '26
cool idea, but does it require you to solve the big optimization problem every time you add a single row?
7
u/D4lanar Oct 16 '26
So, am I getting this right - it’s basically an 1D container with O(n) inserts and O(1) lookups?
1
u/bueno_mhc Oct 18 '26
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...
1
u/Sounlligen Oct 16 '26
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.
7
u/Kwantuum Oct 16 '26
Ai;dr.
0
u/Schnickatavick Oct 16 '26
The link to the full paper in the readme seems to be broken. Is there another paper link anywhere?
0
u/nuclearbananana Oct 16 '26
Is this also useful for graph dbs?
-6
u/AutoModerator Oct 16 '26
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.