Database System （一）

type

status

date

slug

summary

Memory and Disk

每当数据库使用数据时，这些数据必须存在于内存中。访问这些数据的速度相对较快，但一旦数据变得非常庞大，就无法将所有数据都放入内存中。磁盘被用来以较低的成本存储数据库的全部数据，但每次访问数据或写入新数据时，都会带来较高的开销。

磁盘 API

磁盘的基本 API 包括 READ 和 WRITE 操作，分别表示将“页”（pages）大小的数据从磁盘传输到内存，以及将数据从内存传输回磁盘。需要注意的是，由于磁盘的物理结构，这两个操作都非常缓慢。

磁盘结构

磁盘内部的盘片（platters）通常以每分钟约 15000 转的速度旋转。机械臂组件可以向内或向外移动，以将读写磁头定位到目标磁道上，这些磁道在所有磁头正下方组成一个“柱面”（cylinder）。在任意时刻，只有一个磁头能够进行读/写操作。磁盘的数据块或页面的大小是固定扇区（sector）大小的倍数。

访问磁盘页

访问（读/写）一个磁盘块的时间通常包括以下几个部分：

寻道时间（seek time）：移动磁头臂到目标磁道的位置，平均大约需要 2-3 毫秒

旋转延迟（rotational delay）：等待目标数据块旋转到磁头下方，延迟约为 0-4 毫秒（15000 转/分钟的情况下）

传输时间（transfer time）：实际将数据从磁盘表面传输到内存或反向传输，64KB 页大小大约需要 0.25 毫秒

磁盘 vs. 固态硬盘（SSD）

固态硬盘（SSD）或闪存（Flash）是一种用于存储数据的替代介质。与磁盘不同，SSD 是由单元（cells）组成的，支持快速的随机读取操作。

相比之下，硬盘在进行随机读取时性能非常差，因为磁盘对空间局部性非常依赖，顺序读取的性能远远优于随机读取。

SSD 支持细粒度读取（通常为 4-8KB）和粗粒度写入（通常为 1-2MB）。

然而，SSD 的每个单元只能承受有限次数的擦写操作（通常为 2000 到 3000 次），之后就可能失效。

为了解决这个问题，SSD 使用了一种叫做“磨损均衡（wear leveling）”的技术，通过不断在不同的单元之间移动写入单元，避免某个单元被频繁写入导致过早失效。

此外，SSD 的成本通常也高于传统硬盘。

磁盘空间管理（Disk Space Management）

磁盘空间管理是数据库管理系统（DBMS）中最底层的组成部分，负责管理磁盘上的存储空间。它的主要职责包括：

将页面（pages）映射到磁盘上的具体位置

将页面从磁盘加载到内存中

将页面从内存保存回磁盘，并确保写入操作的可靠性和持久性

这个层次为数据库系统上层的缓冲管理器（Buffer Manager）和查询处理器等组件提供底层支持，保障数据的读写操作能够顺利、高效地在磁盘与内存之间进行。

文件、页面与记录（Files, Pages, Records）

在关系型数据库中，记录（record，也就是一行 row）是最基本的数据单位。这些记录被组织成关系（relations），也就是我们常说的表（tables），可以在内存中进行修改、删除、查询或创建。

而对于磁盘来说，最基本的数据单位是页面（page），它是磁盘与内存之间传输数据的最小单元。为了让关系型数据库的数据结构适配磁盘存储，每个关系会被存储在一个独立的文件中，文件中的记录会被组织成多个页面。

数据库系统会根据关系的**模式（schema）和访问模式（access pattern）**来决定以下内容：

使用哪种类型的文件来存储关系

页面在文件中的组织方式

每个页面上记录的组织方式

每条记录的具体格式

这个设计层次是数据库系统物理存储结构的核心，关系到数据的存储效率和访问性能。

选择文件类型（Choosing File Types）

数据库系统主要使用两种类型的文件来存储关系数据：

堆文件（Heap Files）

排序文件（Sorted Files）

对于每个关系，数据库会根据其**访问模式（access pattern）**中的 I/O 成本 来选择最合适的文件类型。

在这里，1 次 I/O 被定义为从磁盘读取一个页面或写入一个页面。数据库会根据该关系的插入（insert）、删除（delete）和扫描（scan）等操作，分别估算在每种文件类型下的总 I/O 成本。

最后，数据库会选择产生更低 I/O 成本的文件类型来存储该关系。这种策略可以在不同类型的操作下最大化性能和效率。

堆文件（Heap File）

堆文件是一种没有特定页面顺序或记录顺序的文件类型，适合随机插入和删除操作。它主要有两种实现方式，其中一种是：

链表实现（Linked List Implementation）

在链表式堆文件中，每个**数据页（data page）**包含：

存储的记录（records）

可用空间的追踪信息（free space tracker）

指向前一页和后一页的指针（通常是字节偏移量）

此外，还有一个特殊的头页（header page），它充当文件的起点，并将数据页划分为：

已满页面部分（full pages）

有空闲空间的页面部分（free pages）

操作行为：

插入记录时：如果需要更多空间，会分配新的空页面并附加到“有空闲空间”的页面部分。

当某个“空闲页面”被填满：它会从“空闲”列表中移出，并移入“已满页面”部分的前端，这样我们在追加时就不必遍历整个已满列表。

另一种实现方法是，在头页中维护一个指向“已满页面”列表尾部的指针，便于快速追加。

注意：具体使用哪种实现方式并不影响本课程内容的重点，因此不需深入掌握其底层差异。

页目录实现（Page Directory Implementation）

页目录与链表实现的不同在于：

只对头页使用链表结构。

每个头页中包含：

指向下一个头页的指针（字节偏移量）
多个条目（entry），每个条目包括：

指向数据页（data page）的指针
该数据页剩余的可用空间大小

由于这些指针都保存在头页中，数据页本身就不再需要保存邻接页面的指针。

优势：插入更高效

与链表实现相比，页目录实现插入记录更快：

在链表实现中，为了找到一个有足够空间的数据页，可能需要读取多个数据页（尤其在“空闲页部分”中）

页目录实现中，只需要读取头页，因为其中已记录每个数据页的剩余空间

→ 减少了 I/O 成本

示例对比：插入一个 20 字节的记录（页面大小为 30 字节）

链表实现（Linked List）

从头页开始，遍历空闲页面：[5, 15, 10, 25]

直到最后一页 25 才能插入

I/O 成本：

读取所有页：5 次
写入数据页：1 次
总计：6 次 I/O

页目录实现（Page Directory）

头页中已有所有空间信息，直接定位到第 4 页（25 空闲）

I/O 成本：

读取头页：1 次
读取目标数据页：1 次
写入数据页：1 次
写入头页：1 次（更新剩余空间信息）
总计：4 次 I/O

总结

尽管堆文件的实现方式不同，但与排序文件相比，插入操作始终较快。因为记录可以插入到任意有空闲空间的页面。

但查找操作效率低，必须全表扫描（unordered）：

每次查找代价是线性：N 页 → N 次 I/O

这也是为什么我们将在下一个部分看到，排序文件在查找性能方面更优。

排序文件（Sorted Files）

排序文件是一种文件类型，其中页面是有序的，并且每个页面内的记录按照键（key）排序。

实现方式

通常也通过**页目录（Page Directory）**来管理

数据页之间有排序约束，并且每个数据页内的记录也按键值有序排列

查找效率高

查找时，可以使用二分查找（binary search）定位记录所在的数据页

如果总共有 N 个页面，则查找的 I/O 成本为：

logN 次 I/O

插入效率低（代价较高）

插入操作要满足排序要求，平均情况可能涉及大量记录移动：

首先使用二分查找定位插入位置：logN I/Os

然后将新记录插入该页，如果该页满了，后面的记录需要依次往后推，可能导致多个页面都要重写

平均插入代价为：logN + N 次 I/O

插入新记录可能触发级联移动（push-back），每次都需要读写多个数据页

最坏情况示例（图示）

假设：

每个数据页最多容纳 2 条记录

当前状态：

Data Page 1: [Jenny, 7], [Brian, 18]
Data Page 2: [Jamie, 20], [Eric, 32]

要插入 [John, 17]，由于需要保持有序：

插入位置在 Page 1，但页已满

[Brian, 18] 被移至 Page 2

[Jamie, 20] 被移至 Page 3

最终形成 3 个页面，每个都经过读写

这就是最坏情况下的级联写操作，成本较高。

总结对比：

类型	插入效率	查找效率
堆文件（Heap）	快（记录插入到任意空页）	慢（全表扫描）
排序文件（Sorted）	慢（需要移动记录）	快（logN 二分查找）

关于统计头页（Header Pages）I/O 的说明

这是一个在计算 I/O 成本时常见的混淆点，特别是在考试或作业题目中。

记忆规则：

提供了具体的文件实现（例如：链表堆文件或页目录）时：

必须计算头页的 I/O 成本

因为头页在操作中扮演实际角色（如记录页面指针或空闲空间信息）

没有提供底层文件实现细节时：

不要计算头页的 I/O 成本

默认题目关注的是数据页的行为，而不是具体结构细节

示例：

“一个堆文件插入一条记录，需要多少 I/O？” ← 如果没有说是链表实现或页目录，不考虑头页

“一个使用页目录实现的堆文件插入一条记录……” ← 必须包含读取/写入头页的 I/O

数据库文件操作 I/O 成本速查表

操作类型	文件实现是否明确	是否包含头页 I/O	常见 I/O 成本计算方式
插入记录	❌ 未说明实现方式	❌ 忽略头页	只统计数据页的读/写
插入记录	✅ 链表堆文件（Linked List Heap）	✅ 包含头页 I/O	多次读取头页和空闲数据页，写入目标页
插入记录	✅ 页目录堆文件（Page Directory Heap）	✅ 包含头页 I/O	读头页、读目标数据页、写数据页、更新头页
查找记录	❌ 未说明实现方式	❌ 忽略头页	堆文件：全表扫描 → N I/Os排序文件：二分查找 → logN I/Os
查找记录	✅ 排序文件（Sorted File）	✅ 包含头页 I/O（如有说明）	logN（页）二分查找
删除记录	✅ 有实现说明	✅ 包含头页 I/O	与查找类似，外加写操作
扫描全部记录	无论实现是否说明	✅/❌ 取决于题目说明	N 次 I/O，遍历所有数据页

建议记忆关键词：

有具体实现 → 包括头页

无实现细节 → 忽略头页

插入（heap）→ 快，但可能移动多个页

查找（heap）→ 慢（线性）｜查找（sorted）→ 快（logN）

写操作总是算 I/O，不管是不是头页

记录类型（Record Types）

数据库中记录的类型完全由关系的 schema 决定，主要有两种：

1. 定长记录（Fixed Length Records, FLR）

仅包含定长字段（如：int、bool、date 等）

同一个 schema 下，每条记录的字节长度都相同

存储结构简单，适合顺序存取与固定偏移定位

2. 变长记录（Variable Length Records, VLR）

同时包含定长字段和变长字段（如 varchar）

即使 schema 相同，不同记录的总长度也可能不同

存储方式：

先存所有定长字段
再存变长字段
使用**记录头部（header）**存放指向变长字段末尾的指针

下图说明：

记录从左到右依次是：

Header（含指针）
定长字段：True、51、9204
变长字段：Jim、Gray

Header 记录了 Jim 和 Gray 在内存中的偏移或结束位置

补充说明：

无论记录格式如何，每条记录都可以通过一个唯一 ID 来标识：

格式为：[页面编号 page #, 页面内记录编号 record #]

Page Formats（页面格式）

页面格式：固定长度记录（Fixed Length Records）

包含 FLRs（固定长度记录）的页面总是使用**页头（Page Header）**来记录当前页面上记录的数量。

Packed Page（紧凑格式页面）

没有空隙（gaps）：所有记录连续排列

插入操作简单：

根据已有记录数量 × 每条记录长度，就能计算下一个插入位置

删除操作稍复杂：

删除中间的记录后，需要将后续记录整体向上移动一位，保持紧凑结构

✅ 优点：节省空间

❌ 缺点：删除成本较高（需要移动后续记录）

Unpacked Page（非紧凑页面）

页面被划分为多个槽（slots）

页头中通常包含一个位图（bitmap）：

每一位表示一个槽是否被占用（1 = 被占，0 = 空闲）

插入记录时放入任意空槽，删除只需更新位图

✅ 优点：插入/删除灵活，不需要移动其他记录

❌ 缺点：可能浪费空间（有空槽但不能合并）

图示解释：

图中显示了一个非紧凑页面的结构：

Page Header：包含记录数量和 bitmap

slot 4, 5, 7：空闲槽位

Record 1 ~ 6：填入的记录，位置可以非连续

bitmap：跟踪哪些槽被使用

小结对比：Packed vs. Unpacked

特性	Packed Page	Unpacked Page
插入	快	快（更灵活）
删除	需要移动记录	只更新 bitmap
空间利用	高效	可能浪费（碎片）
页头内容	记录数量	记录数量 + bitmap

变长记录页面（Pages with Variable Length Records）

与固定长度记录不同，变长记录的大小是不确定的。为了支持灵活存储，每个页面使用：

页尾（Page Footer） 来存储：

槽目录（slot directory）：包含每条记录的偏移和长度
槽数量（slot count）
空闲空间指针（free space pointer）：指向页面中可用空间的开始位置

页尾从页面底部开始向上增长，以给槽目录留出增长空间，而记录从顶部开始向下插入。

槽目录（Slot Directory）

每个槽包含一个：

[记录指针, 记录长度] 对（[record pointer, record length]）

槽数量（slot count） 包含已填槽和空槽。

插入记录的行为

记录会插入到 free space pointer 指向的位置

在槽目录中找一个空槽（[null, null]）更新为新记录的位置和长度

如果没有空槽，就在槽目录中增加新项

定期地，系统会将页面压缩（repack/compact），将已删除记录移除，释放空间。

删除记录的行为

若页面是未压缩（unpacked）：

设置为 [null, null]，表示槽位空闲

若页面是压缩状态（packed）：

删除记录后，将后续记录向上移动一位

这样可以保持记录连续排列，避免碎片

注意：记录的移动仅在当前页面内完成，不跨页面移动

图示说明

图中展示了：

页面顶部是变长记录，存在删除记录的空洞

页面底部是 footer，其中 20 17 10 5 分别是记录偏移量，[null] 表示已删除记录

空间逐渐碎片化，需要压缩来整理

总结：变长记录页面结构

项目	内容
页尾结构	槽目录 + 空闲指针 + 槽数
插入策略	插入空槽或新槽，更新空闲指针
删除策略	设置为 null（unpacked）或移动后续记录（packed）
优点	支持灵活字段大小
缺点	槽管理复杂，可能碎片化，需要定期整理

字段类型（Field Types）

不同的数据类型在磁盘上占用的空间不同，CS 186 使用以下标准约定：

固定 / 可变	类型	大小（字节）
Fixed	Integer	4
Fixed	Float	4
Fixed	Boolean	1
Fixed	Byte	1
Fixed	Char(N)	N
Variable	Varchar(N)	≤ N
Variable	Text	≥ 0

🔍 补充说明：

Fixed（定长）字段：每条记录该字段的大小是固定的

Variable（变长）字段：

Varchar(N)：实际长度可变，不超过 N 字节
Text：大小不固定，可能很小，也可能非常大（取决于内容）

这些字段类型会影响记录格式（FLR 或 VLR）、页面布局、槽目录设计等多个底层实现细节。