Изменения
→Получение полностью персистентных структур данных
[[Файл:Полная персистентность.png]]
Для реализации описанного в предыдущем пункте метода преобразования структур данных в полностью персистентные нам нужен такой список, который поддерживает операции <tex> \mathrm{insert After(p,q})</tex> (вставить <tex>q</tex> после <tex>p</tex>) и <tex>\mathrm{order(p,q)}</tex> (должен уметь ответить верно ли что <tex>p</tex> лежит в этом списке до <tex>q</tex>). <tex>\mathrm{order(p,q)}</tex> возвращает <tex>1</tex>, если <tex>p</tex> лежит до <tex>q</tex> и <tex>0</tex> иначе. Это список с поддержкой запроса о порядке ''List Order Maintenance'' <ref>[http://www.cs.au.dk/~gerth/aa11/slides/order.pdf List Order Maintenance]</ref>, который обе эти операции делает за <tex>O(1)</tex>.
В ''change log'' «толстого» узла теперь будем добавлять два события: одно указывает на изменение, произошедшее в соответствующей версии, а другое на его отмену. События будут добавляться в ''change log'' не по номерам версий, а по их порядку в списке версий ''List Order Maintenance''.
Когда есть запрос к какой-то версии, то нужно найти в списке версий такую, после входа в которую, но до выхода из которой лежит версия запроса, а среди таких максимальную. Список ''List Order Maintenance'' позволяет делать это за <tex>O(1)</tex> с помощью операции <tex>\mathrm{order(p,q)}</tex>.
В какой-то момент ''change log'' «толстого» узла переполнится. Тогда нужно клонировать этот узел и нижнюю половину изменений перенести в ''change log'' склонированного узла. Первую половину изменений применяем к исходной версии узла и сохраняем в качестве исходной в склонированном узле.
