存储管理

1. 存储介质

参考存储系统

• 按CPU访问存储介质的方式分类
  • 主存储器
    • 包括寄存器、高速缓存、内存
    • 按字节寻址
  • 二级存储器
    • 磁盘/机械硬盘（HDD）
    • 闪存/固态硬盘（SSD）
    • 按块寻址
    • 联机使用
  • 三级存储器
    • 磁带、光盘、网络存储
    • 脱机使用
• 按存储介质的易失性分类
  • 易失性存储器
    • 主存储器
  • 非易失性存储器
    • 二级存储器、三级存储器
  • 持久性内存（非易失性内存，NVM）

磁盘

• 组成
  • 磁盘构件
    • 扇区(sector)、磁道(track)、柱面(cylinder)
  • 磁头构件
    • 磁头(disk head)、磁臂(disk arm)

• 磁盘块（页）
  • 操作系统在格式化磁盘时将磁盘划分为许多大小相同的块
  • 磁盘块（页）的大小是扇区的整数倍
  • 通常是512B-16KB
  • 一旦设置，不可以动态改变
• 磁盘控制器
  • 寻道、旋转、传输、预取

固态硬盘（SSD）

• 使用NAND闪存作为存储介质
• 特点
  • 随机读写速度高于磁盘、功耗低于磁盘
  • 先擦除，后写入
  • 写放大、寿命低

2. 面向磁盘的数据库存储

• 设计目标
  • 如何存储
  • 何时读写

文件存储

• 将每一个数据库存储为一个或多个文件
• 每个文件包含多个页
  • 数据库文件的页中可以存储元组、元数据、索引、日志记录等
  • 每个页拥有唯一的编号：页号

面向行的存储

（1）元组的表示

• 元组表示为字节序列
  • 元组头
    • 记录元组的元数据，包括元组的长度、最后修改的时间、可见性等等
  • 元组数据
    • 由元组的所有属性值拼接而成

（2）页布局

页头

• 记录页的元数据
  • 页的大小
  • 页的校验和
  • DBMS的版本
  • 页的可见性（与并发控制相关）
  • 页中数据的数据压缩方法

页数据

• a. 面向元组的组织方法
  • 分槽页
    • 槽
      • 每个元组占一个槽
      • 槽从后向前布置在页的末尾
      • 每个槽的起始位置的偏移量是4字节或8字节的倍数
    • 槽数组
      • 放置在页头后
      • 槽数组的第i个非空元素存储第i个槽的起始位置的偏移量
    • 
  • 记录号
    • DBMS为一个关系中的每个元组分配唯一的记录号
      • 使用（页号，槽号）作为记录号
      • 或者使用唯一的整数作为记录号
  • 溢出页
  • 页碎片化
    • 随着元组删除或版本过期，页中会产生碎片，需要定期回收空间
• b. 日志结构的组织方法
  • 文件中只存储数据更新操作的日志记录，而不存储元组
  • 
  • 读元组
    • 从后向前扫描文件中的日志记录
    • “重建”元组的最新属性值
  • 索引
    • 为了加快读元组的速度，可以在多个连续的页上建立索引

（3）文件组织

• a. 堆文件组织
  • 堆文件中的元组以任意顺序存储
  • 组织方法
    • 基于链表的组织方法
      • 数据页：存储元组，所有数据页组织成链表
      • 空闲页：所有空闲页组织成链表
      • 头页：存储在文件的起始位置，记录堆文件的元数据、指向数据页链表头的指针、指向空闲页链表头的指针
      • 
    • 基于页目录的组织方法
      • 数据页：存储元组
      • 页目录：记录每个数据页的位置和空闲空间信息
      • 
• b. 顺序/有序文件组织
  • 元组按排序键的顺序存储（一般按照主键排序）
• c. 哈希文件组织
  • DBMS使用一个哈希函数
  • DBMS根据元组键的哈希值来确定元组存储在哈希文件的哪个页

面向列的存储

• 将关系的每个属性单独存储

3. 缓冲区管理

CPU无法直接读/写磁盘中的数据，必须先将文件中的页从磁盘读入内存（缓冲区）；
数据库文件的大小经常超过DBMS的可用内存容量；

• 缓冲区管理器负责在磁盘和内存之间复制文件页

（1）缓冲池

• DBMS将可用内存区域划分为也数组，称缓冲池
• 缓冲池的页称作页框(frame)
• 

（2）缓冲池的设计

• 页表（page table）
  • 记录缓冲池中当前有哪些页以及这些页在内存中的地址
  • 将页号映射为所在页框的地址
  • 可使用哈希表实现
  • 
• 页框的元数据
  • DBMS用两个变量记录缓冲池中每个页框的状态
    • $pin\_count$：页框中的页当前被请求但未被释放的次数，即引用次数
    • $dirty$：自从页框中的页被读入缓冲池后，该页是否被修改过

（3）缓冲区管理器的功能

• a. 请求页
  • 情况1
    • 搜索页表，检查缓冲池中是否存在被请求的页P
    • 如果P在缓冲池中，则$pin\_count+1$，并返回包含P的页框的地址
    • 
  • 情况2
    • 页P不在缓冲池中
      • 选替换页：使用页替换策略，从缓冲池中选择一个$pin\_count=0$的页框，将该页框的$pin\_count+1$
      • 写回脏页：如果该页框的$dirty$值为真，则将页框中的页写回磁盘
      • 读请求页：将请求的页P读入该页框，返回该页框的地址
    • 
    • 
  • 情况3
    • 如果缓冲池中没有$pin\_count=0$的页框，则请求开始等待，直至DBMS释放了缓冲池中的页面
    • 实际上，DBMS会终止提出该请求的事务，并重新执行它
    • 
• b. 释放页
  • 将包含该页的页框的$pin\_count-1$
• c. 修改页
  • 将被修改的页所在的页框的$dirty$值置为真

（4）页替换策略

• 最近最少使用策略（LRU）
  • 运行时协议
    • 用一个时间戳记录缓冲池中每个页框的最后访问时间
    • 为了提高效率，可将缓冲池中$pin\_count=0$的页框按时间戳排序
  • 页替换协议
    • 替换$pin\_count=0$且时间戳最旧的页框中的页
• 时钟替换策略（Clock）
  • 运行时协议
    • 将缓冲池中所有页框组织成一个环形缓冲区（表盘）
    • 为每个页框设置一个引用位
    • 初始时，将所有页框的所有引用位都置为0
    • 当一个页被读入一个页框时，将该页框的引用位置为1
    • 当一个页框中的页被访问时，将该页框的引用位置为1
  • 页替换协议
    • 用一根旋转的表针搜索首个$pin\_count=0$且引用位为0的页框，替换该页框中的页
    • 如果表针扫过页框的引用位为1，则将其引用位置为0
• 先进先出策略（FIFO）
• 最近最多使用策略（MRU）