Skip to content

3-Storage and File Structure ​

核心问题:数据的物理布局怎样影响 I/O、内存访问和 CPU 处理成本?

①介质与RAID→②缓冲管理→③记录组织→④文件组织及I/O计算→⑤列式格式→⑥SIMD与高级压缩。

一、物理存储介质与 RAID ​

本主题回答:数据存在哪里,单盘访问为什么慢,多盘如何兼顾性能与可靠性?

Physical Storage Media Overview · 课件第 4—17 页

先从数据库读一条记录的过程来理解:

数据保存在 SSD 或 HDD 上 → 需要时把记录所在的数据页读入 RAM → CPU 访问内存中的数据,过程中使用 GPU Cache

因此,数据库查询的成本不仅是“做了多少次计算”,还包括“需要从存储设备搬多少数据”。

1. 存储层次与访问延迟 ​

要解决的问题:Cache、RAM、SSD、HDD 和磁带在速度、容量、持久性及用途上有什么区别?课件第 4—6 页

不同介质的区别,可以从速度、单位容量成本和断电后能否保存数据三个方面理解。

介质访问特点断电后保存数据数据库中的主要用途
CPU Cache非常快,容量小否缓存 CPU 正在使用的数据和指令
RAM,主存快,可直接供 CPU 访问否缓冲数据页、执行查询、保存中间结果
SSD,固态硬盘无机械寻道,随机访问明显快于 HDD是持久保存数据库文件、日志等
HDD,机械硬盘随机访问受机械运动限制是持久保存大量数据
光盘可移动,适合分发或归档是较少用于数据库的在线读写
磁带定位慢,连续传输可以很快是大规模备份、历史数据归档

总体上,越靠近 CPU,访问越快、单位容量成本越高;越远离 CPU,通常越适合以较低成本保存大量数据。

这里有两个重要区别:

  • 第一,持久性不等于可靠性:HDD 断电后能保存数据,但磁盘可能会因为损坏而丢失数据;RAM 断电后数据丢失,讨论的问题不在同一个维度

  • 第二,访问延迟不等于传输带宽

    • 延迟(latency):发出请求后,等待数据的时间
    • 带宽(bandwidth):开始传输后,单位时间数据传输量

磁带就是高延迟高带宽的典型例子:寻找某段数据可能很慢,但找到后连续读取大量数据可以很快。因此,它适合备份,通常不适合频繁查找单条记录。

很多时候,一次磁盘访问的等待,可能足够 CPU 完成大量内存操作


RAM(Random Access Memory) ​

RAM 就是通常所说的“内存”,用于保存 CPU 当前需要处理的数据和程序。数据库会把当前正在访问的数据页放在 RAM 中,以减少较慢的磁盘访问。

RAM 指的是可以按地址访问任意位置,不必从头依次读取。例如,读取地址 100 和地址 10000,都可以直接定位。

RAM 三个特点:

  • 访问快:没有 HDD 的寻道和旋转等待,CPU 可以通过内存地址访问数据

  • 流失性:普通 RAM 断电后,内容会丢失。

  • 单位容量成本较高:相比 SSD、HDD,通常无法以同样成本配置那么大的容量。

放到数据库中,可以通过一次查询理解 RAM 的作用:

我们要取一条记录,定位到其所在的数据页,数据库接下来会检查这个页是否在 RAM 中的缓冲池(buffer pool)里:

页已经在缓冲池中 → 直接访问该页
页不在缓冲池中   → 从 HDD/SSH 读取该页到 RAM,再访问记录

例如,目标记录只有 100 字节,但所在的数据页大小是 8 KB,数据库通常会把整个 8 KB 页读入 RAM。随后查询同页中的其他记录,就可能直接复用这个页,不必再次访问磁盘。

区分 RAM、缓冲池和 CPU Cache:

概念含义
RAM物理存储介质,也就是内存硬件
数据库缓冲池数据库在 RAM 中管理的一片区域,用来缓存数据页
CPU Cache更靠近 CPU 的硬件缓存,缓存内存中的部分数据

RAM 还会用于排序、哈希连接、聚合等操作的中间结果,不只是用来缓存磁盘数据。


CPU Cache(CPU 高速缓存) ​

CPU Cache 是一种容量小、速度快的存储,用来保存 CPU 近期使用或可能马上使用的数据和指令,减少访问 RAM 的等待。

CPU Cache 通常集成在 CPU 芯片上,作为 CPU 与 RAM 之间的缓冲。

CPU Cache 通常分为 L1、L2、L3 多级。

层级相对速度与容量常见设计
L1 Cache最快、最小每个核心独有,通常分为指令缓存和数据缓存
L2 Cache比 L1 大,稍慢通常靠近单个核心,为其提供缓存
L3 Cache比 L2 更大,访问更慢通常由多个核心共享

具体组织方式依处理器而异,但基本思路一致:用少量很快的存储,配合较大但较慢的存储。

当 CPU 需要读取某个内存地址的数据时,可以简化理解为:

查 L1→未命中则查 L2→未命中则查 L3→再访问 RAM

如果在某一级找到需要的数据,叫作缓存命中(cache hit);找不到则叫作缓存未命中(cache miss),需要继续访问下一层。

Cache 通常以缓存行(cache line)为单位搬运数据:它一般不会只取程序当前需要的那一个字节,而是把附近的一整段数据一起取来。

例如,假设缓存行大小是 64 字节,数组中的每个整数占 4 字节,且数组起始位置对齐:

数组:A[0]   A[1]   A[2]   ……   A[15]
      └──── 一条 64 字节缓存行 ────┘

第一次读取 A[0] 时,可能会把 A[0] 到 A[15] 一起载入 Cache。随后访问这些元素,就有机会直接命中缓存。

这种设计利用了程序访问数据的两种规律:

  • 时间局部性:刚使用过的数据,近期可能再次使用。
  • 空间局部性:访问某个地址后,可能也会访问附近的地址。

在数据库中,CPU Cache 与数据库缓冲池作用在不同层次。

对比项CPU Cache数据库缓冲池(Buffer Pool)
主要目的减少 CPU 访问 RAM 的等待减少数据库访问 SSD/HDD 的次数
保存什么内存数据和指令的副本从数据库文件读取的数据页
主要管理者硬件自动管理DBMS 管理
常用管理单位缓存行,通常几十字节数据页,通常数 KB

2. HDD 结构与页访问成本 ​

要解决的问题:盘片、磁道和扇区怎样关联?寻道、旋转等待和传输如何构成页访问成本,为什么顺序 I/O 更快?课件第 4—6 页

(1)HDD 结构 ​

笔记插图

机械硬盘中有旋转的盘片(platter),读写头通过机械臂移动到对应位置:

  • 磁道(track):硬盘盘片上有很多同心圆轨道。
  • 扇区(sector):磁道划分出的存储单元,数据就分布在这些磁道上的扇区里。
  • 柱面(cylinder):多个盘面上半径相同的磁道组成的集合。

数据库通常以页(page)为单位管理和读写数据。一个数据库页通常覆盖多个设备扇区,不能把“页”和“扇区”直接视为同一个概念。


(2)页访问成本(Page Access Cost) ​

数据库通常把文件划分为固定大小的页(page),以页为单位组织、读取和缓存数据。

页访问成本,就是数据库读取或写入一个数据页所付出的代价。 通常有两种表示方式:花费多少时间,以及发生多少次磁盘 I/O。

对于 HDD,读取一个页的基本时间模型是:

T页访问=T寻道+T旋转等待+T传输

可以把它想成:先移动磁头,再等数据转过来,最后读取数据。

  1. 寻道时间(Seek Time)

    机械臂移动,让磁头到达目标页所在的磁道。目标位置越分散,越容易产生反复移动。

  2. 旋转等待时间(Rotational Latency)

    磁头到达正确磁道后,还要等目标扇区转到磁头下方。假设目标位置均匀分布,平均需要等待半圈。

  3. 传输时间(Transfer Time)

    找到目标位置后,把页的数据传送出来:

    T传输=页大小传输速率

    页越大,或者传输速率越低,这部分时间越长。

很多真实情况下,传输时间只占页访问时间的很小一部分,大部分时间都花在定位和等待。

这进一步解释了随机访问和顺序访问的成本差异。

  1. 顺序访问:页在设备上连续排列,可以在定位后持续读取,摊薄寻道和旋转等待的成本。

    第 20 页→第 21 页→第 22 页→第 23 页
  2. 随机访问:页分散在不同位置,可能需要为每个页重新定位。

    第 20 页→第 51 页→第 800 页→第 123 页

在忽略缓存、排队等因素的简化模型下:

T随机读≈100×(T寻道+T旋转+T单页传输)T连续读≈T初始定位+100×T单页传输

第二个公式是理想化近似;实际连续读取仍可能遇到磁道切换等开销。但它表达了关键原因:连续读取可以让许多页分摊定位成本。

SSD(Solid State Drive) 没有磁头移动和旋转等待,随机访问的劣势通常小得多。不过,连续、批量读取仍常有优势,具体差距取决于设备和请求方式。


3. RAID 的冗余与并行机制 ​

要解决的问题:多盘为何增加故障风险?镜像如何提供冗余,条带化如何提高吞吐或降低大请求延迟?课件第 9—11 页

RAID(Redundant Array of Independent Disks,独立磁盘冗余阵列)就是把多块物理磁盘组织成一个逻辑存储设备,让它们共同保存和读写数据。

数据库使用 RAID,主要希望获得更大的容量、更高的读写性能,以及磁盘损坏后的恢复能力。不同 RAID 级别对这几个目标的取舍不同。

先掌握冗余与并行机制。

(1)条带化(Striping):把数据分散到多块盘,实现并行。

例如,把数据块 A~F 分到三块磁盘:

位置磁盘 1磁盘 2磁盘 3
第一组ABC
第二组DEF

读取 A、B、C 时,三块盘可以同时工作;不同请求访问不同盘时,也可以并行处理。

但这里没有额外保存恢复信息。如果磁盘 2 损坏,B、E 就可能丢失。条带化主要解决性能问题。

实际上,常见的 Striping 方式有三种:Bit-level,Byte-level 和 Block-level:

条带粒度实现
Bit-level striping一个字节有 8 位,把这 8 位分别写到 8 块磁盘上实现复杂,而且对并发 I/O 支持不好,几乎不用了
Byte-level striping数据按字节轮流写到不同磁盘大文件连续大吞吐
Block-level striping上面的例子并行读写;现代主流

(2)镜像(Mirroring):通过保存相同的数据副本提供冗余

磁盘 1:[A][B][C]
磁盘 2:[A][B][C]

同一份数据写到两块盘:

  • 读取时,可以从任意一个有效副本读取。
  • 写入时,需要更新两个副本。
  • 一块盘损坏后,另一块盘仍保存完整数据。

代价是容量:两块各 1 TB 的盘组成这样的镜像,可用容量约为 1 TB。


4. 奇偶校验、RAID 级别与嵌套结构 ​

要解决的问题:XOR 校验如何用于恢复?RAID 0、1、5、6 及课件中的嵌套结构有什么取舍,2、3、4 为何列为过时方案?课件第 12—16 页

(1)奇偶校验 ​

校验解决的问题是:能否比完整镜像少用一些空间,同时保留恢复能力?

最基本的方法是 异或(XOR)。两个二进制位,相同为 0,不同为 1。它有一个关键性质:

A⊕A=0

假设三个数据块是:

A = 1010
B = 1100
C = 0110

计算校验块:

P=A⊕B⊕C=0000

如果 B 所在的磁盘损坏,可以恢复:

B=P⊕A⊕C=1100

笔记插图

因为 A 和 C 在异或运算中分别出现两次,互相抵消,留下 B。

一个这样的校验块,可以恢复同组中一个已知缺失的数据块。如果两个数据块同时缺失,仅靠这一份校验信息通常无法唯一确定它们。


(2)RAID 级别与嵌套结构 ​

假设阵列共有 N 块等容量磁盘,每块容量为 S,忽略元数据等开销,常见级别可以这样比较:

RAID数据组织可用容量磁盘故障容忍能力主要取舍
RAID 0只有条带化NS无容量利用率高,有并行能力
RAID 1镜像,典型情况为两盘一组两盘时为 S两盘镜像可坏任意一盘小写入无需维护校验,但副本占空间
RAID 5块级条带化+一份分布式校验(N−1)S任意一盘容量效率较高,小更新有额外读写
RAID 6块级条带化+两份独立校验(N−2)S任意两盘容错更强,容量与更新开销更大
RAID 10,即 1+0镜像组之间再条带化NS/2每个镜像组至少保留一盘即可兼顾并行与镜像,容量利用率为 50%

RAID 0 虽然名称中有 RAID,但没有冗余。一块盘坏掉,分布在它上面的数据就可能无法恢复。

笔记插图

RAID 5 的“分布式校验”可以画成(N=4,S=3):

条带磁盘 1磁盘 2磁盘 3磁盘 4
第一组ABCP1
第二组DEP2F
第三组GP3HI

每一组都有校验块,但校验位置轮换,没有一块磁盘始终专门负责全部校验。这样可以分散校验写入的负载。

笔记插图

RAID 6 使用两份独立的校验信息,通常称为 P 和 Q。这里 Q 使用另一种编码关系(这里就先不介绍)。它们需要提供不同的恢复信息,不能只是把同一个 XOR 校验复制两遍。

过时方案的级别,重点理解设计思路:

  • RAID 2:位级条带化,使用海明码纠错。
  • RAID 3:字节级条带化,使用专用校验盘。
  • RAID 4:块级条带化,使用专用校验盘。

接下来看嵌套RAID

笔记插图

对比点RAID 0+1RAID 1+0
结构先条带,再镜像先镜像,再条带
故障影响坏一块盘可能导致整个条带组失效坏一块盘只影响一个镜像对
重建范围可能要重建整个条带组只重建一个镜像对
实际可用性低高
使用程度几乎不推荐企业级主流

其他组合:RAID 50 是底层 RAID 5 组、上层 RAID 0;RAID 60 是底层 RAID 6 组、上层 RAID 0。 判断它们的容错能力,也要逐组分析。


5. RAID 的选择与小写入代价 ​

要解决的问题:怎样结合容量成本、随机小写入、连续大写入、故障及重建表现选择方案?为什么校验更新会增加读写?课件第 17 页

选择 RAID,要同时比较容量成本、正常运行性能,以及故障和重建期间的表现。

选择 RAID 的五个考虑因素:

因素具体要考虑什么
金钱成本保存同样多的有效数据,需要购买多少磁盘?
正常运行性能每秒能处理多少次 I/O(IOPS)?连续传输带宽有多大?
磁盘故障时的性能缺少一块盘后,读写是否需要额外操作?
重建时的性能恢复数据会占用多少资源,对正常读写有多大影响?
重建所需时间多久才能恢复完整的冗余保护?

**RAID 5 的小写入代价 **

例如,RAID 5 正常读取某个数据块时,通常可以直接读取它所在的磁盘;如果这块盘已经损坏,读取缺失块就需要利用其他数据块和校验块恢复。因此,正常状态下的速度不能代表故障状态下的速度。

假设 RAID 5 某个条带满足:

P=A⊕B⊕C

现在只修改 A,得到 A′。校验也必须更新:

P′=A′⊕B⊕C

无需重新读取所有其他数据块,也可以利用:

P′=P⊕A⊕A′

所以,在没有相关缓存、采用典型“读—改—写”方式时,一次小更新需要:

  1. 读取旧数据 A;读取旧校验 P。
  2. 写入新数据 A′;写入新校验 P′
RAID 5 小更新:2 次块读+2 次块写

相比之下,两盘镜像通常只需要把新数据写到两个副本上,无须为了校验读取旧数据。

如果一次写入覆盖整个条带,例如 A、B、C 全部都是新数据,就可以直接计算:

Pnew=Anew⊕Bnew⊕Cnew

这时不必为了计算校验读取旧数据和旧校验。因此,完整条带的大写入,比零散的小更新更容易摊薄校验成本,RAID 5 适合连续、大量的写入。

总结,对于 RAID 5:

  • 零散的小更新:为了维护校验块,产生额外 I/O 成本
  • 完整条带的大写入:直接根据新数据生成校验块,更容易摊薄开销

选择思路:

RAID课件中的选择依据
RAID 0数据安全不重要,且数据能够从其他来源快速恢复时使用
RAID 1适合大量随机、小规模更新;写入开销较低,但保存副本的容量成本较高
RAID 5适合需要大量存储容量、写入连续且规模较大的场景
RAID 6比 RAID 5 提供更强的保护,可容忍任意两块磁盘故障,但增加容量和校验维护成本

二、数据库缓冲管理 ​

本主题回答:如何减少重复读盘,并控制页的加载、替换与写回?

Database Buffer Manager 课件第 19—24 页

数据库缓冲管理的核心:把可能再次使用的数据页留在内存中,并管理页面的读入、替换和写回,尽量减少磁盘 I/O。

上一节介绍了磁盘访问为什么昂贵。这一节接着回答:既然磁盘慢,数据库怎样利用有限的 RAM,减少访问磁盘的次数?

0. 缓冲池(Buffer Pool) ​

假设数据库需要读取某条学生记录,它通常先找到这条记录所在的页,再请求访问该页。

如果每次访问都重新读取磁盘,即使连续查询的是同一个页,也会产生重复 I/O。因此,数据库在 RAM 中留出一部分空间,专门保存已经读入的数据页,这块空间叫作 缓冲池(buffer pool)。

磁盘中的数据库文件⟷页的读入、写回操作系统⟷请求文件数据RAM 中的缓冲池⟷访问页内的数据查询执行程序
概念含义
页,page数据库管理和传输数据的基本单位
缓冲帧,frame缓冲池中用于容纳一个页的内存位置
缓冲池,buffer pool一组缓冲帧构成的内存区域
缓冲管理器,buffer manager管理页在哪里、何时读入、何时替换和写回的子系统

例如,忽略管理信息,64 MiB 的缓冲池使用 8 KiB 的页,可以容纳:

64×1024 KiB8 KiB=8192 个页

但数据库可能有几百万个页,所以关键问题是:有限的内存应该留给哪些页?


1. 缓冲、预读与磁盘调度 ​

要解决的问题:缓冲、预读和电梯调度分别减少什么开销?为什么应用处理数据前需要先将它读入 RAM?课件第 19—20 页

三种方法,都能改善 I/O,但作用不同:

方法做法主要收益
缓冲,buffering保留已经读入的页避免重复访问磁盘
预读,read-ahead提前读取预计很快会用到的页减少等待,并利用连续传输
磁盘调度调整待处理请求的顺序减少 HDD 磁头移动
  • 缓冲(Buffering):重复访问

    如果第一次读取 P1 后一直留在缓冲池中,若后面还要访问 P1 就可以直接在缓冲池中读取

    • 命中(hit):所需页已经在缓冲池。
    • 未命中(miss):所需页不在缓冲池,需要读入。
  • 预读(Read-ahead):可以预测的后续访问

    假设数据库正在扫描 P1 → P2 → P3 → P4 → …,处理 P1 时,就可以提前发起对后续 P2、P3的读取,减少计算对于 I/O 的等待时间。批量读取相邻页,还可以摊薄 HDD 的定位成本。

    但预读也有代价:预测错误时,可能会读取不需要的数据占用缓冲池。因此,它适合具有可预测访问模式的场景。

  • 磁盘调度(Disk-arm-scheduling ):请求位置

    假设多个请求分布在多个磁道上,完全按照到达顺序处理,磁头可能会反复来回移动,这样会增加很多寻道成本。

    解决这个问题使用的是电梯算法(elevator algorithm),这是一种 HDD 磁盘调度方法:

    让磁头沿一个方向移动,依次处理沿途请求,再反向处理另一边的请求,减少来回寻道。

    经典形式称为 SCAN 算法。执行规则可以概括为:

    1. 确定当前移动方向。
    2. 按磁道位置顺序处理这个方向上的请求。
    3. 到达磁盘边界后反向。
    4. 继续服务另一方向上的请求。

    它的名字来自电梯:电梯向上运行时,通常先沿途服务上方楼层,再转向下行,而不是完全按照乘客按按钮的先后顺序来回跑。

这三种方法可以同时存在:已经读过的页尽量复用,将要使用的页提前读取,必须执行的磁盘请求尽量高效安排。


2. 为什么 DBMS 自己管理缓冲 ​

要解决的问题:只依赖 mmap 和操作系统换页会遇到什么事务安全、I/O 停顿及性能问题?DBMS 希望控制哪些行为?课件第 21—22 页

(1)操作系统的缓存 Vs DBMS Buffer Pool 的缓存 ​

先明确 “操作系统”:运行数据库软件的 Windows、Linux 等系统。DBMS 本身是一个程序,需要通过操作系统提供的文件读写接口,访问磁盘上的数据库文件。

操作系统也会利用一部分 RAM,保留最近读取过的文件数据(页缓存 page cache),还提供 mmap:把文件映射到程序的虚拟地址空间,让程序通过内存地址访问文件。但建立映射不意味着整个文件已经读入 RAM。访问尚未驻留内存的部分时,仍可能触发缺页和磁盘读取。

所以RAM中有两层缓存:

缓存谁管理保存什么
DBMS buffer pool数据库软件数据库的数据页
操作系统文件缓存操作系统文件中最近访问过的数据,包括数据库文件的数据

以普通的缓冲文件 I/O为例,读取过程是:

markdown
数据库请求 P10
      ↓
检查 DBMS buffer pool
      │
      ├─ 命中 → 直接使用,不必再发起文件读取
      │
      └─ 未命中 → 向操作系统请求这段文件数据
                         ↓
                  检查操作系统文件缓存
                         │
                         ├─ 命中 → 从 RAM 提供数据  # buffer pool 空间不足,淘汰了 P10,但检查操作系统文件缓存还保留
                         │
                         └─ 未命中 → 从磁盘读取
                         
                  数据进入 DBMS buffer pool
                         ↓
                    数据库使用 P10
情况数据从哪里取得这次是否需要读磁盘
Buffer pool 命中DBMS 管理的内存不需要
Buffer pool 未命中,操作系统缓存命中操作系统管理的缓存内存不需要
两层都未命中磁盘需要

既然操作系统已经缓存了,为什么 DBMS 还要缓存?

  • 操作系统提供的是通用文件服务。对他来说,数据库文件也是文件,跟其他文件没有区别;使用普通缓冲读取时,它通常会按自己的机制缓存这些文件数据。
  • DBMS 要自己管理缓冲,主要因为它需要根据查询用途决定“保留哪些页”,并根据事务规则决定“何时写回哪些页”。操作系统掌握的信息不足以独立完成这些决策。
  • 有些数据库会使用直接 I/O(Direct I/O),绕过常规的操作系统文件数据缓存,减少重复缓存

(2)DBMS Buffer Pool 的缓存解决了什么问题 ​

A.1 页面写回影响事务恢复的正确性 ​

对于一个被修改的文件页,操作系统与数据库关心着不同的问题:

  • 操作系统:这个页有修改,需要在适当的时候写回文件。
  • 数据库:这个修改属于哪个事务?恢复它需要的日志是否已经安全保存?

例如,一个事务把账户余额从 100 改为 120:

  1. 数据库要修改数据时,先把对应页从磁盘读进 缓冲池

  2. 在缓冲池里修改这一页后,内存里的版本就和磁盘不一致了

    内存中的数据页:余额 = 120
    磁盘上的数据页:余额 = 100
    
    内存中的日志:记录了这次修改
    磁盘上的日志:尚未保存这次修改

    这时这一页被称为 脏页 (dirty page)

  3. 此时,如果数据页先写入磁盘,随后系统崩溃,就可能出现:

    时刻内存数据页内存日志磁盘数据页磁盘日志
    T1 修改前100—100—
    T2 在缓冲池改值120记录“余额+20”100—
    T3 脏页被刷回磁盘120记录“余额+20”120—
    T4 崩溃(断电)全部丢失全部丢失120—

    重启后数据库只能看磁盘。此时它看到的是:

    • 数据页里余额 = 120;日志里没有这条修改的任何记录

    于是,磁盘上的数据变成了一个“说不清来历”的状态

因此,缓冲管理器需要与日志管理器协作,判断一个脏页是否已经具备安全写回的条件。写回时机必须符合数据库协议,不能只根据“这个页脏了”来决定。


A.2 DBMS 比操作系统更了解页面未来会怎样被使用 ​

操作系统主要能观察访问历史,例如某段内存最近是否被访问。DBMS 还知道这些访问属于什么查询操作。

例如,缓冲池里有两类页:

页面最近访问情况查询中的实际用途
热门索引页刚才访问过接下来大量查询还会访问
全表扫描的数据页刚才访问过本次扫描处理完后,可能很久不再使用

从“刚刚访问过”来看,两者很相似。但从未来用途来看,保留价值可能差别很大。

假设一个分析查询扫描一张非常大的表,如果不断把扫描页加入缓冲,并淘汰原来的热门页,扫描完成后,许多频繁使用的索引页和数据页可能已经被挤出去。这通常称为缓存污染。

DBMS 知道接下来的扫面策略,就可以采用适合扫描的缓冲策略,减少它对热门页的影响。


A.3 DBMS 希望明确知道什么时候需要 I/O,以便安排工作 ​

前面我们说到,操作系统也会缓存文件,并用mmap 把文件映射到虚拟地址空间,程序可以像访问内存一样访问文件内容。但:

有虚拟地址,不代表对应的数据已经驻留在 RAM 中。

例如,查询线程执行一次普通的内存访问:

 访问某个映射地址
        ↓
对应文件页不在 RAM 中
        ↓
     发生缺页
        ↓
操作系统读取磁盘
        ↓
    当前线程等待

问题是,这次磁盘等待藏在一次看似普通的内存访问中,DBMS 不容易提前安排它。

而通过自己的缓冲管理器,DBMS 可以把过程显式化:

请求页 P
   ↓
检查是否已经在缓冲池
   ├─ 已在:直接使用
   └─ 不在:发起读取,并记录等待请求

这样,缓冲管理器就可以与执行器协作:

  • 提前发起异步读取。
  • 等待页面时安排其他可执行任务。
  • 合并或协调多个查询对同一页的请求。
  • 让查询进度和 I/O 状态更容易跟踪。

磁盘读取仍然需要时间,但 DBMS 能更主动地安排这段等待。


所以,理解“DBMS 自己管理缓冲”时,可以抓住这句话:

操作系统管理通用的内存与文件访问;DBMS 利用查询和事务信息,决定页面该如何被使用、保留和持久化


3. 页请求与缓冲池的工作过程 ​

要解决的问题:请求页时怎样检查缓冲池、读入所需页并在缓冲已满时选择替换页?课件第 23 页

笔记插图

  1. 查询缓冲池中是否存在目标页。 缓冲管理器通常维护从“页编号”到“缓冲帧”的映射,以便定位。
  2. 如果命中,直接访问内存中的页。 这次页读取不需要访问磁盘。
  3. 如果未命中,寻找空闲帧(free page) 有空闲帧,就把目标页读入其中。
  4. 如果没有空闲帧,选择可替换页。 这一步由替换策略参与决定。
  5. 必要时先写回被替换页,再读入目标页。 干净页可以直接丢弃其内存副本;尚未写回的脏页需要先妥善保存修改。

为了理解“哪些页可以替换”,还需要补充一个概念:固定(pin)。

当执行程序正在使用一个页时,会将它固定在缓冲池中,避免它被替换。使用结束后再解除固定,即 unpin。多个使用者同时固定一个页时,可以用 pin count 记录数量。

属性它回答的问题对替换的影响
dirty页是否有尚未写回的修改?决定是否需要写回
pin count还有多少使用者正在使用这个页?通常只有为 0 时才可替换

例如,缓冲池只有两个帧:

帧当前页是否脏页pin count
F1P10是0
F2P20否1

现在请求 P30,且 P30 不在内存中:

  • P20 虽然干净,但仍被使用,不能直接替换。
  • P10 没有被固定,可以作为替换对象。
  • 如果 P10 的修改尚未写回,就先按恢复协议保存它,再读入 P30。

如果所有帧都被固定,就需要等待或协调使用者释放页面,不能随意淘汰一个仍在使用的页。


4. LRU、MRU 与重复扫描 ​

要解决的问题:为什么 LRU 不总适合数据库?在课件的嵌套循环与重复扫描情形下,MRU 为什么可能更合适?课件第 24 页

缓冲池已满时,除了排除被固定的页,还要在可替换页中决定淘汰谁(替换策略)。

策略淘汰对象背后的判断
LRU(Least Recently Used)最久没有使用的页最近使用过的页,可能很快再次使用
MRU(Most Recently Used)最近刚使用的页某些扫描中,刚处理完的页短期内不会再用

LRU 的判断经常合理。例如,查询不断访问少数热门索引页,就应该尽量保留这些页。

但在重复顺序扫描中,它可能失效。

一个例子:假设只有三个缓冲帧,反复访问四个页

A→B→C→D→A→B→C→D→⋯
  • 使用 LRU:缓冲池满了之后,每次刚淘汰的页,恰好就是接下来要访问的页。

  • 使用 MRU:读完 A、B、C 后请求 D,会淘汰刚使用过的 C,留下 A、B、D。接下来的第二轮访问结果如下

    缓冲池第二轮请求MRU
    A、B、DA命中
    B、D、AB命中
    D、A、BC未命中
    D、A、CD命中

MRU 在这个例子中保留了部分即将再次访问的页,减少了读取。


三、记录组织 ​

本主题回答:字段如何组成记录,记录增删或移动后如何继续管理空间和引用?

Record Organization · 课件第 26—33 页

上一节讨论“如何把页读入内存”,这一节把视角放到页的内部:字段如何组成记录,记录如何存放,以及增删、移动后怎样继续找到它。

可以沿着这条线理解:

定长记录便于定位 → 易产生空位 → 变长记录增加空间管理难度 → 槽式页通过间接引用支持整理。

1. 定长记录与相对位置 ​

要解决的问题:如何由记录长度计算位置?记录不跨页有什么空间代价,删除后直接移动记录会怎样影响物理引用?

课件第 26—27 页

(1)定长记录 ​

定长记录(fixed-length record)是指:在给定的存储格式下,每条记录占用相同数量的字节。 这种组织方式使记录的位置可以通过算术计算直接确定。

理解这一模型,需要区分三个层次:记录内部的字段布局、记录在页内的位置,以及记录在文件中的位置。

本节采用一个简化模型:同一文件保存同一种类型的记录,每条记录由若干字段组成,每个字段占用固定的字节数,因此每条记录的长度也固定。

设 Student(sid, name, major) 的存储格式规定如下,暂时忽略记录头等辅助信息:

字段固定占用空间在记录内的起始偏移
sid4 字节0
name16 字节4
major12 字节20
合计32 字节

这里的“定长”描述的是分配的物理空间,而不是每个值的实际内容长度。对于 name,若有一条记录的name字段实际只有 8 字节,实际仍会占用预留的 16 字节区域,其余部分按照编码规则填充。

(2)相对位置 ​

相对位置:定长记录的位置可由“起点+前面记录占用的空间”得到。

一条记录对应一行数据,由若干字段组成:

markdown
记录:[学号][姓名][专业]
页:  [页头][记录1][记录2][记录3]……

设每条记录占 L 字节,记录从 1 开始编号,页的开头还有 H 字节的页头。

如果以记录区起点为基准,第 i 条记录之前恰有 i−1 条记录,因此其起始偏移为:

offset记录区(i)=H+(i−1)L

不过,位置计算简单,不意味着按任意条件查找记录也同样简单。


当记录以页为单位存放时,还必须确定是否允许一条记录跨越页边界。 ​

这里采用不跨页存储(unspanned organization),即每条记录必须完整地放在同一个页中。

设页大小为 P,忽略其他管理开销,一页用于存放记录的空间为 P−H,最多容纳的记录数为:

k=⌊P−HL⌋

其中,向下取整⌊∗⌋来自“不允许跨页记录”的要求。

页尽量填满后,页尾可能有空间,剩余空间为:

W=P−H−kL
将页内定位推广到整个文件时,必须计入每页的页头和未使用空间。 ​

在页面连续排列、没有额外文件前缀的模型中,令页编号从 0 开始、记录位置编号 i 从 1 开始。第 i 个记录位置所在的页号为:

q=⌊i−1k⌋

它在该页内的位置编号 s 从 0 开始计数,则:

s=i−(q+1)kors=(i−1)modk

于是,文件内的字节偏移为:

offset文件(i)=qP+H+sL

三项分别表示:

qP⏟跳过前面的完整页+H⏟跳过当前页页头+sL⏟跳过页内前面的记录位置
定长布局解决了位置计算,但记录移动仍会影响依赖物理位置的引用 ​

这种定长布局容易定位,但删除记录后怎么办?

假设一个页中依次存放五条记录:

删除前:[A][B][C][D][E]

删除 B 后,有两种直接的处理思路。

  • 保留空位:

    删除后:[A][空][C][D][E]

    其他记录的位置不变,但需要记录这个空位,以便日后复用。

  • 将后续记录向前移动:

    整理后:[A][C][D][E][空]

    这样能够保持有效记录连续存放,却改变了 C、D、E 的位置。若引用未同步更新,查找结果就可能错误。

因此,存储位置与记录身份必须区分:

概念含义移动记录后的情况
物理位置页号、页内偏移等定位信息可能改变
逻辑标识主键等用于识别记录的值不因单纯搬移字节而改变
  • 如果引用依赖原来的物理位置,那移动记录后需要维护引用;
  • SQL 外键引用的是逻辑键值,所以记录单纯搬移不会导致外键值失效。

2. 空闲链表(Free List) ​

要解决的问题:如何利用已删除记录的空间保存下一空闲位置,复用槽位而不移动有效记录?

课件第 28 页

空闲链表(Free List)是一种空间复用机制,用于将已删除记录留下的位置连接起来,供后续插入使用。

在定长记录模型中,各记录位置大小相同,因此可以直接用空闲位置容纳一条新纪录,而不必根据不同空闲位置的容量不同去寻找空闲位置。

设一个文件中的记录按固定长度存放。删除记录 B 后,文件布局变为:

删除前:[记录A][记录B][记录C][记录D]
删除后:[记录A][空闲 ][记录C][记录D]

如果将C、D向前移动,可以消除空闲,但需要搬动数据,可能使依赖原物理位置的引用失效。

空闲链表采用另一种处理方式:有效记录保持原位置,将被删除记录的空位登记起来,等待复用。

这意味着,“删除一条记录”并不必然使文件缩小。记录原来占用的字节区域仍在文件中,只是从“保存有效数据”变成了“可重新分配”。


(1)链表 ​

链表由文件头中的入口和空闲位置中的链接指针组成。 可以使用以下符号描述:

符号含义
head第一个空闲记录位置的地址
next(p)=q保存在空闲位置 p 中的、下一个空闲位置的地址q
NULL链表结束;若 head = NULL,表示没有已登记的空位
L每个记录位置占用的固定字节数

这里的地址是数据库文件中的位置标识,例如页编号与页内位置,不是程序运行时的内存地址。

假设位置 2、5、7 上的记录已经删除,则可以组织为:

文件头
 head ──→ 位置2 ──→ 位置5 ──→ 位置7 ──→ NULL

对应的管理信息是:

存放位置保存的内容
文件头head = 2
空闲位置 2next(2) = 5
空闲位置 5next(5) = 7
空闲位置 7next(7) = NULL

这一设计的关键在于:链接指针直接写入已删除记录留下的空间。

位置被使用时:[              记录字段              ]
位置空闲时:  [ next 指针 ][      其余空闲字节      ]

(2)删除操作与插入操作 ​

删除操作可以通过“链首插入”登记新空位。

链表:

head → 2 → 5 → 7 → NULL

现在删除位置 4 上的有效记录。登记这个新空位,只需要两项链接修改:

  1. 在位置 4 中保存原来的链首地址,即 next(4) = 2(next(4)←head)
  2. 将文件头的入口改为 head = 4
head → 4 → 2 → 5 → 7 → NULL

其他有效记录的位置没有改变,原空闲链表中的链接也不需要逐个修改。

因此,链表顺序通常取决于空位的加入方式,不必按照物理地址、记录键值或删除时间排序。这里采用链首插入,是因为它不需要遍历链表。

插入操作则从链首取出一个空位。

假设需要插入新记录 X,此时:

head → 4 → 2 → 5 → 7 → NULL

处理过程为:

  1. 取得链首位置:p=head=4
  2. 将链首位置改为后继位置:head=next(4)=2
  3. 把新记录 X 写入位置 4,并将该位置标记为有效。
空闲链表:head → 2 → 5 → 7 → NULL

位置4:  [       新记录X        ]

必须先取得后继地址,再用新记录覆盖空位。 因为 next(4) 原本就保存在位置 4 的字节区域中;一旦写入 X,该链接信息就可能被覆盖。

整个过程的状态变化如下:

阶段head位置 4 的内容
删除前2有效记录
删除后4指向位置 2 的链接
插入 X 后2新记录 X

(3)定长记录与空闲链表 ​

定长记录使链首分配成为一种简单而有效的选择。

设每个记录位置都是 L 字节,每条新记录也占 L 字节,则任意一个空位都能满足插入要求:

空位大小=L=新记录所需空间

系统无须沿链表搜索“哪个空位足够大”,也无须把空位切分成不同大小的区域。


3. 变长记录的四类表示方法 ​

要解决的问题:字节串、嵌入标识、预留空间和指针方法分别怎样表示记录?碎片、浪费空间、锚页及溢出页有哪些取舍?

课件第 29—32 页

定长记录的取舍

  • 优点:每个字段的位置固定,读取和管理比较简单
  • 代价:浪费存储空间。比如为name 设定了 16 byte 的占用空间,但大部分姓名只占用 6~9 个 byte,剩余空间按规则填充。这意味着很多空间没有存储实际有效的信息。

这就引出了变长记录(Variable-length record):让字段按照实际需要占用空间。

这里讨论四种方法,分别采用以下思路:

表示方法基本思路
字节串表示按实际长度连续存放,用标记识别记录边界
嵌入标识在字段值旁保存字段标识等元数据
预留空间按最大长度分配固定空间
指针方法将可增长的内容拆成若干单元,用指针连接

理解这些方法时,需要始终区分两个问题:如何解释记录中的内容,以及如何管理记录占用的空间。


(1)字节串表示(Byte-String Representation) ​

若每条记录的长度不一,如何知道一条记录到哪里结束?

将每条记录编码为一串字节,再将这些字节串依次存放;记录末尾附加特殊的结束标记。这里用符号 ⊥ 表示记录结束。

以学生表为例:

[1001 | 张三 | Statistics] ⊥ [1002 | Jack | Mathematics] ⊥ …

其中,竖线仅用于示意字段边界;实际格式还需要规定各字段如何编码、如何分隔。

设第 i 条记录的内容长度为 ℓi,结束标记占 e 字节,其起始位置为 si,则:

si+1=si+ℓi+e

由于 ℓi 并不固定,通常不能像定长记录那样,仅凭记录编号直接计算位置。没有额外的位置目录时,需要从某个已知边界逐条解析,才能找到后续记录。

还需要区分两种边界:

  • 记录边界:一条记录在哪里结束。
  • 字段边界:记录内部各字段在哪里结束。

这种表示的优势是布局紧凑:短记录按实际长度占用空间,不必为最大长度预留大量空白。但连续布局会给更新带来困难。

例如,页面中分别有 30 字节和 25 字节的空洞,总计 55 字节,却不能直接容纳一条需要连续 50 字节空间的记录。

可以移动其他记录,将空闲空间合并,但这又需要维护记录位置及相关引用。


(2)嵌入标识(Embedded Identification) ​

若字段长度不一,如何识别一个值属于哪个字段?

在字段值之前或附近保存字段标识,使记录携带解释自身内容所需的部分元数据。

以属性名作为典型例子:

[1001 | 张三 | Statistics]

可以表示为:

[studentID : 1001]
[studentName: 张三]
[major   : Statistics]

在固定模式的记录中,读取程序通常根据预先已知的字段顺序和编码规则解释字节。嵌入标识则允许读取程序通过记录中的标识判断“这个值属于哪个字段”。

但嵌入标识不等于必须采用某一种文本格式,字段标识也可以其他格式。

一条记录的空间成本可以概括为:

L记录=L字段值+L字段元数据+L结构信息

如果所有记录都有相同字段,每条记录都重复保存完整字段名,会产生明显冗余。反过来,如果字段非常稀疏,省略大量不出现的字段,也可能抵消元数据开销。


(3)预留空间(Reserved Space) ​

(4)指针方法(Pointer Method) ​

主要解决变长记录记录增长的问题。

磁盘上的物理空间通常被划分成很多固定大小的块,比如每块 4KB。 如果这条记录很长,或者某个字段特别长,就可能不能简单塞进一个连续区域里。

指针方法就是:把一条变长的逻辑记录拆成若干个固定大小的存储单元,每个单元里放一个指针,指向下一个单元。记录增长时,只需增加新的单元,而不必事先预留全部空间。

一个例子,假设需要表示某个支行及其全部账户:

支行:Perryridge

账户:
(A-102, 400)
(A-210, 900)
(A-218, 700)

随着账户增加,这组信息的实际长度不断增长。

预留空间的方法,需要提前决定“最多容纳多少个账户”。指针方法则按当前需要分配单元:

[Perryridge | A-102 | 400 | next]
                              │
                              ▼
                       [A-210 | 900 | next]
                                         │
                                         ▼
                                  [A-218 | 700 | 空]

其中,每个 next 指向同一条逻辑记录的后继单元;“空”表示链结束。

物理结构分为锚记录和溢出记录:

类型存放内容作用
锚页(Anchor Page)各条链的起始记录提供逻辑记录的入口
溢出页(Overflow Page)各条链的后续记录容纳继续增长的内容
  • 锚记录保存:
[支行名][第一个账号][第一个余额][后继指针]
  • 溢出记录保存:
[账号][余额][后继指针]

支行名是整条逻辑记录的公共信息,保存在锚记录中即可,无须在每个账户单元中重复保存。

“锚页”并不意味着一个页面只能存放一个支行。

一个锚页可以容纳多条链的起始记录;同一个溢出页也可以保存来自不同链的后续记录。

例如,采用“页编号、槽编号”作为位置标识,布局可以如下。

锚页 P10:

槽编号支行账号余额next
1PerryridgeA-102400(P20, 3)
2Round HillA-305350空
3DowntownA-101500(P20, 2)

溢出页 P20:

槽编号账号余额next
1A-218700空
2A-110600空
3A-210900(P20, 1)

因此,Perryridge 的访问路径是:

(P10, 1) → (P20, 3) → (P20, 1) → 空
  A-102      A-210      A-218

这个例子说明了两个重要性质:

  • 逻辑上的相邻单元,不必在物理上相邻。
  • 不同逻辑记录的单元,可以交错存放在同一页面中。

指针保存的是后继单元的位置,并非只保存“下一页的编号”。它需要能够进一步确定页内的目标单元。

读取完整记录,需要从锚记录开始沿链访问。

假设已经通过索引或其他方式找到了 Perryridge 的锚记录,读取过程为:

  1. 读取锚记录,取得支行名及第一个账户 A-102。
  2. 根据 next = (P20, 3),访问账户 A-210。
  3. 根据新的 next = (P20, 1),访问账户 A-218。
  4. 遇到空指针,结束遍历。

这是一条典型的单向链。

如果只需要支行名或第一个账户,访问锚记录即可。如果需要第 (k) 个账户,在没有额外索引等辅助结构时,通常需要从链首依次访问,工作量随 (k) 增长。


4. 槽式页(Slotted Page) ​

要解决的问题:页头如何记录条目数、空闲区边界及记录位置和长度?通过槽条目间接引用,为什么允许页内整理记录?

课件第 33 页

槽式页(Slotted Page)是一种通过槽目录管理页内记录的存储结构。它将记录的引用与记录在页内的实际位置分开,使变长记录能够在页内移动,而不必同时修改所有外部引用。

上一节的变长记录表示方法解决了内容如何编码、长度如何变化的问题。槽式页进一步解决:记录放在哪里、占用多少空间,以及页面整理后如何继续定位。


(1) 页内布局 ​

槽式页通常由固定页头、槽目录、空闲空间和记录区组成。

笔记插图

  • Block Header:

    • #Entries :Number of Entries(条目数量)即:“这一页里有多少个条目(槽)”,也就是块头中槽数组的长度。
    • #Entries 下面有虚线连到 “End of Free Space”,表示页头中保存了“空闲区结束位置”的偏移量,用它定位空闲区与记录区的交界
  • 槽(Slots):Size 和 Location 那一行就是一个个槽。

    • 每个槽不存记录本身,只存“这条记录多长、放在哪里”:
      • Size:每个槽里记录的长度。
      • Location:每个槽里记录的起始位置(页内偏移)。
    • 图中从槽引出的箭头指向下方 Records 区里的具体记录。
  • Records:

    • 真正存放变长记录的地方,通常从页面尾部往前增长。
    • 靠槽里的 Location 找到它
  • Free Space:夹在槽数组和记录区中间。

    • 从空闲区分配空间,同时在块头新增一个槽;
    • 删除记录时,对应槽可以标记为无效,空间回收进空闲区。

新增槽条目时,槽目录向高地址方向增长;分配记录空间时,记录区向低地址方向增长。两者之间的区域是连续空闲空间。

槽不是记录本身,而是描述记录位置的目录条目。 即使记录长度不同,槽条目也可以采用固定长度。

在一种典型布局中,设:

  • 页大小为 P;
  • 固定页头大小为 H;
  • 每个槽条目大小为 S;
  • 当前保留的槽条目数为 n;
  • 记录区的起始偏移为 U。

则槽目录结束位置为:

L=H+nS

连续空闲空间为:

F连续=U−L

这里,n 表示保留的槽条目数,不一定等于有效记录数。记录删除后,对应槽可能仍然保留,以便维持其他槽编号的稳定。


(2)记录定位与间接引用 ​

如果外部引用直接保存记录的页内偏移,记录移动后,这个偏移就会失效。槽式页让引用先指向槽,再通过槽找到记录。

在常见设计中,记录标识符写成:

RID=(页编号,槽编号)

例如:

RID = (7, 3)
      │
      ▼
第7页的槽3:[偏移624,长度80]
      │
      ▼
第7页中从偏移624开始的80字节

如果记录从偏移 624 移到偏移 824,只需更新槽 3:

移动前:槽3 = [624, 80]
移动后:槽3 = [824, 80]

其 RID 仍然是 (7, 3)。

因此,槽式页允许:

记录位置改变,槽编号保持稳定;外部通过槽编号进行间接访问。


(3)页内整理:合并空洞,形成连续空闲空间 ​

删除记录后,原来连续排列的记录之间可能留下空洞:

整理前:
[页头与槽目录][空闲空间][记录B][空洞][记录A]

可以移动记录 B,使其紧邻记录 A:

整理后:
[页头与槽目录][更大的连续空闲空间][记录B][记录A]

这样的操作称为页内整理或紧凑化。它将分散的空洞合并到空闲区,使空闲空间更便于后续使用。

整理时,需要同步维护页头信息:

  • 对于被移动的记录,更新对应槽中的位置。
  • 如果只是移动记录而没有修改内容,其长度保持不变。
  • 根据整理后的布局,更新空闲空间的结束位置。
  • 如果没有增加或删除条目,条目数保持不变。

四、文件组织与 I/O 代价 ​

本主题回答:不同文件布局如何影响定位、扫描、插入、删除和页 I/O 次数?

File Organizations · 课件第 35—51 页

前一节讨论了一页内部如何存放和定位记录。本模块将视角扩展到文件层:记录分布在许多页中,数据库应当如何组织这些页,才能有效完成查找、扫描、插入和删除?

文件组织决定记录的存放与访问方式;I/O 代价用于衡量这些操作需要读写多少个页。

主要讨论三种文件组织:

文件组织基本原则后续讨论重点
堆文件(Heap File)记录可以放在文件中有可用空间的位置,不按搜索键排序如何管理文件中的页及其空闲空间
顺序文件(Sequential File)记录按照搜索键的值有序组织如何利用顺序检索,以及如何处理插入、删除与重组
哈希文件(Hash File)通过哈希函数,将搜索键映射到存储页或桶如何定位记录,以及如何处理空间占用与溢出

1. 数据库文件与三种页概念 ​

要解决的问题:存储管理器怎样以页组织文件?设备层、操作系统和数据库各自的页概念为什么要区分?课件第 35—36 页


(1)数据库文件:由存储管理器按页组织 ​

DBMS 通常将数据库保存在磁盘上的一个或多个文件中,文件内部采用由 DBMS 规定的格式。

操作系统可以管理这些文件,但通常不理解其中的数据库结构。例如,哪些字节表示记录、哪些位置保存槽条目,需要由 DBMS 解释。

对于记录存储,可以将其组织关系理解为:

数据库→一个或多个文件→页的集合→数据页中的记录→记录中的字段

负责维护数据库文件的子系统称为存储管理器(Storage Manager)。主要职责包括:

职责含义
按页组织文件将文件作为页的集合进行管理
跟踪页的数据读写管理数据从哪些页读取、向哪些页写入
跟踪可用空间掌握文件中可继续存放数据的空间

至此,前面几节的内容便衔接起来:文件由页组成,缓冲管理器负责页在内存中的使用,而记录组织规定页内记录的布局。


(2)三种页概念:同名,但属于不同层次 ​

需要区分硬件页、操作系统页和数据库页。三者的管理对象不同,大小也不要求相同。

页的概念所属层次含义课件列举的大小
硬件页(Hardware Page)存储设备层设备能够保证故障安全写入的最大数据块通常为 4 KB
操作系统页(OS Page)操作系统内存管理层操作系统管理虚拟内存与物理内存映射的单位通常为 4 KB;另列出 x64 的 2 MB、1 GB 大页
数据库页(Database Page)DBMS 层数据库组织、管理和读写文件内容的单位512 B–32 KB;另列大数据系统中的 64 MB 示例

笔记插图

硬件页关注设备层面的写入保证。 硬件页(Hardware Page)指存储设备能够保证“故障安全写入”的最大数据块。它属于磁盘、SSD 的存储层面。

  • 这里关注的是:设备发生故障时,一次写入能在多大的范围内保持完整。

    • 按课件的简化模型,假设硬件页为 4 KiB:在设备承诺的条件下,一个硬件页的更新具有原子性——要么保留旧内容,要么成为新内容,不会出现半页新、半页旧。

    • 如果数据库页为 8 KiB,就可能跨两个硬件页:

      ┌──────────────────┬──────────────────┐
      │ 硬件页1:4 KiB    │  硬件页2:4 KiB   │
      └──────────────────┴──────────────────┘

      设备分别写这两部分时,如果第一部分更新后发生故障,整个数据库页就可能变成:

      [前半部分:新内容][后半部分:旧内容]

操作系统页关注内存管理。 它用于组织程序的地址空间及其与物理内存的对应关系,不负责解释数据库记录或槽目录的含义:

  • 从一个例子理解。假设操作系统规定每页大小为 4 KiB,也就是 4096 字节,它会把程序看到的内存地址划分成:

    程序的内存地址空间
    
    地址     0~4095    → 第 0 页
    地址  4096~8191    → 第 1 页
    地址  8192~12287   → 第 2 页
    ……

    例如,程序访问地址 5000,就是在访问第 1 页中的某个字节。

    操作系统以这些页为单位,管理内存的映射、保护以及哪些内容需要放入 RAM。

数据库页关注数据库自身的存储结构。 前面学习的页头、空闲区、槽目录和记录区,都属于数据库页内部的组织内容。


(3)数据库页大小:顺序读取与写入粒度之间的取舍 ​

较大的数据库页有利于顺序读取,但可能对写入不利。

情形页大小带来的影响
连续读取大量数据较大的页一次可以带入更多连续数据,减少数据库页的处理次数,便于摊薄访问开销
只修改少量数据在按整页写回的模型下,较大的页意味着一次小修改可能涉及更大范围的数据写回

后续 I/O 分析的基本单位:先明确数据库页大小,再根据记录的组织方式,判断一次操作需要访问哪些页、读写多少次。


2. 搜索键、阻塞因子与页数 ​

要解决的问题:搜索键为什么不一定唯一?在不跨页的简化模型下,怎样计算每页记录数和总页数,并完成 Exercise 1?课件第 37—38 页

本节讨论三个相互衔接的问题:按哪些属性检索记录,一页能够容纳多少条记录,以及存储全部记录需要多少页。 它们分别对应搜索键、阻塞因子和文件页数,为后续分析不同文件组织的 I/O 代价提供基础。


(1)搜索键(Search Key) ​

课件将搜索键定义为检索记录所依据的属性集合。例如,在学生文件中,可以按照学号检索,也可以按照专业代码检索,还可以同时按照专业代码与班级代码检索。

“搜索键”强调的是检索依据,并不要求其取值唯一。

搜索键不一定是主键,也不一定具有唯一性;它还可以由多个属性共同组成。

搜索键示例属性性质按完整键值进行等值检索时
学号假定为主键或候选键至多匹配一条记录
专业代码非键属性可能匹配多条记录

物理文件通常围绕某个搜索键组织,以便提高相应检索的效率。

搜索键说明“按什么检索”,具体采用堆文件、顺序文件还是哈希文件,则决定记录如何存放、检索如何进行。


(2)阻塞因子(Blocking Factor) ​

阻塞因子是一页能够容纳的完整记录数。在本节的简化模型中,记录长度固定,并且一条记录不能跨越页边界,即采用非跨页存储(unspanned records)。

设:

符号含义
P每页大小,单位为字节
L每条记录的长度,单位为字节
bfr阻塞因子,单位为条/页

则:

bfr=⌊PL⌋

(3)文件页数:由记录总数和每页容量确定 ​

设文件共有 N 条记录,在各页尽量装满的模型下,所需页数为:

B=⌈Nbfr⌉

计算顺序应当是:

记录长度⟶每页记录数⟶文件页数

3. 堆文件(Heap File):链表、页目录与空闲空间 ​

要解决的问题:记录无序放置时怎样跟踪文件中的页与空闲空间?链表和页目录怎样帮助寻找插入位置?课件第 39—41 页

堆文件需要解决的基本问题是:记录不按搜索键排序时,如何管理文件中的页面,并找到可以存放新记录的位置。

上一节通过阻塞因子计算文件所需的页数。本节进一步讨论这些页如何组织,以及插入、删除后如何跟踪可用空间。课件第 39–41 页介绍了两种不同的管理方式:链表与页目录。


(1)堆文件的基本特征:记录位置由可用空间决定 ​

这里需要区分记录属于哪一页与记录位于页内何处。

在堆文件(Heap File)中,一条记录可以放入文件中任何有足够空间的位置,通常也可以追加到文件末尾。

其基本特征包括:

  • 不按搜索键确定记录位置。 堆文件本身没有依据键值排列记录的规则。
  • 记录放置后通常不再移动。 无须为了维持键值顺序而持续重排记录。
  • 页面数量可以变化。 文件增长时分配页面,缩小时可以回收不再需要的页面。

课件指出,至少要跟踪三类信息:

管理信息作用
文件包含哪些页确定属于该文件的数据页
各页有多少空闲空间帮助选择新记录的插入位置
各页包含哪些记录支持页内记录访问及增删操作

其中,页内记录的管理可以与前面学习的槽式页结构衔接;

本节重点是前两项,即文件层面的页面与空间管理。


(2)链表方式:将满页与仍有空闲空间的页分开管理 ​

笔记插图

采用一个头页(Header Page),分别指向两条数据页链表:

  • 已满页链表(Full Pages)
  • 有空闲空间的页链表(Pages with Free Space)
    • 不要求整页为空。一个页即使已经存放了多条记录,只要仍有可用空间,就可以属于这一类。
    • 插入新记录时,可以沿着有空闲空间的页链表寻找合适页面:
      1. 通过头页找到这条链表。
      2. 检查候选页是否有足够空间。
      3. 在合适的数据页中插入记录。
      4. 如果该页因此变满,调整它所属的链表,将其移到已满页链表的前端。

图中示例的数据页之间具有前向和反向链接。


(3)页目录方式:通过目录条目管理数据页 ​

页目录方式中,堆文件通过页目录(Page Directory)管理数据页,而页目录自身也由多个页面组成。

笔记插图

Header Page 是第一个目录页;整个页目录由它和后续多个目录页共同组成。

  • 左侧纵向排列的三个表格代表多个目录页。

    蓝色箭头表示目录页之间的链接:

    目录页1 → 目录页2 → 目录页3 → ……

    可以看出,页目录方式中采用链表连接的是目录页。前面另一种堆文件实现中,链表直接连接的是数据页。两者连接的对象不同,所以“页目录方式”本身仍然可以使用链表组织目录。

  • 每个目录页中包含多个条目,每个条目用于引用一个数据页

    红色箭头:从目录条目指向数据页。

    某个目录条目 → 它所管理的数据页

    例如,访问 Data Page 2 时,可以通过第一个目录页中相应目录条目取得该数据页的位置,再访问它。

  • 目录页中的目录条目,还可以包含对应数据页的空闲字节数。

    例如,目录中可以记录如下信息:

    对应数据页空闲字节数
    数据页10
    数据页280
    数据页3240

    若本次插入需要 200 字节可用空间,就可以先根据目录中的空间信息,将数据页3选为候选页,再访问该数据页完成插入。

    这种方式的作用在于:先检查集中保存的目录页中的页面摘要,再选择需要访问的数据页。 相比仅知道页面“未满”,空闲字节数提供了更具体的判断依据。

箭头连接对象用途
蓝色目录页 → 目录页组织整个目录
红色目录条目 → 数据页定位具体数据页

(4)两种方式的主要区别 ​

比较方面链表方式页目录方式
基本结构头页分别指向满页链表和有空闲空间的页链表目录条目指向各数据页
页面连接数据页直接通过链接组织起来数据页通过目录统一引用
寻找插入位置沿有空闲空间的页链表检查候选页先检查目录中的空间摘要,再访问候选数据页
页面状态变化页变满时,将其移入满页链表更新对应目录条目的空间信息
管理空间需要头页和数据页之间的链接信息需要额外的目录页及目录条目
  • 链表方式已经将满页排除在候选链之外,但遇到不同长度的记录时,仍可能需要逐个检查若干非满页。

  • 页目录则可以在比较集中的位置查看多个数据页的空间摘要,因而有机会减少为了寻找空间而直接检查数据页的次数。不过,它仍然需要访问目录,具体 I/O 次数取决于目录规模、缓存情况和查找过程,不能一概认为只需一次或两次。


4. 顺序文件:排序、溢出页与重组 ​

要解决的问题:按搜索键排序如何帮助检索?插入和删除如何使用指针链与溢出页。课件第 42—43 页

顺序文件(Sequential File)按照某个搜索键的值有序组织记录。 排序使基于该搜索键的检索更有效,但插入和删除会逐渐改变原有布局。因此,课件采用指针链与溢出页处理更新,并通过定期重组维持顺序组织的收益。

(1)排序:以搜索键的值确定记录次序 ​

顺序文件的搜索键通常是主键,但也可以是其他属性。课件中的账户文件按照支行名 branchName 排序:

笔记插图

注意:这里它把文件中的记录直接画成一张表,省略了页边界,所以看起来像是在展示一个页内部的布局。这些记录可以不在同一页中。

顺序文件的排序要求,作用于整个文件的记录序列,不只是某一页内部。

Downtown 和 Perryridge 都出现多次,说明排序搜索键不要求唯一。

有序组织使相同或相近键值的记录集中出现。例如,属于 Perryridge 的三条记录在排序次序中相邻。


(2)检索:能否利用有序性,取决于查询依据 ​

课件给出的检索原则是:

检索依据课件中的处理方式
文件的排序搜索键利用有序性进行二分查找
其他属性顺序扫描文件
  1. 如果按排序搜索键 branchName 检索,利用有序性进行二分查找:

    例如,要查找:

    branchName = 'Mianus'

    图中共有九条记录,中间的第五条记录是:

    A-102 | Perryridge | 400

    按名称顺序,Mianus 位于 Perryridge 之前。因此,如果目标存在,就应当在前半部分,可以排除后半部分,再继续缩小查找范围。

    这正是二分查找能够成立的依据:通过中间位置的键值,判断目标应位于哪一侧。

  2. 按其他属性检索,顺序扫描文件:

    例如,要查找:

    account# = 'A-218'

    文件中的账号顺序为:

    A-217、A-101、A-110、A-215、A-102、A-201、A-218……

    这些账号没有排序。即使中间记录的账号小于 A-218,也不能据此断定目标一定在后半部分。

    因此,在没有其他索引、采用表格所述模型时,需要顺序检查记录。


(3)插入:先确定有序位置,再决定实际存放位置 ​

插入新记录时,首先根据搜索键找到它应处于的次序,然后检查对应位置是否有空间。

区分两种情况:

  • 有可用空间:在该处插入记录。
  • 没有可用空间:将记录存放到溢出页(Overflow Page)中。

无论采用哪一种方式,都必须更新指针链,使记录仍能按照搜索键次序访问。

笔记插图

新增的账户记录为:

A-88 | North Town | 800

按照支行名的某种顺序:

Downtown<North Town<Mianus

因此,它应插入 Mianus 与 Downtown 之间。若该处没有空间,可以将新记录存入溢出页,并调整连接。

新记录的实际存放位置可以与原有记录分离,但指针链仍维持正确的键值次序。这样,插入时不必立即通过大规模搬移,将新记录放入原有的紧密排列位置。


另外,对于文件中记录的删除和重组,这里不展开讲述

  • 删除:通过指针链维护有效记录的连接

  • 重组:恢复有序布局的访问收益


5. 哈希文件:桶、装载率与溢出 ​

要解决的问题:哈希函数怎样将搜索键映射到桶?为什么适合等值查询,80% 占用率与溢出页如何影响空间和访问?课件第 44—46 页

哈希文件(Hash File)通过哈希函数,将搜索键值映射到记录应存放的页面。 在课件的模型中,这些页面也称为桶(bucket)。

其基本访问路径为:

搜索键值⟶哈希函数⟶目标桶

本节依次讨论桶的定位、空间预留,以及目标桶装满后的溢出处理。


(1)桶:由搜索键值确定的存放位置。 ​

哈希函数建立搜索键到地址的映射关系,使得记录的物理地址可以根据搜索键值计算得出。

哈希函数的结果指定了记录应存储在文件的哪一个页面。在这里,页面也被称为桶(bucket)。

操作基本过程
插入计算该记录的搜索键的哈希值,将记录存入对应页面中
查询对查询键值计算相同的哈希函数,到对应页面查找记录;通常只需访问一个页面即可检索到对应记录

哈希函数首先确定的是候选范围。检索是先确定对应的目标桶,到达桶后,仍需检查记录中的原搜索键值,找出真正满足条件的记录。

这是因为:

  • 多条记录可以具有相同的搜索键值,例如多个员工领取相同工资;
  • 不同搜索键值也可能得到相同的哈希结果,从而进入同一个桶。

用一个具体的哈希函数来看。假设搜索键是编号,采用:

h(k)=kmod4

即根据编号除以 4 的余数,选择四个桶之一:

目标桶分配到该桶的搜索键值
桶00、4、8
桶11、5、9
桶22、6、10
桶33、7、11

注意:这里的编号全都不同,但仍然有:

h(1)=h(5)=h(9)=1

所以,哈希函数是多对一的:不同键值可以进入同一个桶。

完整过程应理解为:

键值5→哈希桶1中的候选记录→比较原键值匹配记录

可以思考:为什么哈希文件适合针对所选哈希搜索键进行等值检索。


(2) 哈希文件组织示例 ​

假设我们要存储一个包含 10 万条记录的员工表,每页可容纳 100 条记录。因此,我们需要存储记录的理论页数为 1000 页。

为了给将来的插入留出空间,我们可以为该表分配 1250 个页面,即 1250 个桶。

  • 这样可以让页面仅占用 80% 的空间,预留了 20% 的容量。

我们希望对文件进行组织,以便高效地执行基于薪资的选择查询,即以工资为搜索键定位桶。

笔记插图

(一)查询示例:查找所有工资等于 15,500 的员工记录。 ​

采用的哈希函数是:

h(salary)=(3×salary+4)mod1250

其中,mod 表示取余运算。代入工资值 15,500:

h(15,500)=(3×15,500+4)mod1250=46,504mod1250=254

应访问 Page 254:

salary = 15,500
       │
       ▼
h(salary) = 254
       │
       ▼
    Page 254
       │
       ▼
检查记录,找出 salary = 15,500 的员工

插入工资为 15,500 的新员工记录时,也计算同一个函数,将其放入这个桶所对应的存储区域。

(二)溢出(overflow):目标桶装满后,使用关联的溢出页 ​

哈希文件不能仅凭“文件中其他页面还有空间”,就随意改变记录所属的桶。记录的定位仍需遵循哈希映射关系。

课件规定的插入过程是:

  1. 根据搜索键计算目标桶。
  2. 如果目标页有空间,在该页插入。
  3. 如果目标页已满,建立溢出页(Overflow Page),将新记录存入其中。

在图示中,Page 254 连接了一个溢出页:

h(salary) = 254
       │
       ▼
   Page 254 ──→ Overflow Page
     主桶           溢出页

溢出页使记录仍与原来的桶保持关联。查询该桶中的记录时,若存在相关溢出内容,也需要继续检查这些内容。

整体装载率为 80%,仍然可能发生局部溢出。由映射规则可以理解其原因:较多记录可能具有相同工资,或者不同工资值映射到同一个桶。这会使某个桶装满,而其他桶仍保留较多空闲空间。


6. 三种文件组织的 I/O 成本比较 ​

要解决的问题:在课件的简化假设下,如何推导扫描、等值、范围、插入和删除的成本?为什么哈希扫描出现 1.25B?课件第 47—48 页

本节以页读取和页写入的次数为统一尺度,比较堆文件、顺序文件和哈希文件的操作代价。比较对象包括全文件扫描、等值查找、范围查找,以及单条记录的插入和删除。

(1)简化分析 ​

在分析和比较不同的文件组织时,为简化起见,我们将:

  • 忽略 CPU 成本,例如在内存中的一页内比较记录。
  • 忽略预读所节省的 I/O。
  • 进行平均情况分析。
  • 每次只插入或删除一条记录。

三种文件组织还分别采用以下假设:

  • 对于堆文件:

    • 等值选择基于键进行,且只有一个匹配项,例如主键
    • 新记录总是追加到文件末端,而不去前面的页面寻找空位。(读取最后一页 → 插入记录 → 写回该页)
  • 对于顺序文件

    • 记录删除后进行紧凑化
    • 选择操作基于排序字段
  • 对于哈希文件

    • 无溢出页
    • 页面占用率为 80%

为统一理解表中的符号,记:

  • B:存放同一组记录的基准页数;
  • M:范围查询中,包含匹配记录的页数。

(2)成本总表 ​

笔记插图

这些表达式主要由三部分构成:定位目标、读取相关页面,以及修改后的写回或布局维护。

接下来逐个分析:

① 扫描全部记录:必须访问文件中的所有数据页。 ​
文件组织原因
堆文件:B读取全部 B 个页
顺序文件:B虽然记录有序,但读取全部记录仍要访问全部页
哈希文件:1.25B按 80% 占用率存放同批记录,实际需要更多页面,10.8=1.25
② 等值查找:比较如何找到一个给定键值。 ​

堆文件:0.5B。

对于堆文件,记录不按键值排序,需要逐页查找。在匹配存在且唯一的假设下,找到后即可停止。将匹配位置近似视为均匀分布,平均需要扫描约半个文件:平均代价≈B2

顺序文件:log2⁡B。

查询依据是文件的排序搜索键,可以二分查找。每次读取中间页,根据键值排除约一半候选页面,因此定位代价约为:

B2k≈1→k≈log2⁡B

这里是简化模型,若排序字段不唯一,并且需要读取跨多个页的全部匹配记录,还应计入读取这些匹配页的成本。

哈希文件:1。

根据查询键值计算目标桶。课件假定没有溢出页,因此按读取一个桶页计算。

到达页面后仍需比较原搜索键值,但这些比较属于 CPU 工作,本表不计入。

1 次页 I/O 不代表只检查一条记录,而是只读取一个页,再检查该页中的记录。

③ 范围查找:需要找出范围内的全部匹配记录。 ​

堆文件:B。

没有键值顺序,匹配记录可能散布在任何页面。为了找全结果,需要扫描整个文件。

顺序文件:log2⁡B+M。

范围查询可以分成两部分:

  1. 二分定位起点:用二分查找找到第一个可能满足条件的页,代价约 log2⁡B;
  2. 顺序扫描匹配区:从那一页开始往后一页一页读,直到键值超出范围,代价约 M 页。
log2⁡B⏟定位+M⏟读取匹配页

举例说明:假设一个学生文件,按学号(搜索键)升序排列:每页可装 40 条记录,文件总 40000 条记录,即总页数 B=1000 页

查询:学号在 [20500, 22500] 之间的学生。

  1. 对 1000 个页做二分查找,找“第一个可能 ≥ 20500 的页”

    log2⁡1000≈10

    大约读 10 页就能定位到起点所在的页,这里假设是 300 页。

  2. 顺序扫描匹配区

    匹配的记录数:学号从 20500 到 22500,共 2001 条。

    因为文件按学号排序,这些记录物理上连续存放,所以占用的页数为:

    M=⌈200140⌉=51

    从第 300 页开始往后顺序读 51 页,读到第 350 页结束。

总代价:

log2⁡1000+M=61次页读取

哈希文件:1.25B。

哈希组织不保证保留键值的大小顺序。相近键值可能分布在不同桶中,因此本表按扫描整个哈希文件计算。

④ 插入:既要找到插入位置,也要完成页面修改。 ​

堆文件:2。

这里假定记录总是追加到文件末尾,按以下过程计数:

markdown
读取最后一页:1 次 I/O
写回修改后的页:1 次 I/O

顺序文件:log2⁡B+B。

首先需要找到有序插入位置,代价约为 log2⁡B。

表中进一步假定:插入发生在文件中部,需要搬移后半个文件,以维持紧凑的有序布局。

后半个文件约有 B/2 页,每页需要读一次、写一次:

B2⏟读取+B2⏟写回=B

因此:

插入代价≈log2⁡B+B

这里的“+B”是搬移约半个文件的读写成本,不是又扫描整个文件一次。

哈希文件:2。

计算目标桶后:

markdown
读取桶页 → 插入记录 → 写回桶页

在不处理溢出的假设下,计为一次读、一次写,共 2 次 I/O。

⑤ 删除:先找到记录,再修改其所在页面 ​

堆文件:0.5B+1。

0.5B⏟找到唯一匹配记录+1⏟写回删除后的页面

找到记录时,它所在的页已经读入,所以最后只增加一次写回,不再重复计算读取该页的成本。

顺序文件:log2⁡B+B。

跟插入的方式相同

哈希文件:2。

哈希定位目标桶,读取桶页,找到记录并删除,再写回该页:

1 次读+1 次写=2

本表假定没有溢出页,因此没有加入沿溢出链查找等成本。


五、面向列的存储格式 ​

本主题回答:分析查询为何采用列式组织,文件怎样结合布局、元数据、编码与嵌套数据表示?

AdvancedColumn-Oriented Storage Formats · 课件第 53—78 页

面向列的存储格式,首先回应一种典型分析需求:查询需要处理大量记录,却只使用其中少数属性。 在这种情况下,除了考虑如何定位记录,还需要考虑如何减少无关数据的读取,以及如何提高扫描和计算效率。

1. OLTP、OLAP 与扫描优化 ​

要解决的问题:点查与频繁更新、大范围扫描与少列聚合分别需要怎样的布局?预读、延迟物化、跳过数据和向量化各在优化什么?课件第 53—54 页

首先,比较两类数据库工作负载,再列出顺序扫描的主要优化方向。

(1)OLTP:定位少量记录,并支持增量更新 ​

OLTP 是 Online Transaction Processing,联机事务处理。

  • OLTP 使用索引来查找个别元组,避免为少量目标记录进行顺序扫描。

    比如:

    sql
    SELECT balance
    FROM accounts
    WHERE account_id = 789;

    查询根据 account_id 定位目标记录,再读取余额。其主要任务是找到少量相关记录,而非扫描大量账户并进行汇总。

  • OLTP 还需要支持增量更新,即在已有数据上持续进行局部增加或修改。因此,存储结构不仅要便于定位记录,也要能够处理数据更新。


(2)OLAP:扫描大量记录,对少数列进行聚合 ​

OLAP 是 Online Analytical Processing,联机分析处理。

  • OLAP:对大段只读数据进行顺序扫描

    与只定位个别记录相比,分析查询往往需要读取许多记录,但只使用表中一小部分列进行筛选、分组和聚合。

    比如:

    sql
    SELECT region, SUM(revenue), AVG(profit)
    FROM sales
    WHERE sale_date BETWEEN '2024-01-01' AND '2024-12-31'
    GROUP BY region;

    该查询对指定日期范围内的销售记录,按地区计算收入总和与利润平均值。

  • OLAP 的关键特点,是“大范围访问记录”与“只使用少数列”同时存在。 优化目标因而不仅是找到数据,还包括减少扫描过程中搬运和处理的无关内容。


(3)列式存储的动机:减少读取无关属性的 I/O ​

在只需要少数列的分析查询中,行式存储可能将同一行内不需要的属性一起读入,从而产生无效的数据传输。

列式存储将不同列的数据分别组织,使查询能够围绕所需列读取和处理数据。

例如,上面的销售查询主要需要日期、地区、收入与利润,而不必为了取得这些值,将每条记录的所有属性都纳入当前计算。

不过,列式组织也提出了另一个要求:当操作需要完整元组时,必须将不同列块中的对应值组合起来。

总结一下,这包含两个不同环节:

  • 按列读取和计算:利用查询只需要少数属性的特点。
  • 重建元组:在需要完整记录时,组合来自不同列块的值。

(4)顺序扫描优化:分别减少数据量、等待和处理开销 ​

九项优化方向

优化方向基本作用
数据编码/压缩(Data Encoding / Compression)用更紧凑的方式表示数据,减少存储和传输的数据量
预读(Prefetching)提前读取预计即将使用的数据,使 I/O 与计算尽量重叠,减少等待
并行化(Parallelization)将扫描任务分配给多个执行单元,同时处理不同部分
聚簇/排序(Clustering / Sorting)将相关数据安排在相近位置,改善访问局部性,并为限制扫描范围提供布局基础
延迟物化(Late Materialization)推迟将不同列中的值组装为元组,直到后续操作确实需要时再完成
物化视图/结果缓存(Materialized Views / Result Caching)复用已保存的预计算结果或查询结果,减少重复扫描与计算
数据跳过(Data Skipping)利用已有信息排除不可能满足条件的数据部分,减少实际扫描量
数据并行/向量化(Data Parallelization / Vectorization)对一批数据执行相同操作,提高批量数据处理效率
代码特化/编译(Code Specialization / Compilation)针对查询生成或专门化执行代码,减少通用执行过程中的处理开销

2. NSM、DSM 与元组重建 ​

要解决的问题:按行或按列连续存储有什么局部性差异?列存怎样用固定偏移或元组 ID 将不同列重新组合为同一行?课件第 55—58 页

NSM 与 DSM 描述的是:DBMS 如何在磁盘和内存中,物理组织元组及其属性值。 二者保留相同的逻辑表结构,但连续存放的数据不同:NSM 将同一元组的属性放在一起,DSM 将同一属性在不同元组中的值放在一起。

列式组织便于扫描少数属性,同时也提出了一个要求:需要完整元组时,必须能够将不同列中的对应值重新组合起来。


(1)NSM:同一元组的属性连续存放 ​

NSM(N-ary Storage Model):把单个元组的全部或大部分属性,连续存放在同一页内。之前讨论的几乎都是基于这个模型。

设关系为 R(A,B,C),第 i 个元组为:

ti=(ai,bi,ci)

NSM 的布局可以示意为:

markdown
[a0 | b0 | c0] [a1 | b1 | c1] [a2 | b2 | c2] …
     元组0          元组1          元组2

这种布局使同一条记录的不同属性在存储位置上相邻。访问一个元组时,其相关属性集中在一起。

据此,NSM 适合以下 OLTP 访问特点:

  • 对个别元组进行点访问;
  • 频繁插入记录;
  • 频繁更新记录。

(2)DSM:同一属性的值连续存放 ​

DSM(Decomposition Storage Model):分解存储模型,是典型的纯列式组织。

对于相同的关系 R(A,B,C),其布局为:

markdwon
A列:[a0][a1][a2] …
B列:[b0][b1][b2] …
C列:[c0][c1][c2] …

与 NSM 相比,DSM 改变了数据的局部性:

模型连续存放的内容
NSM同一元组中的不同属性
DSM同一属性在不同元组中的值

如果分析查询只使用 A 列,就可以围绕 A 列的数据进行扫描,而不必为了取得 A 的值,将每条记录的 B、C 属性一并纳入处理。

DSM 非常适合 OLAP 工作负载,其中只读查询会针对表中部分属性进行大规模扫描


(3)DSM 的物理组织:列文件、值数组与附属信息 ​

DSM 的物理组织方式是:为每个属性维护一个独立的文件,并在其中设置专门的头部保存列级元数据。

其主要组成包括:

组成部分作用
属性值数组连续保存该列的值
列级元数据保存解释、管理该列所需的信息
NULL 位图标记对应条目是否为 NULL
  1. 采用定长数组存放属性值

    笔记插图

  2. 通过附属数组保存元数据和 NULL 位图

    笔记插图

    对于某一列,NULL 位图为每个元组使用 1 位。例如,第 i 位表示该列第 i 项是否为 NULL。

分列之后,元组的对应关系仍然存在:

ti=(A[i],B[i],C[i])

例如:

A列第2项:a2 ─┐
B列第2项:b2 ─┼──→ 元组2:(a2, b2, c2)
C列第2项:c2 ─┘

关键在于:确定哪些分散的列值属于同一个元组。给出两种识别方式:定长偏移与嵌入元组 ID。


(4)定长偏移:通过共同位置与简单算术定位 ​

如果同一列中的每个值都占用相同长度,就可以根据元组位置直接计算该值的位置。

设:

  • 元组序号为 i,从 0 开始;
  • 第 j 列的值数组起点为 basej;
  • 该列每个值的宽度为 wj。

则:

posj(i)=basej+iwj

读取各列中位置 i 对应的值,即可组合原元组。

这里的“定长”有一个重要限定:同一列内部的值等宽,不要求不同列之间等宽。 A 列可以使用一种宽度,B 列使用另一种宽度。

对于变长数据,这里介绍了两种定长化方法。

  • 填充(Padding)按统一宽度为值预留空间。短值用填充补齐,位置计算简单,但会浪费空间。

  • 字典压缩(Dictionary Compression)则将重复出现的变长值替换为定长编码。示例:

    笔记插图

    这里是使用 0 -> HKUST,1->CUHK,2->HKU 的编码方式。


(5)嵌入元组 ID:通过显式标识建立跨列对应关系 ​

嵌入元组 ID是,在每一列中,将属性值与其所属的元组 ID 一起保存:

markdown
A列:(ID0, a0) (ID1, a1) (ID2, a2) …
B列:(ID0, b0) (ID1, b1) (ID2, b2) …
C列:(ID0, c0) (ID1, c1) (ID2, c2) …

重建 ID2 对应的元组时,需要:

  1. 在各列中找到属于 ID2 的值;
  2. 取出 a2、b2、c2;
  3. 将它们组合为同一元组。

这需要辅助数据结构,根据给定元组 ID 找到相应值在列内的位置。

与依靠数组位置的方式相比,显式 ID 带来两项开销:

  • 每列中的值都需要附带元组 ID,增加空间占用;
  • 根据 ID 定位列值,需要额外查找。

因此,课这种方式空间开销较大、较慢、较少采用。

总结,两种方式建立对应关系的依据不同:

识别方式跨列组合的依据
定长偏移各列中共同的元组位置
嵌入元组 ID各列显式保存的相同元组标识

3. PAX:行组与列块 ​

要解决的问题:如何先按行分组,再在组内按列组织?为什么这种布局兼顾列式读取与元组数据的空间邻近性?课件第 59—60 页

PAX( Partition Attributes Across) 的基本策略是:先按行划分数据组,再在每个组内按列组织属性值。 这样既保留同列数据连续存放的特点,又使同一批元组的不同属性在存储位置上相对接近。


(1)设计动机:保留列式处理,同时改善多列访问的局部性 ​

上一节的 DSM 将不同属性分开存储,有利于扫描少数列。但很多时候,分析查询往往同时使用多个属性:

  • 某些列用于筛选,另一些列用于分组或聚合;
  • 需要重建元组时,还要组合不同列中的对应值。

因此,提出两个需要兼顾的目标:

  • 属性仍然分列组织,保留列式存储与执行的收益。
  • 同一元组的数据保持较近,保留行式存储的空间局部性优势。

PAX 并不将所有属性重新排成逐行连续的记录,而是将列式组织限定在一个局部数据范围内。


(2)组织结构 ​

A.1 行组与列块:先水平划分,再垂直划分。 ​
  • 第一步,按行水平划分,形成行组
  • 第二步,在每个行组内按列垂直划分,形成列块

笔记插图

两个单位的含义是:

单位包含的数据
行组某一批行的各个属性
列块某一行组中,一个属性的全部值
A.2 布局效果:组内保留列式连续性,组间限制数据分散范围 ​

将两个行组合起来,得到基本文件结构:

笔记插图

如果需要第一行组的 B 属性,可以访问其 B 列块;如果需要重建第 1 行,则组合该组中对应位置的 t1=(a1,b1,c1)

这些值仍然分属不同列块,但它们被限制在同一行组范围内。PAX 改善的是相关属性的空间邻近性,元组重建本身仍可能需要进行。

与前两种模型相比:

模型主要的连续存放关系
NSM同一元组的不同属性连续存放
DSM同一属性在不同元组中的值连续存放
PAX先限定一批行,再使组内同一属性的值连续存放

PAX 的“混合”体现在这两个层次:以行组聚集同一批元组,以列块组织组内各属性。

A.3 元数据:分别描述行组内容与文件中的行组位置 ​

行组元数据头(Row Group Metadata Header)属于各个行组,用于描述该组的内容。每个行组都有自己的元数据头。

全局元数据(Global Metadata)属于文件层,其目录保存文件中各个行组的偏移位置,以便定位相应行组。

markdown
全局元数据 → 定位行组
行组内布局 → 访问相应列块