Skip lists: a probabilistic alternative to balanced trees
William White Tison Pugh · Communications of the ACM · 1990
Skip lists are data structures that use probabilistic balancing rather than strictly enforced balancing. As a result, the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.