Skip lists

A skip list is a sorted linked list with extra express lanes stacked on top, so you can skip over long stretches instead of walking every node. The bottom layer holds every item; each layer above holds a random subset of the one below, roughly half, chosen by coin flips when an item is inserted. To search, you race along the top lane until the next step would overshoot, drop down a level and repeat, much like taking an express train and switching to the local near your stop. On average that takes about log n steps, matching a balanced tree without any rebalancing logic. Redis uses skip lists for its sorted sets.