文件组织和数据存储讲解

《文件组织和数据存储讲解》由会员分享，可在线阅读，更多相关《文件组织和数据存储讲解（37页珍藏版）》请在金锄头文库上搜索。

1、6.3文件组织与数据存储 6.3.1 文件的存储 6.3.2 文件的逻辑结构 6.3.3 文件的物理结构 6.3.1 文件的存储 卷是存储介质的物理单位。 物理卷和物理设备不总是一致的 。 文件和卷 单文件卷 多文件卷 多卷文件 多卷多文件 6.3.1 文件的存储 块是存储介质上连续信息所组成的一个区 域，也叫物理记录。 块是主存储器和辅助存储设备信息交换的 物理单位，每次交换一块或整数块。 决定块的大小要考虑到用户使用方式、数 据传输效率和存储设备类型等多种因素。 6.3.1 文件的存储 不同类型的存储介质，块的长短常常 各不相同；同一类型的存储介质，块 的长短也可以不同。 间隙是块之间不记

2、录用户代码信息的 区域。 6.3.2文件的逻辑结构 文件组织指文件中信息的配置和构 造方式，应该从文件的逻辑结构和 组织及文件的物理结构和组织两方 面考虑。 文件的逻辑结构和组织是从用户观 点出发，研究用户概念中的信息组 织方式，这是用户能观察到，可加 以处理的数据集合。 1 流式文件和记录式文件 6.3.2文件的逻辑结构 文件的逻辑结构分两种形式：流式文件， 记录式文件。 流式文件指文件内的数据不再组成记录， 只是依次的一串信息集合，可以看成是只 有一个记录的记录式文件。 文件常按长度来读取所需信息，也可用插 入特殊字符作为分界。 1 流式文件和记录式文件 6.3.2文件的逻辑结构 记录式文

3、件包含若干逻辑记录，逻辑 记录是文件中按信息在逻辑上的独立 含意划分的信息单位。 逻辑记录的概念被应用于许多场合， 特别象数据库管理系统中已是必不可 少的了。 1 流式文件和记录式文件 6.3.2文件的逻辑结构 逻辑记录是按信息在逻辑上的独立含义划 分的单位，块是存储介质上连续信息所组 成的区域。 一个逻辑记录被存放到文件存储器的存储 介质上时，可能占用一块或多块，也可以 一个物理块包含多个逻辑记录。 2 成组和分解 6.3.2文件的逻辑结构 成组操作。 分解操作。 块因子。 2 成组和分解 6.3.2文件的逻辑结构 2 成组和分解 逻辑记录1 逻辑记录2 逻辑记录3 物理记录 逻辑记录 用户

4、缓冲区系统缓冲区 记录成组和分解处理过程 6.3.3文件的物理结构 文件的物理结构和组织是指逻辑文件在物理 存储空间中存放方法和组织关系。 文件的存储结构涉及：块的划分、记录的排 列、索引的组织、信息的搜索，其优劣直接 影响文件系统的性能。 6.3.3文件的物理结构 第一类计算法，设计映射算法，通过对 记录键的计算转换成对应的物理块地址 ，找到所需记录。 直接寻址文件、计算寻址文件，顺序文 件均属此类。 6.3.3文件的物理结构 第二类指针法，设置专门指针，指明相 应记录的物理地址或表达各记录之间的 关联。索引文件、索引顺序文件、连接 文件、倒排文件等均属此类。 6.3.3文件的物理结构 一个

5、文件中逻辑上连续的信息存放到存储介 质的依次相邻的块上便形成顺序文件(连续文 件)。 逻辑记录顺序和物理记录顺序完全一致的文 件，通常，记录按出现的次被读出或修改。 1顺序文件(连续文件 ) 6.3.3文件的物理结构 顺序文件的优点： 顺序文件的缺点： 1顺序文件(连续文件 ) 6.3.3文件的物理结构 1顺序文件(连续文件 ) 紧凑顺序文件 扩展顺序文件 连接顺序文件 划分顺序文件 顺序文件变种 6.3.3文件的物理结构 2连接文件(串联文件 ) 连接文件使用连接字，又叫指针来 表示文件中各个记录之间的关系。 6.3.3文件的物理结构 2连接文件(串联文件 ) 文件 目录项 0 连接文件结构

6、示意图 6.3.3文件的物理结构 2连接文件(串联文件 ) 引进指向其它数据的连接表示是计算 机程序设计的一种重要手段，是表示 复杂数据关系的一种重要方法。 连接结构的优缺点。 6.3.3文件的物理结构 2连接文件(串联文件 ) 堆栈 队列 两端队列 连接文件变种 6.3.3文件的物理结构 3直接文件(哈希文件 ) 记录的关键字与其地址间可通过某种方 式建立对应关系，利用这种关系实现存 取的文件叫直接文件。 6.3.3文件的物理结构 3直接文件(哈希文件 ) hash技术要建立hash表，hash表是一个 指针数组，数组通过索引访问，找到的 指针便指向数据记录。索引是与数据记 录有关的关键字或

7、其变换 描述一座城市人口的hash文件举例。 6.3.3文件的物理结构 3直接文件(哈希文件 ) 设文件名为8个ASC字符。构造的hash 函数为模2加“”，求已知文件名的 ASC字符值的模2加值作为该文件的 FCB所在物理块在目录文件中的索引A， 那么， A= (a1a2a8) 步1 构造转换(hash)函数 6.3.3文件的物理结构 3直接文件(哈希文件 ) 目录文件采用索引结构，建立文件时由步1 求出文件名的hash值A， 凡A值相同的文件的FCB都存放在同一个物 理块。磁盘的物理块号存放在索引表中的相 对位置应等于A值。 步2 建立目录文件 6.3.3文件的物理结构 3直接文件(哈希文

8、件 ) 步2 建立目录文件 目录文件 26 A=10 26号物理块 file1文件控制块 file2文件控制块 0 10 6.3.3文件的物理结构 3直接文件(哈希文件 ) 步3 查找文件 根据给定文件名，由步1算出该文件的FCB 所在物理块号在索引表中的相对位置A。根 据A就可找到该FCB所在物理块号， 把这个物理块读入内存缓冲区，用文件名 逐个比较，找出要求的FCB。 6.3.3文件的物理结构 3直接文件(哈希文件 ) 步4 溢出处理 物理块中存放的FCB是有限的，建立目录文 件时，如果A值相同的文件数目超过物理块 能容纳数时，产生溢出。 溢出时，系统再申请一个盘区，该区物理 块号放在A+

9、k的索引表目中，k是质数作为 位移常数。 第二块盘区也溢出，则申请第三块，块号 放在A+2k表目中，依此类推。 6.3.3文件的物理结构 3直接文件(哈希文件 ) 步4 溢出处理 查找目录时，如第一块找不到可找A+k 表目中的物理块号，读出后继续比较 ，依次类推。 6.3.3文件的物理结构 4索引文件 索引结构是实现非连续存储的另一种方法， 适用于数据记录保存有随机存取存储设备上 的文件。 使用索引表，每个表目包含一个记录的键及 其记录数据的存储地址，这类文件称索引文 件。 6.3.3文件的物理结构 4索引文件 记录1 关键字 地址 记录2 记录N 文件名 索引表 块 块 块 索引区数据区 6

10、.3.3文件的物理结构 4索引文件 索引文件的优点： 索引文件的缺点： 6.3.3文件的物理结构 4索引文件 提高查找速度的办法 二级索引。二级索引表的表项列出一级索引表每 一块最后一个索引项的键值及该索引表区的地址， 若干个记录的索引本身也是一种记录。查找时先查 看二级索引表找到某键所在的索引表区地址，再搜 索一级索引表找出数据记录。 三级索引。 0 1 2 3 4 5 6 7 8 9 10 11 12 0 127 0 127 0 127 0 127 0 127 0 127 0 127 0 127 0 127 0 127 0 127 作业1 某个文件系统中，外存为硬盘， 物理块大小为512字

11、节。有文 件A，包含589个记录，每个记 录占255个字节，每个物理块 访两个记录。文件A所占的目 录如右图所示。 每个目录项占127字节。根 目录的第一块常驻内存。 若文件的物理结构采用链式存 储，链占2个字节，若将文件A 读入内存，至少访问硬盘多少 次？ 若文件为连续文件,那么要读 的487个记录至少存取硬盘多 少次？ 为减少读盘次数，可采取何种 措施？ 某个文件系统中，外存为硬盘，物理块大小为512字节。有文件A， 包含589个记录，每个记录占255个字节，每个物理块访两个记录 。文件A所占的目录如右图所示。 每个目录项占127字节。根目录的第一块常驻内存。 若文件的物理结构采用链式存储

12、，链占2个字节，若将文件A读入 内存，至少访问硬盘多少次？ 为将A读入内存，我们必须找到相关的目录信息。 由1274+2=510512可知一个物理块在链式存储结构下可放4个 目录项及链的信息。 由root起，第1次读硬盘可得bin、dev、etc、boot的信息块和下一 个物理块的地址。 第2次读盘可找到usr的地址。第3次读盘找到you的地址。第4次读 盘找到dir1的地址。第5次读盘找到A的地址。 由2552+2=512可知，一个物理块在链式存储结构下，可放2个记 录及下一个物理块的地址。而文件A共有589个记录。故读取A的所 有记录需要读硬盘的次数为589/2=295次。所以将A读入内存

13、共需 读取硬盘295+5=300次。 某个文件系统中，外存为硬盘，物理块大小为512字节。有文件A， 包含589个记录，每个记录占255个字节，每个物理块访两个记录 。文件A所占的目录如右图所示。 每个目录项占127字节。根目录的第一块常驻内存。 若文件为连续文件,那么要读的487个记录至少存取硬盘多少次？ 当文件是连续文件时，由于只需1次读盘操作即可知usr的物理地 址，故一共只需4次读盘即可找到A的地址。而知道了A的地址之后 通过计算只需1次读盘即可读出第487个记录。 作业2 一个FCB有64个字节。符号目录项占 16字节,文 件名8字节，文件号8字节。假设，物理块大小 512字节。目录文件有256个目录项。比较分解前 和分解后查找某一文件成功时的平均访盘次数。