数据库系统实现_02.ppt

《数据库系统实现_02.ppt》由会员分享，可在线阅读，更多相关《数据库系统实现_02.ppt（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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.每个盘面有2

3、13个磁道(8192个磁道)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)

5、进行效验和判定的时间磁盘数据组织与DBMS(或文件)数据组织的关系 物理概念 逻辑概念磁盘组合磁盘片盘面磁道扇区字节关系(包括数据字典,索引)块记录字段柱面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:对

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