Bf-Tree: modern read-write-optimized concurrent larger-than-memory range index • Hacker News Board

Re: Bf-Tree: modern read-write-optimized concurrent larger-than-memory range index

#21

Post by namibj » Thu, Jan 29, 2026, 2:58 PM UTC

koverstreet wrote: post #11

fuzzybear3965 wrote: post #10

Earlier quoted context omitted.

Sure, but on principle, looking at the paper, I'd expect it to outperform B-trees since write amplification is reduced, generally. You thinking about cases requiring ordering of writes to a given record (lock contention)?

I think their claims of write amplification reduction are a bit overstated given more realistic workloads. It is true that b-trees aren't ideal in that respect, and you will see some amount of write amplification, but not enough that it should be a major consideration, in my experience You really have to take into account workingset size and cache size to make any judgements there; your b-tree writes should be given…

Also you can use dense B+-Trees for reads possibly with some bloom filters or the like if you expect/profile a high fraction of negative lookups, use LSM to eventually compact, and get both SSD/ZNS friendly write patterns as well as full freedom to only compact a layer once it's finer state is no longer relevant to any MVCC/multi-phase-commit schemes. Being able to e.g. run a compression algorithm until you just exceed the storage page size, take it's state from just before it exceeded, and begin the next bundle with the entry that made you exceed the page size.... It's quite helpful when storage space or IO bandwidth is somewhat scarce.

If you're worried about the last layer being a giant unmanageably large B+-Tree, just shard it similarly in key space to not need much free temporary working space on SSD to stream the freshly compacted data to while the inputs to the compaction still serve real time queries.

Re: Bf-Tree: modern read-write-optimized concurrent larger-than-memory range index

#22

Post by SchwKatze » Thu, Jan 29, 2026, 4:16 PM UTC

pgwhalen wrote: post #20

yxhuvud wrote: post #19

Was the link changed? Right now it points to the github page, and it doesn't really say why anyone would care about it.

The top of the readme links to the accompanying paper, which explains very clearly why you would care: https://badrish.net/papers/bftree-vldb2024.pdf I admit I’ll agree that that extra hop was a little confusing to me though. I guess people just like GitHub and don’t like PDFs.

That's on me, I thought it would receive the attention it deserves if people jump straight into the code (and see the "written in Rust btw").

Re: Bf-Tree: modern read-write-optimized concurrent larger-than-memory range index

#23

Post by algorithmsRcool » Fri, Jan 30, 2026, 1:07 AM UTC

reactordev wrote: post #8

algorithmsRcool wrote: post #4

I get excited every time I see a paper from Bradish. I've learned so much about high performance software from studying systems that he has worked on. (not to diminish his many co-authors and contributors) Some of his other projects: [0] https://github.com/microsoft/garnet [1] https://github.com/microsoft/FASTER [2] https://github.com/microsoft/Trill

You should check out Microsoft Orleans https://github.com/dotnet/orleans

I am very familiar with it! My current project at work is taking an Orleans based payment processing system to production

Re: Bf-Tree: modern read-write-optimized concurrent larger-than-memory range index

#24

Post by reactordev » Fri, Jan 30, 2026, 1:54 AM UTC

algorithmsRcool wrote: post #23

reactordev wrote: post #8

Earlier quoted context omitted.

You should check out Microsoft Orleans https://github.com/dotnet/orleans

I am very familiar with it! My current project at work is taking an Orleans based payment processing system to production

Nice!!

I’ve only played with it at scale and haven’t had the balls to do production with it. We are still heavily reliant on our k8s stack but I want to go bare metal with Orleans.