Структуры данных

Skip List: Вероятностная альтернатива деревьям

Цели урока

  • Понять идею 'экспресс-полос' в связном списке
  • Реализовать поиск, вставку и удаление
  • Понять роль рандомизации для балансировки
  • Узнать где Skip List используется на практике

Предварительные знания

  • Связные списки
  • Вероятность
  • Связные списки

Балансировка деревьев - это сложно: AVL, Red-Black, Splay... А что если заменить сложную логику на подбрасывание монетки? Skip List делает именно это - и работает в Redis, обрабатывающем миллионы запросов в секунду.

  • Redis - Sorted Sets для лидербордов и очередей
  • LevelDB - memtable в storage engine
  • Apache Lucene - индексы для Elasticsearch
  • Java ConcurrentSkipListMap - thread-safe sorted map

William Pugh и вероятностная альтернатива сбалансированным деревьям

Уильям Пью, информатик из Мэрилендского университета, представил Skip List в статье 1990 года под названием «Skip Lists: A Probabilistic Alternative to Balanced Trees» (черновик 1989 года, публикация в Communications of the ACM в 1990-м). Его целью была структура, столь же быстрая, как сбалансированное дерево, но гораздо более простая в написании и понимании. Ключевой ход состоял в том, чтобы полностью отказаться от детерминированной балансировки: вместо ротаций каждый узел поднимается на верхние уровни серией подбрасываний монетки, так что ожидаемое число уровней логарифмично, и структура остаётся в среднем сбалансированной без какой-либо явной работы. Платой становится вероятностный, а не гарантированный худший случай, но шансы на плохую раскладку исчезающе малы. Дизайн доказал свою состоятельность в продакшене: Redis реализует sorted sets через Skip List, а LevelDB использует его для буфера записи в памяти.

Проблема связных списков

**Связный список:** вставка O(1), но поиск O(n). Дерево: поиск O(log n), но нужна балансировка (AVL, Red-Black).

**Вопрос:** можно ли получить O(log n) без сложной балансировки?

**Skip List (1990):** William Pugh придумал добавить 'экспресс-полосы' к списку. Результат - O(log n) в среднем, простая реализация!

Skip List решает проблему:

Идея: Уровни 'экспресс-полос'

Представьте метро: есть обычные станции, а есть экспресс-линии, которые останавливаются только на крупных пересадках.

**Поиск 35:** Level 3→50 (слишком много), Level 2→20→50 (слишком много), Level 1→30→40 (перескочили), Level 0→35 ✓

Чем выше уровень - тем меньше узлов, тем быстрее перемещение. Но нужно спуститься для точного поиска.

На верхних уровнях Skip List:

Поиск: Сверху вниз, слева направо

**Сложность:** O(log n) в среднем. На каждом уровне делаем O(1) шагов, уровней O(log n).

Поиск в Skip List начинается с:

Вставка: Рандомизированные уровни

**Главный приём:** уровень нового узла определяется случайно! Подбрасываем монетку: орёл → добавляем уровень.

Это создаёт структуру похожую на сбалансированное дерево - **без явной балансировки!** Вероятность 'плохой' структуры экспоненциально мала.

Уровень нового узла в Skip List:

Полная реализация

Сложность операций Skip List в среднем:

Где используется Skip List

  • **Redis** - Sorted Sets реализованы через Skip List
  • **LevelDB/RocksDB** - memtable для быстрой записи
  • **Lucene** - индексация для полнотекстового поиска
  • **ConcurrentSkipListMap (Java)** - lock-free concurrent map

**Почему Redis выбрал Skip List вместо Red-Black Tree?** 1. Проще реализовать (меньше багов) 2. Легче параллелить (lock-free версии) 3. Range queries естественны (просто идём по level 0) 4. Константы меньше на практике

КритерийSkip ListRed-Black Tree
СложностьПростаяСложная (ротации)
Range queriesЕстественныеТребуют обхода
ПараллелизмLock-free возможенСложно
ПамятьБольше (указатели)Меньше
Worst caseO(n) теоретическиO(log n) гарантировано

Redis использует Skip List потому что:

Skip List

  • Связный список + уровни 'экспресс-полос'
  • O(log n) поиск, вставка, удаление в среднем
  • Уровень узла определяется случайно (монетка)
  • Проще деревьев, легче параллелить
  • Используется в Redis, LevelDB, Lucene

Связанные темы

Skip List - альтернатива сбалансированным деревьям. Для персистентного хранения есть B-Tree - структура, оптимизированная для дисков.

  • B-Tree — Деревья для баз данных

Связанные уроки

  • ds-02-linked-lists — Skip List - это связный список с надстроенными быстрыми уровнями
  • ds-12-balanced-trees — Даёт O(log n) поиск без перебалансировки дерева
  • ds-23-btree — Обе хранят отсортированные данные с поиском за O(log n)
  • prob-09-discrete-dist — Случайный выбор уровня подчиняется геометрическому распределению
  • db-19-redis — Sorted set в Redis внутри построен на skip list
  • alg-10-binary-search
Skip List: Вероятностная альтернатива деревьям

0

1

Войти