文件的物理结构
文件的物理结构就是研究文件的实现，即文件数据在物理存储设备上是如何分布和组织的。同一个问题有两个不同方面的答案：一是文件的分配方式，讲的是对磁盘非空闲块的管理；二是文件存储空间管理，讲的是对磁盘空闲块的管理。
磁盘中的存储单元也被分为一个个的块，成为磁盘块，其大小通常与内存的页面大小相同。内存与磁盘之间的数据交换（磁盘 I/O）都是以块为单位进行的。
连续分配
每个文件在磁盘上占有一组连续的块。
优点：
- 支持顺序访问和直接访问
- 顺序访问容易且速度快
缺点：
- 每个文件需要连续的存储空间，会产生很多外部碎片
- 必须事先知道文件的长度，不能满足动态增长的要求
- 为保持有序性，删除和插入记录时，需要对相邻的记录做物理上的移动
链接分配
隐式链接
文件的目录项中含有文件第一块的指针和最后一块的指针。每个文件对应一个磁盘块的链表，除最后一个磁盘块外，每个盘块都存有指向下一盘块的指针，这些指针对用户透明。
缺点：
- 只支持顺序访问
- 稳定性问题，文件盘块中的任何一个指针出问题，都会导致后续文件内容的丢失
- 指向下一盘块的指针也要耗费一定存储空间
文件分配和簇的关系
可以将几个盘块组成一个簇，按簇来分配，可以减少指针占用的存储空间和大幅降低查找时间，也可以改善许多算法的磁盘访问时间，代价是增加了内部碎片。
显式链接
在整个磁盘中仅设置一张文件分配表 FAT。每个表项中存放下一块的指针，文件目录只需记录该文件的起始块号。用-1 表示文件的末尾，用-2 表示该块空闲。
优点：
- 支持顺序访问，也支持直接访问
- FAT 在系统启动时就读入内存，可以减少访问磁盘次数
缺点：FAT 需要占用一定的内存空间
Tip
FAT 不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的盘区块，也可用于外存空闲空间管理
索引分配
事实上，在打开某个文件时，只需将该文件对应的盘块的编号调入内存即可，不需要将整个 FAT 调入内存。索引分配的思想就是为每个文件分配一个索引块（表），将分配给该文件的所有盘块号都记录在该索引块中。
优点：支持直接访问
缺点：索引块增加了额外的存储空间开销
索引块的主要问题是，每个文件必须有一个索引块，当文件很小时，也需要分配一整个索引块，此时索引块的利用率很低；当文件很大时，若一个索引块不够，可通过链指针将各索引块按序链接起来，但这种方法是低效的。
单级索引分配
多级索引分配
优点：极大加快了对大型文件的查找速度 缺点：当访问一个盘块时，启动磁盘的次数随索引级数的增加而增多
混合索引分配
在索引节点中加入多种形式的地址。小文件使用直接寻址，中型文件使用单级索引分配，大型或特大型使用二级或三级索引分配。
文件的逻辑结构
无结构文件
最简单的文件组织形式，它由字符流构成，所以又称流式文件，其长度以字节为单位。
有结构文件
由一个以上的记录构成的文件，所以又称记录式文件。根据记录的长度是否相等，可分为定长记录和变长记录两种。
顺序文件
文件中的记录顺序排列，记录可以是定长记录和变长记录。顺序文件中记录的排列有两种结构：
- 串结构（乱序）
- 顺序结构（有序）
在对记录进行批量操作，即每次要读或写一大批记录时，顺序文件的效率是所有逻辑文件中最高的。
对于顺序存储设备（如磁带），只能使用顺序文件。
在经常需要查找、修改、增加或删除单个记录的场合，顺序文件的性能较差。
索引文件
定长文件的顺序文件，要查找记录可以直接根据相对地址和记录长度计算得出。变长记录的顺序文件只能顺序查找，效率较低。为此，建立一张索引表
索引表中的每一个表项都包含指向记录的指针和记录长度，索引表按关键字排序，因此索引表本身也是一个定长记录的顺序文件。索引文件增加了存储开销。
索引顺序文件
索引顺序文件是顺序文件和索引文件的结合。
每一层索引表的表项需要有序，但是同一个组内的关键词可以无序。
这种方式就是数据结构中的 分块查找。
直接文件或散列文件（Hash File）
给定记录的键值或通过散列函数转换的键值直接决定记录的物理地址。散列文件有很高的存取速度，但会引起冲突，即不同关键字的散列函数值可能相同。