Skip List

В рамках реализации Redis CodeCrafters есть глава sorted set, который применяется в дизайне рейтинговых систем(Leaderboards). Sorted set как и некоторые LSM-tree: Cassandra, LevelDB, RocksDB используют под капотом skip list.

Давайте решим design skip list на литкоде. Имейджин твое лицо когда на собесе дали эту задачу -_-

Из интересного, skip list вероятностная(probabilistic) структура данных.

Структура skip list - уровни, каждый уровень - отсортированный связный список. Node - содержит val и массив nexts, через nexts[i] мы выбираем уровень, len(nexts) говорит о высоте текущей Node.

Килер-фича skip list - поиск, вставка, удаление за log(n), все потому что высота ноды выбирается случайно через probability(обычно это 0.5)

Search

Вкратце алгоритм - пока следующий элемент меньше target двигаемся вправо, если значения равны элемент найден. Иначе спускаемся вниз

Insert

Используется доп массив update для сохранения потенциальных ссылок после которых добавится новое значение. Функция - get_random_level вычисляет уровень по который мы добавим новый элемент

def get_random_level(self) -> int:
  level = 1
  
  while random.random() < self.probability and level < self.max_level:
    level += 1
  
  return level

Erase

С массивом update работаем как и в insert. Уточнение - дубликаты в skip list могут быть и выглядеть как несколько башен, здесь мы решаем удалить самую первую - candidate = update[0].nexts[0]