一、文件的逻辑结构
逻辑结构是指在用户看来，文件内部的数据应该是如何组织起来的，分为无结构文件，有结构文件。而物理结构指的是在操作系统看来，文件的数据是如何存放在外存中的。
（1）无结构文件
文件内部是数据就是一系列二进制流或字符流组成。又称“流式文件”。如：.txt 文件
（2）有结构文件
由一组相似的记录组成，又称“记录式文件”。每条记录由若干个数据项组成。如：数据表文件。一般来说，每条记录有一个数据项可作为关键字。
有结构文件的逻辑结构：
-
顺序文件：文件的记录一个接一个地顺序排列（逻辑上），记录可以是定长的或可变长的。各个记录在物理上顺序存储或链式存储。根据记录是否按关键字存储可分为：
- 串结构：记录之间的顺序与关键字无关，通常按照时间顺序
- 顺序结构：记录之间的顺序按关键字顺序排列
缺点：不定长记录查找困难，无法随机存取，而定长记录的顺序文件可以随机存取。
- 索引文件：为文件建立一张索引表，每个记录对应一个索引表项。本身是定长记录的顺序文件，可以随机存取。可将关键字或其他数据项作为索引号内容，使其可快速查找。注意每次增删，需要对索引表进行修改。
缺点：每个记录对应一个索引表项，索引表可能会很大，空间利用率低
-
索引顺序文件：同样为文件建立一张索引表，但不同的是一组记录对应一个索引项
为了进一步提高检索效率，可以为顺序文件建立多级索引表。
二、文件目录
（1）文件目录的实现
文件控制块（FCB）：目录文件中的一条记录就是一个FCB，多个FCB组成文件目录，FCB实现了文件名和文件之间的映射。使得用户（用户程序）可以实现“按名存取”。
FCB中包含了文件的基本信息（文件名，物理地址，逻辑结构，物理结构等），存取控制信息（可读/可写、禁止访问的用户名单等），使用信息（如文件的建立时间、修改时间等）
需要对目录进行的操作：
搜索、显示目录、修改目录：系统根据文件名搜索目录，找到对应的目录项，显示或修改相应属性。
创建文件、删除文件：在目录中增加或删除一个相应的目录项。
（2）目录结构
-
单级目录结构：早期操作系统只建立一张目录表，每个文件占一个目录项，实现“按名存取”，但是不允许文件重名，不同用户文件不允许重名。
-
两级目录结构：分为主文件目录和用户文件目录，允许不同用户的文件重名。
image -
多级目录结构（树形目录结构）：不同目录下的文件可以重名，从根目录出发的路径为绝对路径，系统根据绝对路径开始一层一层向下找；从当前的目录出为相对路径，系统从当前路径出发。
优缺：层次结构清晰、不便于实现文件共享
image -
无环图目录结构：允许不同文件名指向同一文件，甚至同一个目录。需要为每个共享结点设置一个共享计数器，当用户提出删除时，只会删除该用户的FCB、并使共享计数器减一，并不删除共享结点（为0时删除结点）。
注意：共享文件与复制文件的区别（共享文件中是同一文件，其中一个用户修改内容，那大家都能看见）
（3） 索引结点（FCB的改进）
将文件文件名以外的信息放在索引结点，一个文件对应一个索引结点，索引结点中记录了文件的各种信息（包括文件在外存中的存放位置，根据“存放位置”即可找到文件）根据索引结点存放在内/外存可分为“磁盘索引结点”、“内存索引结点”。索引结点指针指向文件，为文件进行瘦身，大大提高搜索效率。
因为文件控制块（FCB）存放在磁盘块，而一个磁盘块空间有限，每次搜索需要启动磁盘，每次读取一个磁盘块，假如FCB越大，一个磁盘块存放FCB越好，平均每次搜索要启动磁盘次数越多，速度越慢。
三、文件物理结构
（1）文件块、磁盘块
磁盘块：类似与内存分页，磁盘中的存储单元也会被分为一个个“块/磁盘块/物理块”。很多操作系统中，磁盘块的大小与内存块、页面的大小相同。文件的物理地址也可以表示为（物理块号，块内地址）的形式。
内存与磁盘之间的数据交换（即读/写操作、磁盘I/O）都是以“块 ”为单位进行的。即每次读入一块，或每次写出一块。
文件块：在内存管理中，为了方便对进程管理，将进程的逻辑地址空间分为一个个页面。同样，在外存管理中，为了方便对文件数据的管理，文件的逻辑地址空间被分为一个个“文件块”。于是文件的逻辑地址也可以表示为（逻辑块号，块内地址）的形式。
（2）文件分配方式
-
连续分配：要求每个文件在磁盘上占有一组连续的块。用户通过逻辑地址来操作自己的文件，操作系统找到对应FCB通过计算（物理块号 = 起始块号 + 逻辑块号）实现从逻辑地址映射到物理地址。
优点：支持顺序访问和随机访问，文件在顺序读写速度最快。
注：读取某个磁盘块时，需要移动磁头。访问的两个磁盘块相隔越远，移动时间越长
缺点：文件不方便拓展，存储空间利用率低，会产生难以利用的磁盘碎片。
注：假如要拓展文件A，而A后面的磁盘块不为空，则需要将A整体迁移至空间足够的地方，而且当磁盘剩下一块一块的空闲磁盘块时，难以利用，而处理碎片，需要耗费时间来移动文件。
-
链接分配：采取离散分散的方式，可以为文件分配离散的磁盘块。分隐式链接和显式链接两种。
-
隐式链接：除了文件的最后一个盘块之外， 每个盘块中都存在指向下一个盘块的指针，且对用户透明。文件目录包括文件第一块的指针和最后一块的指针。
实现从逻辑地址映射到物理地址：用户通过逻辑地址来操作自己的文件，操作系统找到对应FCB的起始块号，将0号逻辑块读入内存，由此知道1号逻辑块存放的物理块号，于是读入1号逻辑块，以此类推，因此，读入i号逻辑块，总共需要i+1次磁盘I/O。
优点：方便拓展文件，不会有碎片问题，外存利用率高。
缺点：只支持顺序访问，不支持随机访问，查找效率低，指向下一个盘块的指针需要耗费少量存储空间。
-
显式链接：把用于链接文件各物理块的指针显式地放在一张表中。即文件分配（FAT）。
注意：一个磁盘仅设置一张FAT。开机时，将FAT读入内存，并常驻内存
实现从逻辑地址映射到物理地址：用户通过逻辑地址来操作自己的文件，操作系统找到对应FCB的起始块号，若i>0，则查询内存中的文件分配表FAT往后找到i号逻辑块对应的物理块号。因为FAT常驻内存，逻辑块号转换为物理块号的过程不需要读磁盘操作。
优点：方便文件扩展，不会有碎片问题，外存利用率高，支持顺序访问，随机访问，相比隐式链接，访问速度块。
缺点：文件分配表的需要占用一定的存储空间
-
-
索引分配：允许文件离散地分配在各个磁盘块中，系统为每个文件建立一张索引表，索引表记录了文件的各个逻辑块对应的物理块（索引表的功能类似于文件管理中的页表——建立逻辑页面到物理页之间的映射关系）。索引表存放的磁盘块称为索引块。文件数据存放的磁盘块为数据块。
实现从逻辑地址映射到物理地址：用户通过逻辑地址来操作自己的文件，操作系统找到对应FCB的索引表存放位置，将索引表从外存读入内存，并查找索引表即可知逻辑块在外存中的存放位置。
优点：支持随机访问，方便文件扩展
缺点：索引表需要占用一定的存储空间
存在问题：如果一个文件过大，一个磁盘块装不下文件的整张索引表。
解决方法：-
链接方案：如果索引表太大，一个索引块装不下，那么可以将多个索引块链接起来存放。缺点：文件太大，索引块结点太多，让随机访问成了问题，可能会导致磁盘I/O次数过多，搜索低效。
-
多次索引：建议多层索引（原理类似于多级页表）。使得第一层索引块指向第二层的索引块。还可根据文件大小的要求建立K层索引结构，如果顶级索引表未调入内存，则访问一个数据块只需要K+1次读磁盘操作。缺点：即使是小文件，访问一个数据块依然需要K+1次读磁盘
-
混合索引：多种索引分配方式的结合。例如，以一个文件的顶级索引表中，即包含直接地址索引（直接指向数据块），又包含一级间接索引（指向单层索引表）、还包含一级间接索引（指向两层索引表）。优点：对于小文件来说，访问一个数据块所需的读磁盘次数更少
-
四、文件存储空间管理
存储空间的划分与初始化
- 文件卷（逻辑卷）的概念
存储空间的划分：将物理磁盘划分为一个个文件卷
存储空间的初始化：将各个文件卷划分为目录区、文件区 -
目录区与文件区
目录区：主要存放文件目录信息（FCB）、用于磁盘存储空间管理的信息。
文件区：用于存放文件数据
存储空间管理方法
-
空闲表法：适用于“连续分配方式”
-
空闲盘表：记录每个空闲盘块的起始位置和长度。
-
如何分配磁盘块：
-
如何回收磁盘块：
-
-
空闲链表法
-
空闲盘块链：以盘块为单位组成一条空闲链，适用于离散分配的物理结构。
-
空闲盘曲链：以盘区为单位组成一条空闲链
-
-
位示图表：每个二进制位对应一个盘块。
- 如何分配：若文件需要k块，顺序扫描位示图，找到空格相邻或不相邻的“0”，根据字号、位号算出对应的盘块号，分配给文件，将位示图相应位置设置位“1”。
- 如何回收：根据回收的盘块号计算出对应的字号、位号；将相应二进制位设置位“0”。
-
成组链接法：空闲表法、空闲链表不适用于大型文件系统，因为空闲表或空闲链表可能过大。UNIX系统中采用了成组链接法对磁盘空闲块进行管理。
文件卷的目录区中专门用一个磁盘块作为“超级块”，当系统启动时需要将超级块读入内存。并且确保内存与外存中“超级块”数据一致（内存分配和回收时需要更改超级块信息）
超级块的作用：记录下一组空闲盘块的数量（不超过最大值），记录空闲盘块号的位置，每一分组都会存在像超级块一样作用的块号。
-
如何分配：
image -
如何回收：
image
-
