Lec3&4 数据库存储

 2026/02/03 

数据库存储层结构相关知识。

Background

disk-based architecture：假设数据库管理系统中数据主要存储在非易失性存储设备（non-volatile storage，例如 SSD / HDD）中，而不是全部常驻内存。

因此系统的核心任务之一是协调数据在磁盘和内存之间的移动，并通过缓存与页面机制减少磁盘 I/O 开销。

存储层级结构

典型存储层级结构如下图所示，自顶向下看，读取速度逐级降低，但容量逐级上升。

此外，以 DRAM（内存）为分界线：

DRAM 及以上（CPU Cache / 内存）属于易失性存储，断电后数据丢失；SSD / HDD 属于非易失性存储。
DRAM 是按字节寻址（byte-addressable）的，可以从任意字节地址开始访问；而 SSD / HDD 属于块设备（block device），必须按页或块（通常 4KB 或更大）为单位读写，而不能只读取其中几个字节。

不同存储级别访问时延对比：

Sequencial vs Random Access

一般来说，随机访问 non-volatile storage 比顺序访问要慢得多（在 HDD 上尤其明显，在 SSD 上仍然存在差异但程度较小）。

以机械硬盘为例，一次访问通常包括：

磁头寻道（移动到目标磁道）
旋转延迟（等待目标扇区转到磁头下）
数据传输

顺序访问只需一次寻道即可连续读取；随机访问则可能每次都需要重新寻道，成本很高。

因此 DBMS 往往希望最大化顺序 I/O：

尽量将相关数据存储在连续块中；
一次性分配多个 page；
批量读写而非频繁小 I/O。

面向磁盘的 DBMS

典型访问流程：

Execution Engine 请求某个 PageID
Buffer Pool 查询页是否在内存
若不在，则根据 page table / page directory 定位磁盘位置
从磁盘加载 page 到内存 frame
返回指向内存 page 的指针
Execution Engine 解析页面布局并读取数据
若发生修改，则标记为 dirty page

更新后的页面通常不会立即写回磁盘，而是延迟刷盘，由后台线程按策略统一flush，并遵循 WAL 先行原则。

File Storage

DBMS 通常将数据库存储为一个或多个专有格式文件。不同数据库的文件格式不兼容，例如不能用 MySQL 直接读取 SQLite 数据文件。

近年来在分析型数据库中出现采用开放列式格式（如 Parquet / ORC）的趋势，但这主要用于 OLAP 场景，而不是传统 OLTP 存储引擎格式。

Storage Manager

Storage Manager 负责底层文件与页面管理，包括：

跟踪page上的数据读写，例如删除数据之后，如何压缩空间占用。
跟踪当前可用空间。

Database Pages

page = 固定大小的数据块（常见 4KB / 8KB / 16KB）。

可能包含 tuple、元数据、索引项等
一般不会在同一页面混合不同表的数据
页面通常设计为自描述结构，便于崩溃恢复与一致性检查

每个 page 有唯一 PageID。

说明：PageID 通常是逻辑地址（file_id + page_no），而不是直接物理偏移；SQLite 是少数按文件偏移直接寻址的实现。

注意区分三种 page 概念：

硬件页：设备内部管理单位，不等同于原子写入大小（原子写入由设备保证机制决定）
OS Page：操作系统页，常见 4KB，也支持 huge page
DB Page：数据库自定义页大小

Page Storage Architecture

不同 DBMS 采用不同页面组织策略。

Heap File Organization

最常见方式：无序页面集合。

“无序”指物理存储顺序不等于逻辑顺序，新记录会插入到有空闲空间的页面中。

page directory：记录哪些页面有空闲空间及其位置，本质上是元数据目录结构，而不一定是哈希表实现。

删除记录后产生空洞，新插入数据会优先填补空闲空间。

Tree File Organization

基于树结构（如 B+Tree）组织页面，数据页本身按 key 有序排列。

优点：

范围查询高效
可直接按 key 定位

Sequential / Sorted File Organization（ISAM）

数据按 key 顺序存储，适合读多写少场景。

更新通常写入 overflow 区域，周期性重组。

Hashing File Organization

基于哈希函数定位页面：

等值查询快
范围查询性能差

Page Storage

Page Header 存储页面元数据，例如：

页大小
校验和
LSN
slot 数量
空闲空间偏移
压缩信息

页级 min/max 值常用于查询跳页优化（zone map 思想）。

Page Layout

页面需要定义 tuple 的布局方式。

tuple-oriented storage

简单顺序存储 tuple 存在问题：

删除后难以复用空间
可变长字段导致碎片
查找需要遍历

slotted page

标准页布局方式：

slot array 自上向下增长
tuple 数据自下向上增长
slot 存储 tuple 偏移与长度

删除 tuple 时只需标记 slot 无效；可选择页面压缩，但会影响并发。

插入新元组

通过 page directory 找到有空闲空间页面
若不在内存则加载
在 free space 区写入并更新 slot

使用 RID 更新元组

RID = page_id + slot_no

若新值放不下：

标记旧记录删除
插入新版本

存在的问题

页内碎片
更新需读整页
多页更新导致随机 I/O

log-structured storage

核心思想：不再使用原地更改的slotted pages，而是统一维护日志，记录所有元组的变更。

日志中每个条目代表对一个元组进行一次put/delete操作。

基于上述思想，DBMS的更改过程变成：

将当前更改维护在内存数据结构（MemTable）中；
1. MemTable组织为树型结构，按照key进行排序，可以针对key进行二分查找；
2. 由于内存的读写速度较快，允许对MemTable进行原地更新，例如将a=100更改为a=200，允许直接覆盖；
若MemTable存满，则转变为SSTable写入磁盘。
1. SSTable不以树型结构组织，仅仅为日志形式，SSTable中的条目按照key的顺序有序排序；
2. 从MemTable到SSTable的过程中，仅记录所有记录的最新值；
3. 构造SSTable之后，则原有MemTable释放并开始记录新的内容；
SSTable刷入磁盘level 0，level 0中所有SSTable按照从新到旧的顺序排序；
当level 0满，则临近SSTable被合并为一个大的SSTable，压入level 1；
1. 这里进行的操作即 compaction ；
3. compaction的结果，仅保留两个SSTable中相同key的最新版本。
level 1工作原理同上。