News for hackers. Stuff that matters.
Re:An embedded database written in Rust by jsnell on Monday May 28, 2018 @04:55AM (#17171363)
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

Re:An embedded database written in Rust by krenoten on Monday May 28, 2018 @05:10AM (#17171429)
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.
Re:An embedded database written in Rust by lifepillar on Monday May 28, 2018 @07:50AM (#17171929)
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.

Re:An embedded database written in Rust by arthursilva on Monday May 28, 2018 @07:42AM (#17171902)
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.
Re:An embedded database written in Rust by krenoten on Monday May 28, 2018 @08:18AM (#17172022)
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
Re:An embedded database written in Rust by stult on Monday May 28, 2018 @08:46AM (#17172119)
>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