第4章数据存储与组织管理ppt课件

1、第2部分 关系数据库系统实现第4章 数据存储和组织管理高级数据库系统及其运用第4章 数据存储和组织管理物理存储介质4.1磁盘空间管理4.2文件的页组织4.3页表示格式4.4记录表示格式4.5DB元信息及其组织管理4.6DB缓冲区管理4.74.1 物理存储介质4.1.1 存储介质的层次 4.1.2 磁盘的物理特性4.1.3 磁盘缺点及其处置战略 4.1.4 磁盘块存取的优化4.1.1 存储介质的层次4.1.2 磁盘的物理特性1磁盘构造硬盘容量 盘面数每盘面磁道数每磁道扇区数每扇区字节数 4.1.2 磁盘的物理特性2磁盘根本操作特性磁盘读写的最小单位是扇区。但在操作系统

2、或DBMS系统层次，磁盘读写的根本单位是磁盘块(block)。不同系统块大小能够不同，大多数系统的块取4KB。进展实践磁盘读写时，主存中必需有磁盘块缓冲区；在磁盘和主存之间传送一个磁盘块称为1次I/O操作。读写一个块的时间:寻道时间旋转延迟时间传输时间。例4.1 假设有一个含3个盘片的硬盘，共有4个记录面，转速为4500转/分钟，盘面有效记录区域的外直径为30cm，内直径为10cm，记录位密度为250位/mm，磁道密度为8道/mm，每个磁道分16扇区，每扇区512字节。试计算：1磁盘的总磁道数2非格式化容量3平均速度传输速率。 例4.2 假设一种具有如下特性的硬盘：共有4个盘片，8个盘面；每个

3、盘面有8192个磁道，每个磁道平均有256个扇区；每个扇区512个字节。试计算以下磁盘参数：1磁盘格式化容量。2假设一个块大小为4096字节，求每个磁道能存放的块数。3假设磁盘数据区外径为3.5英寸、内径为1.5英寸， 求磁盘的径向密度。4假定扇区间隙占磁道长度的10%，那么磁盘最内和最外磁道上的位密度分别是多少？ 5假设磁盘转速为3840转/分，即1/64秒转一周。磁头起落1次1毫秒，每移过500个磁道另加1毫秒，试计算读写一个块的平均时间。 4.1.3 磁盘缺点及其处置战略一、磁盘缺点分类 磁盘缺点通常有以下几种方式或类型：延续性缺点。写缺点。部分介质损坏。磁盘解体。二、校验和技术磁盘扇区

4、通常会存储一些冗余位，以可协助识别从扇区读出的内容能否正确。最简单的校验和:是基于扇区内一切位的奇偶性。经过添加奇偶位数，可降低检不出错误的概率。假设用n个位存储校验和,那么漏检错误的概率仅为1/2 n 4.1.3 磁盘缺点及其处置战略一、磁盘缺点分类二、校验和技术三、稳定存储技术校验和技术能协助检测读写缺点或介质缺点，但不能协助我们纠正错误。基于稳定存储(stable storage)的多副本战略，能够协助我们一定程度上处理这个问题。四、从解体的磁盘缺点恢复：RAID技术 磁盘冗余阵列 的磁盘组织技术。Redundant Array of Inexpensive Disks几种常用的RAID

5、级简介 1RAID0级(nonredundant striping)把数据分拆到多块磁盘并行存贮位级拆分且没有任何冗余。在一切RAID级中，RAID0具有最好的写性能，但平安性最低。2RAID1级(mirrored disks)为每一个磁盘配置一镜像磁盘，适宜于平安性要求很高场所。有效容量利用率只需50，本钱较高。几种常用的RAID级简介 3RAID2级(error-Correcting Codes错误-校正码)采用假设干数据盘拆存字节中的位(bits)，并对每个字节计算奇偶校验位，额外的校验位存储在冗余盘。对有D个数据盘的磁盘阵列中，一次读写传输最少是D个块。较有利于传输数据量大的磁盘恳求，

6、不利于传输数据量小的磁盘恳求。4. RAID3级(Bit-Interleaved Parity位-奇偶交替) RAID2中因配置了较多的冗余校验盘，能自动处理坏盘检测问题，但也增大了代价。RAID3只运用一个冗余磁盘，即采用最低的平安性开销。RAID2/3写操作都需求一个read-modify-write 的周期过程。 几种常用的RAID级简介 5RAID4级(block-Interleaved Parity块-奇偶交替) 拆存单位是一个磁盘块。块级分存优点是能充分利用块设备任务特性，且能顺应各种数据量传输的磁盘恳求。不论有多少个数据磁盘，RAID4只用一个冗余盘存储各数据盘中的奇偶校验数据。

7、6. RAID5级是RAID4的改良。RAID4中校验数据块总是用一个固定盘来存储，而在RAID5中，校验块是交替分布在各磁盘上。 RAID4磁盘读写过程读块过程：直接读出相应数据盘中的目的块即可。写块过程：除了写目的数据盘外，还要修正冗余盘上对应块数据。写单个块需求一个read- modify- write 的周期过程。 校验盘对应块新数据(当前数据盘当前块原数据 XOR 当前数据盘当前块新数据 ) XOR 校验盘对应块原数据几种常用的RAID级简介 7RAID6级(P+Q Redundancy)运用RAID6的主要动机是：在很大的磁盘阵列中，仅能恢复一个坏盘显得平安性缺乏；同时出现两个坏盘

8、，或在恢复过程中又出现坏盘的情况也必需思索。RAID6普通采用基于Hamming-Code编码的数据盘-校验盘组合方案，使得能同时恢复两个坏盘。RAID6的缺点恢复步骤4.1.4 磁盘块存取的优化在多数OS中，磁盘I/O恳求是由文件系统和虚拟内存管理器产生的。DB系统中，系统高层的页恳求经过磁盘空间管理器，也会产生基于磁盘块的I/O恳求。由于存取磁盘比存取主存要慢好几个量级，所以，DB系统改善磁盘块存取性能非常重要。 4.1.4 磁盘块存取的优化一、磁头调度技术先到先效力电梯算法例4.6 假设某磁盘的平均寻道时间、旋转等待时间和块传输时间分别为6.5、7.8和0.5毫秒。某一时辰存在着对柱面1

9、000、3000、7000的块访问恳求。初始时磁头正位于1000柱面上而且是向上挪动。此外，还有3个恳求在稍后到来。 试用电梯调度和FIFO战略调度算法，分别计算完成各块恳求效力的时间。 4.1.4 磁盘块存取的优化一、磁头调度技术先到先效力电梯算法二、采用特殊的文件组织方式按延续柱面存储数据三、采用磁盘缓冲池技术基于“传播控制层 的DB数据缓冲池技术磁盘预取技术双缓冲技术4.2 磁盘空间管理4.2.1 磁盘空间管理器 4.2.2 利用OS管理磁盘空间4.2.3 跟踪自在块 磁盘空间管理器是DBMS体系构造的最低层软件模块，隐藏了与磁盘有关的一切下层软硬件操作细节，并支持以页为单位的数据管理。

10、页(page)的大小通常就是磁盘块(block)大小，读写一个页可经过一次磁盘块I/O完成。允许高层软件以为DB数据是一系列以页为单位的磁盘数据集合。提供分配、释放和读写页的有关命令操作经过磁盘空间管理器，可将DB中的“关系映射到 “关系数据文件.这种“文件既能够是实践的OS文件，也能够只是一个虚拟的OS文件。4.3 文件的页组织4.3.1 堆文件 4.3.2 排序文件4.3.3 索引文件 本节内容安排 单个记录文件所包含的记录集， 能够存储在假设干不同的页上。 高层DBMS代码普通将“页视为包容 多个记录的对象，忽略页中详细数据 的表示方式或存储细节。 重点讨论文件中有关页的组织方式。记录独

11、一标识符rid，可被用来识别记录所属的页及记录在页内的相对位置。4.3.1 堆文件属无序文件，文件中页的大小一样。堆文件页中的记录是无序的，只能顺序存取。每个记录有独一标识rid。 堆文件管理支持创建/删除堆文件; 扫描文件; 插入/删除/检索给定rid的记录。不能直接协助定位满足指定查询条件的有关记录rids 基于双向页链表的堆文件组织 将文件页以双链表方式链接在一同。缺陷变长记录情况下，能够一切页都有空闲；检索记录能够需顺序扫描多个页 基于目录页的堆文件组织 组织构造允许有多个目录页，不同的目录页经过指针链接在一同。目录页中包含多个目录项，每个目录项标识一个页。优点：有利于更有效搜索足够包

12、容新记录的数据页。 4.3.2 排序文件文件中记录集按搜索键search key排序普通采用指针把记录按顺序链接起来。能支持按搜索键以顺序或随机方式快速获取记录，这对特定的排序查询非常有用。为减少处置排序文件时页恳求的次数，需求尽能够地按搜索键顺序来存储记录。但绝对维持记录物理上的顺序排序往往非常困难,代价非常高。更常见的做法是：删记录时仅做标志并留下空位，暂不挪动其它记录插入时，相应位置即使没有空，也暂时不挪动其它记录来腾出位置，而是引入溢出页。必要时，系统重组文件安排在相对空闲时间4.3.3 基于索引的文件组织利用辅助索引文件来协助定位数据记录。索引文件记录:索引项4.4 页表示格式4.4

13、.1 定长记录4.4.2 变长记录在处置与I/O有关主题时，通常采用页层次笼统已足够。高层DBMS软件将数据视为记录集。为提高某些特殊运用性能，系统也允许用户指定数据文件存储组织的一些选项参数。这需求进一步了解页内记录的组织方式(即页格式)。普通可将页视为槽的集合，每个槽可包容一个记录。记录可经过运用rid：来标识定位。因一切记录长度都一样，可在页内均匀、延续地安排记录槽。4.4.1 定长记录DB系统中，变长记录是很常见的：记录类型中含有一个或多个变长字段；记录中包含可反复的、数量不确定的字段；允许在一个页中存储多种记录类型。对于变长记录存储，不能将页简单地划分为均匀的槽集。必需仔细处置以下两

14、个问题：当插入一个记录时，如何能找到一个恰好能包容新记录的空间；如何跟踪记录删除后空间。 4.4.2 变长记录基于分槽式页构造表示变长记录(图4.10) 4.5 记录表示格式4.5.1 定长记录的字段表示 4.5.2 变长记录的字段表示4.5.3 跨页记录管理技术 4.5.4 巨型字段/对象管理技术4.5.5 指针记录管理技术指针混写记录首部信息 DB中记录除了存储各字段信息外， 通常还有一个记录首部记录头。记录头中存储记录层次的普通管理 信息，包括记录长度、时间戳和指向 记录方式描画的指针等。记录能否变长主要看它能否含变长字段。本节集中讨论记录中字段的表示问题。4.5 记录表示格式图4.11

15、)4.5.1 定长记录的字段表示4.5.2 变长记录的字段表示一预留空间技术二采用特殊字符结尾来实现变长字段三采用偏移数组来实现变长字段4.5.3 跨页记录管理技术跨页记录存在的缘由至少有两个：记录中存在大型或巨型字段；出于节省存储空间的需求。虽然记录大小不超越1页，但为了利用页内零头空间，也会导致跨页记录。跨页记录会被分割并分存到多个页中，故需求在各页中运用指针把它们链接在一同，构成单个记录的页链。4.5.4 巨型字段/对象管理技术一些运用能够包含非常大的巨型对象。例如，一个多媒体对象能够占用几个MB的空间；一个视频序列，能够达几个GB。在RDB中，巨型字段也称为长字段。可运用BLOB等专门

16、字段型来存储巨型对象.ODB可以直接纳理巨型对象。大多数RDB限制记录的大小不超越1页，以简化缓冲区和空闲空间的管理。对超越一个页的大对象或长字段，普通采用如下两种管理方法：用跨页记录存储技术；将它们单独存储在一些文件或文件集中。4.5.5 指针字段管理技术：指针混写1指针或地址经常是记录的一部分。当DB系统运转时，数据页允许在主存和辅存之间挪动，故指针所指向的目的页/记录，在特定时间，既能够在辅存，也能够在主存。相应地，指针或地址也就有两种方式：内存地址数据库地址，也称耐久化指针。是一种在辅存DB空间地址通常是一个逻辑地址。经过DB系统的“逻辑/物理地址映射表，可将其映射为实践磁盘物理块地址

17、。4.5.5 指针字段管理技术：指针混写2根据给定的指针或地址寻觅目的对象的过程，称为解援用(dereference)。C+内存指针援用语法：*指针名给定一个耐久化指针，解援用一个对象需求额外的步骤：须经过 “转换表 查找耐久化指针所代表对象在内存中的实践位置。如对象不在内存，那么要从磁盘读入，同时要修正转换表，并将存放该耐久指针的内存单元，直接修正为目的对象的内存位置指针。下一次同一耐久化指针再次被解援用时，就可以直接运用内存援用，从而可防止反复转换内存地址的过程开销。当对象被写回磁盘时，它所包含的任何被混写耐久化指针必需执行反混写，与内存指针解援用相比，经过转换表实现解援用仍是一个慢过程。

18、 指针混写的时机选择 自动混写；按需混写；不混写；程序控制4.6 DB元信息及其存储管理在RDB系统，除了关系，还需求维护关于整个DB的元描画数据，如关系的方式等。这类元信息称为数据字典(data dictionary)或系统目录(system catalog)。系统需存储的元信息类型有： 关系的方式关系名、每个属性名字/类型/长度。在DB上定义的视图名字和视图定义。完好性约束。授权名、认证密码等关于用户帐户的信息。当前关系实例的统计/描画数据。如每个关系中的元组总数，或各字段取值的统计直方图信息等描画信息。实践上，一切这些信息组成了一个微型数据库4.7 缓冲区管理4.7.1 DB缓冲池与缓冲区管理器 4.7.2 缓冲区置换战略4.7.3 DBMS与OS的缓冲区管理对比 DB缓冲池与缓冲区管理器DB缓冲池DBMS系统普通都拥有一个公用于处置页读写的、称为DB缓冲池的主存区。该主存区被按页大小划分为一个个页槽简称页面框,frame) 。为表达方便，有时也常简单运用可用主存、缓存、缓冲区、主存缓冲区等名词称谓DB缓冲池。缓冲区管理器指DBMS中专门担任管理DB缓冲池的软件模块。缓冲区置换战略当新页恳求发生且没有空闲缓冲页时，决议交换缓冲区哪些页的战略。缓冲区管理器呼应高层页恳求的根本过程检查缓冲池中能否存在该页，如不在，那么进一步执行以下一些操作。基于置换战略，选择一个可被置换的f