Excerpts / B-Trees vs. Prolly Trees


OperationB-TreesProlly Trees
1 Random Readlogk(n)logk(n)
1 Random Writelogk(n)(1+k/w)*logk(n)
Ordered scan of one item with size zz/kz/k
Calculate diff of size dnd
Structural sharingNoYes

n: total leaf data in tree, k: average block size, w: window width