南京大学：《操作系统》课程教学资源（PPT课件）第六章（6.3-3）文件管理2

6.33文件的物理结构 甘辑上的文件总得以不同方式保存到物理 存储设备的存储介质上去,所以,文件 的物理结构和组织是指逻辑文件在物理 存储空间中存放方法和组织关系。这时, 文件看作为物理文件,即相关物理块的 集合。文件的存储结构涉及块的划分 记录的排列、索引的组织、信息的搜索 等许多问题。因而,其优劣直接影响文 件系统的性能

6.3.3 文件的物理结构 辑上的文件总得以不同方式保存到物理 存储设备的存储介质上去，所以，文件 的物理结构和组织是指逻辑文件在物理 存储空间中存放方法和组织关系。这时， 文件看作为物理文件，即相关物理块的 集合。文件的存储结构涉及块的划分、 记录的排列、索引的组织、信息的搜索 等许多问题。因而，其优劣直接影响文 件系统的性能

两类方法可用来构造文件的物理结构 ≮第一类称计算法,其实现原理是设计一映 射算法,例如线性计算法、杂凑法等,通 过对记录键的计算转换成对应的物理块地 址,从而找到所需记录。直接寻址文件、 计算寻址文件,顺序文件均属此类。计算 法的存取效率教高,又不必增加存储空间 存放附加控制信息,能把分成布范围较广 的键均匀地映射到一个存储区域中。 甘第二类称指针法,这类方法设置专门指针 指明相应记录的物理地址或表达各记录之 间的关联。索引文件、索引顺序文件、连 接文件、倒排文件等均属此类

第一类称计算法，其实现原理是设计一映 射算法，例如线性计算法、杂凑法等，通 过对记录键的计算转换成对应的物理块地 址，从而找到所需记录。直接寻址文件、 计算寻址文件，顺序文件均属此类。计算 法的存取效率教高，又不必增加存储空间 存放附加控制信息，能把分成布范围较广 的键均匀地映射到一个存储区域中。 第二类称指针法，这类方法设置专门指针， 指明相应记录的物理地址或表达各记录之 间的关联。索引文件、索引顺序文件、连 接文件、倒排文件等均属此类。 两类方法可用来构造文件的物理结构

顺序文件(连续文件) 甘将一个文件中逻辑上连续的信息存放到 存储介质的依次相邻的块上便形成顺序 结构,这类文件叫顺序文件,又称连续 文件 ≮这是一种逻辑记录顺序和物理记录顺序 完全一致的文件,通常,记录按出现的 次被读出或修改

顺序文件(连续文件 ) 将一个文件中逻辑上连续的信息存放到 存储介质的依次相邻的块上便形成顺序 结构，这类文件叫顺序文件，又称连续 文件。 这是一种逻辑记录顺序和物理记录顺序 完全一致的文件，通常，记录按出现的 次被读出或修改

甘顺序文件的基本优点是:顺序存取记录时 速度较快 ≮顺序文件的主要缺点是:建立文件前需要 能预先确定文件长度,以便分配存储空间; 修改、插入和增生文件记录有困难;对直 接存储器作连续分配,会造成少量空闲块 的浪费

顺序文件的基本优点是：顺序存取记录时 速度较快。 顺序文件的主要缺点是：建立文件前需要 能预先确定文件长度，以便分配存储空间； 修改、插入和增生文件记录有困难；对直 接存储器作连续分配，会造成少量空闲块 的浪费

艹紧凑顺序文件 ≮扩展顺序文件 连接顺序文件 甘划分顺序文件

紧凑顺序文件 扩展顺序文件 连接顺序文件 划分顺序文件

连接文件(串联文件) ≮连接结构的特点是使用连接字,又叫指 针来表示文件中各个记录之间的关系

连接文件(串联文件) 连接结构的特点是使用连接字，又叫指 针来表示文件中各个记录之间的关系

连接文件结构示意图 文件目录项

连接文件结构示意图 文件目录项 …… 0

甘引进指向其它数据的连接表示是计算机 程序设计的一种重要手段,是表示复杂 数据关系的一种重要方法。 甘仅适宜于顺序存取。连接结构恰好克服 了顺序结构不适宜于增、删、改等的固 有缺点,对某些操作带来很大好处,但 在其它方面又失去了一些性能

引进指向其它数据的连接表示是计算机 程序设计的一种重要手段，是表示复杂 数据关系的一种重要方法。 仅适宜于顺序存取。连接结构恰好克服 了顺序结构不适宜于增、删、改等的固 有缺点，对某些操作带来很大好处，但 在其它方面又失去了一些性能

≮●堆栈——其所有记录的插入和删除操作只能在同 端进行,这一端称栈顶。堆栈中一个‘后进先 出’型数据结构,这是因为后进入栈的记录, 定比先进入栈的所有记录先退出栈。堆栈运算有 特殊的名称,把一个新的记录插入栈中,使之成 为栈的新顶项叫下推运算;反之,删除栈顶记录 叫上推运算,大多数上推需要读取顶项记录以便 运算。 甘●队列——其记录的插入在后端进行,而删除在前 端进行,又叫‘先进先出’型数据结构。 ≮●两端队列一左右两端均可进行插入和删除记录 操作的队列

l堆栈──其所有记录的插入和删除操作只能在同 一端进行，这一端称栈顶。堆栈中一个‘后进先 出’型数据结构，这是因为后进入栈的记录，一 定比先进入栈的所有记录先退出栈。堆栈运算有 特殊的名称，把一个新的记录插入栈中，使之成 为栈的新顶项叫下推运算；反之，删除栈顶记录 叫上推运算，大多数上推需要读取顶项记录以便 运算。 l队列──其记录的插入在后端进行，而删除在前 端进行，又叫‘先进先出’型数据结构。 l两端队列──左右两端均可进行插入和删除记录 操作的队列

直接文件 ≮记录的关键字与其地址之间可以通过某 种方式建立对应关系,利用这种关系实 现存取的文件叫直接文件

直接文件 记录的关键字与其地址之间可以通过某 种方式建立对应关系，利用这种关系实 现存取的文件叫直接文件