一、文件和文件系统
1、基本概念
u数据项：描述对象某种属性的字符集；是数据组织中可以命名的最小逻辑数据单位。
u记录：一组相关数据项集合，描述对象某方面的属性；
u关键字：一个记录中的一个或几个数据项的集合，用于唯一的标识一个记录。
u文件：由创建者定义的、具有文件名的一组相关元素的集合。
2、文件类型
u按用途：系统、用户、库文件
u按数据形式：源文件、目标文件、可执行文件
u按存取控制属性：只执行、只读、读写
u按组织和处理方式：普通文件、目录文件、特殊（设备）文件
3、文件系统模型
二、文件的逻辑结构
1、
1）有结构文件（记录式）
①定长记录
②变长记录
如何组织记录：
l顺序文件。系统需按该类型记录“长度”，通常定长。
l索引文件。系统需为文件建立索引表。
l索引顺序文件。建索引表，记录每组记录的第一个记录位置。
2）无结构文件（字符流式）
字节为单位，利用读写指针依次访问。
系统对该类文件不需格式处理。
2、顺序文件
1）两种记录排列方式
串结构：按记录形成的时间顺序串行排序。记录顺序与关键字无关；
顺序结构：按关键字排序。
2）检索方法：
从头检索，顺序查找要找的记录，定长的计算相对快。
顺序结构，可用折半查找、插值查找、跳步查找等算法提高效率
3）顺序文件的优缺点：
不方便随机存取某条记录，但适用批量存取的场合。
适合磁带等特殊介质。
单记录的查找、修改等交互性差；增减不方便
3、索引文件
1）折半检索过程举例
1.给出用户关键字
2.检索索引表(设有n条记录,设一个索引表项占x字节)，则索引表的x*n/2字节处记录着n/2号记录的地址
3.根据第2步的地址，读一条记录，若记录中关键字不匹配，再判断找第n/4还是第n/2+n/4条记录
2）索引文件的优缺点
适用于变长记录，可提高检索速度，实现直接存取
索引表增加了存储开销
4、索引顺序文件
1）将顺序文件的所有记录分组
2）还是建立索引表，但每个表项记录的是每组第1条记录的键值和地址。
3）组内记录仍按顺序方式检索和使用。
5、直接文件
1）给定键值（如学号）不需顺序检索直接得到记录的物理地址
2）用户对文件的操作由操作系统按文件结构分析执行
3）而操作归根到底要到外存中进行实质操作。
三、外存分配方式
1、连续分配
1）为每一个文件分配一组相邻的盘块。
2）逻辑文件中的记录顺序与存储器中文件占用盘块的顺序一致。
3）优点：顺序访问容易，读写速度快
2、链接分配
1）隐式链接
2）显式链接
【例题】一个1.2M的磁盘，盘块512B大小；若文件系统采用FAT格式，则FAT表大小如何？
答：表项个数 = 盘块个数 = 容量/ 盘块大小= 1.2 *220/ 29 = 1.2 *211 个
表项大小，决定于盘块数量编号需要的位数=12 位；
FAT表大小= 表项个数 * 表项大小= 1.2 *2^11 * 12 bit= 1.2*2^11 * 1.5B = 3.6KB
以半字节（0.5B=4b）为基本单位,表项需12位（1.5B）
3、索引分配
1）单级索引分配
2）多级索引
3）混合组织索引
四、存储空间管理
1、空闲表和空闲链表法
1）空闲表法：常用于连续分配管理方式
2）空闲链表法：将所有空闲盘区拉成一条空闲链
2、位示图法：
1）利用二进制的一位来表示一个盘块的使用情况
2）根据位示图进行盘块分配：
1)顺序扫描位示图。找到为0的二进制位。
2)将所找到的一个或一组二进制位，转换成与之对应的盘块号。进行分配操作。
盘块号计算公式为：盘块号=列总数*（i-1）+ j;（注意下标i，j从1开始）
3)修改位示图。
3、组成链接法
链表长度上限固定
组内的盘块借助一个系统栈可快速处理，且分配回收比较简单。
支持离散分配回收。
五、目录管理
1、目录管理的要求：
o实现“按名存取”；（最基本功能）
o提高对目录的检索速度；
o文件共享；
o允许文件重名。
2、目录结构
1）单级目录
2）两级目录
3）多级目录
3、两级目录特点
1.提高了检索目录的速度。
2.在不同的目录中可重名。
3.不同用户还可以使用相同/不同的文件名来访问系统中的同一个共享文件。
4、目录查询技术
1）线索检索法
2）Hash方法
六、文件共享与保护
1、文件共享方法
1）索引结点法
2）符号链法
