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相反，选择最近刚被用过的页予以淘汰。,
