Notes / Prolly search

A search algorithm based on Probabilistic B-tree. Faster than the Binary search when the observations come from a Uniform Distribution.

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

Excerpts (1)

References (2)

Web (2)