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

Question

我一直在使用Clojure编写玩具数据库，并想要实现B+树。但是当我开始思考时，我意识到在Clojure中可能没有办法像指针/引用那样引用其他节点。对于BST或许多其他树结构这样的东西并不重要，因为你只需要存储一个节点的子项。但是，在B+树这样的情况下，我该怎么做才能引用节点的兄弟节点呢？

在寻找解决方案时，我在Google Groups上看到了一篇帖子，讨论了为什么不要在Clojure中实现双向链表，因为在Clojure中有其他做事情的方法。

但是对于B+树，我该怎么做呢？

- Tachy

---

我并没有完全理解这个问题，但是出于好奇：为什么要使用链表？难道不能用其他方法来解决这个问题吗？ - Belun

我并不是在尝试实现一个链表，但提到它是因为我在实现B+树时遇到的问题，即处理节点引用的问题，与处理链表时遇到的问题相同。 - Tachy

Answer 1

虽然在Clojure中引用对象并不困难，但通常这些引用是不可变的。正是这种不可变性使得双向链表变得不可能，因为与单向链表不同，你无法改变它的任何部分而不产生变异。

为了说明这一点，假设我有一个单向链表，

a -> b -> c

假设我想更改它的头部。 我可以通过更改整个列表来实现。 我通过为头值创建一个新值并重用尾部来创建一个新列表：

a'-> b -> c

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

现在，假设你真的需要Clojure中的可变引用——怎么办？嗯，根据您所需的并发语义，Clojure有vars，refs，atoms等。

此外，使用deftype，您可以创建具有可变字段的对象，并且这些可变字段可以持有对其他内容的引用。您还可以在Clojure中使用原始Java数组来实现相同的目的。

您的数据库将成为内存数据库还是磁盘支持的数据库？如果是后者，则我认为pointer swizzling的问题比具有可变引用的问题更棘手。

回到函数式数据结构的问题，我相信可以创建具有纯函数语义的B树。第一个线索是它是一棵树，而树是函数式数据结构的基础。其次，请注意存在以仅追加方式工作的数据库——例如couchDB。这样做的好处是数据库本身就是日志。要更好地了解此方法的成本和收益，您可能想要观看Slava Akhmechet的演示。他的公司RethinkDB最终采用了一种混合方法，如果我没记错的话。

- Rob Lachlan

---

谢谢你的回答。我会研究一下你指出的事情。我的玩具数据库现在可能会在内存中。看起来我将在这个过程中学到很多关于Clojure的知识。 - Tachy

Answer 2

你可以查看Clojure中Chouser的指数树，了解如何使用函数式风格实现双向链表的功能。

或者，你可能只是想退后一步，问问自己为什么认为B+是函数式语言的好数据结构选择。

如果你不熟悉其他选择，可以看看Chris Okazaki的书《纯函数数据结构》。

- ivar

---

谢谢你的书籍建议，我将尝试寻找替代传统B+树的方式。我想要使用B+树是因为我希望最终将数据存储在磁盘上，而B+树非常适合这种场景，特别是在需要进行少量磁盘访问的范围查询时。 - Tachy