数据库系统实现_02.ppt

1、第二章数据存储,1.存储器层次 2.磁盘 3.第二级存储器的有效使用 4.改善第二级存储器访问时间的策略 5.磁盘故障 6.磁盘恢复,1.存储器层次,高速缓冲存储器 主存储器 第二级存储器(辅存,联机存储) 第三级存储器(脱机存储) 易失和非易失存储器 在各级之间要解决的问题: 1.速度瓶颈 2.容量瓶颈 如主存与辅存之间通过缓冲区:,第三级存储器,第二级存储器(辅存),主存储器,高速缓冲存储器,价格及速度,容量,主存 缓冲区,辅存,2.磁盘,磁盘结构 磁盘控制器 磁盘存储特性 磁盘访问特性 块的写入 块的修改,磁盘结构 1.磁盘组合: 2.磁头组合:又分为移动磁头和固定磁头(高速访问,造价高

2、) 3.磁道: 4.柱面:为讨论提高数据访问速度 5.扇区: 从磁盘读出和写入信息的最小单位,也是磁盘错误的最小单位. 块是OS或DBMS与磁盘进行交换信息的逻辑单位,一般是扇区的整数倍,磁盘控制器 1.结构图: 总线 2.功能: 1)定位磁道(或柱面) 2)选盘面,并选扇区 3)读数据传送到主存(计算效验和数据并与读出的效验和数据比较), 或从主存写数据到所选扇区(包括效验和数据),处理器,主存,磁盘控制器,磁盘存储特性 1.磁盘组合的旋转速度 2.每单元盘片数 3.每面磁道数 4.每个磁道字节数 例:Megatron747有下列特性: 1.4个盘片,8个盘面 2.每个盘面有213个磁道(8

3、192个磁道) 3.每个磁道平均有28个扇区(256个) 4.每个扇区有29个字节(512个) 则磁盘容量如下: 23 * 213 * 28 * 29=231(8GB),磁盘访问特性 1.存取时间(access time): 从发出读写请求到数据开始传输之间的时间 2.寻道时间(seek time),平均寻道时间(average seek time) 寻道时间 : 磁头重定位的时间(230ms) 平均寻道时间 : 410ms 3.旋转等待时间(rotational latency time),平均旋转等待时间 旋转等待时间:磁盘转动到被存取的扇区出现在磁头下所用时间 平均旋转等待时间: 4.数

4、据传输率(data-transfer rate):从磁盘获取数据或者向磁盘存储数据 的速率(25M40M/S) 5.平均故障时间(mean time to failure,MTTF):预期系统无故障连续运行 的平均时间,块的写入与读出: 1)磁头定位(磁道) 2)扇区定位 3)读或写,块的修改 1.过程: 1)将块读入主存 2)对主存中块的副本进行所要求的修改 3)将主存中块的内容写回到磁盘 4)如果需要,检查写操作(对效验和进行检查) 2.所需时间: 1)读的时间 2)在主存中更新的时间 3)写的时间 4)进行效验和判定的时间,磁盘数据组织与DBMS(或文件)数据组织的关系 物理概念 逻辑概

5、念,磁盘组合,磁盘片,盘面,磁道,扇区,字节,关系 (包括数据字典,索引),块,记录,字段,柱面,3.第二级存储器的有效使用,1.计算的I/O模型 2.第二级存储器中的数据排序 3.归并排序 4.两阶段多路归并排序 5.扩展多路归并排序更大的关系,1.计算的I/O模型: 在DBMS中,所有数据不在主存中,数据访问(或处理)的开销,CPU与I/O速度差,导致在考虑相关算法时,只在乎磁盘块访问(读和写)次数或所需时间,而CPU处理时间忽略不计. 目标:为完成某项任务,所实现的算法中,存储器中的块有最少的I/O次 数,2.第二级存储器中的数据排序(也包括第二级/第三级) 讨论:一个表的排序问题,透视

6、如何考虑以I/O开销为主的排序算法 1)小表(=DBMS(主存) 例:表=107行,每行定长=100字节,DBMS(主存)=50M, 磁盘块=4K(4096字节),每块=40行,表=250000块 DBMS(主存)=12800块 1)归并排序(书page31图2-10,算法见书page32) 2)一阶段两路归并排序 表大小= DBMS(主存) 3)多阶段两路归并排序(淘汰赛)(I/O次数较多) 阶段1:排序主存大小的数据片段 阶段n:对阶段n-1所排序的数据片段进行两两归并排序 4)两阶段多路归并排序 阶段1:排序主存大小的数据片段 阶段2:对阶段1所排序的数据片段的块进行多路归并排序 5)多

7、阶段多路归并排序,模拟实现两阶段多路归并排序(DBMS对大表某字段排序时,所采用) 要求: 1)建立模拟所需的数据结构 2)实现两阶段多路归并排序的算法 3)测试或演示排序过程 4)显示排序时间(时间开销),4.改善第二级存储器访问时间的策略,1.按柱面组织数据: 将可能一起被访问的块放在同一柱面上,可以减少访问时间 问题:如何界定一起访问,预留空间多大等 2.使用多磁盘: 数据存储在几个独立的磁盘上,而不是集中在一个较大的磁盘上 数据库的存储策略也是如此:数据,索引,日志等最好是分布在独立的 几个磁盘上 3.磁盘镜像(mirror): 通过磁盘冗余,提高访问速度,同是也提高数据可靠性 4.磁盘调度的电梯算法: 通过在OS,或在DBMS,或在磁盘控制器中采用有效的算法(如电梯算 法) 5.预取和大规模缓冲: 预取将要使用的块到主存中,尽可能地增加缓冲区的大小. 6.各种策略及其优缺点(略):(见书page43),5.磁盘故障,1.间断性故