1、第2部分 关系数据库系统实现第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)磁盘结构,硬盘容量盘面数每盘面磁道数每磁道扇区数每扇区字节数,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,假设一种具
3、有如下特性的硬盘:共有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 磁盘故障及其处理策略,一、磁盘故障分类磁盘故障通常有以下几种方式或类型: 间断性
4、故障。 写故障。 部分介质损坏。 磁盘崩溃。 二、校验和技术 磁盘扇区通常会存储一些冗余位,以可帮助识别从扇区读出的内容是否正确。 最简单的校验和:是基于扇区内所有位的奇偶性。 通过增加奇偶位数,可降低检不出错误的概率。 若用n个位存储校验和,则漏检错误的概率仅为1/2 n,4.1.3 磁盘故障及其处理策略,一、磁盘故障分类 二、校验和技术 三、稳定存储技术 校验和技术能帮助检测读写故障或介质故障,但不能帮助我们纠正错误。 基于稳定存储(stable storage)的多副本策略,可能帮助我们一定程度上解决这个问题。 四、从崩溃的磁盘故障恢复:RAID技术 磁盘冗余阵列 的磁盘组织技术。 Re
5、dundant Array of Inexpensive Disks,几种常用的RAID级简介,1RAID0级(nonredundant striping) 把数据分拆到多块磁盘并行存贮(位级拆分且没有任何冗余)。 在所有RAID级中,RAID0具有最好的写性能,但安全性最低。 2RAID1级(mirrored disks) 为每一个磁盘配置一镜像磁盘,适合于安全性要求很高场合。有效容量利用率只有50,成本较高。,几种常用的RAID级简介,3RAID2级(error-Correcting Codes错误-校正码) 采用若干数据盘拆存字节中的位(bits),并对每个字节计算奇偶校验位,额外的校验
6、位存储在冗余盘。 对有D个数据盘的磁盘阵列中,一次读写传输最少是D个块。较有利于传输数据量大的磁盘请求,不利于传输数据量小的磁盘请求。 4. RAID3级(Bit-Interleaved Parity位-奇偶交替)RAID2中因配置了较多的冗余校验盘,能自动解决坏盘检测问题,但也增大了代价。RAID3只使用一个冗余磁盘,即采用最低的安全性开销。 RAID2/3写操作都需要一个read-modify-write 的周期过程。,几种常用的RAID级简介,5RAID4级(block-Interleaved Parity块-奇偶交替) 拆存单位是一个磁盘块。块级分存优点是能充分利用块设备工作特性,且能
7、适应各种数据量传输的磁盘请求。 不论有多少个数据磁盘,RAID4只用一个冗余盘存储各数据盘中的奇偶校验数据。 6. RAID5级 是RAID4的改进。RAID4中校验数据块总是用一个固定盘来存储,而在RAID5中,校验块是交替分布在各磁盘上。, RAID4磁盘读写过程 读块过程:直接读出相应数据盘中的目标块即可。 写块过程:除了写目标数据盘外,还要修改冗余盘上对应块数据。写单个块需要一个read- modify- write 的周期过程。校验盘对应块新数据(当前数据盘当前块原数据 XOR 当前数据盘当前块新数据 ) XOR 校验盘对应块原数据,几种常用的RAID级简介,7RAID6级(P+Q
8、Redundancy) 使用RAID6的主要动机是:在很大的磁盘阵列中,仅能恢复一个坏盘显得安全性不足;同时出现两个坏盘,或在恢复过程中又出现坏盘的情况也必须考虑。 RAID6一般采用基于Hamming-Code编码的数据盘-校验盘组合方案,使得能同时恢复两个坏盘。RAID6的故障恢复步骤,4.1.4 磁盘块存取的优化,在多数OS中,磁盘I/O请求是由文件系统和虚拟内存管理器产生的。 DB系统中,系统高层的页请求通过磁盘空间管理器,也会产生基于磁盘块的I/O请求。 由于存取磁盘比存取主存要慢好几个量级,所以,DB系统改善磁盘块存取性能非常重要。,4.1.4 磁盘块存取的优化,一、磁头调度技术
9、先到先服务 电梯算法 例4.6 假设某磁盘的平均寻道时间、旋转等待时间和块传输时间分别为6.5、7.8和0.5毫秒。某一时刻存在着对柱面1000、3000、7000的块访问请求。初始时磁头正位于1000柱面上而且是向上移动。此外,还有3个请求在稍后到来。试用电梯调度和FIFO策略调度算法,分别计算完成各块请求服务的时间。,4.1.4 磁盘块存取的优化,一、磁头调度技术 先到先服务 电梯算法 二、采用特殊的文件组织方式 按连续柱面存储数据 三、采用磁盘缓冲池技术 基于“传播控制层” 的DB数据缓冲池技术 磁盘预取技术 双缓冲技术,4.2 磁盘空间管理,4.2.1 磁盘空间管理器,4.2.2 利用
10、OS管理磁盘空间,4.2.3 跟踪自由块,磁盘空间管理器,是DBMS体系结构的最低层软件模块,隐藏了与磁盘有关的所有下层软硬件操作细节,并支持以页为单位的数据管理。 页(page)的大小通常就是磁盘块(block)大小,读写一个页可通过一次磁盘块I/O完成。 允许高层软件认为DB数据是一系列以页为单位的磁盘数据集合。 提供分配、释放和读写页的有关命令操作 通过磁盘空间管理器,可将DB中的“关系”映射到 “关系数据文件”. 这种“文件”既可能是实际的OS文件,也可能只是一个虚拟的OS文件。,4.3 文件的页组织,4.3.1 堆文件,4.3.2 排序文件,4.3.3 索引文件,记录唯一标识符rid
11、,可被用来识别记录所属的页及记录在页内的相对位置。,4.3.1 堆文件,属无序文件,文件中页的大小相同。 堆文件页中的记录是无序的,只能顺序存取。每个记录有唯一标识rid。 堆文件管理支持 创建/删除堆文件; 扫描文件; 插入/删除/检索给定rid的记录。 不能直接帮助定位满足指定查询条件的有关记录rids,基于双向页链表的堆文件组织,将文件页以双链表方式链接在一起。 缺点 变长记录情况下,可能所有页都有空闲;检索记录可能需顺序扫描多个页,基于目录页的堆文件组织,组织结构 允许有多个目录页,不同的目录页通过指针链接在一起。 目录页中包含多个目录项,每个目录项标识一个页。 优点: 有利于更有效搜
12、索足够容纳新记录的数据页。,4.3.2 排序文件,文件中记录集按搜索键(search key)排序 一般采用指针把记录按顺序链接起来。 能支持按搜索键以顺序或随机方式快速获取记录,这对特定的排序查询非常有用。 为减少处理排序文件时页请求的次数,需要尽可能地按搜索键顺序来存储记录。 但绝对维持记录物理上的顺序排序往往非常困难,代价非常高。更常见的做法是: 删记录时仅做标记并留下空位,暂不移动其它记录 插入时,相应位置即使没有空,也暂时不移动其它记录来腾出位置,而是引入溢出页。 必要时,系统重组文件(安排在相对空闲时间),4.3.3 基于索引的文件组织,利用辅助索引文件来帮助定位数据记录。 索引文
13、件记录:索引项,4.4 页表示格式,4.4.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 指针记录管理技术指针混写,4.5 记录表示格式(图4.11),4.5.1 定长记录的字段表示4.5.2 变长记录的字段表示 (一)预留空间技术 (二)采用特殊字符结尾来实现变长字段 (三)采用偏移数组来实现变
15、长字段,4.5.3 跨页记录管理技术,跨页记录存在的原因至少有两个: 记录中存在大型或巨型字段; 出于节省存储空间的需要。虽然记录大小不超过1页,但为了利用页内零头空间,也会导致跨页记录。 跨页记录会被分割并分存到多个页中,故需要在各页中使用指针把它们链接在一起,形成单个记录的页链。,4.5.4 巨型字段/对象管理技术,一些应用可能包含非常大的巨型对象。 例如,一个多媒体对象可能占用几个MB的空间;一个视频序列,可能达几个GB。 在RDB中,巨型字段也称为长字段。可使用BLOB等专门字段型来存储巨型对象. ODB可以直接管理巨型对象。 大多数RDB限制记录的大小不超过1页,以简化缓冲区和空闲空
16、间的管理。对超过一个页的大对象或长字段,一般采用如下两种管理方法: 用跨页记录存储技术; 将它们单独存储在一些文件或文件集中。,4.5.5 指针字段管理技术:指针混写(1),指针或地址经常是记录的一部分。 当DB系统运行时,数据页允许在主存和辅存之间移动,故指针所指向的目标页/记录,在特定时间,既可能在辅存,也可能在主存。相应地,指针或地址也就有两种形式: 内存地址 数据库地址,也称持久化指针。是一种在辅存DB空间地址通常是一个逻辑地址。 通过DB系统的“逻辑/物理地址映射表”,可将其映射为实际磁盘物理块地址。,4.5.5 指针字段管理技术:指针混写(2),根据给定的指针或地址寻找目标对象的过
17、程,称为解引用(dereference)。 C+内存指针引用语法:*指针名 给定一个持久化指针,解引用一个对象需要额外的步骤: 须通过 “转换表” 查找持久化指针所代表对象在内存中的实际位置。 如对象不在内存,则要从磁盘读入,同时要修改转换表,并将存放该持久指针的内存单元,直接修改为目标对象的内存位置指针。 下一次同一持久化指针再次被解引用时,就可以直接使用内存引用,从而可避免重复转换内存地址的过程开销。 当对象被写回磁盘时,它所包含的任何被混写持久化指针必须执行反混写, 与内存指针解引用相比,通过转换表实现解引用仍是一个慢过程。 指针混写的时机选择 自动混写;按需混写;不混写;程序控制,4.
18、6 DB元信息及其存储管理,在RDB系统,除了关系,还需要维护关于整个DB的元描述数据,如关系的模式等。这类元信息称为数据字典(data dictionary)或系统目录(system catalog)。系统需存储的元信息类型有: 关系的模式(关系名、每个属性名字/类型/长度)。 在DB上定义的视图名字和视图定义。 完整性约束。 授权名、认证密码等关于用户帐户的信息。 当前关系实例的统计/描述数据。如每个关系中的元组总数,或各字段取值的统计直方图信息等描述信息。 实际上,所有这些信息组成了一个微型数据库,4.7 缓冲区管理,4.7.1 DB缓冲池与缓冲区管理器,4.7.2 缓冲区置换策略,4.
19、7.3 DBMS与OS的缓冲区管理对比,DB缓冲池与缓冲区管理器,DB缓冲池 DBMS系统一般都拥有一个专用于处理页读写的、称为DB缓冲池的主存区。 该主存区被按页大小划分为一个个页槽(简称页面框,frame) 。 为叙述方便,有时也常简单使用可用主存、缓存、缓冲区、主存缓冲区等名词称谓DB缓冲池。 缓冲区管理器 指DBMS中专门负责管理DB缓冲池的软件模块。 缓冲区置换策略 当新页请求发生且没有空闲缓冲页时,决定替换缓冲区哪些页的策略。,缓冲区管理器响应高层页请求的基本过程,检查缓冲池中是否存在该页,如不在,则进一步执行以下一些操作。 基于置换策略,选择一个可被置换的frame,将其的pin_count计数加1。 如果该frame中原先页被修改过(dirty=1),则将原先页写回磁盘。 从磁盘读入新请求页到该frame中,同时置dirty=0。 返回包含请求页的frame地址给请求者。,几种常用的缓冲区置换策略简介,LRU(least recently used) 它选择最近最久未使用的页予以淘汰。 2. 时钟置换策略 3. FIFO(first in first out) FIFO总是选择最早进入主存的页作为下一个置换页,不能反映页面的使用情况,通常效果较差。 4. MRU(most recently used) MRU策略则刚好与LRU相反,选择最近刚被用过的页予以淘汰。,