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

Question

我一直在Clojure上玩玩具数据库,想要实现一个B + Tree.当我开始考虑它时,我意识到可能没有办法像Clojure中的其他节点那样使用指针/引用.对于像BST或许多其他树结构这样的东西并不重要,因为你需要的只是存储一个Node的孩子.但是我在B +树中做什么,我需要能够引用Node的兄弟？

在寻找解决方案时,我在Google网上论坛中发布了一篇关于如何在Clojure中实现双向链接列表的帖子,因为在Clojure中还有其他方法可以做.

我怎么办B +树呢？

Answer 1

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

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

a -> b -> c

假设我想改变它的头部。我可以通过更改整个列表来做到这一点。我通过为头值创建新值来创建一个新列表，并重用尾部：

a'-> b -> c

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

现在，假设您确实需要 Clojure 中的可变引用——该怎么做？嗯，根据您需要的并发语义，clojure 有vars、refs、atoms等。

此外，使用deftype，您可以创建具有可变字段的对象，并且这些可变字段可以保存对其他事物的引用。您还可以在 clojure 中使用原始 java 数组来实现相同的目的。

您的数据库将是内存数据库还是磁盘支持的数据库？如果在磁盘上，我认为指针混合的问题比可变引用的问题更棘手。

回到函数式数据结构的问题，我相信创建具有纯函数式语义的 B 树是可能的。这里的第一个线索是它是一棵树，而树是函数式数据结构的面包黄油和肉。其次，请注意有些数据库以仅附加方式工作——例如 couchDB。从某种意义上说，这样做的好处是数据库有自己的日志。要更多地了解这种方法的成本和收益，您可能需要观看 Slava Akhmechet 的演示。他的公司 RethinkDB 最终采用了一种混合方法 IIRC。