Geordnete Strukturen, die als balancierte Bäume aufgebaut sind, müssen nach jeder Aktualisierung neu balanciert werden, was Rotationen, Umfärbungen und sorgfältig gepflegte Invarianten bedeutet – all das ist leicht falsch zu machen und schwer zu parallelisieren.
Skip Lists tauschen diese Maschinerie gegen eine probabilistische Regel. Jeder Knoten erhält eine Ebene, die aus einer steil abfallenden Verteilung gezogen wird, sodass die meisten niedrig und eine Minderheit hoch liegt, und eine Suche kann über lange Strecken niedrigerer Ebenen springen, bevor sie hinabsteigt.
Da die Ebenen zufällig sind, ist die erwartete Anzahl von Knoten pro Ebene geometrisch, und Suche, Einfügen und Löschen liegen alle im Erwartungswert bei O(log n). Der Code ist kurz, und es muss im Nachhinein keine Buchführung betrieben werden.
Münzwürfe statt Rotationen sorgen für Balance
Zufällige Ebenen liefern die Höhenschranke ohne Code zum Neu-Balancieren.
Lokale, lock-freundliche Operationen machen die Parallelisierung einfach.
Einfachheit bedeutet weniger Invarianten, die gepflegt und falsch gemacht werden müssen.
Wenn deterministisches Neu-Balancieren der teure, fehleranfällige Teil ist, ersetze es durch ehrliche Zufälligkeit: lokale, einfache Operationen liefern dieselbe erwartete Leistung wie eine von Hand gepflegte Invariante.
Skip Lists wurden in Bibliotheken und Datenbanken zu einer Standardalternative zu Bäumen, am bekanntesten in Redis' Sorted Sets, wo die Einfachheit Nebenläufigkeit und vorhersagbare Leistung begünstigt.
DEN BELEGEN FOLGEN
Die Quellen
- Skip Lists: A Probabilistic Alternative to Balanced Trees William Pugh / University of Maryland · cs.umd.edu
- Skip list Wikipedia · en.wikipedia.org