关系数据库的高效持久数据结构 [英] Efficient persistent data structures for relational database

问题描述

我正在寻找可用于实现关系模型的持久性数据结构的材料。

持续存在不可变数据结构的含义。 >

任何人都知道一些好的资源，书籍，论文等等。

（我已经有这本书纯功能数据结构，这是我正在寻找的一个很好的例子。 ）

解决方案

直接修改无处不在的 B-tree 被持久化。只要节点被修改，只需总是重新分配一个新节点，并将新节点返回给递归调用者，谁将通过分配一个新的节点将其插入到该级别。等等。返回新的根节点。每个操作只分配O（log N）个节点。

这是用于实现功能语言的技术，例如2-3棵树。

I'm looking for material on persistent data structures that can be used to implement a relational model.

Persistence in the meaning of immutable data structures.

Anyone know of some good resources, books, papers and such?

(I already have the book Purely Functional Data Structures, which is a good example of what I'm looking for.)

解决方案

It is straightforward to modify the ubiquitous B-tree to be persistent. Simply always alloctate a new node whenever a node is modified, and return the new node to the recursive caller, who will insert it at that level by allocating a new node, etc. Ultimate the new root node is returned. No more than O(log N) nodes are allocated per operation.

This is the technique used in functional languages to implement, e.g, 2-3 trees.

这篇关于关系数据库的高效持久数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！