3 ms·

Also curious to hear what people think of Bf-tree. https://vldb.org/pvldb/vol17/p3442-hao.pdf https://github.com/microsoft/bf-tree

bddicken 6mo ago
I've read this paper and it's a neat idea. It hasn't been introduced into popular oss databases like postgres and mysql, and my understanding is it has some drawbacks for real prod use vs ths simplistic benchmarks presented in the paper. Would love to know if anyones built something using it outside of academic testing.
infogulch 6mo ago
Another interesting tree filesystem data structure is the Bε-tree ("b epsilon tree"), which also tries to bridge the gap between small writes and the large pages of modern drives. The first paper/talk from 2015 has a fun name "BetrFS: A Right-Optimized Write-Optimized File System" and they published a few dozen times until 2022. https://www.betrfs.org/ https://www.betrfs.org/
ozgrakkurt 6mo ago
The idea seems like it should work but it is questionable what cases will it be better in. B+tree and LSM-tree are very developed and are kind of optimal. They are also fairly easy to beat for a given specific use case. I guess they have a concrete case that has benefitted from this design or this was an attempt at doing that. Would be interesting to read about that specific case they had. I just skimmed the paper, so I'm sorry if they explained it in the middle somewhere. Also I tried some other databases that claim to be better than rocksdb but it just is miles better than other databases when I needed large scale (couple billions of 32byte keys mapped to 8byte values). I tried MDBX(LMDB), sled (also claimed read AND write optimized). Tried sharding and all configuration options with both. Reading papers about database research unfortunately feels like reading LLM output because I have to sift through a lot of fluff, and I have to know exactly that the thing is about and the surrounding ideas. I am not super knowledgeable in this field so this might be just a skill issue, but I would recommend seeing it this way. This paper also writes about variable sized pages so it might be relevant to understanding what the trade-offs might be. https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf Also another thing I highly recommend is to always judge by hardware limits vs db measurement instead of looking at graphs in paper. If something is doing 1GB/s write on an ssd that can do 7GB/s than it is bad at writes. It doesn't matter if it looks cool on a graph. This is kind of a crude way of seeing it but it is at least reliable.

bddicken 6mo ago

I've read this paper and it's a neat idea. It hasn't been introduced into popular oss databases like postgres and mysql, and my understanding is it has some drawbacks for real prod use vs ths simplistic benchmarks presented in the paper. Would love to know if anyones built something using it outside of academic testing.

infogulch 6mo ago

Another interesting tree filesystem data structure is the Bε-tree ("b epsilon tree"), which also tries to bridge the gap between small writes and the large pages of modern drives. The first paper/talk from 2015 has a fun name "BetrFS: A Right-Optimized Write-Optimized File System" and they published a few dozen times until 2022. https://www.betrfs.org/ https://www.betrfs.org/

ozgrakkurt 6mo ago

The idea seems like it should work but it is questionable what cases will it be better in. B+tree and LSM-tree are very developed and are kind of optimal. They are also fairly easy to beat for a given specific use case. I guess they have a concrete case that has benefitted from this design or this was an attempt at doing that. Would be interesting to read about that specific case they had. I just skimmed the paper, so I'm sorry if they explained it in the middle somewhere. Also I tried some other databases that claim to be better than rocksdb but it just is miles better than other databases when I needed large scale (couple billions of 32byte keys mapped to 8byte values). I tried MDBX(LMDB), sled (also claimed read AND write optimized). Tried sharding and all configuration options with both. Reading papers about database research unfortunately feels like reading LLM output because I have to sift through a lot of fluff, and I have to know exactly that the thing is about and the surrounding ideas. I am not super knowledgeable in this field so this might be just a skill issue, but I would recommend seeing it this way. This paper also writes about variable sized pages so it might be relevant to understanding what the trade-offs might be. https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf https://db.in.tum.de/~freitag/papers/p29-neumann-cidr20.pdf Also another thing I highly recommend is to always judge by hardware limits vs db measurement instead of looking at graphs in paper. If something is doing 1GB/s write on an ssd that can do 7GB/s than it is bad at writes. It doesn't matter if it looks cool on a graph. This is kind of a crude way of seeing it but it is at least reliable.