Les structures ordonnées construites comme des arbres équilibrés doivent se rééquilibrer après chaque mise à jour, ce qui implique des rotations, des recoloriages et des invariants délicats - autant de choses faciles à mal faire et peu commodes à paralléliser.
Les listes à sauts remplacent cette mécanique par une règle probabiliste. Chaque nœud reçoit un niveau tiré d'une distribution à décroissance rapide, de sorte que la plupart sont bas, une minorité sont hauts, et une recherche peut sauter par-dessus de longues portions de niveaux inférieurs avant de descendre.
Comme les niveaux sont aléatoires, le nombre attendu de nœuds par niveau est géométrique et la recherche, l'insertion et la suppression se situent toutes en espérance à O(log n). Le code est court, et aucune comptabilité ne doit être effectuée après coup.
Que des lancers de pièce, et non des rotations, maintiennent l'équilibre
Des niveaux aléatoires donnent la borne de hauteur sans code de rééquilibrage.
Des opérations locales, adaptées aux verrous, facilitent la parallélisation.
La simplicité signifie moins d'invariants à maintenir et à mal faire.
Lorsque le rééquilibrage déterministe est la partie coûteuse et sujette aux erreurs, remplacez-le par un aléatoire honnête : des opérations locales et simples donnent la même performance attendue qu'un invariant maintenu à la main.
Suites
Les listes à sauts sont devenues une alternative standard aux arbres dans les bibliothèques et les bases de données, le plus célèbre étant les ensembles triés de Redis, où la simplicité favorise la concurrence et une performance prévisible.
VÉRIFIEZ LES SOURCES
Les sources
- Skip Lists: A Probabilistic Alternative to Balanced Trees William Pugh / University of Maryland · cs.umd.edu
- Skip list Wikipedia · en.wikipedia.org