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

1、LOGO 高级数据库系统及其应用高级数据库系统及其应用 第第4 4章章 数据存储和组织管理数据存储和组织管理 物理存储介质物理存储介质 4.1 磁盘空间管理磁盘空间管理 4.2 文件的页组织文件的页组织 4.3 页表示格式页表示格式 4.4 记录表示格式记录表示格式 4.5 DB元信息及其组织管理元信息及其组织管理4.6 DB缓冲区管理缓冲区管理4.7 4.1 物理存储介质物理存储介质 4.1.1 存储介质的层次 4.1.2 磁盘的物理特性 4.1.3 磁盘故障及其处理策略 4.1.4 磁盘块存取的优化 4.1.1 存储介质的层次存储介质的层次 4.1.2 磁盘的物理特性磁盘的物理特性 （1）

2、磁盘结构）磁盘结构 硬盘容量硬盘容量 盘面数盘面数每盘面磁道数每盘面磁道数每磁道扇区数每磁道扇区数每扇区字节数每扇区字节数 4.1.2 磁盘的物理特性磁盘的物理特性 （2）磁盘基本操作特性）磁盘基本操作特性 v磁盘读写的最小单位是扇区。但在操作系统或磁盘读写的最小单位是扇区。但在操作系统或 DBMS系统层次，磁盘读写的基本单位是系统层次，磁盘读写的基本单位是磁盘块磁盘块 (block)。 不同系统块大小可能不同，大多数系统的块取 4KB。 v进行实际磁盘读写时，主存中必须有磁盘块缓冲进行实际磁盘读写时，主存中必须有磁盘块缓冲 区；在磁盘和主存之间传送一个磁盘块称为区；在磁盘和主存之间传送一个磁

3、盘块称为1次次 I/O操作。操作。 v读写一个块的时间读写一个块的时间: 寻道时间旋转延迟时间传输时间。 例例4.1 假设有一个含假设有一个含3个盘片的硬盘，共有个盘片的硬盘，共有4个个 记录面，转速为记录面，转速为4500转转/分钟，盘面有效分钟，盘面有效 记录区域的外直径为记录区域的外直径为30cm，内直径为，内直径为 10cm，记录位密度为，记录位密度为250位位/mm，磁道，磁道 密度为密度为8道道/mm，每个磁道分，每个磁道分16扇区，每扇区，每 扇区扇区512字节。试计算：字节。试计算： 1）磁盘的总磁道数 2）非格式化容量 3）平均速度传输速率。 例例4.2 假设一种具有如下特性

4、的硬盘：共有假设一种具有如下特性的硬盘：共有4个个 盘片，盘片，8个盘面；每个盘面有个盘面；每个盘面有8192个磁道，个磁道， 每个磁道平均有每个磁道平均有256个扇区；每个扇区个扇区；每个扇区512 个字节。试计算以下磁盘参数：个字节。试计算以下磁盘参数： l 1）磁盘格式化容量。）磁盘格式化容量。 l 2）若一个块大小为）若一个块大小为4096字节，求每个磁道能存放的块数。字节，求每个磁道能存放的块数。 l 3）如果磁盘数据区外径为）如果磁盘数据区外径为3.5英寸、内径为英寸、内径为1.5英寸，英寸， 求磁求磁 盘的径向密度。盘的径向密度。 l 4）假定扇区间隙占磁道长度的）假定扇区间隙占

5、磁道长度的10%，则磁盘最内和最外磁，则磁盘最内和最外磁 道上的位密度分别是多少？道上的位密度分别是多少？ l 5）若磁盘转速为）若磁盘转速为3840转转/分，即分，即1/64秒转一周。磁头起秒转一周。磁头起 落落1次次1毫秒，每移过毫秒，每移过500个磁道另加个磁道另加1毫秒，试计算读写一毫秒，试计算读写一 个块的平均时间。个块的平均时间。 4.1.3 磁盘故障及其处理策略磁盘故障及其处理策略 一、磁盘故障分类一、磁盘故障分类 磁盘故障通常有以下几种方式或类型：磁盘故障通常有以下几种方式或类型： 间断性故障。间断性故障。 写故障。写故障。 部分介质损坏。部分介质损坏。 磁盘崩溃。磁盘崩溃。

6、二、校验和技术二、校验和技术 磁盘扇区通常会存储一些冗余位，以可帮助识 别从扇区读出的内容是否正确。 最简单的校验和:是基于扇区内所有位的奇偶性。 通过增加奇偶位数，可降低检不出错误的概率。 若用n个位存储校验和,则漏检错误的概率仅为1/2 n 4.1.3 磁盘故障及其处理策略磁盘故障及其处理策略 一、磁盘故障分类一、磁盘故障分类 二、校验和技术二、校验和技术 三、稳定存储技术三、稳定存储技术 校验和技术能帮助检测读写故障或介质故障， 但不能帮助我们纠正错误。 基于稳定存储(stable storage)的多副本策略， 可能帮助我们一定程度上解决这个问题。 四、从崩溃的磁盘故障恢复：四、从崩溃

7、的磁盘故障恢复：RAID技术技术 磁盘冗余阵列 的磁盘组织技术。 Redundant Array of Inexpensive Disks 几种常用的几种常用的RAID级简介级简介 1RAID0级级(nonredundant striping) 把数据分拆到多块磁盘并行存贮（位级拆分且 没有任何冗余）。 在所有RAID级中，RAID0具有最好的写性能， 但安全性最低。 2RAID1级级(mirrored disks) 为每一个磁盘配置一镜像磁盘，适合于安全性 要求很高场合。有效容量利用率只有50，成 本较高。 几种常用的几种常用的RAID级简介级简介 3RAID2级级(error-Correc

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

9、RAID级简介级简介 5RAID4级级(block-Interleaved Parity块块-奇偶交替奇偶交替) 拆存单位是一个磁盘块。块级分存优点是能充分利用块 设备工作特性，且能适应各种数据量传输的磁盘请求。 不论有多少个数据磁盘，RAID4只用一个冗余盘存储各 数据盘中的奇偶校验数据。 6. RAID5级级 是RAID4的改进。RAID4中校验数据块总是用 一个固定盘来存储，而在RAID5中，校验块是 交替分布在各磁盘上。 RAID4磁盘读写过程磁盘读写过程 读块过程：直接读出相应数据盘中的目标块即可。 写块过程：除了写目标数据盘外，还要修改冗余盘上对 应块数据。写单个块需要一个写单个块

10、需要一个read- modify- write 的的 周期过程周期过程。 校验盘对应块新数据校验盘对应块新数据(当前数据盘当前块原数据当前数据盘当前块原数据 XOR 当前数据盘当前块新数据当前数据盘当前块新数据 ) XOR 校验盘对应块原数据校验盘对应块原数据 几种常用的几种常用的RAID级简介级简介 7RAID6级级(P+Q Redundancy) 使用RAID6的主要动机是：在很大的磁盘阵列中，仅能 恢复一个坏盘显得安全性不足；同时出现两个坏盘，或 在恢复过程中又出现坏盘的情况也必须考虑。 RAID6一般采用基于Hamming-Code编码的数据盘-校 验盘组合方案，使得能同时恢复两个坏盘

11、。 RAID6的故障恢复步骤的故障恢复步骤 4.1.4 磁盘块存取的优化磁盘块存取的优化 v在多数在多数OS中，磁盘中，磁盘I/O请求是由文件系统请求是由文件系统 和虚拟内存管理器产生的。和虚拟内存管理器产生的。 vDB系统中，系统高层的页请求通过磁盘空系统中，系统高层的页请求通过磁盘空 间管理器，也会产生基于磁盘块的间管理器，也会产生基于磁盘块的I/O请请 求。求。 v由于存取磁盘比存取主存要慢好几个量级，由于存取磁盘比存取主存要慢好几个量级， 所以，所以，DB系统改善磁盘块存取性能非常重系统改善磁盘块存取性能非常重 要。要。 4.1.4 磁盘块存取的优化磁盘块存取的优化 一、磁头调度技术一

12、、磁头调度技术 先到先服务先到先服务 电梯算法电梯算法 例例4.6 假设某磁盘的平均寻道时间、旋转等待假设某磁盘的平均寻道时间、旋转等待 时间和块传输时间分别为时间和块传输时间分别为6.5、7.8和和0.5 毫秒。某一时刻存在着对柱面毫秒。某一时刻存在着对柱面1000、 3000、7000的块访问请求。初始时磁头的块访问请求。初始时磁头 正位于正位于1000柱面上而且是向上移动。此外，柱面上而且是向上移动。此外， 还有还有3个请求在稍后到来。个请求在稍后到来。 试用电梯调度和试用电梯调度和FIFO策略调度算法，分策略调度算法，分 别计算完成各块请求服务的时间。别计算完成各块请求服务的时间。 4

13、.1.4 磁盘块存取的优化磁盘块存取的优化 一、磁头调度技术一、磁头调度技术 先到先服务先到先服务 电梯算法电梯算法 二、采用特殊的文件组织方式二、采用特殊的文件组织方式 按连续柱面存储数据按连续柱面存储数据 三、采用磁盘缓冲池技术三、采用磁盘缓冲池技术 基于基于“传播控制层传播控制层” 的的DB数据缓冲池技术数据缓冲池技术 磁盘预取技术磁盘预取技术 双缓冲技术双缓冲技术 4.2 磁盘空间管理磁盘空间管理 4.2.1 磁盘空间管理器 4.2.2 利用OS管理磁盘空间 4.2.3 跟踪自由块 磁盘空间管理器磁盘空间管理器 v是是DBMS体系结构的最低层软件模块，隐体系结构的最低层软件模块，隐 藏

14、了与磁盘有关的所有下层软硬件操作细藏了与磁盘有关的所有下层软硬件操作细 节，并支持以节，并支持以页页为单位的数据管理。为单位的数据管理。 页页(page)的大小通常就是磁盘块的大小通常就是磁盘块(block)大小，大小， 读写一个页可通过一次磁盘块读写一个页可通过一次磁盘块I/O完成。完成。 允许高层软件认为允许高层软件认为DB数据是一系列以页为单数据是一系列以页为单 位的磁盘数据集合。位的磁盘数据集合。 提供分配、释放和读写页的有关命令操作提供分配、释放和读写页的有关命令操作 v通过磁盘空间管理器，可将通过磁盘空间管理器，可将DB中的中的“关系关系”映映 射到射到 “关系数据文件关系数据文件

15、”. 这种这种“文件文件”既可能是实际的既可能是实际的OS文件，也可文件，也可 能只是一个虚拟的能只是一个虚拟的OS文件。文件。 4.3 文件的页组织文件的页组织 4.3.1 堆文件 4.3.2 排序文件 4.3.3 索引文件 u 单个记录文件所包含的记录集，单个记录文件所包含的记录集， 可能存储在若干不同的页上。可能存储在若干不同的页上。 u 高层高层DBMS代码一般将代码一般将“页页”视为容视为容 纳纳 多个记录的对象，忽略页中具体数据多个记录的对象，忽略页中具体数据 的表示方式或存储细节。的表示方式或存储细节。 u 重点讨论文件中有关页的组织方式。重点讨论文件中有关页的组织方式。 记录唯

16、一标识符记录唯一标识符rid，可被用来识别记录所属的页及记录在页内的相对位置。，可被用来识别记录所属的页及记录在页内的相对位置。 4.3.1 堆文件堆文件 v属无序文件，文件中页的大小相同。属无序文件，文件中页的大小相同。 v堆文件页中的记录是无序的，只能顺序存取。每堆文件页中的记录是无序的，只能顺序存取。每 个记录有唯一标识个记录有唯一标识rid。 v堆文件管理支持堆文件管理支持 创建/删除堆文件; 扫描扫描文件; 插入/删除/检索给定rid的记录。 不能直接帮助定位满足指定查询条件的有关记录rids 基于双向页链表的堆文件组织基于双向页链表的堆文件组织 v将文件页以双链表将文件页以双链表

17、方式链接在一起。方式链接在一起。 v缺点缺点 变长记录情况 下，可能所有 页都有空闲； 检索记录可能 需顺序扫描多 个页 基于目录页的堆文件组织基于目录页的堆文件组织 v 组织结构组织结构 允许有多个目录页， 不同的目录页通过 指针链接在一起。 目录页中包含多个 目录项，每个目录 项标识一个页。 v 优点：优点： 有利于更有效搜索 足够容纳新记录的 数据页。 4.3.2 排序文件排序文件 v文件中记录集按搜索键（文件中记录集按搜索键（search key）排序）排序 一般采用指针把记录按顺序链接起来。 能支持按搜索键以顺序或随机方式快速获取记 录，这对特定的排序查询非常有用。 v为减少处理排序

18、文件时页请求的次数，需要尽可为减少处理排序文件时页请求的次数，需要尽可 能地按搜索键顺序来存储记录。能地按搜索键顺序来存储记录。 但绝对维持记录物理上的顺序排序往往非常困 难,代价非常高。更常见的做法是： 删记录时仅做标记并留下空位，暂不移动其它记录 插入时，相应位置即使没有空，也暂时不移动其它 记录来腾出位置，而是引入溢出页。 必要时，系统重组文件（安排在相对空闲时间） 4.3.3 基于索引的文件组织基于索引的文件组织 v 利用辅助索引文件来帮助定位数据记录。利用辅助索引文件来帮助定位数据记录。 索引文件记录:索引项 4.4 页表示格式页表示格式 4.4.1 定长记录 4.4.2 变长记录

19、v 在处理与在处理与I/O有关主题时，通常采用页层次抽象已足够。有关主题时，通常采用页层次抽象已足够。 v 高层高层DBMS软件将数据视为记录集。为提高某些特殊应用软件将数据视为记录集。为提高某些特殊应用 性能，系统也允许用户指定数据文件存储组织的一些选项性能，系统也允许用户指定数据文件存储组织的一些选项 参数。参数。 这需要进一步了解页内记录的组织方式(即页格式)。 v 一般可将页视为槽的集合，每个槽可容纳一个记录。一般可将页视为槽的集合，每个槽可容纳一个记录。 记录可通过使用rid：来标识定位。 v因所有记录长度都相同，可在页内均匀、因所有记录长度都相同，可在页内均匀、 连续地安排记录槽。

20、连续地安排记录槽。 4.4.1 定长记录定长记录 vDB系统中，变长记录是很常见的：系统中，变长记录是很常见的： 记录类型中含有一个或多个变长字段； 记录中包含可重复的、数量不确定的字段； 允许在一个页中存储多种记录类型。 v对于变长记录存储，不能将页简单地划分为均匀对于变长记录存储，不能将页简单地划分为均匀 的槽集。必须仔细处理以下两个问题：的槽集。必须仔细处理以下两个问题： 当插入一个记录时，如何能找到一个恰好能容 纳新记录的空间； 如何跟踪记录删除后空间。 4.4.2 变长记录变长记录 基于分槽式页结构表示变长记录基于分槽式页结构表示变长记录(图图4.10) 4.5 4.5 记录表示格式

21、记录表示格式 4.5.1 定长记录的字段表示 4.5.2 变长记录的字段表示 4.5.3 跨页记录管理技术 4.5.4 巨型字段/对象管理技术 4.5.5 指针记录管理技术指针混写 u DB中记录除了存储各字段信息外，中记录除了存储各字段信息外， 通常还有一个记录首部（记录头）。通常还有一个记录首部（记录头）。 u记录头中存储记录层次的一般管理记录头中存储记录层次的一般管理 信息，包括记录长度、时间戳和指向信息，包括记录长度、时间戳和指向 记录模式描述的指针等。记录模式描述的指针等。 u记录是否变长主要看它是否含变长字段。记录是否变长主要看它是否含变长字段。 u本节集中讨论记录中字段的表示问题

22、。本节集中讨论记录中字段的表示问题。 4.5 记录表示格式记录表示格式（图（图4.11) 4.5.1 定长记录的字段表示定长记录的字段表示 4.5.2 变长记录的字段表示变长记录的字段表示 （一）预留空间技术（一）预留空间技术 （二）采用特殊字符结尾来实现变长字段（二）采用特殊字符结尾来实现变长字段 （三）采用偏移数组来实现变长字段（三）采用偏移数组来实现变长字段 4.5.3 跨页记录管理技术跨页记录管理技术 v 跨页记录存在的原因至少有两个：跨页记录存在的原因至少有两个： 记录中存在大型或巨型字段； 出于节省存储空间的需要。虽然记录大小不超过1页， 但为了利用页内零头空间，也会导致跨页记录。

23、 v 跨页记录会被分割并分存到多个页中，故需要在各页中跨页记录会被分割并分存到多个页中，故需要在各页中 使用指针把它们链接在一起，形成单个记录的页链。使用指针把它们链接在一起，形成单个记录的页链。 4.5.4 巨型字段巨型字段/对象管理技术对象管理技术 v一些应用可能包含非常大的巨型对象。一些应用可能包含非常大的巨型对象。 例如，一个多媒体对象可能占用几个MB的空间； 一个视频序列，可能达几个GB。 在RDB中，巨型字段也称为长字段。可使用 BLOB等专门字段型来存储巨型对象. ODB可以直接管理巨型对象。 v大多数大多数RDB限制记录的大小不超过限制记录的大小不超过1页，以简化页，以简化 缓

24、冲区和空闲空间的管理。对超过一个页的大对缓冲区和空闲空间的管理。对超过一个页的大对 象或长字段，一般采用如下两种管理方法：象或长字段，一般采用如下两种管理方法： 用跨页记录存储技术； 将它们单独存储在一些文件或文件集中。 4.5.5 指针字段管理技术：指针混写（指针字段管理技术：指针混写（1） v指针或地址经常是记录的一部分。指针或地址经常是记录的一部分。 v当当DB系统运行时，数据页允许在主存和辅存之间系统运行时，数据页允许在主存和辅存之间 移动，故指针所指向的目标页移动，故指针所指向的目标页/记录，在特定时间，记录，在特定时间， 既可能在辅存，也可能在主存。相应地，指针或既可能在辅存，也可

25、能在主存。相应地，指针或 地址也就有两种形式：地址也就有两种形式： 内存地址内存地址 数据库地址，也称持久化指针。是一种在辅存数据库地址，也称持久化指针。是一种在辅存 DB空间地址通常是一个逻辑地址。空间地址通常是一个逻辑地址。 v通过通过DB系统的系统的“逻辑逻辑/物理地址映射表物理地址映射表”，可将，可将 其映射为实际磁盘物理块地址。其映射为实际磁盘物理块地址。 4.5.5 指针字段管理技术：指针混写（指针字段管理技术：指针混写（2） v 根据给定的指针或地址寻找目标对象的过程，称为解引用根据给定的指针或地址寻找目标对象的过程，称为解引用 (dereference)。 C+内存指针引用语法

26、：内存指针引用语法：*指针名指针名 v 给定一个持久化指针，解引用一个对象需要额外的步骤：给定一个持久化指针，解引用一个对象需要额外的步骤： 须通过须通过 “转换表转换表” 查找持久化指针所代表对象在内存查找持久化指针所代表对象在内存 中的实际位置。中的实际位置。 如对象不在内存，则要从磁盘读入，同时要修改转换表，并将如对象不在内存，则要从磁盘读入，同时要修改转换表，并将 存放该持久指针的内存单元，直接修改为存放该持久指针的内存单元，直接修改为目标对象目标对象的内存位置的内存位置 指针。指针。 下一次同一持久化指针再次被解引用时，就可以直接使用内存下一次同一持久化指针再次被解引用时，就可以直接

27、使用内存 引用，从而可避免重复转换内存地址的过程开销。引用，从而可避免重复转换内存地址的过程开销。 当对象被写回磁盘时，它所包含的任何被混写持久化指针必须当对象被写回磁盘时，它所包含的任何被混写持久化指针必须 执行反混写，执行反混写， v 与内存指针解引用相比，通过转换表实现解引用仍是一个与内存指针解引用相比，通过转换表实现解引用仍是一个 慢过程。慢过程。 v 指针混写的时机选择指针混写的时机选择 自动混写；按需混写；不混写；程序控制 4.6 DB元信息及其存储管理元信息及其存储管理 v 在在RDB系统，除了关系，还需要维护关于整个系统，除了关系，还需要维护关于整个DB的元描的元描 述数据，如关系的模式等。这类元信息称为数据字典述数据，如关系的模式等。这类元信息称为数据字典 (data dictionary)或系统目录或系统目录(system catalog)。 系统需存储的元信息类型有：系统需存储的元信息类型有： 关系的模式（关系名、每个属性名字/类型/长度）。 在DB上定义的视图名字和视图定义。 完整性约束。 授权名、认证密码等关于用户帐户的信息。 当前关系实例的统计/描述数据。如每个关系中的元组 总数，或各字段取值的统计直方图信息等描述信息。