Skip Lists

Also Known As

TL;DR

Explanation

A skip list is a layered linked list: the bottom layer has all elements in sorted order; each higher layer contains a random subset of the elements below, acting as express lanes. Search: start at the top layer, move right until the next element is too large, then drop down — O(log n) expected. Insert: coin flips determine which layers the new element appears in. Redis uses skip lists for sorted sets (ZADD/ZRANGE). Advantages over balanced BSTs: simpler implementation, easier lock-free concurrent modification.

Common Misconception

Why It Matters

Common Mistakes

• Fixed levels instead of probabilistic promotion — breaks expected O(log n)
• Maximum level too low — degrades to O(n)
• Using skip list where a hash map suffices — add ordering only when needed
• Concurrent modifications without proper synchronisation

Code Examples

// Assuming zadd is O(1):
for ($i = 0; $i < 1000000; $i++) {
    $redis->zadd('leaderboard', $score, $userId);
    // 1M * O(log n) = O(n log n) total — expected but surprising
}

// Pipeline for bulk inserts:
$pipeline = $redis->pipeline();
foreach ($scores as $userId => $score) {
    $pipeline->zadd('leaderboard', $score, $userId);
}
$pipeline->execute(); // Single round trip for all insertions

References

• ↗ https://en.wikipedia.org/wiki/Skip_list

Tags

Related Terms