B树节点的磁盘表示

概述

B树节点的磁盘表示将节点大小设计为匹配磁盘页大小，一次I/O读取完整节点。这是B树作为外存数据结构的核心设计思想——B树的所有设计决策（最小度的选择、高度上界的推导）最终都服务于一个目标：最小化磁盘I/O次数。

核心思想

磁盘页对齐设计

B树的每个节点被设计为恰好占用一个磁盘页（disk page）的空间。这样，每次磁盘I/O操作可以完整读取或写入一个节点，不会产生”半页”读取的浪费。

• 磁盘页大小：通常为 4KB 或 16KB（由操作系统和硬件决定）
• 节点大小 = 磁盘页大小：一个B树节点恰好填满一个磁盘页
• 一次I/O = 一个节点：DISK-READ 和 DISK-WRITE 以页为单位操作

为什么B树适合磁盘

磁盘访问的两个关键特征：

1. 磁盘I/O代价远高于内存访问：一次磁盘I/O约 10ms，而内存访问约 100ns，相差约 $10^5$ 倍
2. 磁盘读写以页为单位：无论读取1字节还是1页，代价几乎相同

因此，最优策略是每次I/O读取尽可能多的有用信息——这正是B树多路搜索的设计初衷。

节点属性

B树节点的磁盘结构

一个B树节点 $x$ 在磁盘上包含以下属性：

属性	类型	说明
$x.n$	整数	当前存储的关键字数量
$x.\text{leaf}$	布尔值	是否为叶子节点
$x.\text{key}[\mathrm{1..}n]$	关键字数组	$n$ 个关键字，按升序排列
$x.c[\mathrm{1..}n+1]$	指针数组	$n+1$ 个子节点指针（磁盘地址）

对于叶子节点，$x.c[\mathrm{1..}n+1]$ 为空。

节点大小计算

一个节点占用的磁盘空间为：

$\text{节点大小}=\underset{\text{n, leaf}}{\underbrace{O(1)}}+\underset{\text{key和c数组}}{\underbrace{n\cdot (\text{关键字大小}+\text{指针大小})}}+\underset{c_{n+1}}{\underbrace{1\cdot \text{指针大小}}}$

对于最小度为 $t$ 的B树，节点最多有 $2t-1$ 个关键字和 $2t$ 个子指针：

$\text{最大节点大小}=O(1)+(2t-1)\cdot (k+p)+p$

其中 $k$ 为关键字大小，$p$ 为指针大小。

最小度的选择

给定磁盘页大小 $P$，可以反推最大最小度 $t$：

$t\approx \frac{P}{k+p}$

典型计算

设磁盘页大小 $P=16\text{KB}$，关键字为8字节整数，指针为8字节： $t\approx \frac{16384}{8+8}=1024$ 即每个节点最多可存储 $2\times 1024-1=2047$ 个关键字。

由B树高度定理，存储 $n=10^9$ 个关键字时： $h\le {\log }_{1024}\frac{10^9+1}{2}\approx 1.5$ 即仅需 2 次磁盘I/O即可定位任意关键字。

DISK-READ 和 DISK-WRITE 操作

磁盘I/O原语

B树算法使用两个抽象的磁盘I/O操作：

• DISK-READ($x$)：将磁盘上的节点 $x$ 读入内存。如果 $x$ 已在内存中（被缓存），则无需实际磁盘访问。
• DISK-WRITE($x$)：将内存中的节点 $x$ 写回磁盘。

CLRS的伪代码中，在访问节点 $x$ 的属性之前，隐含了 x = DISK-READ(x) 操作。

内存缓存

在实际系统中，常用LRU缓存策略将最近访问的B树节点保留在内存中：

• 根节点通常常驻内存（访问频率最高）
• 最近访问的内部节点和叶子节点缓存在内存中
• 缓存命中时无需实际磁盘I/O

核心性质

1. I/O次数与树高度的关系

B树的每次操作（搜索、插入、删除）的磁盘I/O次数为 $O(h)$，其中 $h$ 为树高。结合B树高度定理：

$\text{I/O次数}=O\left({\log }_t\frac{n+1}{2}\right)$

2. 节点内搜索的CPU代价

在内存中搜索一个节点内的 $n$ 个关键字：

• 线性搜索：$O(n)=O(t)$，对于较小的 $t$ 足够高效
• 二分搜索：$O(\log n)=O(\log t)$，当 $t$ 较大时更优
• 实际系统中通常使用二分搜索

由于 $O(t)$ 或 $O(\log t)$ 的CPU代价远小于一次磁盘I/O的代价，节点内搜索的开销通常可以忽略。

3. 与虚拟内存系统的类比

B树的设计思想与操作系统中的虚拟内存页表有相似之处：

概念	B树	虚拟内存
大块传输	磁盘页	内存页
缓存	内存中的B树节点	TLB / 页表缓存
目标	减少磁盘I/O	减少缺页中断

参见

• B树 — 磁盘表示所服务的核心数据结构
• 最小度 — 由磁盘页大小决定的关键参数
• B树高度定理 — 磁盘I/O次数的理论保证
• B树的插入操作 — 磁盘I/O在插入中的具体表现
• B树的删除操作 — 磁盘I/O在删除中的具体表现