Lobsters | 📄 原文链接 | 2026-10-25 收录

把索引放到 NVMe 上，比放在内存里更快

来源：bitflux.ai — 2026-10

📋 概述

作者在 20 亿节点的有序集合上对比 AVL 树与自研 DiskArray：AVL 需要 144 GiB 内存才装得下，DiskArray 只用 264 MiB 内存加 8 块 NVMe，四项操作却都不输。原因是 Big O 把所有步骤当成等价，而一次 L1 命中、一次 DRAM 缺失、一次 NVMe 随机读的成本差着好几个数量级；把磁盘流水线做起来之后，内存方案要扩到同一规模反而先撞墙。

🔑 核心要点

20 亿节点时 AVL 要 144 GiB 内存，DiskArray 只用 264 MiB，约合每个 8 字节 key 0.1 字节内存
十亿次 L1 命中约 1 秒，十亿次 DRAM 缺失约 90 秒，十亿次 NVMe 读要一天——Big O 全算作一步
DiskArray 同时挂 2048 个事务（两半各 1024），一个核跑算法、28 个 io_uring worker 专管磁盘
脏块攒到 1536 个才批量回写，做到每次插入一次 4 KiB 写，但从不一次一块地等
性能台阶不是数学上的 log n，而是硬件被撑爆的位置：树一超出 35.75 MiB 的 L3，搜索就从 4.0M/s 掉到 2.3M/s
内存方案流水线化后反超 3~6 倍，但 B+tree 只到 8G 节点，DiskArray 能到 64G，这是量级差

💡 金句

RAM stands for Random Access Memory, but it's not really random access anymore. It's a block device with 64-byte blocks and 80-90 ns of latency, and you have to use it like one.

← 返回 Lobsters 首页