数据存储结构
上一章讨论了"介质"层:磁盘、闪存、RAID 决定了字节如何落到硬件。本章上一层,讨论 DBMS 如何把关系表映射成文件、页、记录,如何在有限的主存里通过缓冲池管理这些页,以及现代系统在列存与主存数据库方向上的新组织形式。这一层是查询执行器与存储介质之间的桥梁:查询算子看到的是"元组的迭代器",最终必须落到"页面偏移 + 字节序列"。
13.1 数据库存储架构
一个关系数据库典型的存储 层次如下:
- 段(segment):逻辑对象,如"表 T 的数据段"、"表 T 的索引 IDX1 的段"。Oracle 把每个表、每个索引、每个 LOB 都作为一个段。
- 区(extent):一段连续的物理块,几十 KB 到几 MB。以区为单位分配,能够降低磁盘寻道并保证聚簇。
- 页(page,或 block):DBMS I/O 的基本单位,也是缓冲池的管理单位。同一页只能同时被一个事务修改(页锁 / 闩锁)。
- 记录(record 或 tuple):一行数据,在页内以某种布局存放,通常带有一个页内偏移或 slot 号。
- RID / TID:
<页号,槽号>二元组,是记录的物理定位符,索引叶子通常存的就是它。
DBMS 会通过一个**空间管理层(Space Manager)**在文件里分配/回收区与页,并用位图或链表记录每页的空闲字节数,供插入时挑选合适页。
13.2 文件组织
一个文件由若干页组成,每页里放若干记录。文件组织问题就是:一条记录如何在页内落位?记录大小固定还是变化?跨页记录如何处理?
13.2.1 定长记录
假设记录长度固定为 字节,页大小 字节,最简单的做法是把页看成一个数组,第 条记录起始偏移 。
+------------------------------------------------------------+
| 页头 | R0 | R1 | R2 | R3 | ... | Rn | 空闲区 |
+------------------------------------------------------------+
删除某条记录后如何处理?三种方案:
- 就地留空:位置浪费,但记录物理位置不变,索引里的 RID 无需更新。为标记空缺,需要一个 bitmap 或空闲链表(把每条被删记录的头 8 字节改成"下一空缺"的偏移)。
- 末尾迁移:把最后一条记录搬到空缺位置。空间紧凑,但被搬记录的 RID 变了,所有指向它的索引都要更新,代价大。
- 就地留空 + 定期整理:日常删除只标记 tombstone,等空缺过多时批量重排。
定长记录布局的优点是简单、访问 ;缺点是无法直接支持 VARCHAR / TEXT 等变长字段,也不利于新增列。
13.2.2 变长记录
变长记录出现的原因:
- 有 VARCHAR、TEXT、BLOB 等变长类型。
- 有可为 NULL 的列。
- 需要支持在线加列(schema 演化)。
最主流的实现方式是槽页(slotted page):
页布局:
+-----------------------------------------------------------+
| 页头 | slot 数组 → ← ← 空闲区 → → ← 记录区 |
| |[s0][s1][s2]... ...|R2|R1|R0|
+-----------------------------------------------------------+
- 页头(page header):LSN、校验和、槽数、空闲区起止指针等元信息。
- 页尾方向增长的记录区:每插入一条变长记录,把它写到剩余空闲区的尾端,从右向左生长。
- 页头方向增长 的槽数组:每个 slot 是
<记录起始偏移, 长度>;被删除的槽标记为无效但仍占位。
优点:
- RID 稳定:即使页内 compact 移动了记录物理位置,也只更新 slot 数组指向新偏移,RID =
<页号,槽号>保持不变,索引无需修改。 - 变长友好:记录可任意大小。
- 删除低成本:只需把 slot 置无效,稍后再 compact。
变长记录内部布局有两种常见方式:
- 有序方式:定长字段在前紧凑排布,接着一段偏移数组指向变长字段的位置。
- 头部位图:先放一位图标记哪些字段为 NULL,然后按顺序放非空字段。
跨页记录(spanned record):单条记录大于一页时,可以把它切成若干片段,页头存"下一片段的页号"链起来。这在 LOB 存储中很常见。
13.2.3 大对象存储
BLOB / CLOB / JSON / 长文本这类"大对象"(LOB)通常不放在行内,因为一条膨胀的记录会破坏页布局与访问局部性。常见策略:
- 行内 + 溢出(TOAST,PostgreSQL):小对象仍存行内;超过阈值时压缩,再超过阈值时把内容切分为 chunk,写到附属表
pg_toast_xxx,行内只留一个指针。 - 单独 LOB 段:Oracle 用独立的 LOB 段,行内保存 lob locator。
- 文件系统 / 对象存储:把内容外置到 S3 之类,数据库只存 URI。适合超大 对象、只读、生命周期长的数据。
数据库也会给 LOB 提供流式读写 API(LOB locator + read/write 偏移),避免"必须整个装入内存"。
13.3 文件中记录的组织
一个表可以由不同的组织方式盛放,选择会决定顺序扫描、点查询、范围查询的成本。
13.3.1 堆文件组织
堆文件(heap file):记录无序放置,插入时挑一个"有足够空闲空间的页"即可。为了快速找空闲页,DBMS 通常维护一个 FSM(Free-Space Map):每 8 – 128 页在 FSM 上占一个字节,记录该页剩余空闲字节的粗略档次。
- 插入:(顺着 FSM 找到有空位的页)。
- 删除:(就地留空 + 更新 FSM)。
- 顺序扫描:( 记录、 页容量),扫全表。
- 点查询:需要索引配合,否则要全表扫描。
堆文件是默认组织方式(PostgreSQL、SQL Server 无聚簇索引时都是堆),配合独立索引使用非常灵活。
13.3.2 顺序文件组织
顺序文件(sequential file):记录按某个搜索码物理有序存放,页内 slot 有序,页之间用链表串起。适合范围扫描的场景(如按日期归档、按主键有序遍历)。
问题在于维护有序:
- 插入时如果目标位置所在页已满,就得移动大量记录 —— 严重时形成溢出链(overflow chain):新记录先塞到该页附着的一个"溢出页"里,扫描时先扫主链再扫溢出。
- 溢出多了后,性能退化为堆 + 链表,通常需要周期性重建(reorganize)。
现代数据库很少直接用纯顺序文件,而是用 B+ 树文件组织(索引组织表):叶子节点本身就是数据页,B+ 树把插入/分裂管好,天然维持有序。
13.3.3 多表聚簇文件组织
多表聚簇(multi-table clustering):把经常一起访问的不同表的相关记录物理放到同一页。典型例子:department 与 instructor,把每个院系记录后面紧跟属于该院系的所有教师记录。
页 P:
+--------------------------------------------------------------+
| dept 'CS' | instr(Alice, CS) | instr(Bob, CS) | instr(Cathy,CS) |
+--------------------------------------------------------------+
对于 SELECT * FROM department d JOIN instructor i ON d.dept_name = i.dept_name 这种查询,聚簇后可以在一次 I/O 里读到所有相关记录,避免嵌套循环连接的重复扫描。
代价:
- 单表扫描
SELECT * FROM instructor变慢 —— 相关记录被打散在 dept 之间。 - 变长的家族大小让页布局复杂,插入定位也更麻烦。
- 现代大多数系统改用列存 + 分区或物化视图来解决类似问题,多表聚簇较少直接使用。
13.3.4 划分
划分(partitioning):把一个逻辑表切成若干物理子表(分区),每个分区一个独立文件、独立索引。常见方式:
| 划分方式 | 说明 | 场景 |
|---|---|---|
| 范围划分 range | 按码区间:date < 2023-01-01, 2023-01-01 ≤ date < 2024-01-01… | 时间序列,冷热分层 |
| 列表划分 list | 按枚举值:region IN ('US','EU') | 多租户,地域路由 |
| 哈希划分 hash | 按 hash(key) mod N | 均衡负载,分布式表 |
| 复合划分 composite | 范围内再哈希,如按月分区再哈希 | 大规模日志表 |
划分的价值:
- 分区裁剪(partition pruning):查询谓词能确定只访问部分分区,优化器直接跳过其余分区。
- 独立维护:可对单个分区做归档、压缩、重建、备份,不影响其他分区。
- 并行:不同分区可并行扫描/加载。
13.4 数据字典存储
数据字典(元数据目录 / catalog)本身也是数据库中的表,只不过存的是"关于表的表"。至少包括:
pg_class/sys.tables:所有关系(表、视图、索引、TOAST 等)。pg_attribute:每一列的名字、类型、长度、约束、默认值。pg_index:索引的搜索码、类型、是否唯一。pg_type、pg_operator、pg_proc:类型、算子、函数。- 统计信息:直方图、NDV、行数、页数(供优化器估算)。
- 权限、约束、序列、触发器。
由于系统的每一次 SQL都要先查目录(做名字解析、类型检查、优化),DBMS 会:
- 把常用目录记录长驻缓冲池或做内存 catalog cache(每个会话一份)。
- 对目录本身建索引(PostgreSQL 有大量
pg_..._index)。 - 提供 DDL 一致性:任何 DDL 都在事务中修改多张目录表,故必须支持事务性 DDL 或用二阶段发布。
13.5 数据库缓冲区
主存远小于磁盘,DBMS 用**缓冲池(buffer pool / buffer cache)**把最活跃的页保存在内存,把冷页留在盘上。缓冲池是"透明"的:查询算子只请求"取第 P 页",看不见是否命中。
13.5.1 缓冲区管理器
**缓冲区管理器(Buffer Manager)**的职责:
- 分配与管理若干帧(frame)(页大小相同的内存槽)。
- 维护页表(page table):从
<文件, 页号>映射到某个帧的地址。 - 处理页请求:命中则直接返回,未命中则找一个可替换帧,可能先把脏页刷盘,再从盘读入。
- 维护pin/unpin 计数:帧被使用中(pin > 0)时不可替换。
- 维护脏位(dirty bit ):帧内容被修改过、与盘不一致。
一次 pin 的伪代码:
pin(fileId, pageId):
frame = pageTable.lookup(fileId, pageId)
if frame != null:
frame.pinCount++
return frame
else:
victim = replacementPolicy.chooseVictim()
if victim.dirty:
writeToDisk(victim)
readFromDisk(fileId, pageId, victim)
pageTable.update(fileId, pageId, victim)
victim.pinCount = 1
return victim
**闩锁(latch)**是缓冲池的关键同步原语:帧上的读闩、写闩保证并发访问时页内容不被撕裂。闩锁的作用范围极小(几十条指令),与"锁(lock)"用于事务隔离的场景截然不同。
13.5.2 缓冲区替换策略
当空闲帧耗尽、需要淘汰某页时,选择哪一页是**替换策略(replacement policy)**决定的。策略好坏直接决定命中率。
| 策略 | 淘汰谁 | 优点 | 缺点 |
|---|---|---|---|
| FIFO | 最先进入缓冲池的页 | 实现最简单 | 不区分冷热,扫描一次就把热页挤掉 |
| LRU | 最久未被访问 | 命中率高,符合直觉 | 需维护全局链表,多线程下开销大;顺序扫描会污染 |
| CLOCK / Second-Chance | 顺时针扫描帧,跳过 reference 位为 1 的(清零),淘汰第一个为 0 的 | LRU 的低成本近似,锁竞争小 | 精度略低于 LRU |
| MRU | 最近才访问的 | 大表扫描时刚扫过的页最没用,反而应先淘汰 | 一般工作负载表现差 |
| LRU-K | 考虑第 K 次上次访问时间 | 抗顺序扫描污染 | 数据结构复杂 |
| 2Q / ARC | 用两个队列区分"最近一次访问"和"多次访问" | 抗污染,命中率高 | 实现复杂,参数敏感 |
| LFU | 访问次数最少 | 长时热点友好 | 老热点不肯让位(scan → cache pollution) |
顺序扫描的问题:假设缓冲池有 1000 帧,全表扫描一次 10000 页 —— LRU 会把整个缓冲池刷成"这次扫描过的页",把 OLTP 常访问的热页全挤掉,即"缓冲污染(buffer pollution)"。工程上的对策:
- 循环检测:优化器识别顺序扫描,为其分配一个小的"环形缓冲"(如 256 KB),扫描完立刻释放。
- hint 机制:告诉 buffer manager"此页扫完就丢"(MRU-like 语义)。
- PostgreSQL 使用 clock-sweep + ring buffer,Oracle 使用 touch count,SQL Server 使用 LRU-K,思路一致。
pin 与 replacement:pin 计数 > 0 的帧永远不能被替换;一个替换算法本质上只在 pinCount == 0 的帧集合上工作。
13.5.3 写操作的重排序与恢复
缓冲池会把脏页在内存里保留很久,只在必要时才写盘。这带来的问题:崩溃时脏页可能已丢失。DBMS 借助**日志(WAL, Write-Ahead Logging)**解决:
- WAL 规则:一条修改必须先把对应日志记录(redo/undo)写到日志文件(并 fsync),才能允许对应数据页被写回。
- Force / No-Force:提交时是否强制把该事务修改的所有数据页刷盘。现代系统一律 No-Force:只强制刷日志,数据页由缓冲池按需回写。
- Steal / No-Steal:未提交事务的脏页能否被淘汰刷盘。现代系统一律 Steal:允许,因为 undo 日志可以回滚。
- 检查点(checkpoint):定期把当前所有脏页刷盘并在日志里打上标记,缩短崩溃恢复时的回放范围。
由此形成的写路径:日志顺序写(快) + 数据页异步随机写(在后台完成)。这也是"WAL 让随机写变顺序写"的经典表述。
13.6 面向列的存储
传统 DBMS 是行存(row store):一行的所有字段紧邻存放,一次读入一整行。这对 OLTP 很自然,因为一次事务通常操作若干完整行。
列存(columnar / column store):一列的所有值连续存放,每列一个独立文件/段。同一行的字段被"竖切"到不同列。
| 对比维度 | 行存 | 列存 |
|---|---|---|
| I/O 粒度 | 一次读一整行 | 只读查询涉及的列 |
| OLTP 单行 CRUD | 高效(局部性好) | 需要拼多列,代价高 |
| OLAP 聚合大表 | 读了大量无关列 | 只读所需列,扫描量小 |
| 压缩率 | 一列多类型混排,压缩率低 | 同列同类型数据,RLE、字典编码、位压缩效果好 |
| 向量化执行 | 逐行 | 天然一批一列,SIMD 友好 |
| 更新 | 就地更新简单 | 通常写入 delta,后台合并 |
| 典型系统 | MySQL, PostgreSQL, Oracle | ClickHouse, Vertica, Parquet, Redshift, DuckDB |
列存常用的压缩编码:
- 字典编码(dictionary):把字符串映射到 int,"男/女"→ 0/1。
- RLE(Run-Length Encoding):连续相同值编成
<值, 长度>。 - 位压缩(bit-packing):把最大值 500 的整数用 9 bit 而非 32 bit 表示。
- Delta 编码:连续值只存差值。
- Frame-of-Reference:先减去 min,再位压缩。
列存的执行优势——向量化(vectorized execution):一次给算子传一个 1024 值的批(column vector),循环紧凑、CPU 分支预测友好、可用 SIMD 指令批处理。这与 Volcano 一次一行的迭代器模型形成对比。
混合方案:
- PAX(Partition Attributes Across):页内按列分区,跨页仍按行组织,兼顾局部性与列裁剪。
- HTAP 双引擎:主行存 + 列存副本(TiDB TiFlash、SQL Server Column Store Index),OLTP 命中行存,OLAP 命中列存。
13.7 主存数据库的存储组织
当内存足够大,把整张数据库全部装入内存后,"磁盘 I/O 优化"不再是核心矛盾。**主存数据库(Main-Memory / In-Memory DBMS)**如 SAP HANA、MemSQL、Hekaton、VoltDB 重新审视存储结构:
- 页面抽象弱化:数据可以直接以对象/数组形式存在内存,不再需要 slotted page,只在需要持久化的时候写日志/快照。
- 索引更薄:B+ 树的"高扇出"是为了减少磁盘层次;主存索引更喜欢T 树、Bw-Tree、ART、跳表、哈希, 追求 cache line 命中而不是磁盘 I/O。
- 锁与闩锁重构:磁盘 DBMS 中 latch 开销可以忽略;主存 DBMS 里 latch 就是主要开销之一,故用多版本、无锁数据结构、按分区串行化(VoltDB)。
- 列存 + 压缩几乎必选:内存虽大但仍是稀缺资源,压缩 3 – 10 倍很划算。
- 持久性靠日志 + 快照:仍然需要 WAL 落盘。NVM 出现后,日志与数据可直接持久到 PMEM,恢复时间大幅缩短。
- NUMA 感知:多路 CPU 各有本地内存,跨 socket 访问慢一倍。表要按线程/socket 分区,减少远程访问。
主存 DBMS 的经典结构:
写入先到行存 delta,异步合并到列存主存段;WAL 与快照保证崩溃恢复。这一模式在 SAP HANA、Hyper、Umbra 等系统中反复出现。
13.8 总结
- DBMS 把关系数据映射为 表 → 段 → 区 → 页 → 记录的层次结构,页是 I/O 与缓冲管理的基本单位。
- 记录布局分定长与变长;变长常用槽页 slotted page,通过
<页号,槽号>稳定 RID,支持页内 compact 不动索引。 - 文件组织有堆文件(默认,靠 FSM 找空位)、顺序文件(易退化,需重建)、多表聚簇(老技术,现在多用列存 + 分区替代)、划分(按 range/list/hash 切表,支持分区裁剪与并行)。
- 缓冲池通过页表 + 帧 + 替换策略把热页留在内存;LRU 及其变体(Clock、LRU-K、ARC)是主流;WAL + No-Force + Steal + Checkpoint 让脏页安全地异步刷盘。
- 列存改变了页内组织,用同列同类型换来了高压缩率与向量化执行,在 OLAP 场景显著优于行存;HTAP 系统同时保留两种表示。
- 主存 DBMS在存储层取消了页抽象,用更薄的索引、更细的并发控制、NUMA 感知与列存压缩,把整个数据库放进内存执行。
- 无论哪种组织形式,核心权衡都是相同的三对矛盾:顺序 vs 随机、行 vs 列、就地更新 vs 追加合并。