跳到主要内容

数据存储结构

上一章讨论了"介质"层:磁盘、闪存、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 定长记录​

假设记录长度固定为 LL 字节,页大小 PP 字节,最简单的做法是把页看成一个数组,第 ii 条记录起始偏移 =i⋅L= i \cdot L。

+------------------------------------------------------------+
| 页头 | R0 | R1 | R2 | R3 | ... | Rn | 空闲区 |
+------------------------------------------------------------+

删除某条记录后如何处理?三种方案:

  1. 就地留空:位置浪费,但记录物理位置不变,索引里的 RID 无需更新。为标记空缺,需要一个 bitmap 或空闲链表(把每条被删记录的头 8 字节改成"下一空缺"的偏移)。
  2. 末尾迁移:把最后一条记录搬到空缺位置。空间紧凑,但被搬记录的 RID 变了,所有指向它的索引都要更新,代价大。
  3. 就地留空 + 定期整理:日常删除只标记 tombstone,等空缺过多时批量重排。

定长记录布局的优点是简单、访问 O(1)O(1);缺点是无法直接支持 VARCHAR / TEXT 等变长字段,也不利于新增列。

13.2.2 变长记录​

变长记录出现的原因:

  • 有 VARCHAR、TEXT、BLOB 等变长类型。
  • 有可为 NULL 的列。
  • 需要支持在线加列(schema 演化)。

最主流的实现方式是槽页(slotted page):

页布局:
+-----------------------------------------------------------+
| 页头 | slot 数组 → ← ← 空闲区 → → ← 记录区 |
| |[s0][s1][s2]... ...|R2|R1|R0|
+-----------------------------------------------------------+
  • 页头(page header):LSN、校验和、槽数、空闲区起止指针等元信息。
  • 页尾方向增长的记录区:每插入一条变长记录,把它写到剩余空闲区的尾端,从右向左生长。
  • 页头方向增长的槽数组:每个 slot 是 <记录起始偏移, 长度>;被删除的槽标记为无效但仍占位。

优点:

  1. RID 稳定:即使页内 compact 移动了记录物理位置,也只更新 slot 数组指向新偏移,RID = <页号,槽号>保持不变,索引无需修改。
  2. 变长友好:记录可任意大小。
  3. 删除低成本:只需把 slot 置无效,稍后再 compact。

变长记录内部布局有两种常见方式:

  • 有序方式:定长字段在前紧凑排布,接着一段偏移数组指向变长字段的位置。
  • 头部位图:先放一位图标记哪些字段为 NULL,然后按顺序放非空字段。

跨页记录(spanned record):单条记录大于一页时,可以把它切成若干片段,页头存"下一片段的页号"链起来。这在 LOB 存储中很常见。

13.2.3 大对象存储​

BLOB / CLOB / JSON / 长文本这类"大对象"(LOB)通常不放在行内,因为一条膨胀的记录会破坏页布局与访问局部性。常见策略:

  1. 行内 + 溢出(TOAST,PostgreSQL):小对象仍存行内;超过阈值时压缩,再超过阈值时把内容切分为 chunk,写到附属表 pg_toast_xxx,行内只留一个指针。
  2. 单独 LOB 段:Oracle 用独立的 LOB 段,行内保存 lob locator。
  3. 文件系统 / 对象存储:把内容外置到 S3 之类,数据库只存 URI。适合超大对象、只读、生命周期长的数据。

数据库也会给 LOB 提供流式读写 API(LOB locator + read/write 偏移),避免"必须整个装入内存"。


13.3 文件中记录的组织​

一个表可以由不同的组织方式盛放,选择会决定顺序扫描、点查询、范围查询的成本。

13.3.1 堆文件组织​

堆文件(heap file):记录无序放置,插入时挑一个"有足够空闲空间的页"即可。为了快速找空闲页,DBMS 通常维护一个 FSM(Free-Space Map):每 8 – 128 页在 FSM 上占一个字节,记录该页剩余空闲字节的粗略档次。

  • 插入:O(1)O(1)(顺着 FSM 找到有空位的页)。
  • 删除:O(1)O(1)(就地留空 + 更新 FSM)。
  • 顺序扫描:O(N/B)O(N/B)(NN 记录、BB 页容量),扫全表。
  • 点查询:需要索引配合,否则要全表扫描。

堆文件是默认组织方式(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范围内再哈希,如按月分区再哈希大规模日志表

划分的价值:

  1. 分区裁剪(partition pruning):查询谓词能确定只访问部分分区,优化器直接跳过其余分区。
  2. 独立维护:可对单个分区做归档、压缩、重建、备份,不影响其他分区。
  3. 并行:不同分区可并行扫描/加载。

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)**的职责:

  1. 分配与管理若干帧(frame)(页大小相同的内存槽)。
  2. 维护页表(page table):从 <文件, 页号> 映射到某个帧的地址。
  3. 处理页请求:命中则直接返回,未命中则找一个可替换帧,可能先把脏页刷盘,再从盘读入。
  4. 维护pin/unpin 计数:帧被使用中(pin > 0)时不可替换。
  5. 维护脏位(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, OracleClickHouse, 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 重新审视存储结构:

  1. 页面抽象弱化:数据可以直接以对象/数组形式存在内存,不再需要 slotted page,只在需要持久化的时候写日志/快照。
  2. 索引更薄:B+ 树的"高扇出"是为了减少磁盘层次;主存索引更喜欢T 树、Bw-Tree、ART、跳表、哈希,追求 cache line 命中而不是磁盘 I/O。
  3. 锁与闩锁重构:磁盘 DBMS 中 latch 开销可以忽略;主存 DBMS 里 latch 就是主要开销之一,故用多版本、无锁数据结构、按分区串行化(VoltDB)。
  4. 列存 + 压缩几乎必选:内存虽大但仍是稀缺资源,压缩 3 – 10 倍很划算。
  5. 持久性靠日志 + 快照:仍然需要 WAL 落盘。NVM 出现后,日志与数据可直接持久到 PMEM,恢复时间大幅缩短。
  6. 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 追加合并。