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

LOGO第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）磁盘基本操作特性磁盘读写的最小单位是扇区。但在操作系统或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个盘面；每个盘面有8192个磁道，每个磁道平均有256个扇区；每个扇区512个字节。试计算以下磁盘参数：1）磁盘格式化容量。2）若一个块大小为4096字节，求每个磁道能存放的块数。3）如果磁盘数据区外径为3.5英寸、内径为1.5英寸，求磁盘的径向密度。4）假定扇区间隙占磁道长度的10%，则磁盘最内和最外磁道上的位密度分别是多少？5）若磁盘转速为3840转/分，即1/64秒转一周。磁头起落1次1毫秒，每移过500个磁道另加1毫秒，试计算读写一个块的平均时间。4.1.3磁盘故障及其处理策略一、磁盘故障分类磁盘故障通常有以下几种方式或类型：间断性故障。写故障。部分介质损坏。磁盘崩溃。二、校验和技术磁盘扇区通常会存储一些冗余位，以可帮助识别从扇区读出的内容是否正确。最简单的校验和:是基于扇区内所有位的奇偶性。通过增加奇偶位数，可降低检不出错误的概率。•若用n个位存储校验和,则漏检错误的概率仅为1/2n4.1.3磁盘故障及其处理策略一、磁盘故障分类二、校验和技术三、稳定存储技术校验和技术能帮助检测读写故障或介质故障，但不能帮助我们纠正错误。基于稳定存储(stablestorage)的多副本策略，可能帮助我们一定程度上解决这个问题。四、从崩溃的磁盘故障恢复：RAID技术磁盘冗余阵列的磁盘组织技术。RedundantArrayofInexpensiveDisks几种常用的RAID级简介1．RAID0级(nonredundantstriping)把数据分拆到多块磁盘并行存贮（位级拆分且没有任何冗余）。在所有RAID级中，RAID0具有最好的写性能，但安全性最低。2．RAID1级(mirroreddisks)为每一个磁盘配置一镜像磁盘，适合于安全性要求很高场合。有效容量利用率只有50℅，成本较高。几种常用的RAID级简介3．RAID2级(error-CorrectingCodes错误-校正码)采用若干数据盘拆存字节中的位(bits)，并对每个字节计算奇偶校验位，额外的校验位存储在冗余盘。对有D个数据盘的磁盘阵列中，一次读写传输最少是D个块。较有利于传输数据量大的磁盘请求，不利于传输数据量小的磁盘请求。4.RAID3级(Bit-InterleavedParity位-奇偶交替)RAID2中因配置了较多的冗余校验盘，能自动解决坏盘检测问题，但也增大了代价。RAID3只使用一个冗余磁盘，即采用最低的安全性开销。RAID2/3写操作都需要一个read-modify-write的周期过程。几种常用的RAID级简介5．RAID4级(block-InterleavedParity块-奇偶交替)拆存单位是一个磁盘块。块级分存优点是能充分利用块设备工作特性，且能适应各种数据量传输的磁盘请求。不论有多少个数据磁盘，RAID4只用一个冗余盘存储各数据盘中的奇偶校验数据。6.RAID5级是RAID4的改进。RAID4中校验数据块总是用一个固定盘来存储，而在RAID5中，校验块是交替分布在各磁盘上。☆RAID4磁盘读写过程读块过程：直接读出相应数据盘中的目标块即可。写块过程：除了写目标数据盘外，还要修改冗余盘上对应块数据。写单个块需要一个read-modify-write的周期过程。校验盘对应块新数据＝(当前数据盘当前块原数据XOR当前数据盘当前块新数据)XOR校验盘对应块原数据几种常用的RAID级简介7．RAID6级(P+QRedundancy)使用RAID6的主要动机是：在很大的磁盘阵列中，仅能恢复一个坏盘显得安全性不足；同时出现两个坏盘，或在恢复过程中又出现坏盘的情况也必须考虑。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毫秒。某一时刻存在着对柱面1000、3000、7000的块访问请求。初始时磁头正位于1000柱面上而且是向上移动。此外，还有3个请求在稍后到来。试用电梯调度和FIFO策略调度算法，分别计算完成各块请求服务的时间。块请求到达所在柱面时间1000030000700002000208000305000404.1.4磁盘块存取的优化一、磁头调度技术先到先服务电梯算法二、采用特殊的文件组织方式按连续柱面存储数据三、采用磁盘缓冲池技术基于“传播控制层”的DB数据缓冲池技术磁盘预取技术双缓冲技术4.2磁盘空间管理4.2.1磁盘空间管理器4.2.2利用OS管理磁盘空间4.2.3跟踪自由块磁盘空间管理器是DBMS体系结构的最低层软件模块，隐藏了与磁盘有关的所有下层软硬件操作细节，并支持以‘页’为单位的数据管理。页(page)的大小通常就是磁盘块(block)大小，读写一个页可通过一次磁盘块I/O完成。允许高层软件认为DB数据是一系列以页为单位的磁盘数据集合。提供分配、释放和读写页的有关命令操作通过磁盘空间管理器，可将DB中的“关系”映射到“关系数据文件”.这种“文件”既可能是实际的OS文件，也可能只是一个虚拟的OS文件。4.3文件的页组织4.3.1堆文件4.3.2排序文件4.3.3索引文件本节内容安排单个记录文件所包含的记录集，可能存储在若干不同的页上。高层DBMS代码一般将“页”视为容纳多个记录的对象，忽略页中具体数据的表示方式或存储细节。重点讨论文件中有关页的组织方式。记录唯一标识符rid，可被用来识别记录所属的页及记录在页内的相对位置。4.3.1堆文件属无序文件，文件中页的大小相同。堆文件页中的记录是无序的，只能顺序存取。每个记录有唯一标识rid。堆文件管理支持创建/删除堆文件;扫描文件;插入/删除/检索给定rid的记录。不能直接帮助定位满足指定查询条件的有关记录rids基于双向页链表的堆文件组织将文件页以双链表方式链接在一起。缺点变长记录情况下，可能所有页都有空闲；检索记录可能需顺序扫描多个页基于目录页的堆文件组织组织结构允许有多个目录页，不同的目录页通过指针链接在一起。目录页中包含多个目录项，每个目录项标识一个页。优点：有利于更有效搜索足够容纳新记录的数据页。4.3.2排序文件文件中记录集按搜索键（searchkey）排序一般采用指针把记录按顺序链接起来。能支持按搜索键以顺序或随机方式快速获取记录，这对特定的排序查询非常有用。为减少处理排序文件时页请求的次数，需要尽可能地按搜索键顺序来存储记录。但绝对维持记录物理上的顺序排序往往非常困难,代价非常高。更常见的做法是：•删记录时仅做标记并留下空位，暂不移动其它记录•插入时，相应位置即使没有空，也暂时不移动其它记录来腾出位置，而是引入溢出页。•必要时，系统重组文件（安排在相对空闲时间）4.3.3基于索引的文件组织利用辅助索引文件来帮助定位数据记录。索引文件记录:索引项搜索键值,rid或rid_list4.4页表示格式4.4.1定长记录4.4.2变长记录在处理与I/O有关主题时，通常采用页层次抽象已足够。高层DBMS软件将数据视为记录集。为提高某些特殊应用性能，系统也允许用户指定数据文件存储组织的一些选项参数。这需要进一步了解页内记录的组织方式(即页格式)。一般可将页视为槽的集合，每个槽可容纳一个记录。记录可通过使用rid：page-id,slot-no来标识定位。因所有记录长度都相同，可在页内均匀、连续地安排记录槽。4.4.1定长记录DB系统中，变长记录是很常见的：记录类型中含有一个或多个变长字段；记录中包含可重复的、数量不确定的字段；允许在一个页中存储多种记录类型。对于变长记录存储，不能将页简单地划分为均匀的槽集。必须仔细处理以下两个问题：当插入一个记录时，如何能找到一个恰好能容纳新记录的空间；如何跟踪记录删除后空间。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)4.5.1定长记录的字段表示4.5.2变长记录的字段表示（一）预留空间技术（二）采用特殊字符结尾来实现变长字段（三）采用偏移数组来实现变长字段4.5.3跨页记录管理技术跨页记录存在的原因至少有两个：记录中存在大型或巨型字段；出于节省存储空间的需要。虽然记录大小不超过1页，但为了利用页内零头空间，也会导致跨页记录。跨页记录会被分割并分存到多个页中，故需要在各页中使用指针把它们链接在一起，形成单个记录的页链。4.5.4巨型字段/对象管理技术一些应用可能包含非常大的巨型对象。例如，一个多媒体对象可能占用几个MB的空间；一个视频序列，可能达几个GB。在RDB中，巨型字段也称为长字段。可使用BLOB等专门字段型来存储巨型对象.ODB可以直接管理巨型对象。大多数RDB限制记录的大小不超过1页，以简化缓冲区和空闲空间的管理。对超过一个页的大对象或长字段，一般采用如下两种管理方法：用跨页记录存储技术；将它们单独存储在一些文件或文件集中。4.5.5指针字段管理技术：指针混写（1）指针或地址经常是记录的一部分。当DB系统运行时，数据页允许在主存和辅存之间移动，故指针所指向的目标页/记录，在特定时间，既可能在辅存，也可能在主存。相应地，指针或地址也就有两种形式：内存地址数据库地址，也称持久化指针。是一种在辅存DB空间地址－－通常是一个逻辑地址。通过DB系统的“逻辑/物理地址映射表”，可将其映射为实际磁盘物理块地址。4.5.5指针字段管理技术：指针混写（2）根据给定的指针或地址寻找目标对象的过程，称为解引用(dereference)。C++内存指针引用语法：*指针名给定一个持久化指针