News for hackers. Stuff that matters.
Re:Static search trees: 40x faster than binary search by tmyklebu on Wednesday January 01, 2025 @12:08AM (#42564103)
There are theory papers on "buffer trees"---B-trees where each node is augmented with an O(B)-length array of pending updates and queries. I believe there were also some attempts at building SQL databases based on them. It sounds like you're reaching for the same trick.
Re:Static search trees: 40x faster than binary search by koverstreet on Wednesday January 01, 2025 @12:30AM (#42564169)
that's a hybrid compacting data structure: compacting within the btree node, normal btree topology otherwise.

And it works much better than pure compacting (i.e. the leveldb lineage), because you avoid lock contention at the root on multithreaded update workloads, and the compaction/resort is much lower overhead when it fits in l2.

incidentally, there's a filesystem that uses this technique.

Re:Static search trees: 40x faster than binary search by loeg on Wednesday January 01, 2025 @01:10AM (#42564274)
> incidentally, there's a filesystem that uses this technique.

BetrFS?

Re:Static search trees: 40x faster than binary search by loeg on Wednesday January 01, 2025 @10:49PM (#42571465)
Sounds like "fractal trees" and TokuDB.