#skip-lists

Skip Lists: The Structure Redis Chose Over Balanced Trees

Skip lists replace tree rotations with coin flips: expected O(log n) search, insert, and delete in ~40 lines. Why Redis, LevelDB, and Java picked them.