Search tools and guides ⌘K
Storage & Databases

Skip list

Probabilistic balanced search structure.

In plain terms

William Pugh, 1989. Tall nodes form an "express lane". Lock-free skip lists are easier to write than lock-free balanced trees — why Redis ZSET uses them.

Origin

William Pugh, "Skip Lists: A Probabilistic Alternative to Balanced Trees," CACM 1990. Easier to write lock-free than a balanced tree, which is why Redis ZSET uses them.

Where it shows up in production
  • Redis sorted sets (ZSET) Skip list + hash table backing every ZADD/ZRANGEBYSCORE.
  • LevelDB / RocksDB memtable Skip list of in-memory writes before flush to SSTable.
  • java.util.concurrent.ConcurrentSkipListMap Lock-free skip list in the JDK since 2004.
On Semicolony
Data structures data structures
Sources & further reading
Related Concepts Related Concepts
Simulator Red-Black Tree Simulator — the deterministic alternative Simulator B-Tree Simulator Simulator Storage Engine Simulator — memtable connection Guide Redis — sorted sets use skip lists Study Path Database Internals Study Path
Found this useful?