Skippowane listy: dyskretnie zastępcze ścieżki nad połączoną listą

Idea: tunelery nad posortowaną listą

Posortowana lista jednokierunkowa sprawia, że wyszukiwanie ma złożoność O(n): możesz poruszać się w dół tylko jednym węzłem na raz. Lista skippowana Williamego Pugh'a (1989) poprawia to tworząc dodatkowe

Tworzenie poziomów z rzutu monetą

Wysokość każdego węzła jest decydujona niezależnie, podczas wstawiania, przez powtarzane rzuty monetą: z prawdopodobieństwem p (zazwyczaj 1/2) jest przenoszone do kolejnego poziomu wyżej, a następnie to się powtarza, dopóki rzut nie przestanie się udawać. Brak globalnej balansowania, brak rotacji, brak kolorów — równowaga struktury wynika jedynie z prawdopodobieństwa.

randomLevel(p = 0.5, maxLevel):
  level = 1
  while random() < p and level < maxLevel:
    level += 1
  return level

insert(key):
  level = randomLevel()
  find the predecessor node at each level 1..level (search path)
  splice the new node into the forward pointers at each of those levels

Dlaczego oczekiwany czas wyszukiwania wynosi O(log n)

Z p = 1/2, około połowa węzłów na każdym poziomie jest przenoszona do kolejnego poziomu wyższego, więc oczekiwana liczba węzłów na poziomie k wynosi n/2^(k-1) — a oczekiwany najwyższy poziom wynosi około log2(n). Wyszukiwanie rozpoczęte od najwyższego poziomu i przesuwające się prawo-obocze lub w dół na każdym kroku zajmuje oczekiwane O(1) kroki na poziom (argument geometryczny ogranicza liczbę ruchów w prawo przed opuszczeniem poziomu), dla całkowitej oczekiwanej kosztu O(log n) na wszystkich poziomach. To odzwierciedla analizę równoważnego drzewa binarnego niemal dokładnie, ale z losowością w miejsce jasno określonego warunku balansowania.

Skip lists w porównaniu do drzew równych

Kompromis, jaki robią skippowane listy, jest szczerzy: zastępują gwarancję najgorszego przypadku na znacznie prostszą implementację. Wstawianie i usuwanie w skippowanej liście to tylko łączenie i odłączanie wskaźników po już znalezionym ścieżce wyszukiwania — bez rotacji, recoloringa ani cascadowych napraw. Ta prostość jest najważniejsza w kodzie równoległym, gdzie bezpieczna lub z graniastosłupowymi blokadami skippowana lista jest znacznie łatwiejsza do prawidłowej implementacji niż drzewo równoczesne bez blokady, ponieważ aktualizacje na różnych poziomach często mogą się przeprowadzać niezależnie.

Gdzie są wykorzystywane w produkcyjnych systemach

Redis implementuje typ zagnieżdżony (ZSET) za pomocą listy skippowanej połączonej z tabelą hash, konkretnie dlatego, że listy skippowane ułatwiają realizację zapytań zakresowych ("podaj mi 10 najwyższych wyników") i wykonywanie operacji rankingu wraz z czasowym złożonościem O(log n) do wstawiania i usuwania. Wiele silników magazynowania opartych na drzewach LSM, w tym memtable w LevelDB i RocksDB, używa listy skippowanej jako buforu uporządkowanego w pamięci, do którego zapisy przychodzące docierają przed usunięciem do dysku, co ponownie przeważy prostota i współbieżne zapisy bez blokady nad szybszym drzewem równoważnym.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Skip List — Probabilistic Balanced Search i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.