在Clojure中写入需要指针/引用的数据结构？

我一直在玩Clojure的数据库，并希望实现一个B +树。当我开始思考它时，我意识到可能没有办法像Clojure中的其他节点那样使用指针/引用。对于像BST或许多其他Tree结构这样的东西无关紧要，因为您只需要存储Node的孩子。但是，我在做什么像B +树，我需要能够引用一个节点的兄弟？在Clojure中写入需要指针/引用的数据结构？

在寻找解决方案时，我在Google Groups中发现了一篇关于如何在Clojure中实现双向链表的文章，因为在Clojure中还有其他的做法。

虽然我该怎么做B +树？

来源

2010-11-21 TriArc

我完全不明白这个问题，但出于好奇：为什么链表不能解决问题？ – Belun 2010-11-22 08:28:31

我并没有试图实现一个链表，而是提到它，因为我在实现B +树时遇到的问题，即处理对节点的引用，与我在处理链接列表时遇到的问题相同。 – TriArc 2010-11-24 15:33:32

这并不是说很难在clojure中引用对象;但一般来说，这些引用是不可变的。它是不可变的，它使得双向链表不可能，因为与单链表不同，如果不在某处创建突变，则不能更改它的任何部分。

看到这一点，假设我有一个单向链表，

a -> b -> c

，并假设我想改变它的头。我可以这样做，改变整个列表。我创建一个新的列表，为头值创建一个新的值，并重新使用尾部：

a'-> b -> c

但是双向链表是不可能的。因此，在clojure和其他功能语言中，我们有时在这种情况下使用zipper。

现在，假设你真的需要Clojure中的可变引用 - 它是如何实现的？嗯，这取决于你所需要的并发语义，Clojure的有vars，refs，等

而且，与deftype，您可以创建一个具有可变字段的对象，而这些可变域可以包含到其他事情的引用。你也可以在clojure中使用原始的java数组来达到同样的目的。

您的数据库将成为内存数据库还是磁盘备份数据库？如果在磁盘上，我认为pointer swizzling的问题比具有可变引用的问题要棘手。

回到功能数据结构的问题，我认为有可能创建具有纯功能语义的B树。这里的第一条线索是它是一棵树，树是面包黄油和功能数据结构的肉。其次，请注意，有些数据库只能以append-only方式工作 - 例如couchDB。从某种意义上讲，这有利于数据库是自己的日志。为了更好地了解这种方法的成本和收益，您可能需要watch Slava Akhmechet's presentation。他的公司RethinkDB最终采用了一种混合方法，IIRC。

来源

2010-11-21 20:56:23

感谢您的回答，我会研究您指出的事情。 DB现在可能会在内存中看起来好像我要学习一堆关于Clojure的过程 – TriArc 2010-11-22 02:53:16

您可能希望查看Clojure中的Chouser's finger trees以查看如何使用功能样式实现双向链表的功能。

或者，您可能只是想退一步问自己，为什么您认为B +是功能语言数据结构的不错选择。

如果您不熟悉替代方案，可以查看Chris Okazaki的书“Purely Functional Data Structures”。“

来源

2010-11-22 09:17:33 ivar

感谢这本书的建议我会尽量找到传统B +树的替代品原因我想使用B +树是因为我想最终将数据存储在磁盘上并且B +树是非常适合这种情况，特别是在磁盘访问很少的情况下进行范围查询 – TriArc 2010-11-24 15:32:19

在Clojure中写入需要指针/引用的数据结构？

回答

相关问题