另存为：一次修改要付多少钱
上一章结尾你一定在想同一句话：不修改，那不就是每次都复制一份吗？这一章把那棵树拆开数给你看。一百万个元素，改掉其中一个，新建的节点数是 4。
一个有 1,000,000 个元素的 Clojure 向量 v。
我们执行一句：
(def v2 (assoc v 500000 :X))
执行完之后 v 还是原来那一百万个元素，v2 是改过一个的新向量，
两个都完整可用。
问：为了做到这件事，内存里真正被复制的引用（指针）大约有多少个？
顺便猜第二问：这次 assoc 和「把一个一百万长的数组整个复制一遍」比，谁快？快多少？
先看账单
答案是 C，128 个。下面这台 demo 就是那棵真树， 你可以换规模、换改哪一个，它当场重新数。
默认那一档的数字值得单独抄出来：
一百万个元素的向量，assoc 掉其中一个 ──────────────────────────────────────────────── 整棵树的节点数 32,258 这次新建的节点 4 两个版本共用的节点 32,254 真正复制的引用 128 (4 个节点 × 32 个槽) 天真做法要复制的引用 1,000,000 省下的倍数 7,813×
还有一个数你可能没想到。在这台机器上用真 Clojure 实测（scripts/probe-clj）：
100 万元素向量 assoc 一个 0.0017 ms 100 万元素的数组整个复制一遍 1.04 ms ← 慢 628 倍
也就是说，「不可变」不但没让它变慢，「不可变」正是它不用复制的原因。 能共用旧结构的前提，恰恰是旧结构不会变——如果旧的那份可能被人改， 新版本就一个字节都不敢共用，只能老老实实抄一份。
「持久化数据结构慢」这句话把因果搞反了。可变才是必须复制的那个； 不可变换来的是「可以放心共用」，而共用比复制便宜得多。
它长什么样：一棵 32 岔的树
Clojure 的向量不是数组，是一棵树。规则只有一条：每个节点最多 32 个孩子。
为什么是 32？因为 32 = 2⁵，于是「第 i 个元素在哪」这个问题，
可以完全用位运算回答：把 i 的二进制每 5 位切一刀，
每一刀就是一层要走的岔路口编号。不用比较，不用查表，就是移位和掩码。
# 找第 500000 个元素，i = 500000 # 二进制： 0000 0000 0111 1010 0001 0010 0000 第 1 层（最高 5 位）→ 第 15 个岔口 第 2 层（次 5 位） → 第 8 个岔口 第 3 层（次 5 位） → 第 9 个岔口 叶子（最低 5 位） → 第 0 格 # 一共走 4 步，因为 32⁴ = 1,048,576 > 1,000,000
数一下这棵树：一百万个元素里，最后 32 个待在尾巴上， 其余的装在 31,249 片叶子里（每片 32 个）； 叶子之上还有 977 个二层节点、31 个三层节点、1 个根—— 加起来正好是上面那张表里的 32,258。
树有多深？32⁴ = 1,048,576，所以一百万个元素只要 4 层。
再说一遍：一百万个元素，从根走到任何一个元素，最多 4 跳。
十亿个元素也只要 6 层。这就是为什么这棵树「几乎是常数时间」——
它的深度以 32 为底取对数，涨得极慢。
「另存为」到底做了什么
现在是关键的一步。要把第 500,000 个元素换成 :X：
- 从根往下走到那片叶子，路上经过 4 个节点。
- 只复制这 4 个节点。每个节点是一个 32 格的小数组，复制它就是复制 32 个引用。
- 在复制出来的叶子里，把那一格换成
:X。 - 复制出来的每个节点，其余 31 格原样指向旧树里的那些节点。
- 返回一个新的根。
# 旧根和新根，各自往下指
旧根 ◇ ◆ 新根
╲ ╱ ╲
●────────●────────●────● ◆ ← 这一层只有一个是新的
╱ ╲ ╲ ╲
▪▪▪ ▪▪▪ ▪▪▪ ◆ ← 走到底，重建了 4 个节点
共用 共用 共用 新叶子（32 格里改了 1 格）
# ● 共用：新旧两版指着同一个对象
# ◆ 新建：这次真的分配出来的，一共 4 个
所以「另存为」这个比喻是精确的：你在文档编辑器里点「另存为」， 得到一份新文档，旧的那份还在。区别只是， 这里的「另存」聪明到只写下真正不一样的那一小块， 剩下的 99.99% 直接指向旧文件里的同一批字节。
三个能让你把它记牢的边界情况
去上面那台 demo 里把规模拨到最小和中间，你会看到三件有意思的事：
一、32 个元素的向量，assoc 一个，新建 0 个节点。 因为这么小的向量整个装在「尾巴」里——Clojure 的向量末尾挂着一个最多 32 格的小数组， 专门接住最近添加的元素。改尾巴里的东西，连一个树节点都不用碰。
二、往尾巴没满的向量里 conj，也是新建 0 个节点。 这就是为什么「一个一个往后加」在 Clojure 里便宜得离谱： 32 次里有 31 次只是复制一个小数组，第 32 次才把满了的尾巴挂进树里。
三、1,000 个元素和 1,000,000 个元素，新建的节点数分别是 2 和 4。 规模差了一千倍，代价只差一倍——因为代价正比于树的深度， 而深度是对数。
这棵树在 Java 世界里不是新鲜事，你可能已经用过它的近亲：
ConcurrentHashMap的分段、CopyOnWriteArrayList的整表复制—— 后者就是「天真复制」那一档，所以官方文档明说它只适合读远多于写的场景。- Kotlin 的
listOf()返回的是只读视图，不是不可变值： 底下那个ArrayList如果还有人拿着，照样能改。 「只读」和「不可变」差着一整章。 - 真想在 JVM 上用这一章的东西，有现成的：Clojure 的数据结构可以单独当 Java 库用， 还有 Vavr、 Immutables。
Git 用的是同一招。你改一个文件并提交，Git 不会复制整个仓库， 它新建这个文件的 blob，然后从它所在的目录一路到根， 每一层新建一个 tree 对象——其余目录的 tree 直接复用旧的哈希。 改一个文件，新建的对象数正比于目录深度，不是仓库大小。 这和上面那 4 个节点是同一个算术。
文件系统：ZFS、Btrfs、APFS 的快照能在一秒内完成， 并且几乎不占空间，靠的也是这个——快照和原卷共用所有没被改过的块。 「写时复制」（copy-on-write）这个词你听过， 这一章就是它在数据结构里的样子。
React / Compose：每帧「重建整棵界面树」听起来很浪费， 但重建的是描述（便宜的值），diff 之后真正动的只有变了的那条路径。 《重跑》整本书都在讲这件事的一个具体版本。
「不可变数据结构，就是每次操作都完整复制一份， 所以它是拿性能换安全。」
它一次都没有完整复制过。它复制的是从根到改动点的那一条路径，
长度是 log₃₂(n)——一百万个元素也只有 4 个节点、128 个引用。
真正在做完整复制的是 new ArrayList<>(old) 那种防御性复制，
而你写那行代码，正是因为数据可变。
这条直觉之所以顽固，是因为它在「不共享结构」的前提下完全正确。 整个技巧就在于：不变，所以敢共享；敢共享，所以不用复制。 这三句是一根链条，缺一节就塌。
《快照》（Git）：上面说的 tree 对象复用，那本书讲得更细。 两本书合起来看会很爽——你会发现 Linus 和 Rich Hickey 在两个完全不同的领域里， 独立选中了同一个数据结构策略。
《意外》（信息论）：为什么「只记下不一样的那部分」是可行的？ 因为两个版本之间的意外很小。结构共享省下的空间， 恰好等于两个版本之间没有新增的信息量。
答案是 C，大约 128 个引用（4 个节点 × 每节点 32 格）。
第二问：assoc 比整个复制一遍快 600 多倍（实测 0.0017 ms vs 1.04 ms）。
A 「必须有自己的一份完整数据」——这是把「独立可用」和「独立存储」当成了一回事。 两个版本确实各自完整可用，但完整可用不要求完整拥有。
B 「只复制那个块」——方向对了，但漏了一件事： 光换掉叶子还不够，指向这片叶子的那个父节点也得换（否则旧树就被你改了）， 于是一路往上直到根。要复制的是一条路径，不是一个块。
D 「只记一条差异」——这是另一种做法，叫 diff / 日志。 它写起来最便宜，但读第 500,000 个元素时你得把所有差异重放一遍， 读会越来越慢。Git 早期存全量快照 + 后期打包成 delta，就是在这两头之间做取舍。
你进来时：不可变很安全，代价是复制，所以只适合小数据。
你出去时：不可变的代价是 log₃₂(n) 条路径， 而且不可变本身就是「敢共用」的前提——它不是安全的代价，是省钱的原因。
你原来关于「复制很贵」的判断完全没被推翻，它还在原地。 这一章只重建了一条路径：「产生新版本」不再等于「复制」。
这一章的一句话
不变，所以敢共用；敢共用，所以不用复制。 一百万个元素改掉一个，新建 4 个节点。
下一章处理一个你可能已经嘀咕了两章的问题： 如果值都不能变，那我的程序怎么办？银行账户余额总得变吧？ 答案是把一个词拆成三个——而拆完之后你会发现， Java 里那个「对象」一直在同时扮演三个角色， 这就是为什么「它现在是什么状态」这个问题在多线程下永远问不清楚。