data-structures - リレーショナル データベースの効率的な永続データ構造

Question

リレーショナル モデルの実装に使用できる永続的なデータ構造に関する資料を探しています。

不変のデータ構造の意味での永続性。

良いリソース、本、論文などを知っている人はいますか?

(私は既にPurely Functional Data Structuresという本を持っています。これは私が探しているものの良い例です。)

Answer 1

ユビキタスBツリーを永続的に変更するのは簡単です。ノードが変更されるたびに常に新しいノードを割り当て、再帰的な呼び出し元に新しいノードを返します。再帰的な呼び出し元は、新しいノードを割り当てるなどして、そのレベルに挿入します。最終的には、新しいルートノードが返されます。操作ごとに割り当てられるノードはO（log N）以下です。

これは、関数型言語で2〜3ツリーなどを実装するために使用される手法です。

Answer 2

SQLite には、参照できるb ツリー データ構造の実装があります。