当前位置：文档之家 › 文件的物理结构

文件的物理结构

  • 格式：ppt
  • 大小：1.03 MB
  • 文档页数：21

下载文档原格式

  / 21

合集下载

计算机操作系统第八章

计算机操作系统第八章

将每一组含有的盘块数和该组所有的盘块号，记入前一组的第一个盘块的S.free[0]～S.free[99]中。这样，各组的第一个盘块就链接成一个链表。
将第一组的盘块总数和所有的盘块号，记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。
1
2
3
4
UNIX空闲盘块的组织
文件目录是一种数据结构，由若干目录项组成，每个目录项对应其中一个文件的FCB（包括文件名、文件体的物理地址、存取控制信息等），文件体另外存放。文件目录是用于检索文件的，一般的，目录项应包括以下内容：
整个系统只设一张文件目录表，集中存放文件存储器上所有文件的FCB，这是最简单的一种目录结构。目录表存于外存中的某块固定区域，系统初启或需要时调入内存，每个文件的FCB对应目录表中的一项，通过目录表就可以管理该系统中的所有文件，包括对文件的创建、检索和删除等。
两级文件目录
把登记文件的目录分成两级：主文件目录MFD，和用户文件目录UFD 。系统为每个用户各设置一个UFD，登记本用户所有文件的信息，每个UFD相当于一个一级目录；系统再设置一个MFD，用来登记所有用户的用户名及其UFD在外存上的物理地址、长度，物理结构等属性。
01
记录式文件，在逻辑上可看成是一组记录的集合。每个记录由彼此相关的若干个数据项组成。记录式文件中的逻辑记录可依次编号，其序号称为逻辑记录号（简称记录号）。
02
文件逻辑结构
按照文件的逻辑地址顺序存取。在记录式文件中，这种操作体现为按照记录的排列顺序来进行存取。
01
文件的随机存取 随机存取是指允许用户按照记录编号或者某一数据项的值随机存取存取任一记录。
二级索引存储结构
将索引表离散存储，即将索引表本身分为若干个逻辑块，存储在若干物理盘块中，将索引表所占的各盘块号记入另一个索引表——索引表的索引表。这种结构就称两级索引结构。

文件的物理存储

文件的物理存储
大的、连续分区，将文件占用空间合并在一起。
Operating System Concepts – 7th Edition
9
Operating System Concepts – 7th Edition
10
链接结构
又称串联结构，将一个逻辑上连续的文件信息存 放在外存的不连续(或连续)物理块中。
Operating System Concepts – 7th Edition
25
解决办法
采用间接索引(多重索引)，也就是在索引表所指的物理块 中存放的不是文件信息，而是装有这些信息的物理块地址；
一级间接索引，可寻址的文件长度将变为 n*n 块； 如果文件长度还大于 n*n块的话，则二级间接索引。
由一组相邻的物理块组成，是对记录式文件取连 续区分配而构成的文件。
特点 ：顺序存取速度快
所需的磁盘寻道次数和寻道时间最少
Operating System Concepts – 7th Edition
5
Operating System Concepts – 7th Edition
6
顺序结构
对于字符流的无结构文件来说，每一个物理块中存放长 度相等的文件信息(存储文件尾部信息的物理块除外)。
对于记录式文件来说，由于记录长度既可以固定的，也 可以是可变的，而且其长度不一定刚好等于其物理块的 长度，因此,给记录从逻辑地址到物理地址的变换带来了 额外的负担。为了简单起见，假设文件系统中每个记录 的长度是固定的，且其长度正好等于物理块的长度。
索引表：存放文件信息所在的逻辑块号和与之对 应的物理块号
Operating System Concepts – 7th Edition

PDF文件结构详解

PDF文件结构详解

PDF(Portable Document Format,便携式文档结构)是一种很有用的文件格式,其最大的特点是平台无关而且功能强大(支持文字/图象/表单//音乐/视频等).做PDF的解析，首先要熟悉PDF文件的物理结构和逻辑结构。

PDF文件物理结构可分为以下几块: 1.文件头文件头是PDF文件的第一行,格式如下:%PDF-1.4这是个固定格式，表示这个PDF文件遵循的PDF规范版本，目前PDF的生成工具，除了官方的acrobat，其他生成的以1.4版本的居多。

对于做PDF开发来说，一个最简单的原则就是生成PDF的时候尽量符合低版本规范，以保证大多数解析器能支持；解析PDF的时候尽量支持高版本的规范，以保证支持大多数工具生成的PDF文件。

从1.4版本以后，PDF文件的版本并不唯一的只是在这里表示了，可能后面会改写（catalog的Version词条），所以解析PDF的时候，如果这里的版本大于等于1.4，应该再比较一下catalog里面的version，取其中高一点的版本。

2.对象集合这是一个PDF文件最重要的部分，文件中用到的所有对象,包括文本/图象/音乐/视频/字体/超连接/加密信息/文档结构信息等等,都在这里定义。

格式如下:2 0 obj ... end obj一个对象的定义包含4个部分：前面的2是对象序号，其用来唯一标记一个对象；0是生成号，按照PDF规范，如果一个PDF文件被修改，那这个数字是累加的，它和对象序号一起标记是原始对象还是修改后的对象，但是实际开发中，很少有用这种方式修改PDF的，都是重新编排对象号；obj和endobj是对象的定义范围，可以抽象的理解为这就是一个左括号和右括号；省略号部分是PDF规定的任意合法对象(一共8种，见后面附A)。

可以通过R关键字来引用任何一个对象，比如要引用上面的对象，可以使用2 0 R，需要主意的是，R关键字不仅可以引用一个已经定义的对象，还可以引用一个并不存在的对象，而且效果就和引用了一个空对象一样。

文件的结构——精选推荐

文件的结构——精选推荐

⽂件的结构⽂件的物理结构是从实现观点出发，⼜称为⽂件的存储结构，是指⽂件在外存上的存储组织形式。

⽂件的逻辑结构是从⽤户观点出发看到的⽂件的组织形式。

⽂件的逻辑结构与存储介质特性⽆关，但⽂件的物理结构与存储介质的特性有很⼤关系。

按逻辑结构，⽂件有⽆结构⽂件和有结构⽂件两种类型：⽆结构⽂件和有结构⽂件。

⽆结构⽂件（流式⽂件）⽆结构⽂件是最简单的⽂件组织形式。

⽆结构⽂件将数据按顺序组织成记录并积累保存，以字节(Byte)为单位。

由于⽆结构⽂件没有结构，因⽽对记录的访问只能通过穷举搜索的⽅式，故这种⽂件形式对⼤多数应⽤不适⽤。

但字符流的⽆结构⽂件管理简单，⽤户可以⽅便地对其进⾏操作。

所以，那些对基本信息单位操作不多的⽂件较适于⾤⽤字符流的⽆结构⽅式，如源程序⽂件、⽬标代码⽂件等。

有结构⽂件（记录式⽂件）有结构⽂件按记录的组织形式可以分为：1) 顺序⽂件。

⽂件中的记录⼀个接⼀个地顺序排列，记录可以是定长的或变长的，可以顺序存储或以链表形式存储，在访问时需要顺序搜索⽂件。

顺序⽂件有以下两种结构：第⼀种是串结构，记录之间的顺序与关键字⽆关。

通常的办法是由时间决定，即按存⼊时间的先后排列，最先存⼊的记录作为第1个记录，其次存⼊的为第2个记录，依此类推。

第⼆种是顺序结构，指⽂件中的所有记录按关键字顺序排列。

在对记录进⾏批量操作时，即每次要读或写⼀⼤批记录，对顺序⽂件的效率是所有逻辑⽂件中最⾼的；此外，也只有顺序⽂件才能存储在磁带上，并能有效地⼯作，但顺序⽂件对查找、修改、增加或删除单个记录的操作⽐较困难。

2) 索引⽂件。

如下图所⽰。

对于定长记录⽂件，如果要查找第i个记录，可直接根据下式计算来获得第i个记录相对于第⼀个记录的地址：然⽽，对于可变长记录的⽂件，要查找第i个记录时，必须顺序地查找前i-1个记录，从⽽获得相应记录的长度L，然后才能按下式计算出第i个记录的⾸址：注意：假定每个记录前⽤⼀个字节指明该记录的长度。

5-6 文件的物理结构

5-6 文件的物理结构
索引文件的缺点是：增加了索引表的 空间开销和查找时间
索引表的组织
一级索引 两级索引 多级索引
一种多级索引结构
0
1
…
…
…
2
3 4 5 6 7 8 9 10
0 … 127
0 … 127
…
… …
0 … 127
0
0 … 127
0
0 … 127
… 127
… 127
… 0
… … …
11 12
… 0
将一个文件中逻辑上连续的信息存放 到存储介质的依次相邻的块中便形成 顺序结构，这类文件叫顺序文件，又 称连续文件
磁带文件、光盘文件是典型例子
顺序文件的优缺点
优点：顺序存取记录时速度较快 批处理文件，系统文件用得最多
采用磁带存放顺序文件时，总可以保持快 速存取的优点
缺点：建立文件前需要能预先确定文件长度， 以便分配存储空间；修改、插入和增加文件 记录有困难
计算机操作系统
5文件管理 – 5.2 文件的组织 5.2.4 文件的物理结构
文件的物理结构
文件的物理结构和组织是指文件在物 理存储空间中的存放方法和组织关系
又称为物理文件
文件的存储结构涉及块的划分、记录 的排列、索引的组织、信息的搜索等 许多问题
其优劣直接影响文件系统的性能
顺序文件
索引文件的访问方式
索引文件在文件存储器上分两个区： 索引区和数据区
访问索引文件需两步操作：第一步查 找索引表，第二步获得记录物理地址
需要两次访问辅助存储器，若文件索 引已预先调入主存储器，那么，就可 减少一次内外存信息交换
索引文件的特点
索引结构可以被认为是连接结构的一 种扩展，除了具备连接文件的优点外， 还克服了它只能作顺序存取的缺点， 具有直接读写任意一个记录的能力， 便于文件的增、删、改

文件的逻辑结构

文件的逻辑结构

2. 无结构文件
如果说大量的数据结构和数据库，是采用有结构的文件形式的话，则大 量的源程序、 可执行文件、 库函数等， 所采用的就是无结构的文件形式， 即流式文件。 其长度以字节为单位。对流式文件的访问，则是采用读写 指针来指出下一个要访问的字符。可以把流式文件看作是记录式文件的一 个特例。在UNIX系统中，所有的文件都被看作是流式文件；即使是有结 构文件，也被视为流式文件；系统不对文件进行格式处理。
2. 顺序文件的优缺点
顺序文件的最佳应用场合，是在对诸记录进行批量存取时， 即每次要
读或写一大批记录。此时，对顺序文件的存取效率是所有逻辑文件中最高
的；此外，也只有顺序文件才能存储在磁带上， 并能有效地工作。
在交互应用的场合，如果用户(程序)要求查找或修改单个记录，为此
系统便要去逐个地查找诸记录。 这时， 顺序文件所表现出来的性能就可
能很差， 尤其是当文件较大时， 情况更为严重。 例如，有一个含有104 个记录的顺序文件，如果对它采用顺序查找法去查找一个指定的记录，则
平均需要查找5×103个记录； 如果是可变长记录的顺序文件，则为查找 一个记录所需付出的开销将更大，这就限制了顺序文件的长度。
1.3 索引文件
对于定长记录文件，如果要查找第i个记录， 可直接根据下式计算来获得 第i个记录相对于第一个记录首址的地址： Ai=i×L
操作系统
文件的逻辑结构
对于任何一个文件，都存在着以下两种形式的结构： （1）文件的逻辑结构(File Logical Structure)。 (2) 文件的物理结构， 又称为文件的存储结构， 是指文件在外存上的存 储组织形式。
1.1 文件逻辑结构的类型
1. 有结构文件 (1) 定长记录。 (2) 变长记录。 (1) 顺序文件。 (2) 索引文件。 (3) 索引顺序文件。

计算机操作系统典型例题解析之五

计算机操作系统例题及解析之五【例1】什么是文件？什么是文件系统？答：文件是在逻辑上具有完整意义的信息集合，它有一个名字作标识。

文件具有三个基本特征：文件的内容为一组相关信息、文件具有保存性、文件可按名存取。

文件系统是操作系统中负责管理和存取文件的程序模块，也称为信息管理系统。

它是由管理文件所需的数据结构（如文件控制块、存储分配表）和相应的管理软件以及访问文件的一组操作所组成。

【例2】什么是文件的物理结构和逻辑结构？答：文件的逻辑结构是从用户观点出发所看到的文件组织形式，是用户可以直接处理的数据及其结构。

文件的逻辑结构有两种形式：有结构的记录文件和无结构的流式文件。

文件的物理结构是指文件在外存上的存储组织形式。

文件的物理结构有三种形式：顺序结构、链接结构和索引结构。

【例3】假定盘块的大小为1KB，硬盘的大小为500MB，采用显示链接分配方式时，其FAT 需要占用多少存储空间？答：FAT的每个表项对应于磁盘的一个盘块，其中用来存放分配给文件的下一个盘块的块号，故FAT的表项数目由物理盘块数决定，而表项的长度则由磁盘系统的最大盘块号决定（即它必须能存放最大的盘块号）。

为了地址转换的方便，FAT表项的长度通常取半个字节的整数倍，所以必要时还必须由最大盘块号获得的FAT表项长度作一些调整。

由题意可知，该硬盘共有500K个盘块，故FAT中共有500K个表项；如果盘块从1开始编号，为了能保存最大的盘块号500K，该FAT表项最少需要19位，将它扩展为半个字节的整数倍后，可知每个FAT表项需20位，即2.5个字节。

因此，FAT需占用的存储空间的大小为：2.5×500K=1250KB【例4】存放在某个磁盘上的文件系统，采用混合索引分配方式，其FCB中共有13个地址项，第0～9个地址项为直接地址，第10个地址项为一次间接地址，第11个地址项为二次间接地址，第12个地址项为三次间接地址。

如果每个盘块的大小为4K字节，若盘块号需要用4个字节来描述，请问该系统中允许的文件的最大长度是多少？答：由题意可得，每个盘块最多存放4K/4＝1K个盘块地址。

文件的物理结构及存储设备ppt

8.2.2 文件的物理结构及存储设备
(3) 索引文件 索引文件是由系统为每个文件建立一张索引表，表中 标明文件的逻辑块号所对应物理块号，索引表自身的物理 地址由FCB给出。
索引表结构 ：
FCB . . 文件 A 索引表指针 . . 文件 A 的索引表 记录号 0 1 2 物理块号 4 4 7 10 R2 7 R3 10 R1
04 14 24 34 44 54
05 15 25 35 45 55
06 16 26 36 46 56
07 17 27 37 47 57
08 18 28 38 48 58
09 19 29 39 49 59
8.2.2 文件的物理结构及存储设备
如果索引表很大，超过了一个物理块，则系 统势必要像处理其他文件一样，来处理索引表的 物理存放方式，这样不利于索引表的动态增删。 解决的办法是采用多重索引的方式，也就是说， 当索引表所指的物理块超过一块时，再增加一个 次级索引表。这样，在高一级索引表表项里所指 向的物理块中并不存放实际的文件信息，而是存 放的一个索引表，在这个次一级的索引表中所指 向的物理块才是存放的文件信息。如果需要，可 以增加到3级以上的多级索引。
(Used in BSD Unix)
(filename is not stored in the inode)
index block
. . .
8.2.2 文件的物理结构及存储设备
2. 文件的存储设备 文件的存储设备分为不可重复使用的 和可重复使用的两类。 不可重复使用的文件存储设备也称为 I/O式字符设备，如打印纸等。 可重复使用的文件存储设备有磁带、 磁盘、光盘等，也称块设备。
链接索引块
directory entry

文件的物理结构

实现逻辑块号到物理块号的转变： 从目录中可知索引表存放位置，将索引表从外存读入内存，并查找索引表即可只i号逻辑块在外存中的存放位置。 索引分配的方式支持随机访问，文件拓展也很容易实现（只需给文件分配一个空闲块，并增加一个索引表项即可）但是索引表需要占用一定 的存储空间 出现为问题：当一个磁盘块装不下文件的整张索引表，
索引分配允许文件离散的分配在各个磁盘块中系统会为每个文件建立一张索引表索引表中记录了文件各个逻辑块对应的物理块索引表的功能类似于内存管理中的页表建立逻辑页面到物理页之间的映射关系
文件的物理结构（文件分配方式）
文件的物理结构
操作系统需要对磁盘进行哪些管理？ 对非空闲磁盘块的管理（存放了文件数据的磁盘块）/文件的物理结构/文件分配方式要探讨的问题/ 对空闲磁盘块的管理/文件存储空间管理要探讨的问题
文件的物理结构（文件的分配方式）
连续分配，链接分配（隐式链接，显示链接），索引分配
文件块，磁盘块
类似于内存分页，磁盘中的存储单元也会分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块，页面的大小相同 内存与磁盘之间的数据交换（即读/写操作,磁盘I/O）都是以‘’块‘为单位进行的，即每次读入一块，或每次写出一块。 在内存管理中，进行的逻辑地址空间被分为一个一个页面。同样的在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间也被分 为了一个个的文件块。
链接方案
如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来放
缺点：若想要访问文件的最后一个逻辑块，就必须找到最后一个索引块（第256个索引块），而各个索引块之间是用指针链接起来的，因此 必须先顺序地读入前255索引快，这显然效率是很低的
多层索引
建立多层索引（原理类似于多级页表），使第一层索引快指向第二层的索引快。还可根据文件大小的要求再建立第三层，第四层索引快。 采用K层索引结构，且顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作

文件的结构及存取方法


（2）链接文件 结构是把把每个 物理块的最后一 个单元用作指针， 指向下一个物理 块的地址，通过 指针链接形成物 理文件结构。如 图5.2所示。
返回
图5.2
使用链接文件结构时，在文件说明信息 中只需指明该文件的第一个物理块号就行了。 链接文件的优点是不要求对各个文件分配连 续存储空间，解决了外零头空间问题，提高 了存储空间利用率；文件长度可以动态增长， 只要调整链接指针就可以在任何一个信息块 之间插入或删除一个信息块。链接文件结构 一般适用于逻辑上连续的文件，且存取方法 应是顺序存取的。对随机存取文件，其存取 速度慢，因为只能按链接指针从头至尾顺序 搜索。
式文件的一个特例。在UNIX系统中，所有的文件都被看作是流式文
件，即使是有结构文件，也被视为流式文件，系统不对文件进行格
式处理。
返回
文件的物理结构是指文件在外存上的存储组织方
式。事实上，由于文件的物理结构决定了文件信息在
外存上的存储位置，因此，文件信息的逻辑块号（逻
辑地址）到物理块号（物理地址）的变换是由文件的
（1）空闲链表
空闲链表是将所有空闲空间以空闲块或空闲盘区(每个盘区可包含多 个块)为单位形成一个链表。
对以空闲块为单位形成的链表，称为空闲盘块链。分配存储空间时， 系统从链首依次择取所需的空闲块，回收空闲空间时，释放的空闲块 逐个链入链尾。对以空闲盘区为单位形成的链表，称为空闲盘区链。 空闲盘区链中的结点应包含本盘区拥有的盘块数和下一个空闲盘区结 点的指针。在回收盘区时，要对相邻盘区进行合并。
根据用户和系统管理上的需要，可采用多种方式来组织这些记录， 形成不同的记录文件结构：
（１）连续结构。按记录存入文件的先后次序排列，与文件内容 无关。查找时，只能从第一个记录开始顺序查找，查找效率低， 但有利于记录的追加和修改。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

散列算法的基本思想是根据关键字来计算相应记录的 地址，所以必须解决如下两个问题： 1）寻找一个hash函数h（k）实现关键字到地址的转 换。 2）确定解决冲突的办法。 常用的散列算法有： 1）截断法：截取关键字的某一指定部分作为地址。 这里所以截段是为了缩小关键字的数值范围，且截取时应 选取随机性较好的段。 2）特征位抽取法：抽取关键字数码串的某些位并将 其联结起来作为地址。这种方法既可起到缩小关键字数值 的作用，又能更灵活有效地选择那些随机性较好的数位。 3）除余法：把标识符除以某一数而取其余数作为地 址。使用这种方法时，除数的选择非常重要。
逻辑记录也很简单，如图1.4所示。系统获得所需要的块 数并调整第一块和最后一块的指针。
ri
ri+1
150
New
rj
当前链接 新的链接
图1.3 插入一个新的逻辑记录（情况1）
last block
first block
ri
rj+1
150
new j
r
new j
r
new j
r
当前链接
新的链接
图1.4 插入一个新的逻辑记录（情况2）
三、串联文件
1、串联文件结构 串联文件结构就是指文件内容放置地不连续的外存 区域（块），文件所占用的外存块通过指针串接起来。每 个物理块的最末一个字根或第一个字）作为链接字，它指 出后继块的物理地址。文件的最后一块的链接字为结束标 记“∧”，它表示文件至本块结。如图1.2所示，一个文 件A有三个记录，分别分配到100、150、57号物理块中， 它的第一个物理块号由文件目录的该文件目录项指出。
文件目录
磁盘块号 100 文件 A 3 100 101 102
ro
r1
r3
图1.1 连续文件结构
2、连续文件的优点 连续文件结构的基本优点是：在连续文件存取时速 度较快；如果文件中第n个记录刚被存取过，而在下一个 要存取的是第n+1个记录，则这个存取操作将会很快完成。 当连续文件在顺序存取设备（或称单一存储设备，如磁带） 上时，这一优点是很明显的。 所以，存于磁带上的记录一般均 采用连续结构。连续文件结构对 于变化少、可以作为一个整体处 理的大量数据段较为方便，而对 于变化频繁的少量记录不宜采用。 对于连续文件结构来说，其 文件长度一经固定便不易改变， 因而不利于文件的增生和扩充。
3）、一个物理块有几个逻辑记录 当存取一个记录时，将整个物理块读进主存。文件 管理系统必须从这个物理块中提取所需的那个逻辑记录。 附加一个新的逻辑记录是困难的，因为如果这个物理块已 满，一个或几个当前居留者要移到新的一块中去。通常， 一个逻辑记录是不能被分割在两个物理块中的。 3、一种具有双向查找能力的串联文件结构 这种结构实现方式是在一个逻辑记录的内容后增加 一个前驱指针,将前驱指针和后继指针做异或保存起来。 对记录ri所在的物理块而言，其链接指针值为： Link(ri)=pbn(ri-1) ⊕pbn(ri+1) 其中，pbn为物理块号。注意，其首末物理块中的指针值 为其相邻物理块的块号与0的“异或”值。
邵东夏
/
• 教学目标:了解文件的几种物理结构
及特点
• 重点、难点:三种文件结构之间的区
别
一、概述 二、连续文件 三、串联文件 四、文件映照 五、随机文件 六、文件物理结构比较
一、概述
1、文件结构的定义 文件物理结构涉及文件在存储器上的安排。文件结 构 表示了一个文件在辅存上的安置、链接和编目的方法。 它 和文件的存取方法以及辅存设备的特性等都有密切的关 系。 2、文件结构的分类 大多数字符设备的信息可作为连续文件看待。这种 文件的信息是按线性为序存取的，这种方法在大多数磁带 系统中使用，是比较简单的文件结构。磁盘存储设备上具 有较为复杂的文件组织。 磁盘的结构允许文件管理系统按三种不同的方法组 织文件：连续文件、串联文件、随机文件。
3）随机文件不仅可以实现不连续存放，而且可以实 现随机访问，但系统开销太大。 相比之下，随机文件是一种比较好的结构，便于直 接存取，但问题是，对于索引文件应考虑如何有效地存储 和访问索引表，对于散列文件应寻找一个较好的散列算法 的确定解决冲突的办法。
文件目录
磁盘块号 100
文件 A 100
磁盘块号 150
磁盘块号 57
r0
150
r1
57
r3
∧
1.2
串联文件结构
串联文件采用的是一种非连续的存储结构,文件的逻 辑 记录可以放到不连续的物理块中,能较好地利用辅存空 间。对于串联文件而言，为了找到一个记录，文件必须从 文件头开始一块一块查找，直到所需的记录被找到。 2、串联文件的处理 在处理串联文件应考虑以下三种情况。 1）、一个逻辑记录对应一个物理块 要求存取一个逻辑记录时只将一个物理块存入主存 中。插入一个新的逻辑记录是很容易的，系统只需调节指 针就行了，如图1.3所示。 2）、为了存取一个逻辑记录，必须将该逻辑记录对 应的物理块全部读到主存。存取一个逻辑记录所需的时间 取决于物理块的数目，因为必须将每一个物理块读到主存， 然后检查其指针，以找到下一个记录。附加一个新的
4）折叠法：把关键字数码串分段，然后叠加起来作 为地址。有时，还可以把折叠的结果再折叠。 5）平方取中法：把关键字平方后取其结果的作为地 址。 记录的关键字的值作为hash函数的自变量，计算 hash函数的值作为该记录所占外存块的块号（地址），若 不同记录的hash函数值相同，再进行调整，使其中一个记 录的值做适当变化，被改变的值集中到一张表中。
为了能随机地访问文件的任何一部分，构造了索引 文件。索引文件在存储区中占两个区：索引区和数据区。 索引区存放索引表，数据区存放数据文件本身。 访问索引文件需要两步操作。第一步是查文件索引， 由逻辑块号查得物理块号，再由此物理块号而获得所要求 的信息。这样做需要两次访问文件存储器。如果文件索引 表已经预先调入主存，则只要一次访问就行了。 一般索引表的索引页的排序量遵循记录编号或关键 字值，做升序或降序排列，故查找逻辑记录时可采用二分 法等高效的方法。 3、计算寻址结构——散列文件 在计算寻址结构方法中，记录的关键字经过某种计 算处理，转换成相应的地址。这种计算方式就是通常所说 的的散列（hash，也称为“杂凑”）。
六、文件物理结构比较
文件的物理结构和存取方法与系统的用途和物理设 备有关。比如，磁带和慢速字符设备上的文件对应组织为 连续文件，故采用顺序存取方法。很显然，在磁带上组织 索引文件或串联文件不太合适，因为来回倒带定位花费的 时间太大。对于磁盘（鼓）那样的设备，可以有多种结构 和存取方法。 可以总结出它们的区别如下： 1）连续文件的优点是不需要额外的空间开销，但容 易形成外存碎片，文件内容不易扩充。 2）串联文件可以实现不连ቤተ መጻሕፍቲ ባይዱ存放，但不能实现随机 访问。
四、文件映照
FTP只给出文件所占用的第一个外存设的编号，后 续的外存块查文件映照表可知。如图1.5所示。
文件目录 0 1 文件A 3 2 3 4 5 6 7 8 图1.5 文件映照表 ∧ 4 6 8
五、随机文件
随机文件组织是实现非连续分配的另一种方案。有 三种形式的随机文件结构：直接地址结构、索引结构和计 算机寻址结构。 1、直接地址结构 当知道某个记录的地址时，可直接使用这个地址进 行存取。这意味着，用户必须知道每个记录的具体地址， 这是很不方便的。因此，直接地址结构并不常用。当然在 使用这种结构时，存取效率是最高的，因为不需要进行任 何“查找”。在某些数据库系统中的“数据库码”，就是 采用这种结构。 2、索引结构——索引文件
二、连续文件
1、连续文件结构特点 连续文件结构是由一组分配在磁盘连续区域的物理 块组成的，如图1.1所示。文件中的每一个记录有一个序 号，序号为i+1的记录，其物理位置一定紧跟在i号记录之 后。图中表示一个连续文件A，它由三个记录组成，这些 记录被分配到物理块号为100、101、102的相邻物理块中， 这里假定文件的逻辑记录和物理块的大小是相等的（当然 也可以是一个物理块包括几个逻辑记录或一个逻辑记录占 有一个物理块）。对于这种文件结构，存取块中的一个记 录是非常简单的。若给定记录号r，记录长度为l，物理结 构大小为size，则相对块号计算为： b=l×r/size