Prolly Trees | Dolt Documentation
Excerpts
Operation | B-Trees | Prolly Trees |
---|---|---|
1 Random Read | logk(n) | logk(n) |
1 Random Write | logk(n) | (1+k/w)*logk(n) |
Ordered scan of one item with size z | z/k | z/k |
Calculate diff of size d | n | d |
Structural sharing | No | Yes |
n
: total leaf data in tree, k
: average block size, w
: window width