The Skip List Idea

A skip list is a probabilistic alternative to balanced binary search trees. Same operations (search, insert, delete in O(log n)) but simpler and lock-friendly for concurrent access.

The idea: a sorted linked list where some nodes have "express lanes" to skip ahead.

Level 3:  HEAD -------------------> 30 -------------------> 90
Level 2:  HEAD ------> 10 ----------> 30 -------> 60 ------> 90
Level 1:  HEAD --> 5 -> 10 ---> 20 -> 30 -> 50 -> 60 -> 70 -> 90
Level 0:  HEAD --> 5 -> 10 -> 15 -> 20 -> 30 -> 50 -> 60 -> 70 -> 90

To search for 50:

1. Start at HEAD level 3. 30 < 50, go to 30. Next is 90, too big.
2. Drop to level 2. 60 > 50, drop again.
3. Level 1: 50 found at the next node.

Each level has roughly half as many nodes as the level below. Searching is O(log n) on average.

Used by:

• Redis sorted sets (ZSET)
• LevelDB / RocksDB memtables
• Java ConcurrentSkipListMap
• Apache Cassandra

Skip lists shine because they're simple to implement compared to red-black or B-trees.