Skip list
- title
- Skip list
- type
- concept
- summary
- Вероятностная упорядоченная структура из связных списков с поиском O(log n); стандартный выбор MemTable в LSM-движках
- tags
- data-structures
- created
- 2026-05-19
- updated
- 2026-05-19
- lang
- ru
- translation_of
- skip-list
- source_updated
- 2026-05-19
- translated
- 2026-09-01
- translator
- lllm/antigravity/gemini-3.7-flash-medium
Skip list - это вероятностное упорядоченное отображение, построенное из многоуровневых связных списков. Нижний список содержит все ключи в отсортированном порядке. Каждый следующий уровень выше включает примерно половину узлов уровня под ним, что даёт математическое ожидание поиска O(log n) при спуске сверху вниз: сканирование вперёд на текущем уровне, пока следующий ключ не перескочит цель, спуск на один уровень вниз, повтор. Вставка и удаление также требуют O(log n) в среднем.
По сравнению со сбалансированным BST (красно-чёрным, AVL), преимущество заключается в простоте и поддержке конкурентного доступа. Никаких поворотов, перекрашиваний или рекурсивных балансировок. Структура данных локальна - вставка затрагивает только узлы на своём пути поиска. Именно благодаря этой локальности большинство lock-free реализаций упорядоченных отображений - это skip list'ы, а не сбалансированные деревья: алгоритм Fraser/Harris строит конкурентный skip list с логическим удалением через маркированные указатели и восходящей цепочкой CAS-вставок, а столь же практичного lock-free сбалансированного BST не существует.
MemTable в lsm-tree обычно устроен как skip list. Его используют и RocksDB, и LevelDB. Сочетание упорядоченного обхода (для сброса в отсортированную SSTable), вставки за O(log n) (для приёма записей) и удобства для параллельных читателей делает его стандартным выбором для движков хранения с буферизацией записи.
Полезные варианты:
- Doubly-linked level 0 - добавляет обратные указатели на нижнем уровне для обратного обхода за O(1). Обычным skip list'ам для движения назад требуется поиск за O(log n).
- Deterministic skip list - заменяет случайный выбор высоты фиксированным паттерном, гарантируя оценки в худшем случае вместо математического ожидания ценой усложнения параллельных обновлений.
- splay-list - адаптивно поднимает горячие ключи к вершине, снижая глубину поиска с log n до log(1/p), где p - доля обращений к ключу (Aksenov 2020).
- MVCC skip list - версионирует каждый узел диапазоном временных меток; читатели видят снимок на выбранный момент времени. Распространён в базах данных, которым нужны point-in-time запросы к буферу записи в памяти.
gregburd/skiplist - это header-only библиотека на C, покрывающая большинство этих вариантов: lock-free алгоритм Fraser/Harris по умолчанию, опциональный splay, MVCC-снимки, doubly-linked level 0 и опциональный однопоточный режим, полностью убирающий атомики.