Chapter 12&13 Storage and File Structure¶

1 Physical Storage Media¶

1. 1 Classification of Physical Storage Media¶

物理存储介质通常从以下三个角度分类：

访问速度（speed）
单位数据成本（cost per unit of data）
可靠性（reliability）：断电或系统崩溃是否丢失数据、设备物理损坏是否导致数据丢失

据此，存储介质可分为：

易失性存储（volatile storage）：断电后内容丢失
非易失性存储（non-volatile storage）：断电后内容仍保留

非易失性存储

非易失性存储不仅包括二级存储和三级存储，也包括带电池保护的主存。

1. 2 Types of Physical Storage Media¶

Cache：速度最快、成本最高，易失性，硬件自动管理
Main Memory：
- 易失性，访问速度很快，典型数量级为 10 到 100 ns
- 容量相对有限，通常无法存放整个数据库，成本比磁盘高得多
Flash Memory：
- 断电后数据仍可保留
- 某位置写入一次后，必须先擦除才能再次写入
- 支持的擦写次数有限，通常为 10K 到 1M 次
- 擦除通常以整个 bank / erase block 为单位
- 读速度接近主存，但写和擦除更慢
- 典型应用于手机、相机等嵌入式设备和固态硬盘（SSD）
Magnetic Disk：
- 数据存储在旋转盘片上，以磁方式读写
- 是数据库长期存储的主要介质
- 数据访问前必须先调入主存，比主存慢得多
- 支持直接访问（direct access）
Optical Storage：
- 非易失性，利用激光从旋转盘片上读取数据
- 常见介质：CD-ROM（约 640 MB）、DVD（约 4.7 GB 到 17 GB）、Blu-ray（约 27 GB 到 54 GB）
- 可分为 WORM（write-once, read-many）型和可重写型
Tape Storage：
- 非易失性，主要用于备份和归档
- 顺序访问（sequential access），远慢于磁盘
- 容量极大，单盘带可达数百 TB
- 介质便宜，但磁带机昂贵

1. 3 Storage Hierarchy¶

层次	特点	典型介质
Primary Storage	最快，但通常易失	cache、main memory
Secondary Storage	非易失，速度中等，也称 on-line storage	flash、magnetic disk
Tertiary Storage	非易失，速度慢，也称 off-line storage	optical storage、magnetic tape

Disk Storage Interfaces

SATA：SATA 3 最高约 6 Gbit/
SAS：SAS Version 3 最高约 12 Gbit/s
NVMe：基于 PCIe，延迟更低、吞吐更高，可达约 24 Gbit/s

磁盘通常直接连接到计算机系统

存储区域网络（Storage Area Networks, SAN）：大量磁盘通过高速网络连接至多台服务器，实现集中式存储资源池化。
网络附加存储（Network Attached Storage, NAS）：通过网络文件系统协议提供文件系统接口，而非直接提供磁盘级接口，以网络共享的方式提供存储服务。

2 Magnetic Disks¶

2. 1 Basic Ideas¶

读写磁头（Read-write head）：悬浮在盘片表面极近处，用于读取或写入磁编码的数据信息。
磁道（tracks）：盘面上的同心圆，普通硬盘的单张盘片上的磁道数通常在 5 万到 10 万条之间
扇区（sectors）：磁盘可读写的最小数据单元，典型大小为 512 字节，每条内圈磁道的扇区数约 500 到 1000个，外圈磁道约 1000 到 2000 个
柱面（Cylinder）：多个盘面上半径相同的磁道集合
磁头-盘片组件（Head-disk assemblies）：同一主轴上通常安装 1 到 5 张盘片，每张盘片对应一个磁头，所有磁头安装在同一个磁盘臂上
磁盘块（disk block）：数据库系统使用的逻辑分配与传输单位

扇区的读写过程
- 磁盘臂摆动，将磁头定位到目标磁道上
- 盘片持续旋转，当目标扇区经过磁头下方时，完成数据的读取或写入
磁盘控制器（Disk Controller）：计算机系统与硬盘硬件之间的接口
- 接收读写扇区的高层指令
- 执行底层操作：控制磁盘臂移动到目标磁道，并完成数据的实际读写
- 为每个扇区计算并附加校验和（checksums），用于验证数据读取的正确性，若数据损坏，存储的校验和与重新计算的校验和几乎必然不匹配，从而能被检测到
- 通过写后读校验（写入扇区后再立即读取验证），确保写入操作成功
- 对坏扇区进行重映射（remapping）：将物理损坏的扇区地址映射到备用的健康扇区，避免数据丢失。

控制器屏蔽了大量底层机械细节，使操作系统和 DBMS 可以按块来管理磁盘。

2. 2 Performance Measures¶

访问时间（Access time）：从发出读写请求到开始传输数据所需的时间
- 寻道时间（Seek time）：磁臂移动到正确磁道所需的时间
  - 平均寻道时间约为最坏情况寻道时间的 1/2
  - 若所有磁道的扇区数相同，且忽略磁头臂启动与制动时间，理论上该值应为 1/3
  - 典型磁盘的寻道时间为 4–10 毫秒
- 旋转延迟（Rotational latency）：等待目标扇区旋转到读写头下方所需的时间
  - 平均旋转延迟为最坏情况延迟的 1/2
  - 典型磁盘（转速 5400–15000 转/分钟）的旋转延迟为 4–11 毫秒
数据传输率（Data-transfer rate）：从磁盘读取数据或向磁盘写入数据的速率
- 最大速率为 25–200 MB/秒，内侧磁道的传输速率更低
磁盘块（Disk block）：磁盘存储分配与数据读取的逻辑单元，典型大小为 4–16 KB
- 块过小：会导致磁盘读写次数增加，增加 I/O 开销
- 块过大：会因块内未填满而造成存储空间浪费（内部碎片）
顺序访问（sequential access）：连续访问相邻块，只在第一个块上需要明显寻道
随机访问（random access）：每次访问的位置都可能相距很远，寻道和旋转延迟开销显著增加
每秒 I/O 操作数（IOPS, I/O operations per second）：磁盘每秒可支持的随机块读取操作次数，是衡量随机读写性能的核心指标，当前主流机械硬盘的 IOPS 约为 50–200
平均无故障时间（MTTF, Mean Time to Failure）：磁盘预期能连续无故障运行的平均时长
- 典型硬盘理论 MTTF 可达几十万到上百万小时
- 但在大规模磁盘阵列中，任意一块盘失效的概率会显著上升

2. 3 Flash Storage and SSD¶

NAND 闪存（NAND flash）

SSD 的主流基础技术，广泛应用于数据存储场景，成本低于 NOR 闪存
按页（page）读取，典型页大小从 512B 到 4KB
页只能写一次，重写前必须擦除
擦除以擦除块（erase block）为单位，通常是 256KB 到 1MB
随机读和顺序读差距不大

固态硬盘（Solid state disks, SSD）

采用标准的面向块的磁盘接口，内部则通过多颗闪存芯片存储数据
传输速率：SATA 接口最高可达 500 MB/s，NVMe PCIe 接口最高可达 3 GB/s

由于 flash 不能原地覆盖写，因此 SSD 会维护逻辑页地址到物理页地址的重映射，避免写入时等待擦除操作完成，这种映射由闪存转换层（Flash translation layer, FTL）负责维护。

擦除块在经过 100,000–1,000,000 次擦除后会变得不可靠，无法继续使用，对应的解决方案是磨损均衡（wear leveling）。

2. 4 SSD Performance Metrics¶

SSD 常见性能指标包括：

IOPS（每秒 I/O 次数）
顺序读写带宽
并发队列深度（queue depth）下的吞吐

和机械磁盘的区别

SSD 没有磁头移动和旋转等待，因此：

随机访问性能远高于 HDD
并行读能力更强

Storage Class Memory

存储级内存（Storage Class Memory）试图兼顾接近主存的速度和非易失性的持久保存，典型例子是 Intel Optane 和 3D-XPoint。

2. 5 RAID¶

RAID（Redundant Arrays of Independent Disks）的目标

把多块磁盘组织成一个高容量逻辑磁盘
利用并行提高性能
利用冗余提高可靠性

一组 \(N\) 块磁盘中出现磁盘故障的概率，远高于单块特定磁盘发生故障的概率，因此在磁盘数量庞大的场景下，利用冗余避免数据丢失的技术至关重要。

Mirroring / Shadowing（镜像）：每块逻辑数据在两块物理盘上各存一份。
- 优点：读可从任一副本进行，一块盘坏了仍可继续工作
- 缺点：存储成本翻倍

并行的目标

负载均衡多个小请求，提升吞吐
并行处理大请求，降低响应时间

通过在多块磁盘间对数据进行条带化（striping）存储，提升传输速率。

位级条带化（Bit-level striping）：将每个字节的位拆分到多块磁盘上，但寻道/访问时间比单块磁盘更长，如今已很少使用
块级条带化（Block-level striping）：对于 \(n\) 块磁盘，文件的第 \(i\) 号数据块存储到第 \((i\mod n) + 1\)号磁盘上，对长序列数据块的请求可并行利用所有磁盘资源

常见 RAID 级别

RAID 0：块级条带化，无冗余，适用于数据丢失影响不大的高性能场景
RAID 1：带块级条带化的镜像磁盘，读写性能好但存储成本高，常用于数据库系统日志文件存储等场景
RAID 2：采用内存式纠错码（ECC, Error-Correcting-Codes）与位级条带化

奇偶校验块（Parity blocks）

第 \(j\) 号奇偶校验块存储各磁盘第 \(j\) 号数据块的按位异或（XOR）结果
当向第 \(j\) 号数据块写入数据时，必须重新计算第 \(j\) 号奇偶校验块并写入磁盘
- 可通过旧奇偶校验块、当前数据块的旧值与新值完成（2 次数据块读取 + 2 次数据块写入）
- 或使用奇偶校验块对应所有数据块的新值，重新计算奇偶校验值，该方式更适合大批量数据的顺序写入场景
- 恢复某一数据块的数据时，计算该组内所有其他数据块（含奇偶校验块）的按位异或（XOR）结果即可

RAID 3：位交叉奇偶校验
RAID 4：块交叉奇偶校验，采用块级条带化，并将对应 N 块磁盘数据块的奇偶校验块存储在单独的奇偶校验磁盘上
RAID 5：块间交叉分布式奇偶校验
- 将数据与奇偶校验分散存储在全部 N+1 块磁盘中，而非将数据存在 N 块磁盘、奇偶校验集中存在 1 块磁盘上
- 比 RAID 1 成本低，允许单盘故障恢复，但小写开销较大，因为要额外更新 parity
- 当数据块与其对应的奇偶校验块位于不同磁盘时，数据块写入操作可并行执行
RAID 6：在 RAID 5 基础上保存两份两个纠错块（P、Q）以防范多块磁盘故障，可靠性更高，但成本和写开销更大

RAID 4 vs RAID 5

RAID 4 把 parity 集中放在单独一块盘上，RAID 5 把 parity 分布到所有盘上。RAID 4 在随机写场景下，parity 盘容易成为瓶颈，RAID 5 分布式 parity 更均衡。

选择 RAID 时需要综合考虑成本、正常运行时性能（IOPS 和带宽）、故障时性能、重建时性能和可靠性，经验上：

RAID 0：只在数据可轻易恢复、容错不重要时使用
RAID 1：写多、低延迟要求高的场景更合适
RAID 5：适合顺序大写、容量需求大的场景
RAID 6：适合大容量、对可靠性要求更高的场景

RAID 可分为软件 RAID 和硬件 RAID，需要注意的工程问题有：

课件特别提醒的工程问题有：

写入中途断电可能导致镜像或 parity 不一致，恢复供电时必须检测这类损坏的数据
潜在故障（latent failure）：历史数据已损坏但尚未被发现
数据清洗（data scrubbing）：周期性扫描和修复潜伏故障
热插拔（hot swapping）：不停机换盘，部分硬件 RAID 系统支持，可大幅缩短恢复时间，显著提升系统可用性
许多系统会配置备用磁盘，保持在线状态，故障后自动接替
许多硬件 RAID 系统通过带电池备份的冗余电源或多控制器与多互连链路确保单点故障不会导致系统整体停机

2. 6 Optimization of Disk-Block Access¶

缓冲（Buffering）：通过主存中的 buffer 缓存磁盘块，减少磁盘 I/O
预读（Read-ahead）：在预测后续还会访问相邻块时，提前把额外块一起读入，适合顺序扫描和连续文件访问
磁盘臂调度（Disk-arm-scheduling）：磁盘调度会重排请求顺序以减少磁臂移动，典型算法为电梯算法（elevator algorithm）

文件组织（File organization）：文件在磁盘上的块分配应尽量连续，以扩展区（extent）为单位进行分配，否则可能会产生碎片化（fragmentation），导致顺序访问时磁头移动增多、吞吐下降，部分系统提供文件系统碎片整理（defragment）工具以提升文件访问速度
非易失性写缓冲区（Non-volatile write buffers）

3 File Organization¶

数据库通常存储为一组文件，每个文件（file）是一组记录（record）的序列，而一条记录又是一组字段（field）的序列。

3. 1 Fixed-Length Records¶

记录 \(i\) 从字节 \(n * (i - 1)\) 开始存储，其中 \(n\) 为单条记录的大小。

该实现方式定位简单，但记录可能跨块，可以改进为不允许记录跨块。

Record Deletion Strategies

方案一：将第 \(i+1\) 到第 \(n\) 条记录向前移动，覆盖第 \(i\) 到第 \(n-1\) 条记录的位置

方案二：将最后一条记录移动到第 \(i\) 条记录的位置

方案三：不移动记录，而是将所有空闲记录通过空闲链表（free lists）串联起来，在文件头保存第一个已删除记录的位置，已删除记录内部复用部分空间保存下一个空闲记录地址，这样可以高效重用删除后腾出的空间。

3. 2 Variable-Length Records¶

变长记录产生的典型原因

同一文件中存多种记录类型
某些字段本身是变长，如 varchar
存在可重复字段

记录内部按属性顺序保存
对变长字段保存固定大小的 (offset, length)
实际数据放在记录尾部或单独区域，空值通过空值位图（null-value bitmap）表示

槽式页（slotted page）是数据库管理变长记录的经典结构，槽式页头（Slotted page header）通常包含记录项个数 #Entries、空闲空间末尾位置和每条记录的位置与大小。

页内记录可以移动并重新整理，移动后只需更新页头中的槽项，外部指针不直接指向记录，而应指向页头中该记录对应的条目，这样即使记录在页内搬动，逻辑引用仍然稳定。

对 BLOB / CLOB 等大对象，记录本身通常不能直接整页容纳，常见方案有：

以文件形式存储在文件系统中
以数据库管理的文件形式存储
切成多个片段，保存在单独关系中，如 PostgreSQL TOAST 技术

4 Organization of Records in Files¶

4. 1 Heap File Organization¶

记录可以放在文件中任意有空间的位置，插入方便，一般记录一旦分配后不再移动，关键问题是如何高效找到可用空闲空间。

空闲空间映射（Free-space map）

为每个数据块设置一个表项，组成数组。每个表项占用几比特到 1 字节，记录该数据块的空闲空间占比，便于快速定位能插入新记录的块。

下方示例中，每个数据块用 3 比特表示，数值除以 8 即为该块的空闲占比：

可设置二级空闲空间映射，下方示例中，每个二级表项存储一级映射中 4 个表项的最大值：

空闲空间映射会定期写入磁盘，部分表项存在过时（错误）值是可接受的（后续会被检测并修正）

4. 2 Sequential File Organization¶

记录按某个搜索键（search-key）顺序存储，适合全文件顺序处理和基于该搜索键的范围扫描。

删除：使用指针链（pointer chain）
插入：先定位待插入位置，若有空闲则直接插入，若无空闲则将记录插入溢出块（overflow block），两种情况都需要更新指针链

除此之外，还需要定期对文件进行重组，以恢复记录的顺序存储结构。

Hashing

对某个属性计算 hash 值，根据结果决定记录放在哪个块中，适合：基于哈希键的精确匹配查询。

4. 3 Multitable Clustering File Organization¶

这种聚簇方式将同一部门的部门信息与教师记录物理上相邻存储，可减少关联查询时的磁盘 I/O 次数，但只查单独 department 时反而可能不理想，且会产生可变长度的记录，可以添加指针链，将同一关系的记录关联起来。

4. 4 Partitioning¶

表分区是把一个关系按某种规则拆成多个较小关系分别存储，例如 transaction 可以按年份分区为 transaction_2018、transaction_2019 等。

优点：某些查询只需访问一部分分区，便于归档和管理
缺点：若查询不带分区过滤条件，可能仍要访问全部分区

5 Data-Dictionary Storage¶

数据字典（Data Dictionary）也称为系统目录（System Catalog），用于存储元数据（metadata），即关于数据的数据。

元数据典型内容

关于关系（表）的信息
- 关系的名称
- 每个关系的属性名、数据类型与长度
- 视图的名称与定义
- 完整性约束
用户与账户信息，包括密码
统计与描述性数据
- 每个关系中的元组数量
物理文件组织信息
- 关系的存储方式（顺序/哈希/……）
- 关系的物理存储位置
关于索引的信息

数据字典既可以在磁盘上按关系形式保存，也可以在内存中使用专门的数据结构以提升访问效率。

6 Storage Access and Buffer Manager¶

数据库文件会被划分为固定长度的块（blocks），块既是存储分配的单位，也是数据传输的单位。

数据库系统的核心目标之一是尽量减少磁盘和主存之间的块传输次数，我们可以通过在主内存中尽可能多地保留块副本，来减少磁盘访问次数。

缓冲区（Buffer）：主内存中用于存储磁盘块副本的区域
缓冲区管理器（Buffer manager）：负责在主内存中分配缓冲区空间的子系统

Buffer Manager 的处理流程

若块已在 buffer 中，直接返回主存地址
若不在：分配 buffer 空间，必要时替换其他块，若被替换块已修改，则先写回磁盘，再把所需块读入

大多数操作系统采用最近最少使用（LRU, Least Recently Used）策略，即替换掉最久未被访问的块。

示例：4 pages, 3 buffers

数据库查询常有很强的访问模式，例如顺序扫描和嵌套循环连接，在这类模式下，单纯的 LRU 可能很差，因为它并不理解查询后续还会访问哪些块。

其他缓冲区替换策略

固定块（Pinned block）：不允许被写回磁盘的内存块
立即丢弃（Toss-immediate）策略：块最后一个元组处理完后立即释放
最近最常使用（MRU）策略：对某些重复顺序扫描模式可能比 LRU 更合适

DBMS 往往更了解访问模式，因此可以比通用操作系统做出更有针对性的替换决策。

7 Columnar Representation and Main-Memory Databases¶

传统关系存储通常是 row-oriented，即同一行的所有属性值连续存放，而列存储表示（Columnar Representation）则把同一列的数据聚集存放。

优点：
- 只访问部分属性时可显著减少 I/O
- CPU cache 利用率更好
- 更适合压缩
- 有利于向量化处理（Vector processing）
缺点：
- 元组重建成本高
- 删除和更新复杂
- 可能有解压缩开销

列存储在决策支持类场景中，比行存储更高效，传统行存储更适合事务处理（OLTP）场景，部分数据库同时支持两种存储方式，称为行/列混合存储（hybrid row/column stores）。

典型列存文件格式有 ORC 和 Parquet，这些格式在大数据分析中非常常见。

ORC 文件格式示意图

主存数据库（ Main-Memory Databases）不再需要传统意义上的缓冲区管理器，记录可直接常驻内存，列式存储在分析型场景中依然很有效，压缩技术可以降低内存占用。