Die Skip-Liste ist eine 1989 von William Pugh vorgestellte randomisierte Datenstruktur, die die schnelle Suche eines balancierten Baums mit der Einfachheit einer verketteten Liste verbindet. Sie erreicht im Erwartungswert O(log n) für Suchen, Einfügen und Löschen.
So funktioniert eine Skip-Liste
Eine Skip-Liste ist eine sortierte, einfach verkettete Liste, über die mehrere zusätzliche Ebenen mit „Sprungzeigern" gelegt sind:
- Die unterste Ebene enthält alle Elemente in sortierter Reihenfolge.
- Jede höhere Ebene überspringt eine zufällige Teilmenge der Elemente — beim Aufbau entscheidet ein Münzwurf, ob ein Element in die nächste Ebene aufsteigt.
- Bei der Suche startet man auf der obersten Ebene und „springt" so lange vorwärts, bis das nächste Element zu groß ist; dann geht es eine Ebene tiefer weiter.
Dadurch halbiert sich die Anzahl der zu prüfenden Knoten pro Ebene — die Suchzeit wächst logarithmisch. Der Zufall sorgt dafür, dass die Struktur im Mittel balanciert bleibt, ohne aufwändige Rotationen wie in AVL- oder Rot-Schwarz-Bäumen.
Anwendungen
- Redis: Die Sorted Sets (ZSETs) basieren auf Skip-Listen — die Grundlage für Ranglisten und Leaderboards.
- LSM-Trees: Die MemTable vieler LSM-basierter Datenbanken (LevelDB, RocksDB, HBase) ist als Skip-Liste implementiert, weil Einfügungen sortiert und ohne Verschiebungen erfolgen.
- Concurrent-Container: In der Java-Bibliothek ConcurrentSkipListMap/Multithread-Umgebungen sind Skip-Listen einfacher zu synchronisieren als Bäume, da sie keine globalen Rebalancing-Operationen brauchen.
- Volltextsuche und Ranglisten: Überall dort, wo sortierte dynamische Daten mit vielen Einfügungen benötigt werden.
Bewertung
Gegenüber einem B-Baum oder Trie ist die Skip-Liste einfacher zu implementieren und bietet hervorragende Cache-Eigenschaften. Der Speicherbedarf ist mit durchschnittlich zwei Zeigern pro Knoten moderat — ein guter Kompromiss zwischen Einfachheit und Performance.
Verwandte Grundlagen: LSM-Tree, Bloom-Filter, Redis, In-Memory-Datenbank.