Skip-Liste

Kurz: Eine Skip-Liste ist eine sortierte verkettete Liste mit zusätzlichen „Überholspuren”, sodass man Elemente in durchschnittlich O(log n) finden kann.

Genauer: Die unterste Ebene enthält alle Elemente. Jede höhere Ebene enthält zufällig ausgewählt etwa die Hälfte der Elemente der Ebene darunter. Die Suche beginnt oben, springt weit und steigt ab, wenn sie zu weit gekommen wäre.

Im Detail

• Einfügen: Element unten einfügen, dann per Münzwurf entscheiden, in wie vielen Ebenen es zusätzlich auftaucht.
• Vorteil gegenüber Bäumen: Einfacher zu implementieren, gut für gleichzeitigen Zugriff, weil weniger umgebaut werden muss.
• Nachteil: Etwas mehr Speicher für die Zeiger, Laufzeit nur im Durchschnitt garantiert.
• Einsatz: Redis (sortierte Mengen), LevelDB-/RocksDB-Memtables.

Siehe auch: B-Baum und B+-Baum