Why do Redis sorted sets and LSM MemTables use skip lists instead of balanced trees?
Skip lists are simpler to implement and reason about, but the real win is concurrency. Insertion touches only a few forward pointers; no tree rotations cascade through multiple branches. This makes lock-free implementations dramatically simpler. Redis ZSET uses skip lists alongside hash tables for range queries and scoring; LSM MemTables use them to keep writes sorted in memory with minimal locking.
Answered in
Skip Lists: The Shortcut Nobody RotatesBalanced trees rebalance with rotations. Skip lists layer express lanes with random promotion—same O(log n) search, simpler locking.
Read the full analysisOther questions this article answers
More system design questions
- Why does an index's internal data structure matter if it all ends up 'faster than a scan'?
- Why is disk I/O the thing index structures are actually optimizing for?
- Why can't a hash index handle range queries?
- What makes a bitmap index different from a B-tree, and when is it better?
- Why do B-trees stay balanced automatically as data is inserted?
- Why does a database need an index at all — why can't it just scan the table?
- When is a hash index better than a B-tree index?
- What is a composite index and why does column order matter?
Every answer on Crashtech is written by the editor of the article it comes from — never auto-summarised. Browse all answers or the System Design beat.