Skip list
Probabilistisk datastruktur — en sorterad länkad lista med "expressar" på högre nivåer som låter dig hoppa över element. O(log n) förväntad tid.
William Pugh (1989) som enklare alternativ till balanserade träd. Varje nod har slumpvis många "uppåt-pekare" (klassiskt p=0.5 per nivå). Lookup: starta på toppen, hoppa höger så långt du kan, gå ner, upprepa.
Driver Redis sorted sets (ZSET), LevelDB/RocksDB memtable, Lucene posting lists. Vinst mot balanced trees: enklare lock-free-implementation, bättre cache locality. Förlorar: säkrad worst-case (kan vara O(n) i otur).