I've been looking at Prolly Trees in-depth and they're pretty neat! They have nice properties like:
- self-balancing (probabilistically!)
- unicit (the same data in the tree results in the same tree)
- fast comparisons (they're a Merkle tree, so just comparing root hashes is enough)
The original formulation for Prolly Trees had an expected node size of the target node size, but its standard deviation was geometric. That meant there was a long tail of node sizes far beyond the target node size.
The Dolt formulation is pretty neat. Chef's kiss. It uses the current chunk size thus-far as input into a cumulative distribution function to shape the node size into a normal distribution. So now the standard deviation is under control. But now, the decision to split a node is no longer independent. It now depends on the chunk size so far, which means a decision to rebalance nodes after an insert could potentially cascade to the entire right side of the tree with decreasing probability.
But good news! This can be mitigated by increasing the target node size or by relaxing the target std dev of the node sizes. I detail the investigation here:
https://interjectedfuture.com/lab-notes/lab-note-033-cascadi...
- self-balancing (probabilistically!)
- unicit (the same data in the tree results in the same tree)
- fast comparisons (they're a Merkle tree, so just comparing root hashes is enough)
The original formulation for Prolly Trees had an expected node size of the target node size, but its standard deviation was geometric. That meant there was a long tail of node sizes far beyond the target node size.
The Dolt formulation is pretty neat. Chef's kiss. It uses the current chunk size thus-far as input into a cumulative distribution function to shape the node size into a normal distribution. So now the standard deviation is under control. But now, the decision to split a node is no longer independent. It now depends on the chunk size so far, which means a decision to rebalance nodes after an insert could potentially cascade to the entire right side of the tree with decreasing probability.
But good news! This can be mitigated by increasing the target node size or by relaxing the target std dev of the node sizes. I detail the investigation here:
https://interjectedfuture.com/lab-notes/lab-note-033-cascadi...