数据库存储结构：磁盘、文件、页面与记录

1. 数据库系统架构（DBMS）

1.1 分层架构

SQL Client
    ↓
Query Parsing & Optimization 查询解析和优化
    ↓
Relational Operators 关系运算符
    ↓
Files and Index Management  文件和索引管理
    ↓
Buffer Management  缓冲区管理
    ↓
Disk Space Management  磁盘空间管理
    ↓
File System

1.2 各层职责

查询解析与优化：生成高效查询计划
关系运算符：执行查询计划，操作记录和文件
文件与索引管理：组织表、记录为逻辑文件
缓冲区管理：提供内存操作 illusion
磁盘空间管理：将页面映射到物理磁盘位置

1 2	每一层对下层的进行抽象接下来从最低开始慢慢学习到最高的系统

==还有两个模块一个是并发控制模块，一个是回复模块与多个相关的层联系==

2. 存储层次与磁盘管理

2.1 存储层次结构

![[存储结构.png]]

层级	访问时间	容量（$/1000）	用途
寄存器	0.5 ns	-	当前使用数据
L1/L2 缓存	~1 ns	-	缓存
内存（RAM）	100 ns	80 GB	操作数据
SSD	0.1–20 ms	2.3 TB	缓存/日志
磁盘（DISK）	5–20 ms	40 TB	备份/归档

2.2 ==磁盘==访问成本

寻道时间：移动磁臂到目标磁道，约 2–3 ms
旋转延迟：等待数据块旋转到磁头下，约 0–4 ms（15000 RPM）
传输时间：实际读写数据，约 0.25 ms/64KB
扇区包含一定大小的数据量，和页有关系

磁盘中存在很多个==块==，然后访问下一个Block是最快的，无论何时收到请求都会获得大量的块==（具有局部性）==

关键优化目标：减少寻道和旋转延迟

2.3 ==SSD== （Flash）特点

读取：==快速==且==可预测==~~（500 MB/s）~~
写入：==较慢==且==需“磨损均衡”==~~（120 MB/s）~~
每次写入都会对一个区域进行磨损，因此需要均衡
写入单位大：1–2 MB，读取单位小：4–8 KB

3. 文件组织

3.1 文件类型

类型	描述	适用场景
堆文件（无序）	记录任意分布在页面中	快速插入
聚集堆文件	按某种方式分组	部分有序访问
排序文件	严格按键排序	范围查询、二分查找
索引文件	B+树、哈希等	快速查找

3.2 堆文件实现方式

3.2.1 链表实现

![[链表数据页.png]]

每个数据页包含：
- 记录
- 空闲空间跟踪
- 前后页指针（字节偏移）
一个头页将数据页分为“满页”和“空闲页”两部分
分别指向两条链表

3.2.2 页目录实现

![[页表.png]]

仅头页使用链表
每个头页包含：
- 指向下一个头页的指针
- 多个条目，每个条目包含：
  - 指向数据页的指针
  - 该页的空闲空间信息

3.2.3 I/O 成本对比

操作	链表实现	页目录实现
插入记录	读取所有页 + 写入目标页	读头页 + 读数据页 + 写数据页 + 写头页

页目录优势：插入操作更快，尤其当页数多时

4. 页面格式

4.1 页面结构（需要一个==id==）

页头：记录数、空闲空间、位图、槽表等
数据区：存储记录
页尾（槽目录）：用于变长记录管理

4.2 定长记录页面

![[定长记录页面.png]]
用（Page2， Record 4）来表示record的id

4.2.1 紧凑格式

记录连续存储
插入：追加到末尾
删除：需要移动后续记录，更新 RecordId

（删除后全部往前挪）

4.2.2 非紧凑格式（位图槽）

![[定长记录页面打的非紧凑模式.png]]

使用位图标记槽的使用情况
插入：找到第一个空闲槽
删除：清除对应位，无需重组（只需要清除对应的槽）

4.3 变长记录页面（槽式页面）

problem ：会产生fragmentation
回答：重新整合就可以啦！
![[变长记录页面.png]]

4.3.1 结构

槽目录（从页尾开始）：
- 槽数量
- 空闲空间指针(==放在最后面==)
- 条目：[记录指针, 记录长度]
记录从页头开始存储

4.3.2 操作

插入：
- 在空闲空间处放置记录（==记录的指针指向空闲空间的指针==）
- 在槽目录中添加条目
- 更新空闲空间指针
删除：
- 将对应槽条目设为 null
- 无需移动记录
重组：定期整理碎片

4.3.3 槽目录扩展

槽从页尾向内增长
记录从页头向内增长
可动态扩展槽目录

5. 记录格式

5.1 定长记录

字段位置通过算术计算
紧凑但无法处理 NULL 优化

5.2 变长记录

5.2.1 问题

==填充浪费空间==（并且可能会不够用)
==分隔符处理复杂==（而且会占用大部分的数据空间）
有一定的扫描空间

5.2.2 解决方案：记录头

![[record header.png]]

固定长度字段在前
变长字段在后
记录头包含指向变长字段的指针
示例：

1	[Header（中间包含bob和big.st的指针） \| M \| 32 \| 94703 \| Bob \| Big, St.]

5.3 记录标识

RecordId = [页号, 页内位置]
- 页内位置可以是：
  - 记录编号（紧凑格式）
  - 槽编号（非紧凑/槽式格式）

6. 实践问题与解答

6.1 问题 1：堆文件插入的 I/O 成本

场景：页目录实现的堆文件，4 个头页，每个头页 3 个数据页
最坏情况：只有最后一个数据页有足够空间
I/O 成本：
- 读 4 个头页
- 读 1 个数据页
- 写 1 个数据页
- 写 1 个头页
- 总计：7 次 I/O

6.2 问题 2：最小记录大小

模式：
- name VARCHAR
- student BOOLEAN (1 字节)
- birthday DATE (8 字节)
- state VARCHAR
记录头：5 字节
最小大小：5 + 1 + 8 = 14 字节（当 VARCHAR 字段为 NULL 时）

6.3 问题 3：槽目录大小

组件：
- 槽计数：4 字节
- 空闲空间指针：4 字节
- 每个记录的条目：[记录指针(4) + 记录长度(4)] × 记录数
4 个记录：4 + 4 + (4 + 4) × 4 = 40 字节

7. 关键总结

7.1 设计原则

页面是基本单位：磁盘与内存间的传输单元
局部性原理：顺序访问远快于随机访问
抽象层次：每层隐藏下层复杂性
I/O 优化：减少磁盘访问是性能关键

7.2 技术选择

堆文件：插入快，查找需全扫描
排序文件：查找快（logN），插入慢（logN + N）
页目录：优于链表实现，尤其在大文件中
槽式页面：适用于变长记录，支持高效插入/删除

7.3 实际考虑

NULL 处理：变长记录格式可优化 NULL 字段存储
碎片整理：槽式页面需定期重组
扩展性：槽目录和记录区域可动态增长