3 ms·

Other people have had trouble wringing competitive performance out of Bw-Trees despite heroic optimization efforts [0]. Why is this implementation going to beat

• krenoten 8y ago
  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.
  • lifepillar 8y ago
    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 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.
• arthursilva 8y ago
  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.
  • krenoten 8y ago
    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
  • stult 8y ago
    >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 https://dl.acm.org/citation.cfm?id=2510649.2511251