Hacker News Reader

Comment by jsnell | Hacker News Reader

Other people have had trouble wringing competitive performance out of Bw-Trees despite heroic optimization efforts [0]. Why is this implementation going to beat other index structures with just a bit of tuning?

[0] https://news.ycombinator.com/item?id=17041616

View on HN

It might not. But the critiques of bw trees in terms of performance that I've seen have not had compelling data in terms of things that matter outside of academia or benchmarking shootouts, like write or space amplification. The bw tree is a cheap thing to abandon after I implement a persistent ART and measure it though. The bwtree is only like 1k of rust on top of the modular pagecache, which is the real heart of the system.

I am not familiar with bw-trees, but are you aware of this paper from this year’s SIGMOD?

https://db.cs.cmu.edu/papers/2018/mod342-wangA.pdf

Moving to ARTs (possibly combined with B+ trees) might be a smart choice after all.

Edit: sorry, I missed that grand-parent has cited the same paper already.

That paper is pretty good but it's comparing bw-tree with much simpler in memory data structures. I think bw-tress might work specially well for fast-disk storage.

This was my interpretation as well. I'm going to compare a disk-backed bwtree with a disk-backed ART, both backed by the same pagecache, and maybe end up with an ART that scatters partial pages on disk, bwtree style. But I need to measure apples to apples on the metrics that matter for storage first. The pagecache is where most of the complexity is in my implementation, and it makes building different kinds of persistent structures on top of it pretty easy. docs.rs/pagecache

>I think bw-tress might work specially well for fast-disk storage.

That's precisely the claim made in the original paper describing Bw-trees.

https://dl.acm.org/citation.cfm?id=2510649.2511251

Reply on news.ycombinator.com