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

Question

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

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

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

（本 Purely Functional Data Structures を既に持っています。私が探しているものの良い例です。）

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ツリーデータ構造の実装があります。 をご覧ください。