Skip List

Предпосылки: связный список (узел, указатели next), двоичное дерево поиска (инвариант, O(h) поиск, вырождение), оценка сложности O(…), базовое чтение Ruby (методы, блоки, массивы и хеши).

← Двоичное дерево поиска

Поиск в отсортированном списке

Возьмём отсортированный связный список. Вставить в него элемент — это поменять next у узла-предшественника: сама перестановка указателей занимает O(1). Но чтобы найти этого предшественника, приходится идти от начала узел за узлом, пока значения не перешагнут вставляемое, — а это O(n). Поиск в отсортированном списке упирается в ту же стену: чтобы найти значение, его не с чем сравнить, кроме как пройти всю цепочку по порядку.

Двоичное дерево поиска убирает эту стену: на каждом шаге сравнение отсекает половину оставшихся узлов, и в среднем поиск стоит O(log n). Но при неудачном порядке вставок дерево вырождается в ту же линейную цепочку и возвращает O(n). Дерево можно держать в форме принудительно — самобалансирующиеся деревья (AVL, red-black) после каждой вставки доворачивают часть узлов обратно к балансу и так гарантируют логарифмическую высоту. Цена — заметно более сложная реализация: правила доворота и инварианты, которые легко нарушить (механика этих деревьев — отдельная тема).

Skip list берёт другой путь к тому же логарифмическому поиску — и обходится без принудительной перестройки. Идея: оставить нижним слоем тот же отсортированный список, но надстроить над ним разреженные «экспресс-полосы», по которым поиск перепрыгивает сразу через много узлов. Сколько таких полос захватит конкретный элемент, решается броском монеты при вставке. Дальше — из чего эти полосы складываются и почему случайность даёт в среднем O(log n).

Уровни

Нижний уровень skip list — это и есть обычный отсортированный связный список всех элементов. Над ним лежат дополнительные уровни-«экспрессы»: каждый следующий хранит лишь часть элементов предыдущего, поэтому чем выше уровень, тем реже на нём узлы и тем длиннее прыжок между соседями. Один и тот же элемент может присутствовать сразу на нескольких уровнях — это не копии, а один узел, который держит по указателю на каждый уровень, где он есть.

Поиск всегда стартует из одной точки — головного узла (head). Это узел-страж: он не хранит данных, всегда стоит первым на каждом уровне и нужен только как вход. Чтобы он мог быть входом на любой уровень, у него заранее заведён массив указателей вперёд (forward) на максимально возможное число уровней MAX_LEVEL — по указателю на каждый.

Уровень 3:  head ─────────────────────────── 25 ──→ nil
                                              │
Уровень 2:  head ──────── 8 ──────────────── 25 ──→ nil
                           │                  │
Уровень 1:  head ── 3 ─── 8 ────── 15 ───── 25 ──→ nil
                    │      │        │         │
Уровень 0:  head ── 3 ─ 5 ─ 8 ─ 12 ─ 15 ─ 20 ─ 25 ──→ nil

Вертикальные чёрточки в схеме связывают уровни одного и того же узла: над числом 8 на уровне 0 стоят те же 8 на уровнях 1 и 2 — это один узел, видимый сразу с трёх полос, а не три отдельных. nil справа отмечает конец каждого уровня.

Уровень 0 содержит все 7 элементов. Уровень 1 — четыре. Уровень 2 — два. Уровень 3 — один. Каждый узел хранит массив forward ровно по числу уровней, на которых он есть: forward[0] ведёт к следующему узлу на нижнем уровне (тот самый next из обычного списка), forward[1] — к следующему узлу на уровне 1, и так далее. Узел 8 присутствует на уровнях 0–2, поэтому у него три указателя forward; узел 5, живущий только на уровне 0, — всего один.

Поиск

Поиск начинается с головного узла на самом верхнем уровне и идёт вправо, пока следующий элемент строго меньше искомого: тогда по нему можно прыгнуть, не проскочив цель. Как только следующий элемент оказывается больше искомого, прыгать нельзя — спускаемся на уровень ниже у текущего узла и продолжаем там, где прыжки короче. Равенство означает, что элемент найден.

Найдём элемент 15:

head (уровень 3) → 25 > 15, спускаемся
head (уровень 2) → 8 < 15, идём к 8
   8 (уровень 2) → 25 > 15, спускаемся
   8 (уровень 1) → 15 = 15, найден

Четыре сравнения вместо пяти при последовательном проходе уровня 0 (3 → 5 → 8 → 12 → 15). На больших списках выигрыш значительнее: при n = 1000 линейный поиск — до 1000 сравнений, skip list с p = 1/2 — порядка (1/p)·log₂(n) ≈ 20 сравнений.

Вероятностная конструкция

При вставке элемента нужно определить, на скольких уровнях он будет присутствовать. Skip list решает это случайно: элемент всегда попадает на уровень 0, а затем с вероятностью p «продвигается» на каждый следующий уровень. Продвижение продолжается, пока выпадает «успех», — как серия подбрасываний монеты.

randomLevel():
  level = 0
  while random() < p and level < MAX_LEVEL:
    level += 1
  return level

Параметр p определяет баланс между памятью и скоростью. При p = 1/2 (классическое значение из статьи Пью) каждый второй элемент в среднем поднимается на уровень 1, каждый четвёртый — на уровень 2, и так далее. Сложим средние «добавки» указателей: 1 на нижнем уровне, плюс 1/2 за уровень 1, плюс 1/4 за уровень 2 — сумма 1 + 1/2 + 1/4 + … стремится к 2. То есть в среднем узел держит около двух указателей — память растёт всего вдвое против обычного списка. При p = 1/4 (значение в хранилище Redis, ключ-значение с упорядоченными множествами) среднее число указателей — около 1.33: память экономится ценой чуть большей средней высоты, а значит чуть более длинного поиска.

Максимальный уровень обычно ограничивают: log₁/ₚ(n). Для p = 1/2 и n = 2¹⁶ это 16 уровней, для p = 1/4 и n = 2³² — тоже 16.

Вставка

Вставка состоит из двух шагов: найти позицию (как при поиске) и обновить указатели.

Сложность в том, что на каждом уровне, где появится новый узел, поменять forward придётся у его предшественника именно на этом уровне — а предшественники на разных уровнях разные. Поэтому во время поиска позиции алгоритм запоминает на каждом уровне последний узел, из которого пришлось спуститься ниже, — это и есть предшественник будущего узла на данном уровне. Запоминаем их в массив update: update[i] — предшественник на уровне i. После того как случайный уровень нового узла определён, остаётся на каждом из его уровней вклинить узел между update[i] и тем, на кого update[i] указывал.

Вставляем 10 (randomLevel вернул 1):
 
До:
Уровень 1:  head ── 3 ─── 8 ────── 15 ──→ nil
Уровень 0:  head ── 3 ─ 5 ─ 8 ─ 12 ─ 15 ──→ nil
 
update[0] = 8, update[1] = 8
 
При поиске позиции для 10 на уровне 1 дошли до 8 (следующий — 15 > 10, спускаемся) → предшественник на уровне 1 это 8. На уровне 0 от 8 следующий — 12 > 10, снова стоп → предшественник на уровне 0 тоже 8. Поэтому в `update` оба раза 8.
 
После:
Уровень 1:  head ── 3 ─── 8 ── 10 ── 15 ──→ nil
Уровень 0:  head ── 3 ─ 5 ─ 8 ─ 10 ─ 12 ─ 15 ──→ nil

Никаких ротаций. Указатели обновляются только на тех уровнях, где присутствует новый узел. Сложность — O(log n) в среднем (определяется стоимостью поиска позиции).

Удаление

Удаление зеркально вставке. Первый шаг — поиск удаляемого узла с заполнением массива update (как при вставке). Второй шаг — на каждом уровне, где присутствует удаляемый узел, forward-указатель предшественника из update перенаправляется на следующий узел: update[i].forward[i] = target.forward[i]. Единственное отличие от вставки — после удаления верхние уровни могут оказаться пустыми (head.forward[level] == nil). В таком случае текущая высота skip list уменьшается, чтобы поиск не тратил сравнения на пустые уровни.

Сложность

Операция	Средняя	Худшая	Комментарий
Поиск	O(log n)	O(n)	Худший случай — все элементы только на уровне 0
Вставка	O(log n)	O(n)	Определяется поиском позиции
Удаление	O(log n)	O(n)	Определяется поиском позиции
Память	O(n)	O(n log n)	В среднем ~n·(1/(1-p)) указателей

Худший случай O(n) возникает с исчезающе малой вероятностью — это аналог ситуации, когда все монеты выпали одинаково. На практике skip list работает стабильно на уровне O(log n).

Сравнение с деревьями

Аспект	Skip list	BST (несбалансированное)	Самобалансирующиеся деревья
Поиск (среднее)	O(log n)	O(log n)	O(log n)
Поиск (худшее)	O(n)*	O(n)	O(log n)
Вставка	O(log n)	O(log n)	O(log n) + перестройка
Реализация	Проще	Проще	Сложнее
Параллельный доступ	Проще (локальные изменения)	—	Сложнее (перестройка)
Диапазонные запросы	O(log n + k)**	O(log n + k)	O(log n + k)

* — вероятность экспоненциально мала. ** — k — количество элементов в диапазоне. На уровне 0 элементы уже отсортированы — достаточно найти начало и пройти по списку.

Главное преимущество skip list — простота. Вставка и удаление меняют указатели только у соседей нового или удаляемого узла на затронутых уровнях — обычно одного-двух. Самобалансирующемуся дереву, чтобы вернуть себе форму, приходится доворачивать сразу несколько узлов, иногда по цепочке вверх до самого корня. Меньше затронутых узлов — меньше кода, который легко ошибиться написать, и проще организовать одновременный доступ нескольких потоков: правка локальна, мешать друг другу почти негде.

Именно из-за локальности правок skip list популярен как структура для конкурентного доступа без общих блокировок — этим, например, пользуется ConcurrentSkipListMap из стандартной библиотеки Java. Как организовать такой доступ корректно — отдельная тема (согласование изменений без блокировок).

Простота реализации

Узел skip list хранит ровно две вещи — значение и массив forward с указателями вперёд по числу своих уровней:

Node = Struct.new(:value, :forward) do
  def initialize(value, level)
    super(value, Array.new(level + 1))  # по указателю на каждый из уровней узла
  end
end

Высота узла берётся из того самого броска монеты: уровень растёт, пока rand (случайное число в [0, 1)) выпадает меньше P.

def random_level
  level = 0
  level += 1 while rand < P && level < MAX_LEVEL
  level
end

Поиск, вставка и удаление — это пройденные выше шаги, переписанные на этих указателях: спуститься по уровням, по пути запоминая предшественников в update, и перецепить указатели у одного-двух соседей. Ни доворотов, ни инвариантов формы, которые надо чинить после каждой операции. Для сравнения: реализация red-black дерева хранит у каждого узла цвет, проверяет пять свойств дерева и поддерживает несколько видов доворотов узлов — отсюда и репутация skip list как «дерева без боли реализации».

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

Skip list берут там, где нужно упорядоченное множество с быстрыми операциями и при этом простым кодом. Хранилище Redis строит на нём Sorted Set (ZSET) — множество элементов, отсортированных по числовому ключу (с вероятностью продвижения 1/4). Встраиваемые хранилища LevelDB и RocksDB держат на skip list свежие записи в памяти (буфер, который порциями сбрасывается на диск): упорядоченность даёт быстрый поиск, а простота вставки — высокий темп записи. В стандартной библиотеке Java на нём построен ConcurrentSkipListMap — упорядоченное отображение, к которому несколько потоков обращаются без общих блокировок; на red-black дереве такое далось бы заметно сложнее.

Sources

• Pugh, W. Skip Lists: A Probabilistic Alternative to Balanced Trees, 1990.
• Redis source: src/t_zset.c, структуры zskiplist, zskiplistNode.
• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (CLRS), 4th ed.

---

← Двоичное дерево поиска