ch13 数据存储管理

物理存储介质分类

• 数据访问速度
• 每单位数据成本
• 可靠性
• 按存储信息 易失性存储/非易失性存储

1.高速缓冲存储器Cache

最快最贵易失 硬件管理

2.主存储器

• 快速访问
• 一般太小（太贵）难以储存整个数据库
• 易失

3.快闪存储器

• 非易失
• 数据写入一次不能直接覆盖只能擦除和重写
• 读取速度和主存一样快
• 写入慢一些 擦除更慢

主要使用的是NAND快闪存储器，比NOR更便宜，一次读取一个页面（4KB），擦除有寿命。

4.磁盘

• 数据存储在旋转的盘片上，靠磁的作用读写
• 长期储存的主要介质，通常是整个数据库
• 为了访问数据必须将数据从磁盘迁移到主存，修改后的数据需要写回磁盘
• 直接访问——可以随机读取磁盘上的数据，不必像磁带那样
• 容量很大
• 电源故障系统崩溃不丢数据（非易失）

磁盘控制器

作为计算机系统和磁盘驱动器之间的接口，接受高层次的读写操作。

磁盘性能的度量

访问时间：从发出读写请求到数据开始传输之间的时间，包括寻道时间和旋转等待时间。

数据传输率：从磁盘获得数据或向磁盘存储数据的速率

平均故障时间：预计磁盘连续无故障运行的平均时间，3~5年。随着工作时间增长而下降

磁盘块访问

块：包含固定数目的连续扇区

• 数据在磁盘和主存之间交换以块为单位
• 块的大小不能太大不能太小

5.光学存储器

• 非易失
• CD-ROM和DVD是常见的形式
• 有的能写一次读多次，也有多种可写的光盘
• 外设

6.磁带存储器

• 非易失，主要用于备份
• 顺序访问
• 大容量
• 外设

存储层次

基本存储： 访问快 易失（Cache，主存）

辅助存储： 非易失 访问较快 也叫联机存储（闪存，磁盘）

第三级存储： 非易失 访问速度慢 也叫脱机存储（磁带，光学存储器）

数据存储结构

• 持久性数据储存在非易失性存储器中，通常是磁盘或者是固态硬盘
• 大多数的数据库采用操作系统文件作为存储记录的中间层，抽象底层块的细节
• 为了保证有效访问和故障恢复，数据库系统也必须了解块

文件组织

• 数据库被映射到多个不同文件
• 一个文件逻辑组织成为记录的一个序列
• 一个记录事多个字段的序列
• 每个记录被完全包含在单个块中

定长记录

一种简单的实现方式

• 从字节$n\ast (i-1)$开始记录储存记录$i$，$n$是每个记录的长度。
• 访问记录很容易，但是记录可能分布在不同的块上。

删除记录$i$的三种方法

• 移动记录$i+1,...,n$到$i,...n-1$
• 移动记录$n$到$i$
• 不移动记录，但是链接所用的空闲记录到一个$freelist$

空闲列表

• 将第一个被删除的记录地址储存在文件的头部
• 在第一个被删除记录空间中储存第二个被删除记录的地址，以此类推
• 可以将这些储存的地址想象为“指针”，指向下一条空闲记录
• 更多的有效空间表示：重用空闲记录的属性域存储指针（而未被删除的记录不用储存指针）

变长记录

• 可变长度的记录
• 属性按照顺序存放：先是定长属性，然后是可变长度属性
• （偏移量，长度）对
• Null属性使用空值位图来表示
• 多个记录储存在同一个块中，使用分槽的页结构

分槽的页结构

分槽页页头

• 记录条目个数
• 块中空闲空间的末尾处
• 一条包含每条记录位置和大小的条目组成的数组 可以将记录在一页内移动，保证记录之间没有空的空间，则数组中信息也要更新

大对象存储

blob/clob类型

• 在数据库中存储：访问效率低，备份占用大量空间
• 在文件系统中存储，数据库内存储其绝对路径：删除没有约束容易产生不一致，无法授权

文件中记录的组织

堆文件组织

• 只要有足够的空间，一个记录可以放在文件的任何地方

顺序文件组织

• 记录根据搜索码的值顺序存储

哈希文件组织

• 在每条记录的某些属性上计算一个哈希函数，哈希函数的结果确定了记录应该放到哪一个文件中

每个关系的记录可被储存在一个单独的文件中

• 在多表聚簇文件组织中一个文件可以存储多个不同的关系的记录
• 动机：将像相关记录储存在同一个块上可以减少I/O

堆文件组织

• 记录可以放在对应于一个关系的文件的任何位置
• 记录放好后通常不会移动
• 使用自由空间图高效的找到具有自由空间的块，就比如下边这个数组意味着每个块上对应的自由空间比例

$$\boxed{\text{4}}\boxed{\text{2}}\boxed{\text{1}}\boxed{\text{4}}\boxed{\text{7}}\boxed{\text{3}}\boxed{\text{6}}\boxed{\text{5}}\boxed{\text{1}}\boxed{\text{2}}$$

• 这东西可以分层，逐层访问
• 自由空间图可能会过时

顺序文件组织

• 适用于对需要对整个文件进行顺序处理的应用程序
• 记录在搜索码上排序
• 在记录的末端放一个指针，删除时使用指针链删除，插入时找到记录被插入的位置，如果有空间可以直接插入，没空间可以分配一个溢出块，通过指针指向溢出块中插入的位置
• 需要时对文件进行重组以保持顺序

多表聚簇文件组织

• 一个文件可以存储多个关系，类似分类分组
• 有利于处理包含类似$department\bowtie instructor$这种条件的查询，有利于查询每个$department$里有哪些$instructor$,但不利于只查询$department$有关信息和比较某些$instructor$的$salary$
• 导致记录长度是可变的
• 可以用指针将其中$department$元组连接在一起

划分

表划分：将关系记录分成更小的关系，分别存储

划分的作用：有利于减少查找自由空间的开销，不同分区可以不放在同一介质上（旧数据可以放在磁盘里，新数据常用放在SSD里）

数据字典存储

数据字典：也成为系统目录，存储元数据，也就是关于数据的数据

• 关系有关信息：名字、每个关系的属性名字类型与长度、视图的名字和视图的定义、完整性约束
• 用户账号密码
• 统计和描述的数据：每个关系的元组总数
• 文件的组织信息：关系存储组织、储存位置
• 索引

系统元数据的关系表示

• 磁盘上的关系表示
• 专门的数据结构设计，用于在主存中高效存取

数据库缓冲区

• 数据库系统尽量减少磁盘和内存之间的数据块传输数量。可以在储存中保留尽可能多的块来减少磁盘的访问次数。

缓冲区：部分主存用于存储磁盘中块的副本

缓冲区管理器：负责在主存中分配缓冲区空间的子系统

• 当程序需要从磁盘中得到一个块的时候，调用缓冲区管理器（类似Cache的策略）

缓冲区替换策略

LRU策略：最近最少使用的块替换掉，对于某些特定访问模式不是一个好策略

• 用过去的块访问策略来预测未来的访问
• 查询已经是定义良好的访问模式
• 混合策略效果更好

被钉住的块：不允许写回磁盘的块

立即丢弃策略：一旦一个块的最后一个元组处理完毕就让缓冲区管理器释放这个块所占用的空间

MRU策略：最近最常使用策略，系统必须把当前正在处理的块钉住，然后再块中最后一个元组处理结束以后这个块就不再被钉住，成为最近最常使用的块（替换时替换最近最常使用的块）

• 缓冲区管理器管理器可以使用一个请求将访问某个特定的关系的概率统计信息
• 缓冲区管理器也支持块的强制写出以支持数据库恢复

面向列的存储

• 柱状存储，按照列存储

优势：减少I/O，提高CPU缓存性能，提高压缩效率，向量处理（并行处理）

不足：元组重构的代价，元组删除和更新的代价，解压的代价

• 面向列的存储对决策支持更有效
• 传统的面向行的存储更适合事务处理
• 混合的行列存储两种方式都支持（把几列存在一起）
• 主要分为ORC和Parquet两种实现方式

主存数据库的存储组织

• 全部数据放入内存，相应速度非常快，效率高
• 有个很重要的问题就是持久化问题（易失）
• 在内存中可以面向行，直接分配对于记录的地址，不允许记录移动；也可以面向列，类似ORC的实现方式，分为多个物理数组，用间接表存储指针指向物理数组