软考--操作系统之文件系统多级索引-Toy模板网

这篇具有很好参考价值的文章主要介绍了软考--操作系统之文件系统多级索引。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

概念

索引结构

一个文件的信息存放在若干不连续物理块中
系统为每个文件建立一个专用数据结构——索引表，并将这些物理块的块号存放在该索引表中
索引表就是磁盘块地址数组，其中第i个条目指向文件的第i块
索引块的块号放在FCB(文件控制块)里，通过查找到FCB就可以得到索引表，然后就可以知道文件的每一块放在什么地方了
软考--操作系统之文件系统多级索引

索引表

软考--操作系统之文件系统多级索引
检索过程，分两步，首先查找索引表，如果存在该记录，则根据索引项的指示读取外存。
如果索引表很大，可以再为索引表建立查找表。如下图：

索引方式

文件系统使用索引来标识文件和目录,帮助快速定位。
传统的索引方式是一级索引,即文件和目录直接对应一个索引值。
多级索引则采用层次索引方式:
第一级索引:划分一大块空间,每个空间对应一个第一级索引。
第二级索引:在第一级索引对应空间内再划分,对应第二级索引。
第三级索引…依次类推,可以设置多个等级。

一级索引

软考--操作系统之文件系统多级索引

多级索引

软考--操作系统之文件系统多级索引
多级索引为文件系统带来的优势:

索引利用率高:通过分层组织,空余的索引可供其他文件和目录使用。
查找效率高:高级索引将搜索范围缩小到较小空间,降低比较次数。
扩展性好:可以动态添加高级索引,满足空间不断增加的需要。

今天主要讨论多级索引，以软考真题为例

真题分析

题目1-存储文件最大长度

软考--操作系统之文件系统多级索引

解析

磁盘块大小为1K，每个块号占3B，那么一个物理块可放：1024/3=341个地址项，即：
一个一级索引可存放的文件大小为：3411
一个二级索引可存放文件的大小为：341×3411=116281
一个三级索引可存放文件的大小为：341×341×341*1=39651821

多级索引公式
软考--操作系统之文件系统多级索引
上题中物理块是1K,就是1024B,最后求的单位也是多少K,所以不涉及单位的转换。

题目2-多级索引占用物理块号

软考--操作系统之文件系统多级索引

解析

此题属于混合索引形式，索引表中既有直接索引，又有多级索引。每一个地址项指的是索引表中一行。

解题思路如下图所示
1、0-4这5个地址项存储为直接地址索引，存储在物理块0-4块上，一个地址项对应一个物理块
2、5，6地址项为一级间接地址项，磁盘索引块和磁盘数据块分别为1K,也就是1024B,每个地址项4B,一个磁盘数据块可以存储1024/4=256个地址，此时，接上面的物理块号5开始，256个地址对应的物理块号为5-260块，同理，下一个物理块号是261-516
3、再来看看剩下的一个二级间接地址：1024/4=256个地址项，每一个又分别对应256个物理块，接相面的516块，从517开始-772块，是上面256个地址项中的第一个地址项对应的物理块号。依次往下，结束的时候是多少块号呢？256×256+516=66052
软考--操作系统之文件系统多级索引
分析完之后，来看上题中的问题是不是一目了然了。