(b1)B-树：动机

官官方信息技术老师·12 页·深入（追求细节与边界）·0 次浏览·2 天前
✦ (b1)B-树：动机信息技术(b1)B-树：动机640KB
磁盘I/O内存瓶颈B树动机

B树：动机

看完你能算出磁盘I/O代价并讲清B树的设计动机

按 空格/→ 演示下一步

1 / 12 页

全部页面点击任意一页，跳回舞台从这页播放

磁盘I/O内存瓶颈B树动机

B树：动机

看完你能算出磁盘I/O代价并讲清B树的设计动机

1第 1 页 · B树：动机

640KB的启示

B-树诞生的 1972 年，内存以 KB 计。IBM PC 上市后那句「640KB 够用」被反复引用——但这究竟是硬件约束，还是设计哲学？先看地址线。

20 位地址线
Intel 8086 只有 20 根地址总线，物理上最多寻址 1MB
地址空间分配
1MB 中低 640KB 给 DOS 应用，高 384KB 留给 BIOS 与显存
名言的误读
盖茨本人多次否认说过此话，是 80 年代媒体的演绎
对算法的启示
数据动辄几 MB 而内存只有几百 KB，必须设计面向磁盘的结构
地基大小对应 →640KB 上限

地基决定房子能盖多大，不住的人说'够住'——640KB 是物理事实，不是设计哲学

2第 2 页 · 640KB的启示

越来越大的数据 vs 越来越小的内存

真正的瓶颈不是数据存在哪里，而是内存还能不能装下；混淆规模增长与容量增长，就会误判查询代价。

数据侧
  • 数据量从KB膨胀到TB
  • 数据文件与索引持续累积
  • 完整数据常驻内存越来越难
内存侧
  • 内存容量增长远慢于数据
  • 一次可装入的数据持续变少
  • 查询越来越依赖分层存储
正确理解是数据增长远快于内存增长，因此内存相对数据的占比越来越小。
3第 3 页 · 越来越大的数据 vs 越来越小的内存

从640KB到TB：数量级的跨越

三条平行轴：时间、内存容量、数据规模，自上而下看剪刀差

图解渲染中…
a1：时间起点：每个节点代表一个十年b1：1980s主流内存容量即640KBc1：当时典型数据规模，KB级别c5：2020s数据达PB级，超内存3个量级
4第 4 页 · 从640KB到TB：数量级的跨越

分级I/O

数据已是TB级、内存只有GB级——这意味着每次要找的东西大概率不在内存里。访问磁盘一次要多久？先看清三级存储的代价差距。

三级存储
寄存器/L1/L2/L3 → 内存 → 磁盘，自上而下容量递增、速度递减
访问代价
CPU缓存~1ns、内存~100ns、磁盘~10ms，相邻两级差1~5个数量级
关键瓶颈
一次磁盘I/O ≈ 几百万次内存访问，是程序性能的真正天花板
厨房取食材对应 →三级存储体系

灶台随手拿(缓存)，冰箱走两步(内存)，超市跑一趟(磁盘)

TdiskTmem≈105\frac{T_{\text{disk}}}{T_{\text{mem}}} \approx 10^5
5第 5 页 · 分级I/O

内存相对越来越小

上一页从 640KB 跨到 TB，看到数据规模膨胀了几个数量级。但更要命的是：内存也在长，只是长得远没有数据快。差距在拉大。

摩尔定律放缓
DRAM 容量约两年翻一倍，但近年工艺逼近极限，增速明显放缓
数据爆炸式增长
全球数据量增速远超摩尔定律，常以 10 倍/几年计
容量比持续拉大
数据与内存的比值不断攀升，缺口越拉越开
磁盘被迫上位
装不进内存的部分必须落到磁盘，磁盘成为主存
内存退居缓存
内存从「主存」降级为磁盘的「高速缓存」
书桌与仓库对应 →内存与磁盘数据

书桌偶尔换大点，仓库却年年扩建，桌上能摆的永远是仓库的零头

6第 6 页 · 内存相对越来越小

一秒与一天

CPU 和磁盘 I/O 的差距，横跨 5 个数量级——这不是量变，是质变。

CPU 一次计算
  • 实际耗时：约 1 纳秒
  • 按比例放大：≈ 1 秒
  • 感受：一眨眼的事
磁盘一次 I/O
  • 实际耗时：约 10 毫秒
  • 按比例放大：≈ 1 天
  • 感受：等到天荒地老
差 5 个数量级——优化算法先砍 I/O 次数，再谈计算量。
7第 7 页 · 一秒与一天

1 Byte = 1 KB：块读写的代价

上页说到，磁盘一次读写比内存慢百万倍。那一次读写到底读了多少数据？是 1 字节还是更多？这个答案，决定了后面所有算法设计的取舍。

磁盘块
磁盘 I/O 的最小读写单位，一般 4~64 KB
整块读写
不能只取几个字节，要么不读，要么读完整个块
1B = 1KB
读 1 字节和读满整个块，付出的 I/O 时间完全相同
装满有用数据
既然代价一样，就该让每次 I/O 带回尽可能多的有效数据
快递车送货对应 →磁盘块读写

快递员跑一趟就是「一车」成本，取一件还是装满都要跑这一趟

8第 8 页 · 1 Byte = 1 KB：块读写的代价

二叉搜索树的磁盘困境

前面讲过磁盘按块读写——读一个节点和读一整块开销相同。把这代价放到 BST 的每一层上，log₂n 的树高就意味着 n 越大，每次查找要走的趟数越多。

一次访问一次 I/O
磁盘上每个节点落在一块里，访问它就等于读一整块
路径长度 log₂n
n 个节点，BST 高度 = ⌈log₂(n+1)⌉，命中要下探这么多层
总 I/O = log₂n
内存中「一次比较」到磁盘上变成「一次块读」，量级跃升
块严重浪费
一块 KB 级只放 1 个键 + 2 个指针，绝大多数字节空着
n 越大越慢
10⁹ 条约 30 层，30 次 ms 级 I/O 累计可达秒级
一格一书的大书架对应 →BST 节点落盘

书架（盘）容量大，但一格（块）只放一书（一节点），找一本要下 log n 层

h=⌈log⁡2(n+1)⌉h = \lceil \log_2(n+1) \rceil
9第 9 页 · 二叉搜索树的磁盘困境

B树的核心设计思想

二叉树每个节点只放一个键，比较一次就要一次I/O。但磁盘一次能读一整块——如果把多个键塞进一个节点呢？这就是B树的核心思路：让一个磁盘块做更多的事。

多键节点
一个节点内放多个键与子指针，比较时一次二分
节点≈磁盘块
节点大小对齐页大小，让每次I/O都「装满」
多路平衡
分叉多但仍强制所有叶子同层，避免退化
树高骤降
n=10亿时二叉树约30层，B树仅约4–5层
查英汉词典对应 →B树节点内二分

一页几百词对应一节点几十键，二分到中间再决定翻前后

hB树=⌈log⁡mn⌉,n=109,m=128⇒h=4h_{\text{B树}} = \lceil \log_m n \rceil,\quad n=10^9,m=128 \Rightarrow h=4
10第 10 页 · B树的核心设计思想

核心理解检验

点击作答

B树通过增大单个节点容量来减少磁盘I/O次数，根本原因是？

11第 11 页 · 核心理解检验

课后思考

先自己想，再看参考答案。三个问题分别对应回顾、应用、迁移。

1为什么B树节点恰好取一个磁盘块的大小？为什么不是更大或更小？

参考答案想分支因子B与树高的关系：B越大树高越低但块内二分查找变慢，存在一个由硬件决定的甜点。

2NVMe SSD 随机读延迟已接近内存，B树的设计思想还成立吗？

参考答案成立。延迟下降≠带宽变高，块对齐思想依然有效；只是 B 的最优值变大了，甜点会移动。

3从640KB到TB级数据，I/O优化的核心思路是变了还是没变？

参考答案没变。无论数量级怎么涨，"让一次I/O带回尽量多的有用信息"始终是核心，变的只是参数。

12第 12 页 · 课后思考