Skip List

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

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

Отсортированный связный список позволяет вставить элемент за O(1), если известна позиция. Но найти эту позицию — O(n): приходится пройти все узлы последовательно. BST решает проблему поиска за O(log n) в среднем случае, но при неудачном порядке вставок вырождается в список и даёт O(n). Чтобы гарантировать логарифмическую высоту, самобалансирующиеся деревья после каждой вставки или удаления перестраивают часть структуры. Это работает, но усложняет реализацию и затрудняет параллельный доступ: перестройка затрагивает несколько узлов одновременно, и все они должны быть заблокированы.

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

Устройство: уровни

Нижний уровень skip list — обычный отсортированный связный список всех элементов. Над ним строятся дополнительные уровни: каждый содержит подмножество элементов нижнего. Чем выше уровень, тем меньше в нём элементов. Специальный головной узел (head) присутствует на всех уровнях — это sentinel без значения, его массив 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

Уровень 0 содержит все 7 элементов. Уровень 1 — четыре. Уровень 2 — два. Уровень 3 — один. Каждый узел хранит массив указателей forward: по одному на каждый уровень, на котором он присутствует. Узел 8 присутствует на уровнях 0–2, поэтому у него три forward-указателя.

Поиск

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

Найдём элемент 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, и так далее. Среднее число указателей на узел — 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.

Вставка

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

При спуске по уровням алгоритм запоминает последний узел перед «спуском» на каждом уровне — массив update. После определения случайного уровня нового узла остаётся лишь вставить его в связные списки соответствующих уровней, обновив forward-указатели узлов из update.

Вставляем 10 (randomLevel вернул 1):
 
До:
Уровень 1:  head ── 3 ─── 8 ────── 15 ──→ nil
Уровень 0:  head ── 3 ─ 5 ─ 8 ─ 12 ─ 15 ──→ nil
 
update[0] = 8, update[1] = 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 затрагивает только соседние узлы на затронутых уровнях — обычно 1–2 узла. В самобалансирующихся деревьях перестройка может затронуть несколько узлов одновременно; при каскадной перестройке блокировка может распространиться до корня.

Для параллельного доступа без блокировок (lock-free) skip list проще: каждый forward-указатель обновляется независимо атомарной операцией CAS (compare-and-swap — «сравнить текущее значение с ожидаемым и заменить, если совпадает»). Самобалансирующееся дерево требует атомарного обновления нескольких связей одновременно, что значительно сложнее. Поэтому ConcurrentSkipListMap в Java — стандартная lock-free упорядоченная коллекция.

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.

Реализация

class SkipList
  MAX_LEVEL = 16
  P = 0.5
 
  Node = Struct.new(:value, :forward) do
    def initialize(value, level)
      super(value, Array.new(level + 1))
    end
  end
 
  def initialize
    @level = 0
    @head = Node.new(nil, MAX_LEVEL)
  end
 
  def search(value)
    current = @head
    @level.downto(0) do |i|
      current = current.forward[i] while current.forward[i] && current.forward[i].value < value
    end
    current = current.forward[0]
    current&.value == value ? current.value : nil
  end
 
  def insert(value)
    update = Array.new(MAX_LEVEL + 1)
    current = @head
 
    @level.downto(0) do |i|
      current = current.forward[i] while current.forward[i] && current.forward[i].value < value
      update[i] = current
    end
 
    new_level = random_level
    if new_level > @level
      ((@level + 1)..new_level).each { |i| update[i] = @head }
      @level = new_level
    end
 
    node = Node.new(value, new_level)
    (0..new_level).each do |i|
      node.forward[i] = update[i].forward[i]
      update[i].forward[i] = node
    end
  end
 
  def delete(value)
    update = Array.new(MAX_LEVEL + 1)
    current = @head
 
    @level.downto(0) do |i|
      current = current.forward[i] while current.forward[i] && current.forward[i].value < value
      update[i] = current
    end
 
    target = current.forward[0]
    return unless target&.value == value
 
    (0..@level).each do |i|
      break unless update[i].forward[i] == target
      update[i].forward[i] = target.forward[i]
    end
 
    @level -= 1 while @level > 0 && @head.forward[@level].nil?
  end
 
  private
 
  def random_level
    level = 0
    level += 1 while rand < P && level < MAX_LEVEL
    level
  end
end

Вся структура — один массив forward на узел и генератор случайных чисел. Для сравнения: реализация red-black дерева требует хранения цвета узла, проверки пяти свойств дерева и нескольких видов ротаций.

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

Skip list применяется там, где нужно упорядоченное множество с быстрыми операциями и простой реализацией. Redis использует skip list (с вероятностью продвижения 1/4) как основу Sorted Set (ZSET). LevelDB и RocksDB используют skip list для memtable — буфера записи в оперативной памяти перед сбросом на диск. В Java стандартная библиотека содержит ConcurrentSkipListMap — упорядоченное отображение с lock-free параллельным доступом, что было бы значительно сложнее реализовать на основе 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.