Skip Lists: Швидкі Смуги Над Зв’язним Деревом

Ідея: експресних доріжок поверх відсортованого списку

Відсортоване поодиноке зв’язне лістинґ робить пошук O(n): ви можете ходити лише вперед по одному вузлу за раз. Skip list Вільяма Пужа (1989) вирішує цю проблему, будуючи додаткові "експресних доріжок" шари поверх базового списку. Вузол, що існує на рівні k, має прямий покажчик, який може пропустити кожен вузол нижче за рівняння (k-1), перед ним, дозволяючи пошуку спускатися з високого, розрідженого рівня вниз до рівня 1, рухаючись широкими стрибками та лише вузькими кроками біля цілі.

Визначення висоти вузла за допомогою підкидання монетки

Висота кожного вузла визначається незалежно, під час вставки, шляхом повторних кидків монетки: з ймовірністю p (зазвичай 1/2) він підвищується на наступний рівень, і це повторюється до тих пір, поки кидок не зазнає невдачі. Немає глобального перерозподілу, без обертань, без кольорів — баланс структури виникає лише за допомогою ймовірності.

randomLevel(p = 0.5, maxLevel):
  level = 1
  while random() < p and level < maxLevel:
    level += 1
  return level

insert(key):
  level = randomLevel()
  find the predecessor node at each level 1..level (search path)
  splice the new node into the forward pointers at each of those levels

Чому очікуваний час пошуку становить O(log n)

З p = 1/2 приблизно половина вузлів на будь-якому рівні просувається на наступний рівень, тому очікувана кількість вузлів на рівні k становить n/2^(k-1) — і очікуваний верхній рівень становить приблизно log2(n). Пошук, який починається з верхнього рівня та рухається вправо або вниз на кожному кроці, займає очікувано O(1) кроків на рівні (невеликий геометричний аргумент обмежує кількість правильних рухів перед переходом на рівень), що дає загальну очікувану вартість O(log n) у всіх рівнях. Це майже точно відображає аналіз збалансованого бінарного пошукового дерева, але випадковість замінює явну балансуючу інваріанту.

Skip lists проти збалансованих дерев

Торгують пропуски, чесно: вони відмовляються від гарантії найгіршого випадку набагато простішу реалізацію. Вставлення та видалення в списку пропусків – це просто з’єднання покажників вздовж пошукового шляху — без обертань, без перефарбовування, без каскадного виправлення. Ця простота має значення найбільше у конкурентному коді, де lock-free або тонкоадаптивне блокування списку пропусків значно легше реалізувати правильно, ніж lock-free збалансоване дерево, оскільки оновлення на різних рівнях часто можуть відбуватися незалежно.

Де саме вони працюють у виробництві

Redis реалізує свій тип відсортованого множинного набору (ZSET) за допомогою перемикача, що попарно з хеш-таблицею, особливо тому, що перемикачі роблять прості в реалізації запити діапазонів ("дайте мені 10 найвищих оцінок") та пошук ранжування простим, поряд із простотою впровадження O(log n) вставлення та видалення. Кілька двигунів зберігання LSM-дерева, включаючи memtable у LevelDB і RocksDB, використовують перемикач як внутрішній відсортований буфер, куди прибувають вхідні записи, знову ж таки, віддаючи перевагу простому, друкованому одночасним записам замість трохи швидшого збалансованого дерева.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Skip Lists і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.