5.1 数据库物理存储

基本内容
- 基础回顾-计算机系统的存储体系
- 磁盘的结构与特性
- DBMS数据存储与查询实现的基本思想
- 数据库之表和记录与磁盘块的映射
- 数据库之文件组织方法?
重点与难点
- 理解利用磁盘组织大规模数据的基本思维
- 初步了解数据存储与查询实现的基本思想
- 理解三种文件组织方法及其特性：堆文件、顺序文件和散列文件
- 理解数据库重组的概念和作用

5.1.1 基础回顾-计算机系统的存储体系

数据库的存储与检索问题
- 如何高效率的存储？—— 数据组织与索引
- 如何快速的检索？—— 查询实现与查询优化
存储体系
- 数据组织的基础 —— 存储体系
- 将不同性价比的存储器组织在一起，满足高速度、大容量、低价格需求
- CPU与内存直接交换信息，按存储单元(存储字)进行访问
- 外存按存储块进行访问，其信息需先装入内存，才能被CPU处理
操作系统如何管理磁盘和数据
- 操作系统对数据的组织：FAT-目录(文件夹)-磁盘块/簇
- FAT(文件分配表-File Allocation Table)
操作系统对内存-缓冲区的管理

内存管理
- 一条记录的地址=存储单元的地址=内存地址=页面：页内偏移量
- 页面(Page) = 块(Block)
- 内存页面的分配
- 内存页面的置换

5.1.2 磁盘的结构与特性

磁盘及磁盘的容量

盘面: 磁道: 扇区
- 磁盘读写单位：Sector $\rightarrow$ 簇Cluster/块Block:连续的若干个扇区
- -
- 示例：
  
  一个磁盘的基本信息
  
  8个圆盘，16个盘面，每个盘面有 $2^{16}$ 或 65536 个磁道
  
  每个磁道(平均)有 $2^8=256$ 个扇区，每个扇区有 $2^{12}=4096$ 个字节
  
  $\Rightarrow$ 磁盘的容量 = $2^4*2^{16}*2^8*2^{12}=240$ 字节
磁盘数据的访问
- 磁盘数据读写时间
  - 寻道时间(约在1-20ms)
  - 旋转时间(约0-10ms)
  - 传输时间(每4KB页<1ms)
- 物理存取算法考虑的关键:
  - 降低I/O次数
  - 降低排队等待时间
  - 降低寻道/旋转延迟时间：
    - 同一磁道连续块存储；
    - 同一柱面不同磁道并行块存储；
    - 多个磁盘并行块存储
提高磁盘数据读写时间与存储可靠性的方法
- RAID技术: Redundant Array of Independent Disk
  - 并行处理:并行读取多个磁盘
  - 可靠性:奇偶校验与纠错
- 方法
  - 块级拆分但无冗余
  - 镜像处理：每一个磁盘有一个镜像磁盘C
  - 位交叉纠错处理：4个磁盘存储4位+3个校验盘P存储3校验位
  - 位交叉校验：4个磁盘存储4位+1个校验盘存储1校验位，位拆分存储(借助于扇区读写校验判断出错磁盘，再依据校验盘进行纠错)
  - 块交叉校验：块拆分存储，其他同。
  - 块交叉分布式校验：块拆分存储，互为校验盘
  - 更为复杂的冗余处理(略)

5.1.3 DBMS数据存储与查询实现的基本思想

数据存储的映射关系示意
数据存储与查询实现的基本框架示意

5.1.4 数据库之表-记录与磁盘块的映射

数据库记录在磁盘上的存储
- 定长记录，还是变长记录(靠分隔符区分开始与结束)
- 记录是非跨块存储，还是跨块存储(靠指针连接)
**数据库-表所占磁盘块的分配方法 **
- 连续分配: 数据块被分配到连续的磁盘块上(会存在扩展困难问题)
- 链接分配: 数据块中包含指向下一数据块的指针(访问速度问题)
- 按簇分配: 按簇分配，簇是若干连续的磁盘块，簇之间靠指针连接; 簇有时也称片段Segment或盘区extent
- 索引分配: 索引块中存放指向实际数据块的指针

5.1.5 数据库之文件组织方法

数据组织与存取方法

数据组织要考虑更新(增、删、改)和检索需求
- 更新将涉及数据存储空间的扩展与回收问题
- 检索将涉及扫描整个数据库的问题、大批量处理数据问题
- 不同的需求要求不同的数据组织方法和存取方法
- 文件组织(File Organization) 指的是数据组织成记录、块和访问结构的方式，包括把记录和块存储在磁盘上的方式，以及记录和块之间相互联系的方法
- 存取方法(Access Method) 指的是对文件所采取的存取操作方法
- 一种文件组织可以采取多种存取方法进行访问
文件组织方法之一 — 无序文件组织

文件组织方法之一：无序记录文件(堆文件heap或pile file)
- 特点：
  
  记录可存储于任意有空间的位置，磁盘上存储的记录是无序的。更新效率高，但检索效率可能低
- 方法1：新记录总插入到文件尾部；删除记录时，可以直接删除该记录所在位置的内容，也可以在该记录前标记“删除标记”
- 方法2：在前者基础上，新增记录可以利用那些标记为“删除标记”的记录空间
- 频繁删增记录时会造成空间浪费，所以需要周期性重新组织数据库
  
  数据库重组(Reorganization) 是通过移走被删除的记录使有效记录连续存放，从而回收那些由删除记录而产生的未利用空间。
文件组织方法之二 — 有序文件组织

文件组织方法之二：有序记录文件(排序文件Sequential)
- 特点：
  
  记录按某属性或属性组值的顺序插入，磁盘上存储的记录是有序的。检索效率可能高。
- 用于存储排序的属性通常称为排序字段(Orderingfield)，通常，排序字段使用关系中的主码，所以又称排序码(Orderingkey)
- 当按排序字段进行检索时，速度得到很大提高；但当按非排序字段检索时，速度可能不会提高很多
- 有序记录文件的更新效率可能很低
  
  因为：在更新时要移动其他记录，为插入记录留出空间
- 改进
  - 改进措施是可为将来有可能插入的元组预留空间(这可能造成空间浪费), 或者再使用一个临时的无序文件(被称为溢出文件)保留新增的记录。
  - 当采取溢出文件措施时，检索操作既要操作主文件，又要操作溢出文件。
  - 所以需要周期性重新组织数据库
  - 数据库重组是将溢出文件合并到主文件中，并恢复主文件中的记录顺序
文件组织方法之三 — 散列文件组织

文件组织方法之三：散列文件(Hash file)
- 特点：可以把记录按某属性或属性组的值,依据一个散列函数来计算其应存放的位置：桶号(Bucket,块号或簇号等)。检索效率和更新效率都有一定程度的提高
- 用于进行散列函数计算的属性通常称为 散列字段(Hashfield)，散列字段通常也采用关系中的主码，所以又称散列码(hashkey)
- 不同记录可能被hash成同一桶号，此时需在桶内顺序检索出某一记录
  - 链接法处理溢出
  - 散列还有许多问题及许多的处理技巧,如散列桶的数目以及桶的大小，动态散列技术等等(这里不再叙述)
文件组织方法之四 — 聚簇文件组织

文件组织方法之四：聚簇文件(Clustering file)
- 聚簇：将具有相同或相似属性值的记录存放于连续的磁盘簇块中
- 多表聚簇：将若干个相互关联的Table存储于一个文件中—这可提高多表情况下的查询速度(有很多问题及相关的处理技巧，不再详细叙述)
小结