Splay list

Splay list - это skip-list с адаптивной балансировкой. Для каждого ключа ведётся учёт частоты обращений, и структура периодически пересчитывает высоту узлов, поднимая горячие ключи в верхние слои башни и оставляя холодные внизу. В результате ключ с долей попаданий p оказывается на глубине log₂(1/p) вместо равномерной log₂(n), свойственной обычному skip list.

Название отсылает к splay-дереву, где узлы при обращениях ротируются к корню. В skip list ротаций нет, поэтому аналогичный приём заключается в увеличении высоты башни узла. В статье 2020 года Aksenov et al. формализовали процедуру обновления высоты: узел с долей обращений u/T получает высоту K − 1 − log₂(T/u), где K - текущая высота головы. Ключ, к которому обращаются в 50% случаев, оказывается на глубине 1, а при 25% обращений - на глубине 2. По мере изменения нагрузки структура автоматически сходится к глубине log(1/p) для каждого ключа.

Выигрыш в константе вполне реален, но ограничен. Splay list - это не B+tree: раскладка по кэш-линиям здесь неоптимальна, каждый спуск на уровень ниже требует перехода по указателю, а абсолютная задержка поиска остаётся заметно выше, чем у in-memory B+tree. Суть в том, чтобы сместить распределение стоимости: глубина поиска для горячих ключей пропорциональна их популярности, а не размеру всей структуры.

В конкурентных реализациях ребалансировка выполняется только на путях чтения (search, contains, позиционные запросы). Если повысить уровень узла, который вот-вот будет удалён, после его освобождения через EBR на верхних уровнях останутся висячие ссылки, поэтому операция удаления полностью пропускает ребалансировку. В библиотеке gregburd/skiplist это поведение включается флагом SKIPLIST_SPLAY_REBALANCE с настраиваемым интервалом балансировки (по умолчанию - каждые 64 обращения).