Скиплист, или список с пропусками, с момента своего появления стал одной из базовых структур данных, широко применяемых в различных областях информатики и разработки систем. Он сочетает в себе преимущества простоты односвязного списка и эффективного поиска, свойственного сбалансированным деревьям. Главная идея скиплиста заключается в создании нескольких уровней иерархически связанных списков, где каждый следующий верхний уровень содержит подмножество элементов предыдущего, что позволяет значительно ускорить поиск, вставку и удаление элементов по сравнению с обычным линейным списком. Поиск в скиплисте обладает ожидаемой логарифмической сложностью, что делает его конкурентоспособным с большинством сбалансированных деревьев, таких как AVL или B-деревья, при этом реализуется значительно проще. Первоначально предложенный Уильямом Пьюгом, скиплист отличается высоким уровнем вероятностной сбалансированности.
В отличие от строгих правил балансировки деревьев, скиплист использует случайное определение «высоты» узла — чем выше узел расположен в иерархии уровней, тем реже он встречается. Такая вероятностная модель позволяет избежать затрат на поддержание жесткой структуры и сказывается на удобстве реализации, особенно в системах с высокой конкуренцией при операциях поиска и обновления данных. Одним из ключевых преимуществ скиплиста является его беспрецедентная адаптивность: начиная с классического вероятностного варианта, появилось множество расширений и модификаций для решения специальных задач. Среди них детерминированные скиплисты с гарантированными временными характеристиками, многоверсионные структуры, поддерживающие параллельные транзакции, а также варианты, оптимизированные для современных архитектур — многопроцессорных систем, систем с энергонезависимой памятью, GPU и даже распределенных сетей. Важное достоинство скиплиста — его способность к параллельному доступу.
Благодаря естественному распределению данных по уровням и отсутствию необходимости в агрессивном ребалансировании, скиплист легко адаптируется для многопоточной среды с минимальными блокировками или с полностью безблокировочной реализацией. Это ключевое качество делает его незаменимым для баз данных и памяти с высокой конкуренцией на современных серверах. Появление специализированных версий скиплиста позволило успешно применять этот инструмент в системах с энергонезависимой памятью (NVM, PM). Такие системы требуют особого внимания к атомарности операций записи и эффективности восстановления после сбоев. Оптимизированные варианты, сдерживающие количество операций записи и использующие стратегии выборочного сохранения состояний, обеспечивают высокий уровень отказоустойчивости и производительности в этой перспективной области.
Со стороны программного обеспечения скиплист широко используется как компонент ключевых хранилищ данных и систем с интенсивными операциями вставки и поиска. Многие популярные NoSQL базы данных, такие как RocksDB и LevelDB, эксплуатируют вероятностные скиплисты для организации внутреннего индекса в памяти. Так же скиплисты находят применение в системах управления версиями, реализуя многоверсионный доступ с минимальными затратами и позволяя ускорить операции консистентного чтения и записи. Одно из перспективных направлений развития — адаптация скиплиста к особенностям данных и характеру их доступа. Биased-скиплисты, например, приоритетно кешируют часто запрашиваемые элементы ближе к верхним уровням, что снижает среднюю задержку поиска для наиболее востребованных данных.
Саморегулирующиеся структуры, подобные splay-list, динамически меняют высоту узлов, ориентируясь на статистику обращений. Это делает их особенно полезными для приложений с выраженной локальностью доступа. В последние годы скиплисты активно внедряются в распределенных системах и сетевых алгоритмах. Благодаря своей «сквозной» иерархической структуре и способности к децентрализованной балансировке, скиплисты используются в сетевых оверлеях и пиринговых системах, где требуется быстрое и масштабируемое хранение и поиск данных без единой точки отказа. Многообразие вариантов скиплиста свидетельствует о его универсальности.
Разработаны модификации, которые позволяют индексировать сложные типы данных — многомерные точки, интервалы, а также поддерживать эффективный поиск по диапазонам. Интервальные скиплисты и многомерные k-d скиплисты расширяют область применения, позволяя эффективно работать с пространственными и временными данными. Изучение и внедрение скиплистов не ограничивается только алгоритмической стороной. Сильно развитый инструментарий оптимизаций, включающий участие специализированных инструкций CPU (SIMD), улучшенное распределение данных по физической памяти с учётом NUMA-архитектуры, а также применение в масштабируемом параллельном программировании — все это модернизирует классический скиплист под современные реалии вычислительных систем. Однако даже при таких широко признанных достоинствах, перед скиплистами стоят вызовы.
