Skip List
Сегодня расскажу о структуре данных Skip List. Хочу сделать упор не на деталях реализации, а на том, зачем он нужен. И почему в java Skip List есть только в многопоточном варианте.
Кто вообще использует связные списки?
Давным-давно мы сравнивали
В большинстве энтерпрайзных задач
✅ В инфраструктурных задачах вставка в середину более актуальна.
✅ Многие структуры используют связный список косвенно: элементы ссылаются друг на друга для упрощения обхода или дополнительной сортировки.
Взять ту же
Самая проблемная операция
Как устроен Skip List
Чтобы искать элементы быстрее, добавляем для исходного списка несколько уровней со ссылками.
Пример — на картинке под постом. Чтобы найти пятёрку, движемся от верхнего уровня к нижнему.
В реальности на верхних уровнях промежутки больше, и мы быстрее приходим к нужному месту. В идеальном случае за O(log N).
❓ Это разве не дерево теперь?
Действительно, алгоритм поиска очень похож. Но чем Skip List отличается от дерева:
🔸 Балансировка
В деревьях очень строгие правила, при добавлении-удалении дерево часто перестраивается. Зато мы получаем высокую и стабильную скорость поиска.
В Skip List более расслабленный подход. Новый элемент добавляется в основной список, а вопрос с наличием ссылки на верхних уровнях решается через рандом.
В целом структура получается нормально сбалансированной. Одни элементы будут находиться быстрее, другие медленнее, в среднем время поиска стремится к O(log N).
🔸 Расположение элементов
В Skip List все элементы хранятся на нижнем уровне. Добавление-удаление происходит очень легко — надо переписать всего пару ссылок.
В дереве элементы находятся в узлах со строгой структурой. Вставка и удаление часто приводят к ребалансировке.
Резюме
✍️ Связные списки редко используются в энтерпрайзе, но часто в инфраструктуре (кэши, БД). Основной сценарий здесь — поиск. И сам по себе, и для работы с текущими значениями.
✍️ Дерево не всегда подойдёт, тк часто балансируется. В нагруженных системах лишняя суета ни к чему😑
✍️ Чтобы ускорить поиск в связном списке, добавляем дополнительные уровни. Получаем Skip List!
Сортированные структуры в JDK
В однопоточной среде для хранения сортированных элементов чаще используют
Поддерживать дерево в многопоточной среде сложно как раз из-за балансировки. Чтобы дерево безопасно сбалансировалось, лучше заблокировать его целиком, что снижает общую пропускную способность.
В многопоточной среде для той же задачи используется
Ответ на вопрос перед постом
Сегодня расскажу о структуре данных Skip List. Хочу сделать упор не на деталях реализации, а на том, зачем он нужен. И почему в java Skip List есть только в многопоточном варианте.
Кто вообще использует связные списки?
Давным-давно мы сравнивали
ArrayList (список на основе массива) и LinkedList (связный список). В большинстве энтерпрайзных задач
LinkedList проиграл. Вставка в середину редко встречается в бизнес-логике, в основном мы работаем со списком как с хранилищем данных. Но✅ В инфраструктурных задачах вставка в середину более актуальна.
SortedSet в Redis — сортированный список уникальных элементов. Элементы часто добавляются и удаляются из произвольных мест, логично взять за основу именно LinkedList. В очереди с приоритетами и secondary indexes тоже пригодится связный список.✅ Многие структуры используют связный список косвенно: элементы ссылаются друг на друга для упрощения обхода или дополнительной сортировки.
Взять ту же
LinkedHashMap из JDK — хэшмэп, в котором элементы связаны между собой в порядке добавления.Самая проблемная операция
LinkedList — поиск элемента. Даже в сортированном списке приходится ходить по ссылкам последовательно. Это долго.Как устроен Skip List
Чтобы искать элементы быстрее, добавляем для исходного списка несколько уровней со ссылками.
Пример — на картинке под постом. Чтобы найти пятёрку, движемся от верхнего уровня к нижнему.
В реальности на верхних уровнях промежутки больше, и мы быстрее приходим к нужному месту. В идеальном случае за O(log N).
❓ Это разве не дерево теперь?
Действительно, алгоритм поиска очень похож. Но чем Skip List отличается от дерева:
🔸 Балансировка
В деревьях очень строгие правила, при добавлении-удалении дерево часто перестраивается. Зато мы получаем высокую и стабильную скорость поиска.
В Skip List более расслабленный подход. Новый элемент добавляется в основной список, а вопрос с наличием ссылки на верхних уровнях решается через рандом.
В целом структура получается нормально сбалансированной. Одни элементы будут находиться быстрее, другие медленнее, в среднем время поиска стремится к O(log N).
🔸 Расположение элементов
В Skip List все элементы хранятся на нижнем уровне. Добавление-удаление происходит очень легко — надо переписать всего пару ссылок.
В дереве элементы находятся в узлах со строгой структурой. Вставка и удаление часто приводят к ребалансировке.
Резюме
✍️ Связные списки редко используются в энтерпрайзе, но часто в инфраструктуре (кэши, БД). Основной сценарий здесь — поиск. И сам по себе, и для работы с текущими значениями.
✍️ Дерево не всегда подойдёт, тк часто балансируется. В нагруженных системах лишняя суета ни к чему😑
✍️ Чтобы ускорить поиск в связном списке, добавляем дополнительные уровни. Получаем Skip List!
Сортированные структуры в JDK
В однопоточной среде для хранения сортированных элементов чаще используют
TreeMap/Set. Это красно-чёрное дерево. Балансируется при каждом изменении, поиск работает быстро и стабильно.Поддерживать дерево в многопоточной среде сложно как раз из-за балансировки. Чтобы дерево безопасно сбалансировалось, лучше заблокировать его целиком, что снижает общую пропускную способность.
В многопоточной среде для той же задачи используется
ConcurrentSkipListMap/Set. Изменения очень локальные: меняется несколько ссылок, а большая часть списка остаётся неизменной. Поэтому одновременно со структурой могут работать больше потоков.Ответ на вопрос перед постом
ConcurrentSkipListSet — сортированный список без повторов. Skip List — название базовой структуры данных, Set — признак уникальности элементов.