若允许文件能分别在开始、中间、末尾增长,试讨论在顺序式、链接式以及索引式文件物理组织之下的开销。
[1]
顺序结构
顺序结构又称连续结构,这是一种最简单的文件物理结构,它把逻辑上连续的文件信息依次存放在连续编号的物理块中。也就是说,如果一个文件长N块,并从物理块号A开始存放,则该文件占据物理块号A、A+1、A+2、 .... A+N-1。在顺序结构中,一个文件的目录项中,只要指出该文件占据的总块数和起始块号即可。
(2) 优点
顺序结构的优点是,一旦知道了文件在文件存储设备上的起始块号和文件长度,就能很快地进行存取。这是因为从文件的逻辑块号到物理块弓的变换是非常简单的。另外顺序结构支持顺序存取和随机存取。对于顺序存取,顺序的存取速度快。
(3)缺点
顺序结构的缺点在于,文件不能动态增长。
对于顺序结构的文件,电请新的空闲空间时,如果该文件长N块,必须找到连续的N个空闲块,才能存放该文件,相对来说查找速度较慢。有可能出现找不到满足条件的连续的N个空闲块的情况,也不利于文件插入和删除。(本题的开销)
另外,随着文件不停地被分配和被删除,空闲空间逐渐被分割为很小的部分,最终导致出先存储碎片,此时虽然空间的总空闲数比申请的要多,但却因为不连续,都是小碎片而无法分配。解决.上述问题的根本方法是采取不连续分配,以下两种分配方式都是不连续。
当然,还要确定文件最大长度。
[2] 链接结构
(1) 原理
(2)优点
链接结构的优点是,存储碎片问题迎刃而解了,有利于文件动态扩充,有利于文件插入和删除,提高了磁盘空间利用率。在开始、中间、末位插入,对入磁盘的量不一样,但是不需要移动物理块。
存取速度慢,不适合随机存取文件;磁盘的磁头移动多,效率相对较低:存在文件的可靠性问题,比如指针出错,文件也就出错了。另外,链接指针需要占网一定的空间。每一次查找文件,都得从头开始遍历查找。超找的开销,跟查找的位置有关系。很相似与遍历链表超找某一个值的查找次数很类似。读者自已可以算算
[3] 索引结构
索引结构的文件把每个物理盘块的指针字,集中存放在称为索引表的数据结构中的内存索引表中。在每个文件相应的目力条目中包括该文件的索引表地址, 而索引表中的第I个条目指向文件的第I块。这样,要读某个文件的第I块,只需从该文件索引表的第I个条目中得到该文件块的地址就行了。
索引文件结构保持了链接结构的优点,又解决了其缺点。索引结构文件既适于顺序存:取;也适用于随机存取。这是因为有关逻辑块号和物理块号的信息全部保存在了一个集中的索引表中,而不是像链接文件结构那样分散在各个物理块中。索引文件可以满足文件动态增长的要求,也满足了文件插入、删除的要求。索引文件还能充分利用外存空间。
会引起较多的寻道次数和寻道时间;索引表本身增加了存储空间的开销。显然,如果文件很大,它的文件索引表也就较大。如果索引表的大小超过了一个物理块,那么也必须决定索引表的物理存放方式。
在索引结构文件中要查找文件,要顺着链进行查找,但是整个索引表都可以存放在内存中,不需要访问磁盘,不管文件有多太,在目录项中只需记录一个起始块号,按照它就可以找到文件的全部块。
另外,在索引结构文件中要存取文件时,需要至少访向存储设备二次以上。其中,一次是访问索引表,另一次是根据索引表访问在存储设备上的文件信息。这样势必降低了对文件的存取速度。 另外,索引的级数越多,找到物理块的开销也越大。
索引结构对空间的占用比较严重。这是因为大多数文件都是小文件,如果一个文件系统中索引表是定长的话,那么即使一个文件仅占一-两个盘块,也同样需要一整个索引表。如果为了加快存取速度而把索引表放在内存,那么要占用的空间对内存来说是非常大的。
这道题你会答吗?花几分钟告诉大家答案吧!
扫描二维码,关注牛客网
下载牛客APP,随时随地刷题
[1]
顺序结构
顺序结构又称连续结构,这是一种最简单的文件物理结构,它把逻辑上连续的文件信息依次存放在连续编号的物理块中。也就是说,如果一个文件长N块,并从物理块号A开始存放,则该文件占据物理块号A、A+1、A+2、 .... A+N-1。在顺序结构中,一个文件的目录项中,只要指出该文件占据的总块数和起始块号即可。
(2) 优点
顺序结构的优点是,一旦知道了文件在文件存储设备上的起始块号和文件长度,就能很快地进行存取。这是因为从文件的逻辑块号到物理块弓的变换是非常简单的。另外顺序结构支持顺序存取和随机存取。对于顺序存取,顺序的存取速度快。
(3)缺点
顺序结构的缺点在于,文件不能动态增长。
对于顺序结构的文件,电请新的空闲空间时,如果该文件长N块,必须找到连续的N个空闲块,才能存放该文件,相对来说查找速度较慢。有可能出现找不到满足条件的连续的N个空闲块的情况,也不利于文件插入和删除。(本题的开销)
另外,随着文件不停地被分配和被删除,空闲空间逐渐被分割为很小的部分,最终导致出先存储碎片,此时虽然空间的总空闲数比申请的要多,但却因为不连续,都是小碎片而无法分配。解决.上述问题的根本方法是采取不连续分配,以下两种分配方式都是不连续。
当然,还要确定文件最大长度。
[2] 链接结构
(1) 原理
(2)优点
链接结构的优点是,存储碎片问题迎刃而解了,有利于文件动态扩充,有利于文件插入和删除,提高了磁盘空间利用率。在开始、中间、末位插入,对入磁盘的量不一样,但是不需要移动物理块。
(3)缺点
存取速度慢,不适合随机存取文件;磁盘的磁头移动多,效率相对较低:存在文件的可靠性问题,比如指针出错,文件也就出错了。另外,链接指针需要占网一定的空间。每一次查找文件,都得从头开始遍历查找。超找的开销,跟查找的位置有关系。很相似与遍历链表超找某一个值的查找次数很类似。读者自已可以算算
[3] 索引结构
(1) 原理
索引结构的文件把每个物理盘块的指针字,集中存放在称为索引表的数据结构中的内存索引表中。在每个文件相应的目力条目中包括该文件的索引表地址, 而索引表中的第I个条目指向文件的第I块。这样,要读某个文件的第I块,只需从该文件索引表的第I个条目中得到该文件块的地址就行了。
(2) 优点
索引文件结构保持了链接结构的优点,又解决了其缺点。索引结构文件既适于顺序存:取;也适用于随机存取。这是因为有关逻辑块号和物理块号的信息全部保存在了一个集中的索引表中,而不是像链接文件结构那样分散在各个物理块中。索引文件可以满足文件动态增长的要求,也满足了文件插入、删除的要求。索引文件还能充分利用外存空间。
(3)缺点
会引起较多的寻道次数和寻道时间;索引表本身增加了存储空间的开销。显然,如果文件很大,它的文件索引表也就较大。如果索引表的大小超过了一个物理块,那么也必须决定索引表的物理存放方式。
在索引结构文件中要查找文件,要顺着链进行查找,但是整个索引表都可以存放在内存中,不需要访问磁盘,不管文件有多太,在目录项中只需记录一个起始块号,按照它就可以找到文件的全部块。
另外,在索引结构文件中要存取文件时,需要至少访向存储设备二次以上。其中,一次是访问索引表,另一次是根据索引表访问在存储设备上的文件信息。这样势必降低了对文件的存取速度。 另外,索引的级数越多,找到物理块的开销也越大。
索引结构对空间的占用比较严重。这是因为大多数文件都是小文件,如果一个文件系统中索引表是定长的话,那么即使一个文件仅占一-两个盘块,也同样需要一整个索引表。如果为了加快存取速度而把索引表放在内存,那么要占用的空间对内存来说是非常大的。