1. 顺序 vs 链接: CPU 视角下两种物理化

一句话

数据结构教科书里有十几种结构, 但落到物理内存上只有两种选项: 顺序 (contiguous) 和 链接 (linked). 顺序赢在 cache locality 和 SIMD 吞吐, 链接赢在 O(1) splice 和迭代器稳定性. 这两种物理化在 CPU 视角、运行时视角、网络协议视角、磁盘视角都反复出现 —— 理解了"顺序 vs 链接"这一对双胞胎, 你就理解了数据结构差异的 80%.

思想链

工程问题: 为什么 std::vector 几乎总是比 std::list 快?
  └─► 数学对象必须选一个物理化身
        └─► 顺序: addr[i] = base + i * sizeof(T), 地址可以直接算出来
        └─► 链接: node->next 逐个追指针, 地址不可预测
  └─► 硬件三层把差距放大成数量级
        └─► cache: 顺序流一次取回 64B line 全是有用数据;
                   链表节点散落各处, 指针 + 有效负载挤在一起
        └─► prefetcher: 固定 stride 的顺序流是理想客户; 指针追逐无法预取
        └─► SIMD: AVX-512 一条 load 吃 16 个 int; 链表喂不进向量寄存器
  └─► 但链接买到了两样东西: O(1) splice + 迭代器稳定性
        └─► 选型问题归结为一句: "你要局部性, 还是要稳定性?" —— 其余全是推论

第一站: 物理化

数据结构本身是数学对象:

• 数组 = 索引到值的有限映射;
• 链表 = 头 + 尾组成的可拼接序列;
• 二叉树 = 节点 + 左右孩子组成的多级结构;
• 哈希表 = 函数 (hash) → 槽 + (比较) 的组合.

但计算机必须给数学对象一个物理化身: 内存的字节怎么排布、指针怎么连、cache 怎么预取. 这一步 "数学对象 → 物理化身" 的选择几乎只有两条路:

选项 A: 顺序 (contiguous)

把所有元素紧排到连续内存, 用偏移量 i 找元素: addr[i] = base + i * sizeof(T).

• 代表: 数组、动态数组、堆、CSR 邻接表、B+ 树页、SIMD 缓冲、SSD page;
• 优势: O(1) 索引、cache 极友好、SIMD 可并行、零指针开销;
• 代价: 大小固定 / 改大小要扩容、中间插入代价 O(n)、迭代器失效.

选项 B: 链接 (linked)

每个元素自带一个或多个指针指向下/上一个元素, 内存可以散乱分布.

• 代表: 链表、树、跳表、哈希桶链、std::map (红黑树);
• 优势: O(1) splice (已知指针时)、迭代器稳定、动态扩容零拷贝;
• 代价: 每元素 +8B (或更多) 指针开销、cache miss 风暴、几乎无法 SIMD.

同一抽象的两条物化路径

数学抽象层面, 它们是一对对偶: 同一个抽象有两条工程化路径. 下面从 CPU、运行时、协议、磁盘四处各举一对实例:

CPU 层

顺序: SSE/AVX SIMD — 16/32/64 字节一条 load 装多个元素 ≈ 1 cycle / 8 个元素
链接: 间接寻址 (load 指针再 load 数据) ≈ 10+ cycle / 元素

CPU 在 SIMD 上一次处理的就是"一段顺序". "链接" 在 CPU 层是被惩罚的代名词 —— 链接破坏 prefetcher 的 stride 模型.

内存模型层 (运行时)

顺序: std::vector / Go slice / Python list 内部 = 一段连续字节.
链接: std::list / intrusive_list / dict overflow bucket 链.

std::vector::iterator 在扩容时失效 (底层基地址换了); std::list::iterator 在 erase 之后对其他节点仍然有效 —— 这就是 "链接" 的标志特征.

网络协议层

顺序: TCP 字节流 — 数据按序到达, 滑动窗口按 sequence 号推进
链接: IP 路由的 next-hop 链 — 数据包一跳一跳地走

TCP 是 sequential 接收, IP 是 hop-by-hop 路由 —— 这是网络栈里同型的两个层级 (详见 三次握手与滑动窗口).

磁盘与日志层

顺序: WAL / LSM-Tree / Kafka append-only — 顺序写可达 GB/s
链接: inode / extent tree / B+ 树内部节点

LSM-Tree 把"顺序写"做到极致 (单段顺序追加), B+ 树把"范围查询"做到极致 (叶子链接 + 内部有序). LSM 与 B+ 都在"一棵树"上, 但 LSM 把"顺序"放在 IO 层, B+ 把"顺序"放在内存层 —— 这就是同一抽象不同物化的对偶 (分别见 LSM-Tree 与 SSTable 与 B+ 树索引).

怎么决定选哪种?

业务真的需要 迭代器稳定性 / splice / 已知指针位置的 O(1) 操作 ⇒ 链接. 否则, 选顺序.

一个简单决策表:

工程的折衷: 跨层同构

这一段的中心观点: "顺序 / 链接" 这对对偶在不同层次反复出现.

软件层: 数组 vs 链表
OS 层:  page cache 顺序读 vs fsync 散写
网络层: TCP 顺序字节流 vs IP 逐跳路由
硬件层: SIMD packed op vs 间接寻址

底层是同一抽象的两个方向物化: 在同一规模上, "顺序" 总在 cache、SIMD、batch 上占优; "链接" 总换来 splice、稳定迭代器、跨层 indirection.

多语言对比

语言标准库对 "顺序 / 链接" 的默认提供非常不同:

特别提到 Rust 故意不在标准库内置链表 —— 这是语言设计哲学的表态: 现代默认应该选顺序, 链接只在确需时引入. 这个决定不是性能微调, 而是把数据结构物理化的选择显式化 —— 你真需要链表就得自己写或者引第三方 crate. 这反而强迫你思考清楚需求.

FPGA 视角

在 FPGA 上, 这种对偶更明显:

• 顺序 BRAM: 单地址空间, 给 base addr + offset 即可寻址, 等价软件的数组;
• 链式 BRAM: 链表节点存下一节点地址, 需要在 BRAM 上模拟指针解引用, 一次跳转延迟几十 cycle.

数据流图 (DFG) 加速器里常见的 shift register / systolic array 就是顺序物化的"流水"; 而链式描述必须在 BRAM 上模拟 ptr. 这就是 FPGA 上几乎所有高速数据通路都选顺序物化的原因.

这一章带走的东西

• 物理化几乎只有顺序 vs 链接两条路, 绝大多数数据结构都是这两者之一或其组合;
• 顺序赢 cache + SIMD + indexing, 链接赢 splice + 迭代器稳定性;
• 网络层、OS 层、硬件层都有这种对偶同构;
• 选哪种不只看操作复杂度 O(), 更看 cache、并发、迭代器稳定性;
• Rust 标准库不内置 list 是一种哲学态度: 显式选择物理化.

一页速查

下一篇: 2. 摊还 vs 最坏: 工程常数与硬实时的张力。