文件的逻辑结构
标签: 操作系统
学习人数: 6762

所谓逻辑结构,指的是在用户看来,文件内部的数据应该是如何组织起来的。而物理结构指的是在操作系统看来,文件的数据是如何存放在外存中的。类似于数据结构中的逻辑结构和物理结构。算法的具体实现与逻辑结构、物理结构都有关。文件也一样,文件的操作的具体实现与文件的逻辑结构、物理结构都有关。

按文件是否有结构进行分类,可以分为无结构文件、有结构文件两种无结构文件

 

1.无结构文件

文件内部的数据就是一系列二进制流或字符流组成,又称“流式文件”。文件内部的数据实际就是一系列的字符流,没有明显的结构特性,因而对记录的访问只能通过穷举搜索的方式,因此这种文件形式对大多数应用不适用。

 

2.有结构文件

有一组相似的记录组成,又称“记录式文件”。每条记录由若干个数据项组成。例如数据库表文件。一般来说,每条记录都有一个数据项可以作为关键字,作为识别不同记录的ID。根据各条记录的长度(占用的存储空间)是否相等,又可分为定长记录和可变长记录两种。可变长记录更为灵活,能更好地利用内存空间。

①顺序文件:文件中的记录一个接一个地顺序排列(逻辑上),记录是定长或可变长的。各个记录在物理上可以顺序存储或链式存储。在访问时需要顺序搜索文件。根据记录是否按照关键字顺序排列可分为串结构和顺序结构:

串结构:记录之间的顺序和关键字无关。

顺序结构:记录之间的顺序按照关键字顺序排列。

②索引文件

索引结构为一个逻辑文件的信息建立一个索引表。索引表中的表目存放文件记录的长度和所在逻辑文件的起始位置,因此逻辑文件中不再保存记录的长度信息。索引表本身是一个定长文件,每个逻辑块可以是变长的,索引表和逻辑文件两者构成了索引文件。

索引文件的优点是可以进行随机访问,也易于进行文件的增删。但索引表的使用增加了存储空间的开销,另外,索引表的查找策略对文件系统的效率影响很大。

③索引顺序文件

索引顺序文件是索引文件和顺序文件思想的结合。索引顺序文件中,同样会为文件建立一张索引表,但不同的是,并不是每一个记录都对应一个索引表项,而是一组记录对应一个索引表项。也就是先将文件中的各个记录按照关键字进行分组,然后让索引表的表项对应一组记录,注意一个索引表项对应的是一组记录,不再是一个记录,这就大大地节省了存储空间。

索引表中包含关键字和指针两个数据项,索引表中索引项按照关键字顺序排列。索引顺序文件的逻辑文件(主文件)是一个顺序文件,每个分组内部的关键字不必有序排列,但是组与组之间的关键字是有序排列的。

索引顺序文件大大提高了顺序存取的速度,但是,仍然需要配置一个索引表,增加了存储开销。

④直接文件和哈希文件

直接文件:采用前述几种文件结构对记录进行存取时,都须利用给定的记录键值,先对线性表或链表进行检索,以找到指定记录的物理地址。对于直接文件,则可根据给定的关键字直接获得指定记录的物理地址。关键字本身就决定了记录的物理地址。

哈希(Hash)文件:这是目前应用最为广泛的一种直接文件。利用 Hash 函数(或称散列函数)可将关键字转换为相应记录的地址。为了能实现文件存储空间的动态分配,通常由 Hash 函数所求得的并非是相应记录的地址,而是指向某一目录表相应表目的指针,该表目的内容指向相应记录所在的物理块。

 



课后作业


登录后发布评论

暂无评论,来抢沙发