Skip-Liste
Probabilistische Datenstruktur — eine sortierte verkettete Liste mit „Express"-Spuren auf höheren Ebenen, die das Überspringen von Elementen erlauben. O(log n) erwartete Zeit.
William Pugh (1989) als einfachere Alternative zu balancierten Bäumen. Jeder Knoten hat eine zufällige Anzahl von „Nach-oben-Zeigern" (klassisch p=0,5 pro Ebene). Lookup: oben anfangen, so weit wie möglich nach rechts springen, eine Ebene runter, wiederholen.
Treibt Redis Sorted Sets (ZSET), die LevelDB/RocksDB-Memtable und Lucene-Posting-Lists an. Vorteil gegenüber balancierten Bäumen: einfachere Lock-free-Implementierung, bessere Cache-Lokalität. Nachteil: kein garantierter Worst-Case (kann bei Pech O(n) sein).