---
title: "Skip Lists: A Probabilistic Alternative to Balanced Trees"
description: "Skip Lists asks whether a sorted linked list can search like a balanced tree without rotations or global rebalancing. Read it to see how random node heights create sparse express lanes, how an advance-or-drop search finds a key in expected logarithmic time, and why the result trades a strict worst-case guarantee for simpler local updates and a tunable pointer budget."
canonical_url: "https://fanout.sh/daily/2026-09-19-skip-lists-probabilistic-balancing"
md_url: "https://fanout.sh/daily/2026-09-19-skip-lists-probabilistic-balancing.md"
last_updated: "2026-09-19"
access: "public"
---

# Skip Lists: A Probabilistic Alternative to Balanced Trees

Skip Lists asks whether a sorted linked list can search like a balanced tree without rotations or global rebalancing. Read it to see how random node heights create sparse express lanes, how an advance-or-drop search finds a key in expected logarithmic time, and why the result trades a strict worst-case guarantee for simpler local updates and a tunable pointer budget.

## Paper details

- Authors: William Pugh

- Venue: Communications of the ACM 1990

- Track: Systems

- Difficulty: Easy

- Reading time: 30 min

- Original paper: https://doi.org/10.1145/78973.78977

## What you will learn

- How randomly promoted node towers turn one sorted base list into progressively sparser express levels.

- Why search advances while the next pointer stays below the target, then drops a level when the next jump would overshoot.

- How promotion probability trades pointer space, constant factors, and run-time variability without creating a worst-case guarantee.

## Continue exploring

[Explore database indexing in Fanout](https://fanout.sh/system/archive/database-indexing): Connect the skip list's in-memory ordered-dictionary mechanism to Fanout's broader indexing path, including B-trees, page locality, query shapes, and the storage boundary that changes which structure fits.

---
This representation contains public Fanout content only. Protected Pro lessons, account data, billing, checkout, and pricing are not included.

Browse the public content map: https://fanout.sh/sitemap.md