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

Question

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

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

Кто-нибудь знает какие-нибудь хорошие ресурсы, книги, документы и тому подобное?

(у меня уже есть книга Чисто функциональные структуры данных , которая является хорошим примером того, что я ищу.)

Answer 1

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

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

Answer 2

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

Я бы предложил прочитать

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

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

Answer 3

SQLite имеет реализацию структуры данных b-tree , на которую вы можете взглянуть;