Skip Lists are pretty awesome

I believe Redis makes use of these for sorted sets.