数据存储与组织管理ppt课件.ppt

《数据存储与组织管理ppt课件.ppt》由会员分享，可在线阅读，更多相关《数据存储与组织管理ppt课件.ppt（40页珍藏版）》请在金锄头文库上搜索。

1、LOGO 第第2 2部分部分 关系数据库系统实现关系数据库系统实现 第第4 4章章 数据存储和组织管理数据存储和组织管理 高级数据库系统及其应用 第4章 数据存储和组织管理 物理存储介质4 1 磁盘空间管理4 2 文件的页组织4 3 页表示格式4 4 记录表示格式4 5 DB元信息及其组织管理4 6 DB缓冲区管理4 7 2 4 1 物理存储介质 4 1 1 存储介质的层次 4 1 2 磁盘的物理特性 4 1 3 磁盘故障及其处理策略 4 1 4 磁盘块存取的优化 3 4 1 1 存储介质的层次 4 4 1 2 磁盘的物理特性 1 磁盘结构 硬盘容量 盘面数 每盘面磁道数 每磁道扇区数 每扇区

2、字节数 5 4 1 2 磁盘的物理特性 2 磁盘基本操作特性 v磁盘读写的最小单位是扇区 但在操作系统或 DBMS系统层次 磁盘读写的基本单位是磁盘块 block 不同系统块大小可能不同 大多数系统的块取 4KB v进行实际磁盘读写时 主存中必须有磁盘块缓冲 区 在磁盘和主存之间传送一个磁盘块称为1次 I O操作 v读写一个块的时间 寻道时间 旋转延迟时间 传输时间 6 例4 1 假设有一个含3个盘片的硬盘 共有4个 记录面 转速为4500转 分钟 盘面有效 记录区域的外直径为30cm 内直径为 10cm 记录位密度为250位 mm 磁道 密度为8道 mm 每个磁道分16扇区 每 扇区512字

3、节 试计算 1 磁盘的总磁道数 2 非格式化容量 3 平均速度传输速率 7 例4 2 假设一种具有如下特性的硬盘 共有4个 盘片 8个盘面 每个盘面有8192个磁道 每个磁道平均有256个扇区 每个扇区512 个字节 试计算以下磁盘参数 l 1 磁盘格式化容量 l 2 若一个块大小为4096字节 求每个磁道能存放的块数 l 3 如果磁盘数据区外径为3 5英寸 内径为1 5英寸 求磁 盘的径向密度 l 4 假定扇区间隙占磁道长度的10 则磁盘最内和最外磁 道上的位密度分别是多少 l 5 若磁盘转速为3840转 分 即1 64秒转一周 磁头起 落1次1毫秒 每移过500个磁道另加1毫秒 试计算读写

4、一 个块的平均时间 8 4 1 3 磁盘故障及其处理策略 一 磁盘故障分类 磁盘故障通常有以下几种方式或类型 间断性故障 写故障 部分介质损坏 磁盘崩溃 二 校验和技术 磁盘扇区通常会存储一些冗余位 以可帮助识 别从扇区读出的内容是否正确 最简单的校验和 是基于扇区内所有位的奇偶性 通过增加奇偶位数 可降低检不出错误的概率 若用n个位存储校验和 则漏检错误的概率仅为1 2 n 9 4 1 3 磁盘故障及其处理策略 一 磁盘故障分类 二 校验和技术 三 稳定存储技术 校验和技术能帮助检测读写故障或介质故障 但不能帮助我们纠正错误 基于稳定存储 stable storage 的多副本策略 可能帮助

5、我们一定程度上解决这个问题 四 从崩溃的磁盘故障恢复 RAID技术 磁盘冗余阵列 的磁盘组织技术 Redundant Array of Inexpensive Disks 10 几种常用的RAID级简介 1 RAID0级 nonredundant striping 把数据分拆到多块磁盘并行存贮 位级拆分且 没有任何冗余 在所有RAID级中 RAID0具有最好的写性能 但安全性最低 2 RAID1级 mirrored disks 为每一个磁盘配置一镜像磁盘 适合于安全性 要求很高场合 有效容量利用率只有50 成 本较高 11 几种常用的RAID级简介 3 RAID2级 error Correct

6、ing Codes错误 校正码 采用若干数据盘拆存字节中的位 bits 并对每个字节 计算奇偶校验位 额外的校验位存储在冗余盘 对有D个数据盘的磁盘阵列中 一次读写传输最少是D 个块 较有利于传输数据量大的磁盘请求 不利于传 输数据量小的磁盘请求 4 RAID3级 Bit Interleaved Parity位 奇偶交替 RAID2中因配置了较多的冗余校验盘 能自动解决坏 盘检测问题 但也增大了代价 RAID3只使用一个冗 余磁盘 即采用最低的安全性开销 RAID2 3写操作都需要一个read modify write 的周期 过程 12 几种常用的RAID级简介 5 RAID4级 block

7、 Interleaved Parity块 奇偶交替 拆存单位是一个磁盘块 块级分存优点是能充分利用块 设备工作特性 且能适应各种数据量传输的磁盘请求 不论有多少个数据磁盘 RAID4只用一个冗余盘存储各 数据盘中的奇偶校验数据 6 RAID5级 是RAID4的改进 RAID4中校验数据块总是用 一个固定盘来存储 而在RAID5中 校验块是 交替分布在各磁盘上 RAID4磁盘读写过程 读块过程 直接读出相应数据盘中的目标块即可 写块过程 除了写目标数据盘外 还要修改冗余盘上对 应块数据 写单个块需要一个read modify write 的 周期过程 校验盘对应块新数据 当前数据盘当前块原数据

8、XOR 当前数据盘当前块新数据 XOR 校验盘对应块原数据 13 几种常用的RAID级简介 7 RAID6级 P Q Redundancy 使用RAID6的主要动机是 在很大的磁盘阵列中 仅能 恢复一个坏盘显得安全性不足 同时出现两个坏盘 或 在恢复过程中又出现坏盘的情况也必须考虑 RAID6一般采用基于Hamming Code编码的数据盘 校 验盘组合方案 使得能同时恢复两个坏盘 RAID6的故障恢复步骤 14 4 1 4 磁盘块存取的优化 v在多数OS中 磁盘I O请求是由文件系统 和虚拟内存管理器产生的 vDB系统中 系统高层的页请求通过磁盘空 间管理器 也会产生基于磁盘块的I O请 求

9、 v由于存取磁盘比存取主存要慢好几个量级 所以 DB系统改善磁盘块存取性能非常 重要 15 4 1 4 磁盘块存取的优化 一 磁头调度技术 先到先服务 电梯算法 例4 6 假设某磁盘的平均寻道时间 旋转等待 时间和块传输时间分别为6 5 7 8和0 5 毫秒 某一时刻存在着对柱面1000 3000 7000的块访问请求 初始时磁头 正位于1000柱面上而且是向上移动 此外 还有3个请求在稍后到来 试用电梯调度和FIFO策略调度算法 分 别计算完成各块请求服务的时间 16 4 1 4 磁盘块存取的优化 一 磁头调度技术 先到先服务 电梯算法 二 采用特殊的文件组织方式 按连续柱面存储数据 三 采

10、用磁盘缓冲池技术 基于 传播控制层 的DB数据缓冲池技术 磁盘预取技术 双缓冲技术 17 4 2 磁盘空间管理 4 2 1 磁盘空间管理器 4 2 2 利用OS管理磁盘空间 4 2 3 跟踪自由块 18 磁盘空间管理器 v是DBMS体系结构的最低层软件模块 隐 藏了与磁盘有关的所有下层软硬件操作细 节 并支持以 页 为单位的数据管理 页 page 的大小通常就是磁盘块 block 大小 读写一个页可通过一次磁盘块I O完成 允许高层软件认为DB数据是一系列以页为单 位的磁盘数据集合 提供分配 释放和读写页的有关命令操作 v通过磁盘空间管理器 可将DB中的 关系 映射 到 关系数据文件 这种 文

11、件 既可能是实际的OS文件 也可能 只是一个虚拟的OS文件 19 4 3 文件的页组织 4 3 1 堆文件 4 3 2 排序文件 4 3 3 索引文件 本节本节 内容内容 安排安排 u 单个记录文件所包含的记录集 可能存储在若干不同的页上 u 高层DBMS代码一般将 页 视为容纳 多个记录的对象 忽略页中具体数据 的表示方式或存储细节 u 重点讨论文件中有关页的组织方式 记录唯一标识符rid 可被用来识别记录所属的页及记录在页内的相对位置 20 4 3 1 堆文件 v属无序文件 文件中页的大小相同 v堆文件页中的记录是无序的 只能顺序存取 每 个记录有唯一标识rid v堆文件管理支持 创建 删

12、除堆文件 扫描文件 插入 删除 检索给定rid的记录 不能直接帮助定位满足指定查询条件的有关记录rids 21 基于双向页链表的堆文件组织 v将文件页以双链表 方式链接在一起 v缺点 变长记录情况 下 可能所有 页都有空闲 检索记录可能 需顺序扫描多 个页 22 基于目录页的堆文件组织 v 组织结构 允许有多个目录页 不同的目录页通 过指针链接在一起 目录页中包含多个 目录项 每个目录 项标识一个页 v 优点 有利于更有效搜索 足够容纳新记录的 数据页 23 4 3 2 排序文件 v文件中记录集按搜索键 search key 排序 一般采用指针把记录按顺序链接起来 能支持按搜索键以顺序或随机方

13、式快速获取记 录 这对特定的排序查询非常有用 v为减少处理排序文件时页请求的次数 需要尽可 能地按搜索键顺序来存储记录 但绝对维持记录物理上的顺序排序往往非常困 难 代价非常高 更常见的做法是 删记录时仅做标记并留下空位 暂不移动其它记录 插入时 相应位置即使没有空 也暂时不移动其它 记录来腾出位置 而是引入溢出页 必要时 系统重组文件 安排在相对空闲时间 24 4 3 3 基于索引的文件组织 v 利用辅助索引文件来帮助定位数据记录 索引文件记录 索引项 25 4 4 页表示格式 4 4 1 定长记录 4 4 2 变长记录 v 在处理与I O有关主题时 通常采用页层次抽象已足够 v 高层DBM

14、S软件将数据视为记录集 为提高某些特殊应用 性能 系统也允许用户指定数据文件存储组织的一些选项 参数 这需要进一步了解页内记录的组织方式 即页格式 v 一般可将页视为槽的集合 每个槽可容纳一个记录 记录可通过使用rid 来标识定位 26 v因所有记录长度都相同 可在页内均匀 连续地安排记录槽 4 4 1 定长记录 27 vDB系统中 变长记录是很常见的 记录类型中含有一个或多个变长字段 记录中包含可重复的 数量不确定的字段 允许在一个页中存储多种记录类型 v对于变长记录存储 不能将页简单地划分为均匀 的槽集 必须仔细处理以下两个问题 当插入一个记录时 如何能找到一个恰好能容 纳新记录的空间 如

15、何跟踪记录删除后空间 4 4 2 变长记录 28 基于分槽式页结构表示变长记录 图4 10 29 4 5 记录表示格式 4 5 1 定长记录的字段表示 4 5 2 变长记录的字段表示 4 5 3 跨页记录管理技术 4 5 4 巨型字段 对象管理技术 4 5 5 指针记录管理技术 指针混写 记录记录 首部首部 信息信息 u DB中记录除了存储各字段信息外 通常还有一个记录首部 记录头 u记录头中存储记录层次的一般管理 信息 包括记录长度 时间戳和指向 记录模式描述的指针等 u记录是否变长主要看它是否含变长字段 u本节集中讨论记录中字段的表示问题 30 4 5 记录表示格式 图4 11 4 5 1

16、 定长记录的字段表示 4 5 2 变长记录的字段表示 一 预留空间技术 二 采用特殊字符结尾来实现变长字段 三 采用偏移数组来实现变长字段 31 4 5 3 跨页记录管理技术 v 跨页记录存在的原因至少有两个 记录中存在大型或巨型字段 出于节省存储空间的需要 虽然记录大小不超过1页 但为了利用页内零头空间 也会导致跨页记录 v 跨页记录会被分割并分存到多个页中 故需要在各页中使 用指针把它们链接在一起 形成单个记录的页链 32 4 5 4 巨型字段 对象管理技术 v一些应用可能包含非常大的巨型对象 例如 一个多媒体对象可能占用几个MB的空间 一个视频序列 可能达几个GB 在RDB中 巨型字段也称为长字段 可使用 BLOB等专门字段型来存储巨型对象 ODB可以直接管理巨型对象 v大多数RDB限制记录的大小不超过1页 以简化 缓冲区和空闲空间的管理 对超过一个页的大对 象或长字段 一般采用如下两种管理方法 用跨页记录存储技术 将它们单独存储在一些文件或文件集中 33 4 5 5 指针字段管理技术 指针混写 1 v指针或地址经常是记录的一部分 v当DB系统运行时 数据页允许在主存和辅存之间