逻辑结构与物理结构

逻辑结构是用户视角下文件内部数据如何组织。物理结构是操作系统视角下文件数据如何存放到外存块中。

同一个逻辑结构可以用不同物理结构实现。比如顺序文件在用户看来是一组有先后关系的记录，但这些记录对应的文件块在外存中可以连续分配、链接分配，也可以索引分配。

随机访问的两层含义

文件逻辑结构支持随机访问，是指可以根据记录号直接算出记录的逻辑地址。文件物理结构支持随机访问，是指操作系统可以较快把逻辑块号转换为物理块号。这两件事不是同一层问题。

# 无结构文件与有结构文件

类型	含义	例子
无结构文件	文件内部是一串二进制流或字符流，也称流式文件	文本文件
有结构文件	文件由一组相似记录组成，也称记录式文件	数据库表文件

有结构文件中的基本单位：

数据项：文件系统中最基本的数据单位。
记录：一组相关数据项的集合。
关键字：记录中可用于识别不同记录的数据项。

有结构文件按记录长度又可分为：

类型	特点
定长记录	每条记录长度相同，各字段位置固定
可变长记录	记录长度不固定，通常需要额外记录长度或分隔信息

有结构文件按记录组织形式分类：顺序文件、索引文件、索引顺序文件。

顺序文件

顺序文件中的记录在逻辑上一个接一个排列。记录可以定长，也可以可变长；物理上可以顺序存储，也可以链式存储。

定长记录并且物理顺序存储时，可以直接计算第 $i$ 条记录的位置：

$$
\text{address}(i)=\text{start}+i\times L
$$

其中 $L$ 是每条记录长度。这种情况下可以快速定位第 $i$ 条记录。

顺序文件的特点：

情况	访问特点
定长记录 + 顺序存储	支持随机访问；若按关键字有序，还可快速检索
可变长记录	通常需要从头扫描前面的记录才能定位目标记录
链式存储	逻辑上有序，物理上不一定相邻

顺序文件增加或删除记录通常不方便。若记录在物理上顺序存储，插入或删除可能需要移动大量记录。

索引文件

对于可变长记录，若要快速找到第 $i$ 条记录，可以为文件建立索引表。索引表的每个索引项记录某条记录的长度、指针或关键字等信息。

索引文件的特点：

索引表本身通常是定长记录的顺序文件。
可以快速找到第 $i$ 个索引项，再通过索引项找到目标记录。
若索引项按关键字排序，还可以支持按关键字折半查找。
可以按不同数据项建立多个索引表。

两种“索引表”不要混淆

索引文件的索引表由用户或文件内容组织方式决定，映射“关键字或记录号 -> 记录逻辑地址”。
索引分配中的索引表由操作系统维护，映射“逻辑块号 -> 物理块号”。

索引文件的问题是索引表可能很大。若每条记录都对应一个索引项，而记录本身很小，索引表甚至可能比数据本身更占空间。

索引顺序文件

索引顺序文件结合了索引文件和顺序文件。它不是每条记录对应一个索引项，而是一组记录对应一个索引项。

检索过程：

先查索引表，找到目标关键字可能所在的分组。
再在该分组中顺序查找目标记录。

若文件有 $N$ 条记录，分成 $m$ 组，每组 $\frac{N}{m}$ 条记录，则平均查找次数约为：

$$
\frac{m}{2}+\frac{N}{2m}\geqslant \sqrt{N}
$$

当仅当 $m = \sqrt{ N }$ 时取等号

显然，引入多级索引顺序文件还可以进一步降低查找次数。

目录与 FCB

目录是一种特殊的有结构文件。目录中的每条记录对应一个文件或子目录，这条记录称为目录项。

FCB 是文件控制块。一个 FCB 就是一个文件目录项，FCB 的有序集合就是文件目录。

FCB 通常包含：

内容	作用
文件名	实现按名查找
类型	区分普通文件、目录、链接文件等
存取权限	用于文件保护
物理位置	指向文件数据或索引结构在外存中的位置
逻辑结构、物理结构	决定如何解释和定位文件内容
时间、所有者等信息	文件管理和保护所需的元数据

FCB 实现了文件名到文件实体的映射，因此用户可以按名存取文件。

1000

目录操作

目录系统至少要支持：

操作	含义
搜索	根据文件名找到对应目录项
创建文件	在目录中增加目录项
删除文件	从目录中删除目录项，并配合回收文件空间
显示目录	显示目录中所有文件及其属性
修改目录	文件重命名、属性变化时修改目录项

目录结构

单级目录

整个系统只有一张目录表。它实现简单，但所有文件共享同一命名空间，不允许重名，不适合多用户系统。

两级目录

两级目录分为：

MFD：主文件目录，记录用户名及其用户文件目录位置。
UFD：用户文件目录，由该用户文件的 FCB 组成。

两级目录允许不同用户使用相同文件名，也可以在用户目录层面做访问限制。但用户仍不能灵活分类自己的文件。

树形目录

树形目录也称多级目录。路径从根目录开始逐级定位文件，能够清晰分类文件，并支持不同目录下重名。

绝对路径从根目录开始，例如：

1	/照片/2015-08/自拍.jpg

相对路径从当前目录开始。设置当前目录后，访问同一目录附近的文件不必每次从根目录重新查找，可以减少目录读取次数。

无环图目录

树形目录不便共享文件。无环图目录允许多个目录项指向同一个文件或目录节点，用有向无环图表达共享关系。

共享节点通常设置共享计数器。删除某个目录项时，只减少共享计数；只有计数变为 0，才真正删除共享节点。

inode

查找目录时，最常用的信息是文件名。若 FCB 中保存了所有文件属性，目录项会很大，目录检索需要读入更多磁盘块。

inode 的思想是把目录项瘦身：

结构	保存内容
目录项	文件名 + inode 指针
inode	除文件名之外的属性、权限、外存位置等信息

这样只有文件名匹配后，才需要读入 inode。

假设一个 FCB 为 64 B，磁盘块大小为 1 KB，则每块只能放 16 个 FCB。若某目录有 640 个目录项，平均检索 320 项，约需读 20 个目录块。

若目录项缩小为 16 B，则每块可放 64 个目录项，平均检索同样的 320 项只需读约 5 个目录块。目录项瘦身能明显减少目录检索 I/O。

inode 可分为：

类型	含义
磁盘 inode	存放在外存中的 inode
内存 inode	调入主存后的 inode，通常还会增加是否被修改、打开计数等运行时信息