Как устроен список с пропусками (skip list)

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

Устройство

• Нижний уровень — все элементы по порядку, каждый следующий содержит подмножество предыдущего.
• Высота узла выбирается подбрасыванием монеты: с вероятностью p узел поднимается ещё на уровень (обычно p = 1/2 или 1/4).
• Ожидаемое число указателей — n/(1−p): при p = 1/4 это около 1,33 на элемент.

Поиск

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

Вставка — тот же поиск с запоминанием последнего узла на каждом уровне, затем перевязка указателей до выпавшей высоты.

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

• Плюсы: простой код, локальные изменения без вращений — удобно для конкурентных lock-free реализаций, естественный обход диапазона по нижнему уровню.
• Минусы: гарантии только вероятностные (худший случай O(n)), хуже локальность кеша, чем у B-дерева.

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

• Redis: сортированные множества (ZSET) — skip list плюс хеш-таблица, p = 1/4.
• Memtable в LevelDB и RocksDB.
• ConcurrentSkipListMap в Java — потокобезопасная упорядоченная мапа без глобальной блокировки.

Коротко для собеседования

Skip list получает логарифмический поиск за счёт случайных уровней-«экспресс-полос» вместо вращений, как у деревьев. Код проще и хорошо подходит для конкурентных реализаций, но гарантии только вероятностные; его выбирают Redis для ZSET и RocksDB для memtable.