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

Question

我一直在 Clojure 中开发一个数据库，并希望实现一个 B+ 树。当我开始考虑它时，我意识到可能没有办法在 Clojure 中拥有指向其他节点的指针/引用之类的东西。对于像 BST 或许多其他树结构这样的东西并不重要，因为您需要的只是存储节点的子节点。但是我在像 B+ 树这样需要能够引用节点的兄弟节点的东西中做什么？

在寻找解决方案时，我在 Google Groups 中看到了一篇关于如何不在 Clojure 中实现双向链表的帖子，因为在 Clojure 中还有其他处理方式。

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

Answer 1

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

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

a -> b -> c

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

a'-> b -> c

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

现在，假设您真的需要 Clojure 中的可变引用——怎么做？好吧，取决于你需要什么样的并发语义，clojure 有 vars , refs , atoms ， 等等。

另外，还有 deftype ，您可以创建具有可变字段的对象，这些可变字段可以保存对其他事物的引用。出于同样的目的，您还可以在 clojure 中使用原始 java 数组。

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

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