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