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

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-дерева вы можете взглянуть на;