1 存储介质与存储层次

1.1 为什么数据库系统要关心存储结构

数据库管理系统（DBMS）不仅负责逻辑层面的 SQL、关系模型和事务管理，也必须处理底层数据怎样放在物理介质上的问题。原因很直接：数据库中的数据通常远大于内存，且必须持久化保存。因此，DBMS 的很多性能瓶颈不是来自 CPU 计算，而是来自磁盘或其他 I/O 设备的读写。

从应用角度看，数据库系统至少有两个基本需求：

持久化存储：数据不能因为程序退出或断电就丢失，因此必须存放在磁盘、SSD、磁带等非易失介质中。
高效、可靠访问：数据不仅要能保存，还要能以较低代价被读取、修改和恢复。

“性能”不是单一指标。数据库内核的很多优化都是 trade-off：例如为了提高可靠性可能牺牲空间利用率，为了提高顺序读速度可能让随机写更复杂。不存在适用于所有场景的 one fits all 方案。

1.2 存储介质的层次结构

计算机系统中的存储通常按速度、容量、价格和持久性形成层次结构：

层次	典型介质	速度	容量	是否持久	主要用途
第一级存储器（Primary Storage）	高速缓存、内存	最快	较小	通常不持久	CPU 直接访问、DBMS Buffer Pool
第二级存储器（Secondary Storage）	Flash/SSD、磁盘	中等	大	持久	数据库文件、索引、日志
第三级存储器（Tertiary Storage）	光盘、磁带、胶片	慢	很大	持久	归档、备份、冷数据

分级存储存在的原因主要有三点：

价格因素：越快的存储越贵。主存价格通常远高于磁盘，因此不能把所有数据库数据都放在内存中。
寻址能力限制：例如 32 位机器可直接寻址的主存空间受 $2^{32}$ 限制。
持久化需求：内存断电后数据会丢失，数据库必须依赖非易失存储保存数据。

数据库系统的核心思想之一就是：把当前需要处理的页从磁盘调入内存，在内存中操作，再按需要写回磁盘。这正是后面 Buffer Pool 和 Replacement Policy 要解决的问题。

2 磁盘的数据存储原理

2.1 磁盘的基本结构

传统机械磁盘由盘片、磁道、扇区、磁头和磁盘臂等部分组成。理解这些结构有助于解释为什么随机 I/O 昂贵、顺序 I/O 相对便宜。

概念	含义
盘片（Platter）	实际存放数据的圆形盘面，一个磁盘可以有多个盘片
磁道（Track）	盘面上的同心圆轨道
柱面（Cylinder）	多个盘面上半径相同的磁道集合
扇区（Sector）	硬件上的最小存储单位，是硬件不可变属性
块（Block）	数据存储和传输的基本单位，通常由若干 sector 构成
磁头（Head）	读写盘面数据的部件，每个盘面通常有一个磁头

磁盘容量可估算为：

\[ \text{容量} = \text{盘面数} \times \frac{\text{磁道数}}{\text{盘面}} \times \frac{\text{盘块数}}{\text{磁道}} \times \frac{\text{字节数}}{\text{盘块}} \]

传统磁盘访问主要涉及两类机械动作：

盘片转动：让目标扇区转到磁头下面。
磁头伸缩/磁盘臂移动：让磁头移动到目标磁道。

因此，“找数据”并不是 CPU 里一次寻址那么简单，而是包含机械定位过程。这也是机械磁盘随机访问慢的根本原因。

2.2 磁盘访问时间

磁盘读取一个块的时间通常由三部分组成：

\[ \text{Access Time} = \text{Seek Time} + \text{Rotational Delay} + \text{Transfer Time} \]

组成部分	中文含义	解释
Seek Time	寻道时间	磁头移动到目标磁道所需时间
Rotational Delay	旋转延迟	等目标扇区转到磁头下方所需时间
Transfer Time	传输时间	数据真正从磁盘传到内存所需时间

在机械磁盘中，寻道和旋转延迟通常比实际传输更昂贵。所以 DBMS 会尽量把经常一起访问的数据放在物理上接近的位置，例如同一个 block、track 或 cylinder 上。这样可以减少机械移动，提高顺序读写性能。

2.3 磁盘读写单位与 DBMS 性能

DBMS 在操作数据时，真正执行计算的是内存中的数据；磁盘和内存之间交换数据的单位通常是 Block 或 DBMS 逻辑上的 Page。一次磁盘页传输可以看作一次 I/O 操作。

需要特别注意：

DBMS 的很多代价模型都以页 I/O 次数为单位，而不是以 CPU 指令数为单位。

原因是传统磁盘 I/O 比内存计算慢得多。典型量级是：

读写一页时间 $D \approx 15$ 毫秒。
处理一条记录或执行 Hash 函数的时间 $C,H \approx 100$ 纳秒。

两者相差多个数量级，所以在数据库内核的代价模型中，估算查询代价时通常优先关注“读写了多少页”。

2.4 磁盘控制器、校验与记录跨块

磁盘控制器负责执行底层操作，例如移动磁头、定位块、传输数据等。为了检测数据读写是否正确，磁盘系统会使用 Checksum：写入时计算校验值，读取时重新计算并比较，以发现传输或存储错误。

记录在磁盘块中的存放方式有两类：

不跨块方式：一条记录必须完整放在一个块中，实现简单，读取一条记录最多访问一个块，但可能造成块内空间浪费。
跨块方式：一条记录可以跨多个块，空间利用率更高，但读取和维护更复杂。

3 Flash Memory 与第三级存储器

3.1 Flash Memory 的特点

Flash Memory 是一种电可擦可编程只读存储器（EEPROM）。SSD 就是基于 Flash Memory 的常见存储设备。

Flash 的关键特点是：

Page 是读写操作单位，典型大小如 2KB。
写操作只能把 bit 从 $1$ 改成 $0$。
如果要把 bit 从 $0$ 改回 $1$，必须擦除整个区域。
擦除单位是固定大小的区域，称为 erase unit、erase block 或 block，典型值如 128KB。

这说明 Flash 与机械磁盘的性能瓶颈不同。机械磁盘的主要问题是机械移动；Flash 没有磁头寻道，但有“先擦除再写入”的限制。因此 Flash/SSD 的随机读通常较好，但写入、擦除、磨损均衡等问题需要专门管理。

3.2 第三级存储器

第三级存储器主要用于备份、归档和冷数据存储，常见介质包括：

光盘：CD、DVD、WORM。
磁带：价格便宜、容量大，但通常顺序读取。
胶片等其他长期归档介质。

其中磁带的典型特点是顺序访问。如果要读取中间某段数据，往往要先经过前面的数据，因此不适合频繁随机查询，但适合长期备份和批量恢复。

4 RAID 磁盘系统

4.1 RAID 的动机

磁盘长期是数据库系统性能瓶颈。微处理器速度提升很快，而磁盘访问速度提升较慢，这使得 CPU 与 I/O 之间的差距越来越大。

RAID（Redundant Array of Independent Disks） 的基本思想是把多个磁盘组织成一个整体：

通过 数据条带（Data Striping） 把数据分布到多个磁盘上，利用并行性提高读写吞吐。
通过 冗余（Redundancy） 保存校验或副本，提高可靠性。

也就是说，RAID 同时关注两个目标：性能和 可靠性。

4.2 数据条带

数据条带是把数据切分成等长分区，并分布到多个磁盘上。每个分区大小称为 条带单元（striping unit）。

举例来说，如果有 4 块盘，数据页可以轮流放到 Disk 1、Disk 2、Disk 3、Disk 4。这样读取连续数据时，多个磁盘可以并行工作，提高整体吞吐量。

条带大小会影响性能：

条带较小：更容易利用并行性，但管理开销较大。
条带较大：连续访问效率高，但小请求可能只落在少数磁盘上，并行性不足。

4.3 数据冗余与校验

仅仅把数据分散到多个磁盘会降低可靠性，因为任意一个磁盘损坏都可能破坏整个磁盘组的数据。RAID 通过冗余提升可靠性，关键问题包括：

冗余信息放在哪里。
冗余信息怎样计算。

常见冗余方法包括：

奇偶校验（Parity）。
海明码（Hamming Code）。
Reed-Solomon Code。

4.3.1 海明码直觉

海明码是一种可以纠正一位错误的编码方法。其基本思想是：在 $k$ 位信息位之外增加 $r$ 位冗余位，形成 $n=k+r$ 位码字。接收或读取时通过若干监督关系式计算校正因子，从而判断是否出错以及哪一位出错。

以 4 位数据为例：

\[ d_3\ d_2\ d_1\ r_2\ d_0\ r_1\ r_0 = b_7\ b_6\ b_5\ b_4\ b_3\ b_2\ b_1 \]

其中冗余位通过异或计算：

$b_1$ 是 $b_3,b_5,b_7$ 的异或。
$b_2$ 是 $b_3,b_6,b_7$ 的异或。
$b_4$ 是 $b_5,b_6,b_7$ 的异或。

验证方程为：

\[ G_1=b_1 \oplus b_3 \oplus b_5 \oplus b_7 \]

\[ G_2=b_2 \oplus b_3 \oplus b_6 \oplus b_7 \]

\[ G_3=b_4 \oplus b_5 \oplus b_6 \oplus b_7 \]

如果所有 $G_i$ 都为 0，说明没有检测到错误；如果不为 0，则这些校验结果组合起来可以定位一位错误。练习中通常不要求复杂推导，但要理解：海明码用额外冗余位换取错误定位和纠错能力。

4.4 RAID Level 对比

RAID Level	核心思想	冗余方式	空间利用率/代价	适用场景
RAID 0	只做条带化	无冗余	空间利用率 100%，可靠性差	追求低成本和高写性能，但不能容忍故障的场景较少
RAID 1	镜像	每块盘有备份	空间利用率约 50%，成本最高	可靠性要求高、小型系统
RAID 0+1	条带化 + 镜像	镜像冗余	性能类似 RAID 1，利用条带提升并行性	小型系统或大量写场景
RAID 2	位级条带 + 海明码	Hamming Code	校验盘数量约为数据盘数量的对数	现在较少使用
RAID 3	位级条带 + 奇偶校验	单校验盘	一个 check disk	大规模连续读写，优于 RAID 2
RAID 4	块级条带 + 奇偶校验	单校验盘	写入时 check disk 容易成为瓶颈	被 RAID 5 改进
RAID 5	块级条带 + 分布式奇偶校验	校验信息分布到不同磁盘	避免单个 check disk 瓶颈	综合性能较好，优于 RAID 4
RAID 6	RAID 5 + 双重冗余	Reed-Solomon 等 P+Q 冗余	可容忍两个磁盘同时故障，冗余代价更高	高可靠性系统

4.4.1 Read-Modify-Write Cycle

RAID 2、4 等级别中，写操作可能遵循 read-modify-write cycle。其直觉是：如果只修改一个数据块，系统不能简单覆盖数据，还必须更新对应校验信息。因此需要读取旧数据和旧校验，计算新校验，再写回新数据和新校验。

这解释了为什么某些 RAID level 的写性能不如读性能，也解释了为什么 RAID 5 要把校验信息分散到不同磁盘上：避免所有写操作都争用同一个 check disk。

5 DBMS 的磁盘空间管理与缓冲区管理

5.1 磁盘空间管理

磁盘空间管理位于 DBMS 结构的最底层，主要负责以页为单位组织数据库文件。其基本操作包括：

读页。
写页。
申请新页。
释放页。

它还需要记录哪些块或页正在使用、每一页的位置，以及哪些页仍有空闲空间。常见方法包括：

方法	含义	特点
空闲块链表	把空闲块串成链表	实现简单，但查找满足特定空间大小的页可能不够高效
空闲块位图	用 bitmap 标记块是否空闲	查询和统计更方便，适合规则管理

DBMS 管理磁盘空间有两种实现路线：

利用操作系统文件系统：跨平台和实现成本较好，但某些底层控制能力受限。
DBMS 自己实现磁盘访问：可以获得更强控制能力，但实现复杂、跨平台成本高。

选择时要考虑跨平台需求、操作系统是否提供所需功能、DBMS 对性能和可靠性的控制要求等因素。

5.2 Page 的含义与层次关系

在 DBMS 中，页（page）是数据库在磁盘和内存之间搬运数据的基本单位。查询语句看到的是表、记录和属性，但 DBMS 内核真正读写磁盘时，通常不是一条记录一条记录地搬，而是以 page 为单位把一整块数据库数据读入内存。

可以把一个数据库文件想成下面这样的层次：

数据库文件
  -> Page 1
      -> Record 1
      -> Record 2
      -> Record 3
      -> free space
  -> Page 2
      -> Record 4
      -> Record 5
      -> free space

也就是说，一个 page 里通常会放多条记录。比如一页大小是 8KB，一条学生记录平均 100B，那么一个 page 大约可以放几十条记录。DBMS 读入这一页后，页内的多条记录都已经在内存中，后续访问同页记录时就不需要再次访问磁盘。

Page 的作用可以从三个角度理解：

角度	Page 的作用
磁盘 I/O	DBMS 以页为单位从磁盘读入、写回数据
Buffer Pool	Buffer Pool 中的一个 frame 通常容纳一个 page
记录定位	一条记录常用 `(page id, slot number)` 定位

因此，记录标识符 rid 通常写成：

\[ \text{rid} = (\text{page id}, \text{slot number}) \]

例如 rid = (17, 2) 表示：这条记录在第 17 页的第 2 个 slot 中。这里的 page id 先定位到哪一页，slot number 再定位到页内哪条记录。

5.2.1 Page、Block、Sector 的区别

Page 容易和 block、sector 混在一起。它们的关键区别是所属层次不同：

概念	所属层次	谁主要使用	含义
Sector	磁盘硬件层	硬盘硬件	硬件最小物理存储单位
Block	磁盘/文件系统层	文件系统、磁盘 I/O	操作系统或存储设备一次分配、读写的连续空间单位
Page	DBMS 层	数据库系统	数据库组织文件、缓存数据和估算 I/O 代价的单位

一个常见关系是：

1 2	多个 sector 组成一个 block 一个或多个 block 对应一个 DBMS page

例如：

1
2
3

sector = 512B 或 4KB
block  = 4KB
page   = 8KB

在这个例子中，一个 DBMS page 可能对应两个 4KB 的 block。实际系统里 page 和 block 的大小可能相同，也可能不同。一般来说，“磁盘以块为单位读写”偏底层硬件/文件系统；“DBMS 以页为单位组织数据”偏数据库内核。

5.2.2 为什么 DBMS 不按单条记录读写

DBMS 使用 page 而不是单条记录作为 I/O 单位，主要是因为磁盘访问的固定开销很高。一次随机读通常包含寻道、旋转延迟和传输时间，其中前两项与读取多少字节没有完全线性关系。既然已经付出了定位成本，一次多读一些相邻数据通常更划算。

这也符合数据库访问的局部性：

如果正在顺序扫描一个表，同一页里的下一条记录很可能马上会被访问。
如果通过索引找到某条记录，页内附近记录也可能属于相近键值范围。
如果一个 page 被放进 Buffer Pool，后续访问同一页记录时可以直接命中内存。

所以可以这样记：

Page 是 DBMS 眼里的“一块数据”；Block 是文件系统或存储设备眼里的“一块数据”；Sector 是硬件眼里的“一小格数据”。

5.3 缓冲区管理器与 Buffer Pool

缓冲区管理器负责把磁盘上的页读入内存，并在需要时写回磁盘。它管理的一片内存区域称为 Buffer Pool。Buffer Pool 中每个可容纳一页的单位称为 Frame。

如果表有 100 个页，而 Buffer Pool 只有 10 个 frame，那么扫描表时 DBMS 不可能把所有页同时放入内存。它必须不断决定：

请求的页是否已经在 Buffer Pool 中。
如果不在，应该读入哪个 frame。
如果 Buffer Pool 满了，应该替换哪个已有页。
被替换的页如果修改过，是否需要先写回磁盘。

决定哪些页被替换的策略称为 Replacement Policy。

5.4 Frame 的关键状态：pin_count 与 dirty

每个 frame 至少需要维护两个重要信息：

字段	含义	作用
`pin_count`	正在访问该 frame 的事务/操作个数	`pin_count > 0` 表示该页正在被使用，不能被替换
`dirty`	该 frame 中的数据是否被修改过	dirty frame 被替换前必须写回磁盘

请求处理流程可以概括为：

查看 Buffer Pool 中是否已有目标页。
如果已有，增加该 frame 的 pin_count，返回 frame 地址。
如果没有，寻找一个 pin_count=0 的可替换 frame。
如果该 frame 是 dirty，则先写回磁盘。
将目标页从磁盘读入该 frame。
设置元数据并返回 frame 地址。

如果没有任何 pin_count=0 的 frame，说明所有 frame 都正在被使用，此时新的请求只能等待。

5.5 Buffer Replacement Policy

5.5.1 LRU

LRU（Least Recently Used，最近最少使用） 的思想是：最近使用过的页未来可能还会被使用，而最久没有被使用的页更适合淘汰。

在 Buffer Pool 中，一个页只有在 pin_count=0 时才成为可替换候选。LRU 会优先替换最早变成“可选择”的页。

举个例子，假设 Buffer Pool 只有 3 个 frame，当前有 Page A、Page B、Page C，最近访问顺序是：

1 2	最久未使用最近使用 A -> B -> C

如果现在要读入 Page D，Buffer Pool 已满，并且 A、B、C 的 pin_count 都是 0，那么 LRU 会淘汰 Page A，因为它最长时间没有被访问：

1 2	淘汰前：A -> B -> C 淘汰后：B -> C -> D

如果之后又访问了 Page B，那么 Page B 会移动到“最近使用”的位置：

1 2	访问 B 前：B -> C -> D 访问 B 后：C -> D -> B

所以下一次需要替换时，LRU 会优先考虑 Page C。

还要注意 pin_count 的限制。如果当前顺序是 A -> B -> C，但 Page A 的 pin_count=1，说明它正在被使用，即使 A 最久未访问也不能淘汰。此时 LRU 会跳过 A，选择下一个最久未使用且 pin_count=0 的页，例如 Page B。

简单记忆：LRU 不是淘汰“最早放进 Buffer Pool 的页”，而是淘汰“最长时间没有再被访问、且当前没有被 pin 住的页”。

5.5.2 Clock

Clock 策略可以看作 LRU 的近似实现，可以想象成一个“带第二次机会的缓存淘汰算法”。它把所有 frame 排成一个环，并维护一个指针扫描这些 frame。每个 frame 有一个 referenced 标志。

规则很简单：

新访问过的页：referenced = true
要找页替换时，指针开始转
如果遇到 pin_count > 0 的页：正在被用，跳过
如果遇到 pin_count = 0 且 referenced = true 的页：给它一次机会，把 referenced 改成 false，跳过
如果遇到 pin_count = 0 且 referenced = false 的页：淘汰它

举个小例子。假设 Buffer Pool 有 4 个 frame：

Frame	Page	pin_count	referenced
F1	A	0	true
F2	B	0	true
F3	C	1	true
F4	D	0	false

现在要读入新页 E，但 Buffer Pool 满了。Clock 指针从 F1 开始：

F1：没被 pin，但 referenced=true，说明最近用过，改成 false，跳过。
F2：同理，改成 false，跳过。
F3：pin_count=1，正在被使用，不能淘汰，跳过。
F4：pin_count=0 且 referenced=false，淘汰 D，把 E 放进 F4。

所以 Clock 的核心直觉是：最近访问过的页先不给淘汰；如果转了一圈后它还没再被访问，就说明它可能没那么重要，可以淘汰。

Clock 的好处是实现成本低，不必像精确 LRU 那样维护复杂的访问顺序。

DB2 和 SQL Server 使用 clock 或类似策略；Sybase、Informix、Oracle 等系统使用 LRU 或类似策略。不同系统还可能支持单个或多个 Buffer Pool。

5.6 Buffer Pool 与虚拟内存的区别

Buffer Pool 看起来像操作系统虚拟内存中的页缓存，但数据库缓冲区管理有一个重要优势：DBMS 更了解数据访问模式。

数据库页访问不是随机发生的，它往往由上层查询计划决定。例如顺序扫描会连续访问大量页，索引查找会访问根节点、内部节点和叶子节点。DBMS 可以利用这些信息做：

Prefetching（预取）：提前把将要访问的页读入 Buffer Pool。
Dirty frame 强制写盘：在合适时机提前写回脏页，减少替换时等待。

这也是为什么数据库系统通常自己管理 Buffer Pool，而不是完全依赖操作系统页缓存。

6 文件组织方式

6.1 文件、页与记录标识符

在 DBMS 中：

一个文件包含多个页。
每个页包含多条记录。
每条记录有唯一标识符 rid（record id）。

这里 rid 通常包括：

\[ \text{rid} = (\text{page id}, \text{slot number}) \]

即 rid 对应的数据在【page id】页的第【slot number】个槽上。5.2 节举了一个例子，这里不再赘述。不同数据库系统对 rid 的具体定义可能略有不同，但核心作用相同：用一个稳定标识定位某条记录。

牢记在心：

数据库文件
  -> Page 1
      -> Record 1
      -> Record 2
      -> Record 3
      -> free space
  -> Page 2
      -> Record 4
      -> Record 5
      -> free space

6.2 堆文件

堆文件（Heap File） 是最简单的文件组织方式：记录在文件中无序存储。它通常支持：

创建文件。
删除文件。
插入记录。
删除记录。

堆文件的关键问题不是“顺序”，而是怎样找到有空闲空间的页。尤其是变长记录场景中，不同页剩余空间大小不同，插入一条记录前必须找到足够大的空闲区域。

这里的“堆文件”和数据结构中的“大根堆/小根堆”不是同一个概念。数据结构里的堆强调堆序性质，例如大根堆要求父节点不小于子节点，小根堆要求父节点不大于子节点，常用于优先队列和堆排序。数据库里的堆文件反而强调无序存放：记录不按某个 key 排序，只是被放到有空间的页中。

例如学生表中有几条记录：

S1 Wang 20
S2 Liu  21
S3 Chen 22
S4 Ma   19

在堆文件中，它们可能被放成：

Page 1
  slot 1: S2 Liu 21
  slot 2: S4 Ma 19

Page 2
  slot 1: S1 Wang 20
  slot 2: S3 Chen 22

这里既没有按照学号排序，也没有按照年龄排序。S1 不一定在最前面，年龄最大或最小的记录也不会自动处在某个特殊位置。所以可以把数据库中的 heap 理解成“随便堆在一起的一组记录”。正因为没有顺序结构，堆文件插入很方便，但如果没有索引，按条件查找通常只能扫描页。

堆文件有两种实现方式：页链表和页字典。（其实更准确地说应该是管理空闲页的方式）

6.2.1 页链表

页链表是一种管理堆文件中数据页的简单方法。它的核心思想是：不要让 DBMS 每次插入记录时都从头扫描整个文件，而是在文件头维护一些指针，直接找到可能有空闲空间的页。

一种常见做法是让文件头页（header page）记录两条链表的起点：

含空闲空间的页链表。
不含空闲空间的页链表。

可以画成：

1
2
3

Header Page
  free_page_list -> Page 3 -> Page 8 -> Page 10
  full_page_list -> Page 1 -> Page 2 -> Page 5 -> Page 7

这里的含义是：

free_page_list 指向仍有空闲空间的数据页。
full_page_list 指向已经没有空闲空间，或者空闲空间不足以继续插入常规记录的数据页。
每个数据页内部除了保存记录，还会保存“下一页”的指针，从而把多个页串成链表。

6.2.1.1 插入操作

插入记录时，DBMS 可以先看 free_page_list：

从文件头找到含空闲空间链表的第一个页，比如 Page 3。
检查 Page 3 是否能放下新记录。
如果能放下，就把记录插入 Page 3 的某个空闲 slot。
插入后如果 Page 3 仍有空闲空间，它继续留在 free_page_list。
如果 Page 3 被插满，就把它从 free_page_list 移到 full_page_list。

举个例子，假设每页最多放 3 条定长记录。当前堆文件是：

Header Page
  free_page_list -> Page 2 -> Page 4
  full_page_list -> Page 1 -> Page 3

Page 1: [S1, S2, S3]        已满
Page 2: [S4, S5, 空]        有空闲 slot
Page 3: [S6, S7, S8]        已满
Page 4: [S9, 空, 空]        有空闲 slot

现在插入新记录 S10，DBMS 不需要从 Page 1 开始逐页找空位，而是直接通过 free_page_list 找到 Page 2：

1	Page 2: [S4, S5, S10]

插入后 Page 2 满了，所以链表要调整为：

1
2
3

Header Page
  free_page_list -> Page 4
  full_page_list -> Page 2 -> Page 1 -> Page 3

6.2.1.2 删除操作

删除记录时，情况反过来。如果从一个满页中删除一条记录，这个页又重新有了空闲空间，就应该把它从 full_page_list 移回 free_page_list。例如删除 Page 1 中的 S2 后：

1	Page 1: [S1, 空, S3]

Page 1 不再是满页，因此可以进入含空闲空间链表：

1
2
3

Header Page
  free_page_list -> Page 1 -> Page 4
  full_page_list -> Page 2 -> Page 3

6.2.1.3 优缺点

页链表的优点是实现简单，插入时能较快找到“可能有空位”的页。但它的缺点也很明显：链表通常只告诉我们某页有没有空闲空间，却不一定告诉我们空闲空间有多大。对于定长记录，这个问题不严重，因为只要有一个空 slot 就能插入；但对于变长记录就麻烦了。

例如 Page 3 只剩 20B 空间，Page 8 剩 200B 空间，它们都在 free_page_list 中。如果要插入一条 150B 的变长记录，DBMS 可能先访问 Page 3，发现放不下，再继续沿链表找 Page 8。这会增加额外 I/O。因此，对于变长记录，后面的页字典通常更合适，因为它会记录每个页的空闲空间大小。

6.2.2 页字典

另一种管理堆文件空闲空间的方法是 页字典（page directory）。它和页链表的目标相同：都是为了让 DBMS 在插入记录时尽快找到合适的数据页。但页字典不是简单地把页串成链表，而是用一个目录结构记录每个数据页的状态，尤其是每个页还剩多少空闲空间。

可以把页字典理解成一本“页目录”：

Header Page / Directory Page
  Page 1: free space = 0B
  Page 2: free space = 120B
  Page 3: free space = 20B
  Page 4: free space = 300B
  Page 5: free space = 80B

数据页本身仍然存放记录：

Page 1: [S1, S2, S3]             free = 0B
Page 2: [S4, S5, ...]            free = 120B
Page 3: [S6, ...]                free = 20B
Page 4: [S7, ...]                free = 300B
Page 5: [S8, S9, ...]            free = 80B

页字典中的每一项通常至少包含：

字段	含义
Page id	数据页编号
Free space	该页剩余空闲空间大小
Page pointer	指向该数据页的位置或偏移

6.2.2.1 插入操作

插入记录时，DBMS 可以先读页字典，而不是逐个访问数据页：

假设要插入一条长度为 100B 的记录。
DBMS 查看页字典，发现 Page 2 剩 120B，Page 4 剩 300B。
Page 2 和 Page 4 都能放下记录，可以选择其中一个，例如 Page 2。
将记录插入 Page 2。
更新页字典中 Page 2 的空闲空间信息，例如从 120B 改成 20B。

插入前：

Directory
  Page 1: free = 0B
  Page 2: free = 120B
  Page 3: free = 20B
  Page 4: free = 300B

插入一条 100B 记录到 Page 2 后：

Directory
  Page 1: free = 0B
  Page 2: free = 20B
  Page 3: free = 20B
  Page 4: free = 300B

如果要插入的是一条 200B 的变长记录，DBMS 就不会选择 Page 2，因为 Page 2 只有 120B。它可以直接根据字典选择 Page 4：

要插入记录大小 = 200B

Page 2: free = 120B   不够
Page 3: free = 20B    不够
Page 4: free = 300B   可以放

这就是页字典比页链表更适合变长记录的原因。页链表通常只能告诉 DBMS“这个页有空闲空间”，但不能直接说明“空间够不够”。页字典则把空闲空间大小记录下来，DBMS 可以更精确地挑选页面。

6.2.2.2 删除操作

删除记录时，页字典也要同步更新。假设从 Page 1 删除一条 90B 的记录：

删除前：+
Directory
  Page 1: free = 0B

删除后：
Directory
  Page 1: free = 90B

这样下一次插入记录时，Page 1 又会被视为候选页。

6.2.2.3 优缺点

页字典的优点是：

字典相对数据部分较小，通常读入字典的代价比扫描大量数据页低。
能记录每个页的空闲空间大小，因此能更精确地选择有足够空间的页。
对变长记录更友好，减少“访问了某页才发现放不下”的无效 I/O。

页字典的缺点是：

每次插入、删除或记录长度变化后，都要维护字典信息。
如果文件非常大，字典本身也可能占多个页，需要进一步管理目录页。
字典记录的是“页级别”的空闲空间，不一定能完全反映页内碎片是否连续，因此有时还要结合页内部的 slot 字典或空闲空间整理。

简单记忆：页链表像是只说“哪些页可能有空位”；页字典像是额外写清楚“每页具体还剩多少空间”。

6.3 顺序文件

顺序文件（Sorted/Sequential File） 是另一种文件组织方式。它和堆文件最大的区别是：堆文件中的记录无序存放，而顺序文件会根据某个 查找键（search key） 的值，把记录按顺序组织起来。

这里的 search key 不一定是主键，它只是文件用来排序或组织记录的属性。例如学生表可以按学号 sid 排序，也可以按姓名 name 排序，还可以按年龄 age 排序。选择哪个属性作为 search key，取决于系统希望优化哪类查询。

假设学生记录按学号 sid 排序：

S1 Wang 20
S2 Liu  21
S3 Chen 22
S4 Ma   19
S5 Zhou 23

这些记录在文件中的逻辑顺序就是：

1	S1 -> S2 -> S3 -> S4 -> S5

如果每页最多放 2 条记录，可能组织成：

Page 1
  slot 1: S1 Wang 20
  slot 2: S2 Liu  21
  next -> Page 2

Page 2
  slot 1: S3 Chen 22
  slot 2: S4 Ma   19
  next -> Page 3

Page 3
  slot 1: S5 Zhou 23
  slot 2: 空
  next -> null

next 表示页或记录之间可以用指针维持顺序。“每个记录有一个指针，按键值大小创建链表”的意思是：即使物理页不一定严格连续，DBMS 也能通过指针按 search key 的顺序访问下一条记录。

6.3.1 等值查询为什么更快

如果查询条件正好用的是 search key，例如：

1	SELECT * FROM Student WHERE sid = 'S3';

顺序文件可以利用“按 sid 有序”这个性质查找。直觉上类似在有序数组中查找元素：不需要从头到尾扫描所有记录，而是可以通过二分查找或类似方法先定位到目标页，再在页内找目标记录。

例如：

1
2
3

Page 1: S1, S2
Page 2: S3, S4
Page 3: S5

要找 S3，DBMS 可以较快判断目标应该在中间附近，而不必像堆文件那样从 Page 1 一路扫到最后。

但注意：这个优势只对排序属性明显。如果文件按 sid 排序，而查询是：

1	SELECT * FROM Student WHERE age = 20;

那么 age 不是排序键，顺序文件就不能直接利用 sid 的顺序，仍可能需要扫描很多页。

6.3.2 范围查询为什么更适合顺序文件

顺序文件特别适合范围查询，例如：

1 2	SELECT * FROM Student WHERE sid BETWEEN 'S2' AND 'S4';

因为记录按 sid 排序，DBMS 可以先定位到 S2，然后顺着文件向后读，直到超过 S4 为止：

1
2
3

S1 -> S2 -> S3 -> S4 -> S5
      ^---------^
       需要读取的范围

这比堆文件高效得多。堆文件中记录无序，S2、S3、S4 可能分散在任意页里。即使找到了 S2，也不能保证后面就是 S3 和 S4，所以通常还要扫描整个文件。

顺序文件的优势是：

按排序属性做等值查找或范围查找时效率较高。
适合经常按某个键顺序扫描的数据。

6.3.3 插入为什么麻烦

顺序文件的代价主要体现在插入和删除。因为记录必须保持 search key 顺序，不能像堆文件那样随便找个有空位的页放进去。

还是以上面的文件为例：

1
2
3

Page 1: [S1, S2]
Page 2: [S3, S4]
Page 3: [S5, 空]

现在插入一条新记录：

1	S2.5 Tang 20

它的正确位置应该在 S2 和 S3 之间：

1	S1 -> S2 -> S2.5 -> S3 -> S4 -> S5

如果 Page 1 已经满了，就不能直接塞进去。DBMS 可能需要：

插入时要找到正确位置。
需要申请空闲空间。
需要维护链表或顺序结构。
如果要求物理连续存放，插入删除可能引发大量数据移动。

一种可能的结果是申请新页或使用溢出页（overflow page）：

Page 1: [S1, S2]
Overflow Page: [S2.5]
Page 2: [S3, S4]
Page 3: [S5, 空]

逻辑顺序：
S1 -> S2 -> S2.5 -> S3 -> S4 -> S5

这样虽然保持了逻辑顺序，但文件结构变复杂了。如果溢出页越来越多，顺序扫描时就会频繁跳转，性能会下降。因此实际系统可能需要定期重组文件，把溢出页重新整理回主数据页。

6.3.4 删除为什么也要维护顺序结构

删除记录看起来比插入简单，因为删除不会破坏顺序。但删除后会产生空洞，也可能需要维护指针。

例如删除 S3：

删除前：
S1 -> S2 -> S3 -> S4 -> S5

删除后：
S1 -> S2 -> S4 -> S5

如果记录之间有指针，那么 S2 的 next 指针需要从 S3 改成 S4。如果页内留下空 slot，还要记录这个空闲位置，方便后续插入使用。如果系统要求物理空间紧凑，还可能移动记录，但这样又可能影响 rid 的稳定性。

所以顺序文件的典型 trade-off 是：

操作	表现	原因
Scan	好	数据按顺序组织，适合连续读取
Equality Search	对 search key 好	可以利用有序性快速定位
Range Search	很好	定位起点后顺序向后读即可
Insert	较差	必须找到正确位置并维护顺序
Delete	较差	要维护指针、空洞或物理紧凑性

简单记忆：顺序文件用“维护有序”的成本，换取按 search key 查询，尤其是范围查询的效率。

6.4 聚集文件

聚集文件（Clustered File） 是一种把多个关系中“经常一起访问”的记录放得很近的文件组织方式。更具体地说，它把多个关系中的元组存放在同一个文件中，并根据某个键属性组织这些数据。

它的核心思想不是“单个表内部按某个属性排序”，而是：把不同表中有联系的记录放在同一个文件里，甚至放在相邻 page 或同一个 page 中，这样做连接查询时可以减少磁盘 I/O。

6.4.1 从学生表和选课表理解聚集文件

假设有两个关系：

学生表 S：

sid	name	age	gender
S1	Wang	20	M
S2	Liu	21	F
S3	Chen	22	M

选课表 SC：

sid	cid	grade
S1	C1	80
S1	C2	70
S3	C1	90
S3	C2	85
S3	C3	95

如果不使用聚集文件，两个关系通常分别存放：

S 文件：
Page S1: [S1 Wang 20 M, S2 Liu 21 F]
Page S2: [S3 Chen 22 M]

SC 文件：
Page SC1: [S1 C1 80, S1 C2 70]
Page SC2: [S3 C1 90, S3 C2 85]
Page SC3: [S3 C3 95]

现在如果查询：

SELECT *
FROM S, SC
WHERE S.sid = SC.sid
  AND S.sid = 'S3';

DBMS 需要先在 S 文件里找到 S3 Chen 22 M，再去 SC 文件里找所有 sid='S3' 的选课记录。这涉及两个文件，可能访问多个 page。

聚集文件的做法是，把同一个学生的基本信息和他的选课记录组织在一起：

Clustered File, clustered by sid

Group S1:
  S  record:  S1 Wang 20 M
  SC record: S1 C1 80
  SC record: S1 C2 70

Group S2:
  S  record:  S2 Liu 21 F

Group S3:
  S  record:  S3 Chen 22 M
  SC record: S3 C1 90
  SC record: S3 C2 85
  SC record: S3 C3 95

如果按 page 来想，可能是：

Page 1
  S1 Wang 20 M
  S1 C1 80
  S1 C2 70
  S2 Liu 21 F

Page 2
  S3 Chen 22 M
  S3 C1 90
  S3 C2 85
  S3 C3 95

这样查询 S3 及其所有选课记录时，DBMS 读到 Page 2 后，很可能同时拿到学生基本信息和相关选课信息，减少了额外访问其他文件或其他页的次数。

6.4.2 聚集文件优化的是哪类查询

聚集文件特别适合频繁做连接查询、且连接条件稳定的场景。例如：

1
2
3

SELECT S.name, SC.cid, SC.grade
FROM S JOIN SC ON S.sid = SC.sid
WHERE S.sid = 'S3';

这个查询的访问模式是：找到一个学生，再找他的所有选课记录。因为 S 和 SC 经常通过 sid 一起访问，所以把它们按 sid 聚集在一起是有意义的。

再比如，如果应用经常查询：

某个订单及其所有订单明细。
某个部门及其所有员工。
某个帖子及其所有评论。

那么也可以考虑把主表记录和从表记录按共同 key 聚集存放。

6.4.3 聚集文件和顺序文件的区别

聚集文件容易和顺序文件混淆。它们都可能“按某个 key 组织”，但重点不同：

文件组织	重点	例子
顺序文件	一个关系内部按 search key 有序	学生表 `S` 内部按 `sid` 排序
聚集文件	多个关系中相关元组放在一起	`S` 中的 `S3` 和 `SC` 中所有 `S3` 选课记录放在附近

也就是说，顺序文件主要优化单表按键查找和范围查询；聚集文件主要优化多个关系之间的连接访问。

6.4.4 聚集文件的优点

聚集文件的主要优点是减少 I/O。因为相关记录存放得近，DBMS 一次读入一个 page 时，可能同时读到多个查询需要的记录。

以上面的 S 和 SC 为例：

非聚集存放：可能先读 S 文件的 page，再读 SC 文件的多个 page。
聚集存放：读到包含 S3 的 page 时，附近就有 S3 的选课记录。

这对连接查询很有帮助，尤其是“一对多”关系中经常查询“一的一方 + 多的一方”的全部相关记录。

6.4.5 聚集文件的缺点

聚集文件的缺点是维护复杂，而且高度依赖访问模式。

插入、删除和更新更复杂。
如果访问模式变化，聚集方式可能不再适合。
一个文件中混合多个关系，管理难度更高。

具体来说：

插入复杂：如果给 S3 新增一条选课记录 S3 C4 88，最好放在 S3 这一组附近。但如果 Page 2 已经满了，就可能需要溢出页或移动记录。
删除复杂：删除某个学生时，可能还要处理和他聚集在一起的多条选课记录。
更新复杂：如果聚集 key 改变，例如某条记录的 sid 改了，它可能需要移动到另一个聚集组。
不适合所有查询：如果查询只扫描整个 SC 表，聚集文件中穿插着 S 记录，反而可能增加处理复杂度。

所以聚集文件的 trade-off 是：

方面	表现
连接查询	通常更快，相关记录离得近
单独扫描某个关系	可能不如单独文件清晰
插入/删除/更新	更复杂，需要维护聚集关系
适用性	依赖 workload，如果应用访问模式变化，收益会下降

简单记忆：聚集文件就是把“经常一起查”的不同表记录放近一点，用存储上的接近换取连接查询时更少的 I/O。

6.5 哈希文件

哈希文件（Hashed File） 是一种按 Hash 函数组织记录的文件方式。它的核心思想是：对 search key 做 Hash 运算，根据运算结果直接决定记录应该放到哪个 bucket 中。

\[ \text{bucket} = h(\text{search key}) \]

这里的 bucket（桶） 可以理解成一组数据页。一个 bucket 可能只有一个 page，也可能包含多个 page。如果某个 bucket 放不下，还可能接溢出页（overflow page）。

6.5.1 用学生表理解哈希文件

假设学生表按学号 sid 作为 search key，并使用一个简单的 Hash 函数：

\[ h(\text{sid}) = \text{sid最后一位数字} \bmod 4 \]

如果有 4 个 bucket：

Bucket 0
Bucket 1
Bucket 2
Bucket 3

那么记录可能被分配为：

S1 -> 1 mod 4 = Bucket 1
S2 -> 2 mod 4 = Bucket 2
S3 -> 3 mod 4 = Bucket 3
S4 -> 0 mod 4 = Bucket 0
S5 -> 1 mod 4 = Bucket 1
S6 -> 2 mod 4 = Bucket 2

对应的文件结构可以想成：

Bucket 0: [S4 Ma 19]
Bucket 1: [S1 Wang 20, S5 Zhou 23]
Bucket 2: [S2 Liu 21, S6 Tang 20]
Bucket 3: [S3 Chen 22]

6.5.2 等值查询为什么快

哈希文件最适合等值查询，例如：

1	SELECT * FROM Student WHERE sid = 'S6';

DBMS 可以直接计算：

\[ h(S6)=6 \bmod 4 = 2 \]

然后只访问 Bucket 2：

1	Bucket 2: [S2 Liu 21, S6 Tang 20]

接着在 Bucket 2 内部比较记录，找到 S6。如果 Hash 函数分布均匀、bucket 不太大，那么 DBMS 不需要扫描整个文件。这就是哈希文件等值查询快的原因。

和堆文件对比：

堆文件：不知道 S6 在哪，可能要扫描很多 page。
哈希文件：先算 $h(S6)$，直接跳到对应 bucket。

6.5.3 插入如何进行

插入记录也很直接。假设要插入：

S9 Xu 22

DBMS 先计算：

\[ h(S9)=9 \bmod 4 = 1 \]

所以 S9 应该插入 Bucket 1：

插入前：
Bucket 1: [S1 Wang 20, S5 Zhou 23]

插入后：
Bucket 1: [S1 Wang 20, S5 Zhou 23, S9 Xu 22]

只要 Bucket 1 还有空间，插入就比较高效。它不需要像顺序文件那样维护全局有序关系。

6.5.4 溢出问题

哈希文件必须处理 overflow（溢出）。如果很多记录经过 Hash 后落到同一个 bucket，而这个 bucket 的主 page 已经满了，就需要额外的溢出页。

例如假设 Bucket 1 的主 page 最多只能放 3 条记录：

1 2	Bucket 1 main page: [S1 Wang 20, S5 Zhou 23, S9 Xu 22]

现在再插入：

1	S13 Zhao 21

因为：

\[ h(S13)=13 \bmod 4 = 1 \]

它也应该进入 Bucket 1，但主 page 已满，只能使用溢出页：

Bucket 1 main page:
  [S1 Wang 20, S5 Zhou 23, S9 Xu 22]
  overflow -> Bucket 1 overflow page:
                [S13 Zhao 21]

如果溢出页越来越多，查询 Bucket 1 时就不再只是读一个 page，而是要沿着 overflow chain 继续查找：

1	Bucket 1 main page -> overflow page 1 -> overflow page 2 -> ...

这样会削弱哈希文件的优势。因此好的 Hash 函数、合适的 bucket 数量、动态扩展机制都很重要。

6.5.5 为什么范围查询不适合哈希文件

哈希文件不适合范围查询，例如：

1 2	SELECT * FROM Student WHERE sid BETWEEN 'S2' AND 'S5';

我们想要的是：

1	S2, S3, S4, S5

但它们经过 Hash 后可能分散在不同 bucket：

S2 -> Bucket 2
S3 -> Bucket 3
S4 -> Bucket 0
S5 -> Bucket 1

也就是说，S2 到 S5 在逻辑上连续，但在哈希文件中被打散了。DBMS 不能像顺序文件那样“找到 S2 后顺着读到 S5”，通常只能扫描大量 bucket，甚至扫描整个文件。

所以哈希文件的典型 trade-off 是：

操作	表现	原因
Equality Search	很好	计算 Hash 后直接定位 bucket
Range Search	差	Hash 打乱了 key 的大小顺序
Insert	通常较好	计算 Hash 后插入对应 bucket
Delete	通常较好	先定位 bucket，再在 bucket 内删除
Scan	一般	要扫描所有 bucket，且可能有空闲空间和溢出页

简单记忆：哈希文件用“打乱顺序分桶”的方式，换取等值查询的快速定位；但正因为顺序被打乱，范围查询就不擅长。

7 文件组织的代价模型

7.1 基本符号

可以用代价模型估算不同文件组织方式在不同操作下的成本。基本符号如下：

符号	含义
$B$	数据库或文件中的数据页数量
$R$	每页中的记录个数
$D$	读写一页的时间
$C$	处理一条记录的时间，例如比较属性
$H$	对一条记录执行 Hash 函数的时间

由于 $D$ 远大于 $C$ 和 $H$，很多简化代价公式会忽略 CPU 计算，只保留页 I/O 主项。

7.2 基本操作

文件组织方式通常从以下操作角度比较：

操作	含义
Scan	读取文件中的所有记录
Equality Search	读取满足某个相等条件的记录
Range Search	读取满足区间条件的记录
Insert	插入一条特定记录
Delete	删除一条特定记录

7.3 堆文件的代价

堆文件无序，因此查找通常只能扫描。

操作	代价	解释
Scan	$B(D+RC)$	每页读一次，每页处理 $R$ 条记录
Equality Search	若确定只有一个结果：$0.5B(D+RC)$；否则同 Scan	单个结果平均扫描半个文件；多个结果必须扫完
Range Search	$B(D+RC)$	无序文件无法利用范围顺序
Insert	$2D+C$	$读这一页D+插入C+写这一页D=2D+C$。若数据加在关系最后面，需要读写相关页
Delete	$D+C$	假设数据已经在内存中，可用 rid 中的 page id 访问对应页

堆文件适合插入频繁、查询条件不固定或主要通过索引访问的场景。

7.4 排序文件的代价

排序文件和顺序文件几乎是一件事。排序文件按 search key 有序存储。

操作	代价	解释
Scan	$B(D+RC)$	全表扫描仍需读所有页
Equality Search	$D\log_2B + C\log_2R$	没有重复且按查询属性排序时，可二分定位页和页内记录
Range Search	$D\log_2B + C\log_2R$	这里简化为同上或 $D\log_2B+\#matches$ 的形式
Insert	$B(D+RC)$	若数据连续存放，插入可能移动大量数据
Delete	$B(D+RC)$	若数据连续存放，删除也可能移动大量数据

排序文件适合按某个键频繁做范围查询，但不适合频繁插入删除。

7.5 哈希文件的代价

哈希文件通过 Hash 函数定位 bucket。若文件中保留一定空闲空间，扫描代价可估为 $1.25B(D+RC)$。

这里的系数 $1.25$ 和 bucket/page 中预留空闲空间的比例 有关。哈希文件为了让后续插入不至于频繁产生 overflow，通常不会把每个 bucket 都塞满，而是预留一部分空闲空间。这里的 $1.25B$ 相当于假设哈希文件的空间利用率约为 $80\%$。

也就是说，如果数据在完全放满的情况下需要 $B$ 个页，那么哈希文件因为保留了约 $20\%$ 的空闲空间，实际可能需要约 $1.25B$ 个页。Scan 时必须扫描这些实际存在的页，所以扫描代价变成 $1.25B(D+RC)$。

操作	代价	解释
Scan	$1.25B(D+RC)$	保存空闲空间导致页数相对更多
Equality Search	$H+D+0.5RC$	计算 Hash 后读目标 bucket，假设只有一个结果
Range Search	$1.25B(D+RC)$	Hash 打乱顺序，范围查询无法直接利用
Insert	$2D$	定位 bucket 后插入，可能读写页
Delete	$C+D$	查找目标记录并删除

哈希文件最适合等值查询，不适合范围查询。

7.6 三种文件组织方式总表

不同文件组织方式的简化比较如下：

文件类型	Scan	Equality Search	Range Search	Insert	Delete
Heap	$BD$	$0.5BD$	$BD$	$2D$	Search $+D$
Sorted	$BD$	$D\log_2B$	$D\log_2B+\#matches$	Search $+D$ 或更高	Search $+BD$
Hashed	$1.25BD$	$D$	$1.25BD$	$2D$	Search $+D$

这里的表格忽略了 $C$ 和 $H$ 等 CPU 项，是因为该模型主要关注页 I/O 主导的代价分析。

核心记忆：

Heap：插入简单，查找差。
Sorted：范围查询好，插入删除差。
Hashed：等值查询好，范围查询差。

8 页格式与记录格式

8.1 页格式

一个页由多条记录构成，每条记录占据一个 slot。记录标识符通常为：

\[ (\text{page id}, \text{slot number}) \]

这样做的好处是，外部模块可以通过 rid 定位记录，而不需要知道记录在页内的真实字节偏移。页内部可以通过 slot 字典或其他元数据把 slot number 翻译成实际位置。

8.2 定长记录

定长记录（Fixed-Length Record） 指每条记录长度固定，没有变长字段。因此：

每页能放多少条记录是确定的。
每条记录在页内的位置也容易计算。
字段偏移可以通过字段长度直接得到。

如果一条记录包含字段 $F_1,F_2,F_3,F_4,\ldots$，对应长度为 $L_1,L_2,L_3,L_4,\ldots$，页内基地址为 $B$，那么字段 $F_4$ 的地址可通过偏移计算：

\[ \text{Address}(F_4)=B+L_1+L_2+L_3 \]

8.2.1 Packed 与 Unpacked

定长记录删除时有两种常见处理方式：

方式	删除后处理	优点	缺点
Packed	把页中最后一条记录移动到被删除位置，使空闲空间集中在页尾	空间紧凑	rid 可能变化
Unpacked	删除后不移动记录，用 bitmap 或页尾信息记录空闲 slot	rid 稳定	页中可能有空洞

这里的重点是 rid 稳定性。数据库中很多上层结构可能持有某条记录的 rid，如果删除导致其他记录移动并改变 rid，就会带来额外维护成本。因此实际系统常常愿意牺牲一点页内紧凑性来保持 rid 稳定。

8.3 变长记录

变长记录（Variable-Length Record） 包含变长字段，因此无法简单分配固定 slot。常见例子包括字符串、可变数组、大对象等。

变长记录带来的问题包括：

每条记录长度不同，页内空间更容易碎片化。
删除记录后，需要调整页内空间，避免出现大量零碎空间。
修改某个字段可能导致记录变长，需要移动其他字段或整条记录。
如果记录变长后当前页容纳不下，可能要移动到其他页。
如果记录超过一页大小，需要分页或使用大对象机制。

8.4 Slot 字典

为了解决变长记录定位和 rid 稳定性问题，这里提出使用 slot 字典。slot 字典保存每条记录的：

起始位置。
记录长度。

此时 rid 中的 slot number 不再直接表示记录的物理起始位置，而是表示该记录在 slot 字典中的条目位置。即：

\[ \text{slot number} \rightarrow \text{slot dictionary entry} \rightarrow (\text{offset}, \text{length}) \]

这样，即使页内为了压缩碎片而移动记录本体，只要 slot 字典中的条目位置不变，rid 就可以保持稳定。

举个例子，假设 Page 17 中有三条变长记录，页尾维护一个 slot 字典：

Page 17

记录数据区：
  offset 100: R1 = "S1 Wang"
  offset 140: R2 = "S2 Christopher"
  offset 210: R3 = "S3 Li"

Slot 字典：
  slot 1 -> (offset=100, length=30)
  slot 2 -> (offset=140, length=60)
  slot 3 -> (offset=210, length=20)

此时记录 R2 的 rid 可以写成：

\[ \text{rid}(R_2) = (17, 2) \]

意思是：先找到 Page 17，再查 Page 17 的 slot 字典第 2 项，得到 R2 真正的页内位置 (offset=140, length=60)。

现在假设删除 R1。如果不整理空间，Page 17 里会出现一个空洞：

1
2
3

offset 100: 空洞，原来是 R1
offset 140: R2 = "S2 Christopher"
offset 210: R3 = "S3 Li"

为了减少碎片，DBMS 可能把 R2 和 R3 往前移动，压缩页内空间：

Page 17 压缩后

记录数据区：
  offset 100: R2 = "S2 Christopher"
  offset 160: R3 = "S3 Li"

Slot 字典：
  slot 1 -> deleted 或 free
  slot 2 -> (offset=100, length=60)
  slot 3 -> (offset=160, length=20)

注意，R2 的物理位置从 offset=140 变成了 offset=100，但它在 slot 字典中的位置仍然是 slot 2，所以它的 rid 仍然是：

\[ \text{rid}(R_2) = (17, 2) \]

这就是 slot 字典的核心价值：记录本体可以在页内移动，但外部看到的 slot number 不变，从而保持 rid 稳定。如果没有 slot 字典，rid 直接保存物理 offset，那么每次页内压缩或移动记录后，外部索引和引用都可能需要更新，维护成本会很高。

8.5 变长字段的两种存放方法

常见方法有两类：

方法	思想	优点	缺点
分隔符存放	字段连续存放，用特殊分隔符区分字段	实现直观	查找第 $i$ 个字段时可能要扫描前面字段
指针/偏移存放	在记录前端保存指向字段位置的指针或偏移	可快速定位字段	记录头部需要额外空间

8.5.1 分隔符存放的例子

假设有一条学生记录，字段分别是：

1
2
3

sid = S1
name = Wang
address = Shanghai

如果用分隔符 $ 存放，可以写成：

1	S1$Wang$Shanghai$

这里 $ 用来表示一个字段结束。DBMS 如果想读取第 1 个字段 sid，从开头读到第一个 $ 即可：

S1$

如果想读取第 3 个字段 address，就要先跳过前两个字段：

S1$Wang$Shanghai$
^  ^    ^
|  |    第三个字段开始
|  第二个分隔符
第一个分隔符

也就是说，分隔符方法实现简单，但访问靠后的字段时，可能必须从记录开头扫描，数过前面的分隔符后才能找到目标字段。这就是表格里“查找第 $i$ 个字段时可能要扫描前面字段”的含义。

8.5.2 指针/偏移存放的例子

另一种方法是在记录前端保存每个字段的起始位置，后面再连续存放字段内容。例如同一条记录：

1
2
3

sid = S1
name = Wang
address = Shanghai

可以存成：

记录头部：
  field 1 offset = 20
  field 2 offset = 22
  field 3 offset = 26

记录数据区：
  offset 20: S1
  offset 22: Wang
  offset 26: Shanghai

如果 DBMS 想读取 address，不需要从 S1 开始扫描，也不需要数分隔符，而是直接看记录头部：

1	field 3 offset = 26

然后跳到 offset 26 读取 Shanghai。这种方法访问字段更快，尤其适合字段很多、变长字段较多的记录。但它也需要额外空间保存 offset 或 pointer。

8.5.3 修改变长字段为什么麻烦

变长字段的麻烦在于：一个字段长度变化后，后面字段的位置可能都要变。

例如原记录是：

1	S1$Wang$Shanghai$

现在把 name 从 Wang 改成更长的 Christopher：

1	S1$Christopher$Shanghai$

可以看到，address = Shanghai 的起始位置被往后推了。对于指针/偏移存放方式，也要更新字段 offset：

修改前：
  field 1 offset = 20   -> S1
  field 2 offset = 22   -> Wang
  field 3 offset = 26   -> Shanghai

修改后：
  field 1 offset = 20   -> S1
  field 2 offset = 22   -> Christopher
  field 3 offset = 33   -> Shanghai

如果这一条记录变长后当前 page 仍然有足够空间，DBMS 可以在页内移动后续字段或移动整条记录，并更新 slot 字典中的 (offset, length)。如果当前 page 空间不够，就可能把记录移动到其他 page。为了保持原来的 rid 不变，系统可以在原位置留下一个转发信息（forwarding pointer），指向记录的新位置：

原位置：
  rid = (17, 2)
  forwarding pointer -> Page 25, slot 4

新位置：
  Page 25, slot 4: S1 Christopher Shanghai

这样外部仍然可以通过原来的 rid=(17,2) 找到记录，只是中间多了一次跳转。

对于变长记录，修改某列可能改变后续列的位置。如果记录变长后当前页空间不足，为保持 rid 不变，系统可能在原位置保存一个转发信息，指向记录的新位置。对于超大记录，Oracle 等系统可能不限制记录总长度，而 DB2 等系统可能限制记录长度，但提供大对象数据类型（LOB）来存放大字段。

9 总结

9.1 主线

本节课的主线可以概括为：

数据库数据必须持久化，不能只放在内存中。
机械磁盘访问慢，主要慢在寻道和旋转延迟。
DBMS 用页作为磁盘与内存之间的基本管理单位。
Buffer Pool 负责缓存页，Replacement Policy 决定淘汰谁。
文件组织方式影响 Scan、Equality Search、Range Search、Insert、Delete 的代价。
页内记录格式决定 rid 是否稳定、空间利用率如何、变长字段怎样访问。

9.2 核心概念

概念	一句话记忆
Seek Time	磁头移动到目标磁道的时间
Rotational Delay	等目标扇区转到磁头下方的时间
Transfer Time	真正传输数据的时间
Sector	磁盘硬件层的最小物理存储单位
Block	文件系统或存储设备一次分配、读写的连续空间单位
Page	DBMS 组织文件、缓存数据和估算 I/O 代价的基本单位
RAID	多盘并行提高性能，冗余提高可靠性
Striping	把数据切分并分布到多个磁盘
Parity	用校验信息恢复或检测数据错误
Buffer Pool	DBMS 管理的内存页缓存
Frame	Buffer Pool 中容纳一个页的位置
pin_count	表示 frame 正在被多少操作使用
dirty	表示 frame 中数据已被修改，替换前要写回
Heap File	无序存储，插入方便，查找通常慢
Sorted File	按 search key 有序，范围查询好
Hashed File	等值查询好，范围查询差
rid	记录的唯一标识，常见形式为 `(page id, slot number)`
Slot Dictionary	用 slot 号间接定位记录，帮助保持 rid 稳定

9.3 概念辨析

9.3.1 Sector、Block、Page 的区别

Sector 是硬件层面的最小单位；Block 通常是磁盘传输或文件系统层面的单位；Page 是 DBMS 逻辑管理和缓冲区管理的单位。DBMS 代价模型通常使用 page I/O，是因为 DBMS 的读写请求以页为核心。

9.3.2 LRU 与 Clock 的区别

LRU 尽量精确替换最近最少使用的页；Clock 是近似 LRU，用环形扫描和 referenced 标志降低实现开销。Clock 不保证严格的最近最少使用顺序，但实践中成本低、效果好。

9.3.3 Dirty 与 pin_count 的区别

pin_count 说明页是否正在被使用，决定能不能替换。dirty 说明页是否被修改，决定替换前要不要写回磁盘。

一个 frame 可以：

pin_count>0 且 dirty：正在使用，而且修改过，不能替换。
pin_count=0 且 dirty：可以被选择替换，但替换前必须写回。
pin_count=0 且不 dirty：最容易替换。

9.3.4 堆文件、排序文件、哈希文件的选择

如果应用经常插入记录，堆文件简单高效；如果经常按某个键做范围查询，排序文件更合适；如果主要是等值查询，哈希文件通常更高效。实际系统中还会结合索引、聚集索引、页空闲空间管理和 workload 进行综合选择。

9.3.5 Packed 删除为什么会影响 rid

Packed 删除会把页中最后一条记录移动到删除位置。这样页内空间更紧凑，但被移动记录的 slot 或位置可能改变。如果外部索引或上层模块保存了原 rid，就需要同步更新，否则会定位错误。

Unpacked 删除不移动其他记录，通过 bitmap 或空闲 slot 信息标记空位，牺牲部分紧凑性换取 rid 稳定。

9.4 常用公式

磁盘容量：

\[ \text{容量} = \text{盘面数} \times \frac{\text{磁道数}}{\text{盘面}} \times \frac{\text{盘块数}}{\text{磁道}} \times \frac{\text{字节数}}{\text{盘块}} \]

磁盘访问时间：

\[ \text{Access Time} = \text{Seek Time} + \text{Rotational Delay} + \text{Transfer Time} \]

记录标识符：

\[ \text{rid} = (\text{page id}, \text{slot number}) \]

字段偏移：

\[ \text{Address}(F_i) = B + \sum_{j=1}^{i-1} L_j \]

堆文件扫描：

\[ B(D+RC) \]

堆文件单结果等值查找平均代价：

\[ 0.5B(D+RC) \]

排序文件无重复等值查找：

\[ D\log_2B + C\log_2R \]

哈希文件单结果等值查找：

\[ H+D+0.5RC \]

9.5 学习建议

学习时建议把本章理解成“DBMS 如何把关系模型落到物理存储上”：

先理解磁盘为什么慢，以及为什么页 I/O 是代价核心。
再理解 RAID 如何用多盘并行和冗余改善性能与可靠性。
然后理解 Buffer Pool 如何在内存中管理磁盘页。
最后比较三种文件组织方式，并能根据查询类型判断哪种方式更合适。

分析代价时，优先写出 $B,D,R,C,H$ 的含义，再说明为什么可以近似忽略 CPU 项，只保留页 I/O 主项。这样推导会更清楚，也更符合数据库内核代价模型的分析习惯。

文件类型	Scan	Equality Search	Range Search	Insert	Delete
Heap	\(BD\)	\(0.5BD\)	\(BD\)	\(2D\)	Search \(+D\)
Sorted	\(BD\)	\(D\log_2B\)	\(D\log_2B+\#matches\)	Search \(+D\) 或更高	Search \(+BD\)
Hashed	\(1.25BD\)	\(D\)	\(1.25BD\)	\(2D\)	Search \(+D\)

符号	含义
\(B\)	数据库或文件中的数据页数量
\(R\)	每页中的记录个数
\(D\)	读写一页的时间
\(C\)	处理一条记录的时间，例如比较属性
\(H\)	对一条记录执行 Hash 函数的时间

操作	代价	解释
Scan	\(B(D+RC)\)	每页读一次，每页处理 \(R\) 条记录
Equality Search	若确定只有一个结果：\(0.5B(D+RC)\)；否则同 Scan	单个结果平均扫描半个文件；多个结果必须扫完
Range Search	\(B(D+RC)\)	无序文件无法利用范围顺序
Insert	\(2D+C\)	\(读这一页D+插入C+写这一页D=2D+C\)。若数据加在关系最后面，需要读写相关页
Delete	\(D+C\)	假设数据已经在内存中，可用 rid 中的 page id 访问对应页

操作	代价	解释
Scan	\(1.25B(D+RC)\)	保存空闲空间导致页数相对更多
Equality Search	\(H+D+0.5RC\)	计算 Hash 后读目标 bucket，假设只有一个结果
Range Search	\(1.25B(D+RC)\)	Hash 打乱顺序，范围查询无法直接利用
Insert	\(2D\)	定位 bucket 后插入，可能读写页
Delete	\(C+D\)	查找目标记录并删除