案例库 · 工程与运营 · 技术决策 · 1989–1990
这条还没译成中文，下面是英文原文。
Skip lists used coin flips instead of rotations to stay balanced
William Pugh's skip list assigns each node a level with a coin flip, getting expected log(n) operations with far simpler code than a balanced tree.
University of Maryland
那一手
Ordered structures built as balanced trees must re-balance after each update, which means rotations, recolouring and careful invariants - all of it easy to get wrong and awkward to parallelise.
Skip lists swap that machinery for a probabilistic rule. Each node is given a level drawn from a steeply falling distribution, so most are low, a minority are high, and a search can jump over long stretches of lower levels before dropping down.
Because levels are random, the expected number of nodes per level is geometric and search, insert and delete all land in expectation at O(log n). The code is short, and no bookkeeping has to be performed after the fact.
为什么管用
- Random levels give the height bound without re-balancing code.
- Local, lock-friendly operations make it easy to parallelise.
- Simplicity means fewer invariants to maintain and get wrong.
可以搬走什么
When deterministic re-balancing is the expensive, error-prone part, replace it with honest randomness: local, simple operations give the same expected performance as a hand-maintained invariant.
后来呢
Skip lists became a standard alternative to trees in libraries and databases, most famously Redis's sorted sets, where the simplicity aids concurrency and predictable performance.
资料来源
发现哪里写错了？告诉我们。