Коротко — идея персистентных (immutable) структур данных: при изменении не модифицировать существующий объект, а создавать новую версию, максимально переиспользуя (шаря) неизменные части старой. Это даёт логические «снимки» (versions) за дешёвую цену за счёт структурного шаринга.
Ключевые приёмы
- Структурный шаринг и path-copying: меняют только узлы на пути от корня к месту изменения, остальные узлы разделяются между версиями.
- Высокая арность/широкие узлы: уменьшают глубину дерева и число копируемых узлов (практически константная глубина).
- Сжатая/битовая адресация (HAMT): разбивают хэш/индекс на куски по $c$ бит и идут по уровням дерева.
- Транзиенты (transients): внутри локальной области делать мутабельные изменения, потом «заморозить» в иммутабельную структуру для эффективных батч-операций.
Примеры и сложность
1) Дерево (балансированное дерево: AVL/Red‑Black)
- При обновлении (insert/delete) копируются только узлы вдоль пути к изменяемой позиции.
- Высота $h=O(\log n)$, поэтому создаётся $O(h)$ новых узлов.
- Стоимость: доступ/обновление $O(\log n)$, память на одну операцию $O(\log n)$ новых узлов.
2) Персистентный массив / вектор (bit‑partitioned trie, как в Clojure/Scala)
- Индекс разбивается на куски по $c$ бит; каждая вершина имеет арность $b=2^c$.
- Глубина $h\approx \lceil \frac{{\log }_{2}n}{c}\rceil =O({\log }_{b}n)$.
- При обновлении копируется только путь длины $h$ (каждый новый узел содержит массив из $b$ ссылок, но создаются только эти $h$ узлов).
- Часто используют $c=5$ ($b=32$), тогда глубина невелика: $h\approx \lceil \frac{{\log }_{2}n}{5}\rceil$ (для миллионов элементов $h$ порядка $3-4$).
- Стоимость: доступ/assoc $O(h)$ с малым константным фактором; память на одну assoc $O(h\cdot b_{\text{node\_size}})$ только для новых узлов.
3) Hash Array Mapped Trie (HAMT) для отображений (maps/sets)
- Берут хэш ключа, разбивают на уровни по $c$ бит и используют битовые маски/bitmap для компактного представления детей.
- Глубина $h=\lceil \frac{w}{c}\rceil$ где $w$ — разрядность хэша; на практике константная и мала.
- Обновление/поиск $O(h)$, практически константа, разделяется большая часть структуры.
4) Улучшения: RRB‑tree и др.
- Для операций concat/slice используют «relaxed radix balanced» деревья (RRB), которые сохраняют быстрые конкатенации/сплайсы при сохранении шаринга.
Иллюстрация path-copying (упрощённо)
- Для дерева: при изменении листа создаём новый лист; затем создаём новую версию каждого родителя по пути до корня, где каждый новый родитель ссылается на старых детей, кроме изменённого — остальные дети остаются общими.
Транзиенты (batch-оптимизация)
- Для многих последовательных обновлений: сделать временную мутабельную версию (транзиент), выполнить $k$ операций за $O(k)$ как для изменяемой структуры, затем «заморозить» — вернуть персистентную структуру. Это комбинирует безопасность иммутабельности с эффективностью in-place для пакетной работы.
Итог (комплексно)
- Доступ/обновление в персистентных структурах: обычно $O({\log }_{b}n)$ (баланс/ширина $b$ выбирается для малой глубины); для HAMT — практически константа.
- Память на одну операцию: создаётся только $O({\log }_{b}n)$ новых узлов (не копируется весь объект), остальное — шарится.
- Практически: использовать широкие деревья (b≈32), HAMT для мап, RRB/bit‑tries для векторов, и транзиенты для массовых изменений.