Эффективные постоянные структуры данных для реляционной базы данных

Question

Я ищу материал для постоянных структур данных, которые можно использовать для реализации реляционной модели.

Сохранение в значении неизменяемых структур данных.

Кто-нибудь знает о хороших ресурсах, книгах, газетах и ​​т. Д.?

(у меня уже есть книга Purely Functional Data Structures, что является хорошим примером того, что я ищу.)

Answer 1

Несложно изменить вездесущий B-tree быть стойкими. Просто всегда добавляйте новый узел при каждом изменении узла и возвращайте новый узел рекурсивному вызывающему, который будет вставлять его на этом уровне, назначая новый узел и т. Д. Окончательный новый корневой узел возвращается. Для каждой операции выделяется не более O (log N) узлов.

Это метод, используемый в функциональных языках для реализации, например, 2-3 деревьев.

Answer 2

SQLite имеет b-tree data structure implementation, на котором вы можете взглянуть;

Answer 3

Я реализовал такую ​​структуру данных для BergDB (http://bergdb.com/) - базу данных с моделью данных, которая является постоянной структурой данных.

Я предлагаю читать

http://www.cs.cmu.edu/~sleator/papers/Persistence.htm

Это оригинальное произведение о том, как создать Устойчивые структуры данных на основе обычного (эфемерной) один.