关系数据库的高效持久数据结构
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.)
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
将无处不在的 B-tree 修改为持久性是很简单的。 只要每当修改节点时总是分配一个新节点，并将新节点返回给递归调用者，递归调用者将通过分配新节点等将其插入到该级别。最终返回新的根节点。 每个操作分配的节点数不超过 O(log N)。
这是函数式语言中用于实现例如 2-3 棵树的技术。
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.
我已经为 BergDB (http://bergdb.com/) 实现了这样的数据结构 - 一个具有数据模型的数据库这是一个持久的数据结构。
我建议阅读
http://www.cs.cmu.edu/~sleator /papers/Persistence.htm
这是关于如何基于普通（短暂）数据结构创建持久数据结构的原创作品。
I have implemented such a data structure for BergDB (http://bergdb.com/) - a database with a data model that is a persistent data structure.
I would suggest reading
http://www.cs.cmu.edu/~sleator/papers/Persistence.htm
It is the original work on how to create a persistant data structure based on an ordinary (ephemeral) one.
SQLite 有一个 b 树数据结构实现< /a> 你可以看一下；
SQLite has an b-tree data structure implementation you can take a look at;