The relevant paper, "Skip Lists: A Probabilistic Alternative to Balanced Trees": http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117...