The Random Buffer Tree : A Randomized Technique for I/O-efficient Algorithms

Saju Jude Dominic, G. Sajith

In this paper, we present a probabilistic self-balancing dictionary data structure for massive data sets, and prove expected amortized I/O-optimal bounds on the dictionary operatio…