erlang - Erlang 数据结构：副本或引用

Question

我正在使用 Erlang 中的二叉树实现。这是代码片段，可以让您了解一下：

-record(node, {key, value, left, right}).

% ...

insert(Tree, {Key, Value}) when Key == Tree#node.key ->
    #node{key=Key,
          value=Value,
          left=Tree#node.left,
          right=Tree#node.right};

insert(Tree, {Key, Value}) when Key > Tree#node.key ->
    Tree#node{right=insert(
        Tree#node.right, {Key, Value})};

% ...

在这里，当我向树中插入一个新的键和值时，我返回一个带有插入（或修改）节点的新树。

问题： VM 会实际复制树并 GC 旧的（效率低下），还是复制对旧分支的引用并仅更改受新密钥影响的节点/分支？

有关的：

• Erlang“单一赋值”与Haskell“不可变值”不同吗？
• Common Lisp 中的不可变持久数据结构

Answer 1

表达式 Tree#node{right=...} 创建一个新记录（一个元组），其中包含与 Tree 相同的条目，除了“right”字段。每个条目使用一个机器字。如果条目是“立即数”，例如原子、整数或空列表，则所有信息都在该单词中。否则，该条目是指向实际数据的标记指针（如元组或二进制）。在任何一种情况下，只有那个词被复制到新记录中；Erlang 从不做“深拷贝”，除非你发送消息。（请注意，在 ETS 表中存储数据的行为就像您将数据发送到表中一样。）只有旧的 Tree 记录会变成垃圾。