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/
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.
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.
I keep hearing about the downside of B(+)-Trees for DBs, that they have issues for certain scenarios, but I've never seen a simple, detailed list about them, what they are, and the scenarios they perform badly in.
"The deeper the tree, the slower it is to look up elements. Thus, we want shallow trees for our databases!"
With composite indices in InnoDB it's even more important to keep the tree streamlined and let it fan out according to data cardinality: https://news.ycombinator.com/item?id=34404641
I've known for a long time that you usually want b-tree in Postgres/MySQL, but never understood too well how those actually work. This is the best explanation so far.
Also, for some reason there have been lots of HN articles incorrectly advising people to use uuid4 or v7 PKs with Postgres. Somehow this is the first time I've seen one say to just use serial.
I always thought this was too complicated to every really understand how it worked, especially the lock policy, but now with LLMs (assisted with sqlite’s very comprehensive comment policy) even a relative neophyte can start to understand how it all works together. Also the intro to the file is worth reading today:
* 2004 April 6
*
* The author disclaims copyright to this source code. In place of
* a legal notice, here is a blessing:
*
* May you do good and not evil.
* May you find forgiveness for yourself and forgive others.
* May you share freely, never taking more than you give.
*
*************************************
* This file implements an external (disk-based) database using BTrees.
* See the header comment on "btreeInt.h" for additional information.
* Including a description of file format and an overview of operation.
*/
15 comments
[ 3.9 ms ] story [ 37.8 ms ] threadhttps://planetscale.com/learn/courses/mysql-for-developers
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
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.
With composite indices in InnoDB it's even more important to keep the tree streamlined and let it fan out according to data cardinality: https://news.ycombinator.com/item?id=34404641
Also, for some reason there have been lots of HN articles incorrectly advising people to use uuid4 or v7 PKs with Postgres. Somehow this is the first time I've seen one say to just use serial.
https://github.com/sqlite/sqlite/blob/master/src/btree.c
I always thought this was too complicated to every really understand how it worked, especially the lock policy, but now with LLMs (assisted with sqlite’s very comprehensive comment policy) even a relative neophyte can start to understand how it all works together. Also the intro to the file is worth reading today:
* 2004 April 6 * * The author disclaims copyright to this source code. In place of * a legal notice, here is a blessing: * * May you do good and not evil. * May you find forgiveness for yourself and forgive others. * May you share freely, never taking more than you give. * ************************************* * This file implements an external (disk-based) database using BTrees. * See the header comment on "btreeInt.h" for additional information. * Including a description of file format and an overview of operation. */