Balanced by a Coin: Skip Lists

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 54m

At midnight in Lisbon, Rosa Ferreira watches two million players flood a game's live leaderboard, which sits in one Redis sorted set, which is, as her colleague Jun delights in pointing out, a data structure balanced by flipping coins. In part nine of The Deep End's Data Structures series we build William Pugh's skip list, ride its express lanes by ear, compute a player's rank from spans, and see why LevelDB, RocksDB and Java's concurrent maps chose it for the one thing balanced trees do badly: sharing. Then a five-million-row query freezes the server for four seconds, and the fix has nothing…