Skip list: как устроен отсортированный набор с быстрым поиском

Прямой ответ

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

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

1. Начинаем с самого верхнего уровня с левого края.
2. Идём вправо, пока следующий элемент меньше искомого.
3. Спускаемся на уровень ниже и повторяем.
4. На нижнем уровне находим точную позицию.

Высота каждого узла выбирается случайно: с вероятностью p (обычно 1/4) узел получает ещё один уровень выше. В результате получается вероятностно сбалансированная структура — балансировка достигается не перебалансировкой, а случайностью при вставке.

Сложность операций:

Память: в среднем 1/(1−p) указателей на узел; при p = 1/4 — около 1,33 указателя, то есть заметно экономнее сбалансированного дерева с двумя указателями на потомка плюс указателем на родителя.

Почему Redis использует skip list для sorted set:

• Диапазонные операции — главный сценарий. ZRANGEBYSCORE, ZRANK, топ-N — это обход подряд идущих элементов. В skip list после спуска к началу диапазона дальше идёт обычное движение по нижнему уровню.
• Простота реализации и отладки. Нет вращений и перебалансировки, как в AVL или красно-чёрном дереве.
• Предсказуемая производительность. Средний случай практически совпадает с худшим при разумном объёме данных.
• Указатели на предыдущий элемент. В реализации Redis узлы нижнего уровня имеют обратный указатель, что даёт обход в обе стороны.

# sorted set: рейтинг игроков
redis-cli ZADD leaderboard 1500 anna 1420 boris 1610 vera
redis-cli ZREVRANGE leaderboard 0 2 WITHSCORES   # топ-3
redis-cli ZRANGEBYSCORE leaderboard 1400 1550    # диапазон
redis-cli ZRANK leaderboard boris                # позиция

Практика: применение и ограничения

1. Очереди с приоритетом и отложенные задачи. Элементы с меткой времени в качестве score дают естественный порядок: ZRANGEBYSCORE key 0 <now> LIMIT 0 10 выбирает задачи, готовые к выполнению. Это проще, чем отдельный планировщик, при умеренных объёмах — подробнее о структурах Redis в статье про кэш и очереди.

2. Лидерборды и топы. Хранение счёта в score и обход с конца — стандартный приём. Обратите внимание: при равных score элементы упорядочиваются лексикографически по значению, что влияет на стабильность порядка.

3. Скользящие окна. Удаление устаревших записей по score до текущей границы окна выполняется одной командой ZREMRANGEBYSCORE.

4. Индексы внутри хранилищ. Некоторые системы используют skip list как индекс для memtable — например, в RocksDB это один из вариантов реализации активной таблицы в памяти. Альтернатива для дисковых индексов — B-tree.

Ограничения:

• Память. Каждый элемент — отдельный узел с несколькими указателями. Для миллионов мелких элементов расход заметен.
• Локальность. Узлы разбросаны в памяти, поэтому обход даёт больше промахов кэша процессора, чем у массива или B-tree со страницами.
• Отсутствие детерминизма. Случайные высоты означают, что в редких случаях глубина поиска выше средней. Для систем с жёсткими требованиями к худшему случаю существуют детерминированные варианты.

Рекомендации:

1. Не используйте sorted set как основную БД. Это структура в памяти без транзакционных гарантий; при большом объёме данных стоимость памяти растёт линейно.
2. Следите за размером ключа. Один sorted set с десятками миллионов элементов хуже, чем несколько поменьше: операции над большим набором блокируют обработчик дольше.
3. Проверяйте сложность команды. У Redis она указана в документации; ZRANGEBYSCORE с большим LIMIT остаётся дешёвым, а без ограничения может вернуть огромный объём.
4. Помните про дубликаты значений. В sorted set значение уникально; повторный ZADD обновляет score, а не добавляет новую запись.

Практический сценарий: отложенные задачи без отдельного планировщика

Контекст: сервису потребовалось отправлять напоминания через заданное время. Поднимать Celery ради одной задачи не хотели.

1. Первое решение. Задачи писали в таблицу PostgreSQL с полем времени и опрашивали её каждые пять секунд. При росте числа задач запрос начал заметно нагружать базу: сортировка и фильтрация по индексу выполнялись постоянно, хотя большинство строк ещё не готовы.
2. Переход. Готовность к отправке перенесли в Redis sorted set: score — метка времени отправки, значение — идентификатор задачи.
3. Реализация. Воркер раз в секунду выполняет выборку готовых задач с ограничением по количеству и атомарно переносит их в рабочую очередь, чтобы два воркера не взяли одну задачу.
4. Результат. Нагрузка на PostgreSQL по этому пути исчезла, задержка отправки снизилась с пяти секунд до примерно одной, память Redis при миллионе задач составила около 120 МБ.
5. Надёжность. Redis в этой схеме — очередь с риском потери при сбое, поэтому состояние «задача запланирована» дополнительно фиксировалось в БД; при старте воркер сверял наборы и восстанавливал пропущенное. Гарантии доставки разобраны в статье про надёжность очередей.

Вывод: отсортированный набор в памяти хорошо решает задачу «выбрать элементы, готовые к обработке», если объём данных умещается в память, а потеря данных при сбое компенсируется внешним источником истины.

FAQ

Почему не сбалансированное дерево? Дерево даёт ту же асимптотику, но требует вращений при балансировке и сложнее в реализации. Skip list проще, а для основного сценария sorted set — диапазонного обхода — он удобен тем, что элементы уже лежат в связном списке.

Что такое p и на что она влияет? Это вероятность добавления следующего уровня. Меньшее p уменьшает расход памяти на указатели, но увеличивает среднее число шагов по нижним уровням. Классический выбор — от 1/4 до 1/2.

Можно ли реализовать skip list самостоятельно для продакшена? Технически да, алгоритм прост. Практически стоит сначала проверить, не решает ли задачу готовая структура в используемом хранилище: самостоятельная реализация добавляет риск ошибок в конкурентном коде.

Чем skip list отличается от хеш-таблицы? Хеш-таблица даёт быстрый доступ по точному ключу, но не поддерживает порядок и диапазоны. Skip list поддерживает и поиск, и упорядоченный обход ценой большей стоимости операции. Устройство хеш-таблиц — в статье про хеш-таблицы и коллизии.

Источники: Redis docs (sorted sets), Wikipedia (skip list) — ссылки в шапке.