# SkipList: Альтернативы linked list для итерации

Анализ альтернатив текущей singly-linked list структуре на level 0 SkipList.
Контекст: нужен `DoubleEndedIterator` для обратной итерации (пагинация).

---

## Текущая структура

Каждый узел — отдельная heap аллокация, связан forward pointer'ом (`tower[0]: AtomicPtr`).
Pointer chasing на каждый `next()`. Нет `prev` — обратная итерация невозможна.

---

## Альтернатива 1: Unrolled Linked List (блоки по N элементов)

Level 0 — цепочка блоков, каждый блок — sorted array из N записей (например N=64).

**Плюсы:**
- Cache-friendly обход (линейный скан внутри блока)
- `prev` нужен один на блок, не на элемент (overhead / N)
- Естественный bidirectional iteration внутри блока
- Меньше pointer overhead (1 next + 1 prev на 64 элемента вместо 64 next)

**Минусы:**
- Insert требует сдвиг внутри блока + возможный split
- Под write_lock это терпимо, но сложнее текущего `store(next)`
- Lock-free read сложнее — reader может видеть mid-split состояние
- Удаление: mark+compact или shift
- Значительный рефакторинг

---

## Альтернатива 2: Arena-backed SkipList (индексы вместо указателей)

Все узлы в одном `Vec<Node>`. "Указатели" — `u32` индексы.

**Плюсы:**
- 4 байта вместо 8 на указатель (tower уменьшается с 160 до 80 байт)
- Лучше cache locality при traversal (узлы ближе в памяти)
- Проще сериализация/snapshot

**Минусы:**
- Не решает проблему reverse iteration — всё ещё нужен prev
- `seize` не работает с arena — нужна своя reclamation strategy
- Grow arena = realloc, все индексы остаются валидными, но нужен `unsafe`
- Удаление создаёт дыры в arena (free list)
- Большой рефакторинг

---

## Альтернатива 3: Sorted Vec per shard

Вместо SkipList — `Vec<(Key, Value)>` отсортированный, binary search для lookup.

**Плюсы:**
- Идеальная cache locality
- Естественный bidirectional iteration (просто индекс ± 1)
- Простейшая реализация
- Нет pointer overhead вообще

**Минусы:**
- Insert = O(n) сдвиг элементов — неприемлемо для больших наборов
- Lock-free read невозможен без COW или RCU на весь вектор
- Writes блокируют reads (или нужен RwLock с COW)

---

## Альтернатива 4: Добавить `prev: AtomicPtr` к текущему SkipList

**Плюсы:**
- Минимальное изменение (3 строки в insert, 2 в remove)
- Корректность гарантирована write_lock
- Всё остальное не меняется
- +8 байт на узел

**Минусы:**
- +8 байт на узел (для миллионов узлов это мегабайты)
- Pointer chasing при reverse iteration (cache miss на каждый prev)

---

## Вывод

Вариант 4 (prev pointer) — минимальный risk для текущей задачи.
Вариант 1 (unrolled linked list) — интересен как future optimization,
решает одновременно cache locality и bidirectional iteration.
