存储结构和文件结构解析

《存储结构和文件结构解析》由会员分享，可在线阅读，更多相关《存储结构和文件结构解析（63页珍藏版）》请在金锄头文库上搜索。

1、第3章 存储结构和文件结构,存储器层次 缓冲区管理 缓冲区置换策略 文件组织 文件中记录的组织 面向对象数据库的存储结构,3.1存储器层次,高速缓冲存储器,主存储器,第三级存储器,DBMS,DBMS的 程序、主存,3.1存储器层次,高速缓冲存储器(cache)：是一种集成电路芯片，或者是处理器芯片的一部分，能存放数据或机器指令，其中的数据是主存储器中特定位置的数据的副本，主存中相应的变化滞后于高速缓存的变化。机器的高速缓存通常分为两级 单版高速缓存：位于微处理器本身的同一芯片上 二级高速缓存：附加的，位于另一个芯片上 当机器执行指令时，在高速缓存中寻找指令以及要使用的数据。如果找不到，就要去主

2、存中寻找，并将他们拷贝到高速缓存中。 由于cache的容量有限，为接纳新数据，必须将其中某些内容移出。,3.1存储器层次,主存储器：主存或内存，计算机的活动中心。主存是随机访问的，10100纳秒。 虚拟存储器：32位字节长可寻址232=4G。由于虚拟存储器空间比内存大得多，一个完全被占用的虚拟存储器的大部分内容实际上是保存在磁盘上。磁盘被逻辑地分成多个块(block)，虚拟存储器以整个块为单位在磁盘和主存间移动，在主存中，这些块被称作页(page)。 磁盘：支持对给定地址的直接访问，广泛用于数据库应用。DBMS提供对磁盘数据的无缝存取，应用不必考虑数据是否在磁盘或主存上。 即支持虚拟存储器，又

3、支持文件系统。 磁盘空间管理 第三级存储器：磁带，光盘,磁盘,磁盘臂装置,转轴,磁道t,扇区s,柱面c,盘片,旋转,磁盘臂,读写头,磁盘块(页),磁盘控制器,磁盘控制器：是磁盘驱动器与计算机的接口，是一个小处理器，能完成以下功能： 控制移动磁头组合的机械传动装置，将磁头定位到一个特定的半径位置。 选择一个准备读写的盘面，并从位于该盘面的磁头下的磁道上选择一个扇区。 将从所要求的扇区读取的二进制位传送到计算机的主存储器，或者将从主存储器写入的二进制位传送到所期望的扇区。,磁盘控制器,处理器,主存,磁盘控制器,磁盘,磁盘,磁盘,总线,3.1存储器层次,主存储器：主存或内存，计算机的活动中心。主存是

4、随机访问的，10100纳秒。 虚拟存储器：32位字节长可寻址232=4G。由于虚拟存储器空间比内存大得多，一个完全被占用的虚拟存储器的大部分内容实际上是保存在磁盘上。磁盘被逻辑地分成多个块(block)，虚拟存储器以整个块为单位在磁盘和主存间移动，在主存中，这些块被称作页(page)。 磁盘：支持对给定地址的直接访问，广泛用于数据库应用。DBMS提供对磁盘数据的无缝存取，应用不必考虑数据是否在磁盘或主存上。 即支持虚拟存储器，又支持文件系统。 磁盘空间管理 第三级存储器：磁带，光盘,虚拟存储器,传统的内存管理方式要求将一个作业全部装入内存才可以运行，由此造成了以下两种情况： 大作业对内存的要求

5、超出物理内存总容量，致使其无法运行 内存由于容量的限制，只能装入少量的作业使其运行，而其它大量作业留在外存上 怎么办？ 方法一：从物理上增加内存容量 成本高 方法二：从逻辑上扩充内存容量,虚拟存储器,局部性原理：程序在执行过程中的一个较短时期，所执行的指令地址和指令的操作数地址，分别局限于一定区域。 引入：在程序装入时，不必将其全部读入到内存，而只需将当前需要执行的部分页或段读入到内存，就可让程序开始执行。 在程序执行过程中，如果需执行的指令或访问的数据尚未在内存（称为缺页或缺段），则由处理器通知操作系统，将相应的页或段调入到内存，然后继续执行程序。,虚拟存储器,虚拟存储器概念: 虚拟存储器是

6、指具有请求调入功能和置换功能，能从逻辑上对内存容量进行扩充的一种存储系统。它不是一个实际的物理存储器，而是一个容量可以非常大的存储器的逻辑模型，在该模型的支撑下，把程序的一部分装入内存便可以执行。 虚拟的: 大小由OS决定 逻辑模型: 概念,原理,技术解决方案,具体实现 部分执行,虚拟存储器,实现原理 进程运行只装入部分程序和数据 在外存保留完整副本 运行中动态调整进程在内存中的部署 技术难点 如何确定和记录当前哪些部分在内存 执行中访问不在内存的指令和数据时如何处理 从外存中调入某页时,内存中空间不够如何处理 优点: 利用率高，方便用户，对多道程序运行有较强的支持,3.2 缓冲区管理,数据库

7、：由若干文件组成 文件：(由操作系统管理的文件)由若干个定长的存储单元构成-存储块-页 页：可以包含若干个数据项，存储分配和数据传输的单位 数据库系统主要目标是：最小化磁盘和主存间传输存储块的数量，即磁盘存取的次数 实现手段：在主存中保持尽可能多的存储块，以使得当某一存储块被存取时它以在主存中的概率最大,3.2 缓冲区管理,缓冲区管理器的功能：负责管理可利用的内存空间，这些内存被划分为页面的集合，这些页面的集合称为缓冲池。当被访问的数据所在的页面不在内存中时缓冲区管理器必须将所需的页面从磁盘调入到缓冲池中。 缓冲区管理模型,3.2 缓冲区管理,DB,页面置换,来自高层代码的请求,缓冲池,主存,

8、磁盘页,空闲帧,3.2 缓冲区管理,(1)高层请求可以向缓冲区管理器请求某页，如果它不在缓冲池中将被调入缓冲池中 (2)请求该页的高层代码若不再需要该页时必须通知缓冲区管理器释放该页以使缓冲池中的空间可以重新利用 (3)高层代码必须通知缓冲区管理器如果它修改了被请求的页，缓冲区管理器必须保证该页的数据一致性 (4)对于缓冲池中的每个页面，缓冲区管理器必须为其设置两个变量：pin_count和dirty pin_count: 该页面的当前用户数 dirty: 该页面是否被修改过,3.2 缓冲区管理,(5)当一个页面被请求时缓冲区管理器做如下事情 a.检查缓冲池中是否包含该页。如果该页不在缓冲池中

9、 a.1通过置换策略来选择一个缓冲池单元用于置换 a.2如果被置换的缓冲池单元对应的dirty为on, 将该页写回到磁盘上 a.3将被请求的页调入到被置换的页中 b.将相应的pin_count变量加1，将对应的内存地址返回给调用者 (6)如果被请求的页不在缓冲池中且又没有空闲的入口项时，一个pin_count为0的页面被选择用于置换，当这样的页面很多时使用缓冲区管理的置换策略来确定被置换的入口项。,3.2 缓冲区管理,(7)如果缓冲池中一个入口项被选择用于置换，若对应的dirty位为off，该入口项可以直接被新页覆盖；否则该入口项必须先写回到磁盘上再用新页覆盖。 (8)如果不存在pin_cou

10、nt为0的页且被请求的页不在缓冲池中，缓冲区管理器必须等到某些入口项被释放再响应该请求。,3.3 缓冲区置换策略,(1) LRU(Least Recently Used): 维护一个队列，当缓冲池中某页的pin_count变为0时被插到队列的尾部；队列的头部为被置换的对象。 (2) Clock(LRU算法的一个变种)：缓冲池中所有的页被编号：1,2,N，这些页被安排成一个圆形，类似于时钟的表盘；clock算法还使用一个变量：current，在1到N之间循环变化，类似于时钟的指针；为了模仿LRU行为clock算法为每个页分配一个变量referenced位：当pin_count变为0时，refer

11、enced位被置为on。 如果current指向的页的pin_count0，则current+; 如果current指向的页的pin_count0且referenced为on时，则referenced被置为off，current+; 当前的pin_count=0且referenced=off时，该页被选为被置换页,3.3 缓冲区置换策略,MRU(Most Recently Used) FIFO(First In First Out) FILO(First In Last Out) Random ,OS的虚存和DBMS的缓冲区管理,OS的虚存和DBMS的缓冲区管理很相似，两者的目标都是对超出主存

12、容量的数据存取提供支持，其主要思想是必要时，从磁盘读出数据页，并替换掉主存中不再需要的页。 一个问题：为什么不利用OS的虚存能力建立DBMS呢？,DBMS比典型的OS环境更能准确地预测页的存储顺序（页的引用模式），并且他希望利用这个特性。 DBMS在写回磁盘时需要的控制比OS提供的控制更多。,OS的虚存和DBMS的缓冲区管理,被钉住的块（pinned block） 不允许写回磁盘的块 目的：为了使数据库系统能从系统崩溃中恢复，限制块写回磁盘的时间。 块的强制写出（forced output of blocks） 尽管不需要一个块所占用的缓冲区空间，仍将其写回磁盘的操作 目的：使磁盘上的数据在崩

13、溃时得以保留。,3.4 文件组织,定长记录文件实现 变长记录文件实现 基本字节流表示法 分槽的页结构表示法 定长的表示方法 保留空间（reserved space） 链表表示（list representation） 锚块（anchor block）、溢出块（overflow block）,3.4页格式,3.4页格式,槽记录,指针指向 空闲空间 的起始处,长度=24,3.4 文件组织,3.4.1定长记录 type deposit = record branch-name:char(22); account-number:char(10); balance:real; end,3.4.1定长记录

14、,3.4.1定长记录,3.4.1定长记录,3.4.1定长记录,3.4.1定长记录,特点： 删除记录比较困难 一个记录可能跨越两个存储块的边界 实现简单 空间利用率高,3.4.1定长记录,3.4.2变长记录,type account-list = record branch-name: char(22); account-info: array1 of record account-number: char(10); balance:real; end end,3.4.2变长记录,3.4.2.1 基本字节流表示法,3.4.2变长记录,基本字节流表示方法的缺点 重新使用被删记录曾占用的空间十分困难

15、 通常分配给记录的空间不能随记录长度的增长而增长,3.4.2变长记录,大小,位置,3.4.2.2 分槽的页结构表示法 每个页的存储结构如下： 记录入口数：表示块中记录条目的个数 存储块中空闲空间的末尾地址 一个数组：包含每个记录的位置和大小,3.4.2变长记录,3.4.2.3定长的表示方法-保留空间,3.4.2变长记录,3.4.2.4定长的表示方法-指针,3.4.2变长记录,3.4.2.5定长的表示方法-锚块、溢出块,锚块,溢出块,3.5文件中记录的组织,堆文件组织 Heap file organization 顺序文件组织 Sequential file organization 散列文件组

16、织（第4章） Hashing file organization 聚簇文件组织 Clustering file organization,3.5文件中记录的组织,3.5.1堆文件 （1）最简单的文件结构是堆文件：记录的组织是无序的，每个记录具有唯一的rid，支持所有记录的检索，在文件中每个页具有相同的大小。 （2）在堆文件上应支持的操作：文件的建立与删除、插入记录、删除一个给定rid的记录、查找给定rid的记录、从文件中扫描所有记录,3.5文件中记录的组织,两种堆文件结构 (1)页链接式结构 在这种结构中，堆文件中所有页被组织在两个链表中，一个为满页(即没有空闲空间的页)链表，另一个为有空闲空间的页链表。 当一个新的页从原始(raw)空间中被分配出来以后，该页要被插入第一个链表。 每个页中空闲空间的管理可采用前面讨论过的方法和途径。缺点：对于变长记录而言，所有的页可能在第一个链中，要插入一个记录的话，必须要找