存储和文件结构

约 4407 个字 预计阅读时间 29 分钟

引言

数据库系统需要将数据存储在非易失性设备上（通常是磁盘），并能够高效地访问和管理这些数据。本章介绍存储媒体、文件组织和记录管理的基本概念，这些是构建高效数据库系统的基础。通过理解存储结构和访问方法，我们可以优化数据库性能并确保数据的可靠性。

物理存储媒体

• 存储媒体概述

  ---

  数据库系统使用多种类型的存储媒体，每种具有不同的特性：

  • 存取速度：不同媒体访问数据的速度差异很大
  • 每单位数据成本：从昂贵的高速缓存到廉价的磁带存储
  • 可靠性：面对掉电或系统崩溃时的数据丢失风险
  • 容量：从几GB到数PB不等的存储能力

存储层次结构

存储媒体可以按照其速度、成本和易失性组织成层次结构：

1. 高速缓存：最快和最昂贵的存储形式；易失性；由计算机系统硬件管理

2. 主存（内存）：

   • 快速访问（10-100纳秒）
   • 通常太小或太昂贵，无法存储整个数据库
   • 容量通常为几GB到几TB
   • 易失性——断电或系统崩溃时内容通常丢失

3. 闪存：

   • 数据在断电后仍然存在
   • 数据只能在一个位置写入一次，但位置可以被擦除后重写
   • 支持有限数量（10K-1M）的写入/擦除周期
   • 读取速度接近主存，但写入较慢

4. 磁盘：

   • 数据存储在旋转磁盘上，通过磁头读写
   • 长期存储数据的主要媒介
   • 支持直接访问（不像磁带需要顺序访问）
   • 容量可达15TB（2019年数据）
   • 能够在断电和系统崩溃时保存数据
   • 磁盘故障可能导致数据丢失，但较罕见

5. 光存储：

   • 非易失性，数据通过激光从旋转光盘上读取
   • CD-ROM（640MB）和DVD（4.7-17GB）是最常见形式
   • 蓝光光盘：27-54GB
   • 一次写入多次读取（WORM）光盘用于归档存储

6. 磁带存储：

   • 非易失性，主要用于备份和归档数据
   • 顺序访问——比磁盘慢得多
   • 非常高的容量（每盘可达300TB）

存储类别

按访问特性和用途可将存储分为三类：

• 主存储：最快但易失性（缓存、主存）
• 次级存储：中等访问速度，非易失性（闪存、磁盘）
  • 也称为在线存储
• 三级存储：最慢访问速度，非易失性（磁带、光存储）
  • 也称为离线存储

磁盘存储

磁盘是数据库系统中最重要的存储媒体，了解其结构和性能特性对于优化数据库性能至关重要。

磁盘结构

磁盘基本结构

• 盘片：磁盘由一个或多个盘片组成
• 磁道：每个盘片表面分为同心圆磁道（典型硬盘有50K-100K个磁道）
• 扇区：每个磁道被划分为扇区（最小的可读写单位，通常为512字节）
• 读写头：位于盘片表面附近，读取或写入磁编码信息
• 柱面：所有盘片上相同位置的磁道集合

磁盘性能参数

磁盘的关键性能参数包括：

1. 访问时间：从发出读/写请求到数据传输开始的时间，包括：

   • 寻道时间：将磁臂移动到正确磁道所需的时间（典型值：4-10毫秒）
   • 旋转延迟：等待所需扇区出现在读写头下的时间（典型值：4-11毫秒）

2. 数据传输率：数据从磁盘存储或检索的速率

   • 25-200MB/秒，内部磁道速率较低

3. 磁盘块：存储分配和检索的逻辑单位

   • 通常为4-16KB
   • 小块：需要更多传输
   • 大块：部分填充的块会浪费更多空间

4. 随机访问性能：

   • 每秒I/O操作数（IOPS）：磁盘每秒支持的随机块读取数
   • 当前磁盘通常为50-200 IOPS

5. 平均故障时间（MTTF）：

   • 磁盘预期连续运行而不出现故障的平均时间
   • 通常为3-5年

闪存存储

闪存技术在数据库存储中越来越重要，特别是SSD（固态硬盘）。

闪存特性

• NAND闪存：广泛用于存储，比NOR闪存便宜

  • 需要页面读取（页大小：512字节至4KB）
  • 页面读取时间：20-100微秒
  • 页面只能写入一次，必须先擦除才能重写

• 固态硬盘（SSD）：

  • 内部使用多个闪存存储设备
  • 传输率高达500MB/秒（SATA）或3GB/秒（NVMe PCIe）
  • 擦除以块为单位（256KB-1MB），时间为2-5毫秒
  • 随机读取性能：典型的4KB读取可达10,000 IOPS
  • 随机写入性能：典型的4KB写入可达40,000 IOPS
  • 并行读取可大幅提高性能

非易失性内存技术

• 3D-XPoint内存：英特尔开创的技术

• Intel Optane：

  • SSD接口（2017年推出）
  • 比闪存SSD具有更低的延迟
  • 非易失性内存接口（2018年宣布）
  • 支持以接近主存速度直接访问字

冗余磁盘阵列（RAID）

• RAID概念

  ---

  RAID（独立磁盘冗余阵列）是一种磁盘组织技术，管理大量磁盘，提供单个磁盘的视图：

  • 通过并行使用多个磁盘提供高容量和高速度
  • 通过冗余存储数据以提高可靠性，即使在磁盘故障时也能恢复数据
  • 降低大型磁盘系统中数据丢失的风险

镜像与条带化

RAID系统使用两种基本技术：

1. 镜像（Mirroring）：

   • 复制每个磁盘，形成镜像对
   • 每次写入都在两个磁盘上进行
   • 读取可以从任一磁盘进行
   • 只有当一个磁盘和其镜像在系统修复前都失败时才会丢失数据

2. 条带化（Striping）：

   • 将数据分散到多个磁盘以提高并行性
   • 位级条带化：将每个字节的位分布在多个磁盘上（现在较少使用）
   • 块级条带化：文件的块i存储在磁盘(i mod n)+1上

RAID级别

不同的RAID级别具有不同的成本、性能和可靠性特性：

RAID 0RAID 1RAID 5RAID 6

• 块条带化；无冗余
• 用于对数据丢失不敏感的高性能应用

• 带块条带化的镜像磁盘
• 提供最佳写入性能
• 用于数据库系统中的日志文件存储等应用

• 块交错分布式奇偶校验
• 将数据和奇偶校验分布在所有N+1个磁盘上
• 块写入可以并行进行（如果块及其奇偶校验块位于不同磁盘上）

• P+Q冗余方案；类似于Level 5，但存储两个错误校正块
• 比Level 5具有更好的可靠性，但成本更高
• 随着存储规模增加变得越来越重要

RAID选择考量

选择RAID级别时需要考虑的因素：

• 金钱成本
• 正常运行时的性能：每秒I/O操作数和带宽
• 故障期间的性能
• 故障磁盘重建期间的性能

一般来说：

• RAID 1为写密集型应用提供更好的性能
• RAID 5适用于顺序写入大量数据的应用
• RAID 6随着容量增大变得更加重要

RAID实现与高级特性

1. 软件RAID：完全在软件中实现，无特殊硬件支持

2. 硬件RAID：具有特殊硬件支持的实现

   • 使用非易失性RAM记录正在执行的写入
   • 断电可能导致磁盘损坏，需要检测和恢复

3. 高级故障管理特性：

   • 数据擦洗：持续扫描潜在故障并从副本/奇偶校验恢复
   • 热插拔：在系统运行时更换磁盘，无需断电
   • 备用磁盘：保持在线，在检测到故障时立即用作替代

磁盘性能优化

提高磁盘性能的主要技术包括：

1. 缓冲：使用内存缓冲区缓存磁盘块
2. 预读：预期将很快请求额外的块

3. 磁盘臂调度算法：重新排序块请求以最小化磁盘臂移动

   • 电梯算法

   • 文件组织：尽可能连续地分配文件的块

   • 以范围（extents）为单位分配

   • 文件可能会碎片化
   • 一些系统提供碎片整理工具
   • 非易失性写入缓冲区：减少延迟并批处理写入

文件组织与记录组织

• 文件组织基础

  ---

  数据库存储为文件集合，每个文件是记录序列，每个记录是字段序列：

  • 固定长度记录比变长记录更容易实现
  • 每个文件通常只包含一种特定类型的记录
  • 不同的关系存储在不同的文件中
  • 通常假设记录比磁盘块小

固定长度记录

记录可以使用以下方式组织：

1. 简单方法：

   • 从字节n·(i-1)开始存储记录i，其中n是每个记录的大小
   • 记录访问简单，但记录可能跨越块边界
   • 修改：不允许记录跨越块边界

2. 记录删除：

   • 选项1：将记录i+1,...,n移动到i,...,n-1
   • 选项2：将记录n移动到i
   • 选项3：不移动记录，而是将所有空闲记录链接到空闲链表上

变长记录

变长记录在数据库系统中出现在几种情况下：

1. 在文件中存储多种记录类型
2. 允许一个或多个字段（如字符串）变长的记录类型
3. 允许重复字段的记录类型

槽页面结构

变长记录通常使用槽页面头部来组织：

• 包含记录条目数
• 页面中空闲空间的结束位置
• 每个记录的位置和大小

记录可以在页面内移动以保持它们连续且中间没有空隙；必须更新头部中的条目。

指针不应直接指向记录，而应指向头部中记录的条目。

非常大的对象

对于非常大的对象（如BLOB/CLOB类型）：

• 记录必须小于页面

• 存储选项：

• 作为文件系统中的文件

• 作为数据库管理的文件
• 分解为多个元组并存储在单独的关系中（如PostgreSQL TOAST）

文件组织方式

• 文件组织类型

  ---

  常见的文件组织类型包括：

  • 堆文件：记录可以放置在文件中任何有空间的位置
  • 顺序文件：基于每个记录的搜索键值按顺序存储记录
  • 哈希文件：根据某些属性计算哈希函数以决定记录存储位置
  • 多表聚簇文件：不同关系的记录存储在同一文件中
  • B+树文件组织：有序存储

堆文件组织

堆文件的特点：

• 记录可以放置在文件中任何有空闲空间的地方
• 记录分配后通常不会移动
• 需要高效查找文件内的空闲空间

• 使用空闲空间映射（free-space map）

• 每块一个条目的数组

• 每个条目几位到一个字节，记录块空闲部分的比例
• 可以有第二级空闲空间映射

顺序文件组织

顺序文件组织适用于需要顺序处理整个文件的应用程序：

• 文件中的记录按搜索键排序
• 删除：使用指针链

• 插入：定位记录应插入的位置

• 如果有空闲空间，则在那里插入

• 如果没有空闲空间，则将记录插入溢出块
• 在任何情况下，都必须更新指针链
• 需要不时重组文件以恢复顺序

多表聚簇文件组织

使用多表聚簇文件组织可以将多个关系存储在一个文件中：

department                  instructor
dept_name building budget   ID  name  salary  dept_name

multitable clustering of department and instructor
dept_name building budget   ID  name  salary

优缺点： - 对于涉及department和instructor的查询很好 - 对于仅涉及department的查询较差 - 导致可变大小记录 - 可以添加指针链来链接特定关系的记录

表分区

表分区允许将关系中的记录分区为较小的关系，并单独存储：

• 例如，transaction关系可以分为transaction_2018、transaction_2019等
• 除非查询有类似year=2019的选择条件，否则针对transaction的查询必须访问所有分区的记录

分区的好处：

• 降低某些操作（如空闲空间管理）的成本
• 允许不同分区存储在不同存储设备上
• 例如，当前年份的transaction分区存储在SSD上，而较早年份存储在磁盘上

数据字典存储

• 数据字典内容

  ---

  数据字典（也称为系统目录）存储元数据（关于数据的数据），例如：

  • 关系信息（关系名称、属性名称/类型/长度等）
  • 视图的名称和定义
  • 完整性约束
  • 用户和账户信息（包括密码）
  • 统计和描述性数据（如每个关系中的元组数）
  • 物理文件组织信息
  • 索引信息

系统元数据表示

数据字典通常使用两种方式存储：

1. 关系表示：磁盘上的关系表示
2. 内存数据结构：为高效访问而设计的专用内存数据结构

存储访问与缓冲管理

缓冲管理

• 缓冲管理基础

  ---

  缓冲管理是在磁盘和内存之间高效移动数据的关键：

  • 缓冲区：可用于存储磁盘块副本的主内存部分
  • 缓冲管理器：负责分配主内存中缓冲区空间的子系统
  • 数据库系统旨在最小化磁盘和内存之间的块传输次数
  • 通过在主内存中保留尽可能多的块可以减少磁盘访问

缓冲管理器工作流程

当程序需要磁盘上的块时：

1. 如果块已在缓冲区中，缓冲管理器返回块在主内存中的地址

2. 如果块不在缓冲区中，缓冲管理器：

3. 在缓冲区中为块分配空间

   • 如有必要，替换（淘汰）某个其他块来为新块腾出空间
   • 如果被替换的块自最近一次写入/从磁盘获取以来被修改，则只将其写回磁盘
4. 将块从磁盘读入缓冲区，并将块在主内存中的地址返回给请求者

缓冲替换策略

1. 最近最少使用（LRU）策略：

   • 多数操作系统替换最近最少使用的块
   • LRU的思想是将过去的块引用模式作为未来引用的预测器
   • 对于某些涉及重复扫描数据的访问模式，LRU可能是一种糟糕的策略

2. 数据库特定策略：

   • 查询有明确定义的访问模式
   • 数据库系统可以使用用户查询中的信息来预测未来的引用
   • 带有查询优化器提供的替换策略提示的混合策略通常更可取

3. 其他策略：

   • 固定块：不允许写回磁盘的内存块
   • 立即丢弃策略：处理完块的最后一个元组后立即释放块占用的空间
   • 最近最多使用（MRU）策略：系统必须固定当前正在处理的块；处理完块的最后一个元组后，块被解除固定，成为最近最多使用的块

列式存储组织

• 列式存储特性

  ---

  列式存储将表按列而非按行存储：

  • 优点：

    • 如果只访问某些属性，可减少I/O
    • 改善CPU缓存性能
    • 改善压缩效率
    • 利用现代CPU架构上的向量处理

  • 缺点：

    • 从列式表示重构元组的成本
    • 元组删除和更新的成本
    • 解压缩的成本

  对于决策支持，列式表示比面向行的表示更高效；对于事务处理，传统的面向行的表示更可取。

列文件格式

• ORC和Parquet：文件内部采用列式存储的文件格式
• 在大数据应用中非常流行
• ORC文件格式包含多个条带，每个条带包含索引和列数据

内存数据库

• 可以直接在内存中存储记录，无需缓冲管理器
• 决策支持应用程序可以在内存中使用面向列的存储
• 压缩减少内存需求

总结

存储和文件结构是数据库系统的基础组件，它们直接影响系统的性能、可靠性和可用性：

1. 物理存储媒体提供了从高速易失性内存到慢速持久性磁带的多层次存储选项
2. RAID技术通过镜像和条带化提高了存储系统的可靠性和性能
3. 文件组织方式（如堆、顺序、哈希等）适应不同的访问模式和应用需求
4. 记录组织处理固定长度和变长记录的存储和管理
5. 缓冲管理通过智能缓存策略优化内存和磁盘之间的数据传输
6. 列式存储为分析性工作负载提供了更高效的数据组织方式

好的存储和文件结构设计目标是：

• 最小化I/O操作数量
• 高效利用存储空间
• 在不牺牲整体系统性能的情况下确保数据的可靠性和持久性

pdf资料