第七章 文件管理
1 文件的逻辑结构（P243）
类型—按是否有结构分类
（1）有结构文件
记录长度
- 定长记录
- 变长记录
（2）无结构文件
类型—*按文件的组织方式分类
（1）顺序文件：
指由一系列记录按某种顺序排列所形成的文件，其中的记录可以时定长记录或可变长记录。
（2）索引文件：
指为可变长记录文件建立一张索引表，为每个记录设置一个表项，以加速对记录的检索速度。
（3）索引顺序文件：
指为每个文件建立一张索引表时，并不是为每一个记录建立一个索引表项，而是为一组记录的第一个记录建立一个索引表项。
2 文件目录（P249）
文件控制块（FCB）：
为了能对一个文件进行正确的存取，必须为文件设置用于描述和控制文件的数据结构，称之为文件控制块。
文件目录：
文件控制块的有序集合称为文件目录。
文件目录作用：
标识系统中的文件及其物理地址，供检索时使用。
目录管理要求：
（1）实现“按名存取”
（2）提高对目录的检索速度
（3）文件共享
（4）允许文件重名
3 树形目录结构（P253）
小规则：
主目录成为根目录，在每个文件目录中，只能有一个根目录，每个文件和每个目录都只能有一个父目录。
第八章 磁盘存储器的管理
1 设备（外存）的组织方式（P268）
（1）连续组织方式
又称为连续分配方式，要求为每一个文件分配一组相邻接的盘块。
优点：
①顺序访问容易
②顺序访问速度快
缺点：
①要求为一个文件分配连续的存储空间
②必须事先知道文件的长度
③不能灵活的删除和插入记录
④对于那些动态增长的文件，由于事先很难知道文件的最终大小，因而很难为其分配空间，而即使是事先知道文件的最终大小，在采取预分配存储空间的方法时，也会使大量的存储空间长期空闲。
（2）链接组织方式
优点：
①消除了磁盘的外部碎片，提高了外存的利用率
②对插入、删除和修改记录都非常容易
③能适应文件的动态增长，无需事先知道文件的大小。
缺点：
①只适合于顺序访问
②对随机访问是极其低效的
（3）FAT技术
利用文件分配表FAT来记录每个文件中所有盘块之间的链接。
发展：
卷：
在FAT中引入了“卷”的概念，支持将一个物理磁盘分成四个逻辑磁盘，每个逻辑磁盘就是一个“卷”。
（4）NTFS（New Technology File System）的文件组织方式
是专门为Windows NT开发的，适用于Windows2000/XP及后续的Windows OS
特性：
①使用了64位磁盘地址。
②更好的支持长文件名，单个文件名限制在255个字符以内，全路径名为32767个字符。
③具有系统容错性。
④保证系统的数据一致性。
⑤提供了文件加密、文件压缩等功能。
磁盘组织：
NTFS是以簇为磁盘空间分配和回收的基本单位。一个文件占用若干个簇，一个簇只属于一个文件。
文件的组织：
在NTFS中，以卷为单位，将一个卷中所有的文件信息、目录信息以及可用的未分配空间信息，都以文件记录的方式记录在一张主控文件表MFT中，该表时NTFS卷结构的中心，从逻辑上讲，卷中的每个文件作为一条记录，在MFT表占有一行，其中还包括MFT自己的这一行。
（5）*索引组织方式
① 单级索引
优化版的链接组织方式，优点是可以直接访问。
②多级索引
为索引增加索引，优点是大大加快了对大型文件的查找速度。
③增量式索引
更加全面的照顾到小、中、大及特大型作业，可采用多种组织方式来构成文件的物理结构。
2 文件存储空间的管理（P278）
（1）空闲表法和空闲链表法
空闲表法：
属于连续分配方式，与内存的动态分配方式相似，为每个文件分配一块连续的存储空间。
空闲链表法：
将所有的空闲盘区拉成一条空闲链，根据构成链所用的基本元素不同，可以把链表分成两种形式：空闲盘块链和空闲盘区链。
（2）*位示图法
位示图法是利用二进制的一位来表示磁盘中的一个盘块的使用情况，当其值为“0”时，表示对应的盘块空闲，为“1”时表示已分配。磁盘上的所有盘块都有一个二进制位与之对应，所产生的集合就叫做位示图。
借用下书上的图：
盘块的分配（三步） ：
① 顺序扫描位示图，从中找出一个或一组其值为“0”的二进制位。
② 将找到的一个或一组二进制位转换成与之对应的盘块号。并按如下公式计算：
b = n(i-1) + j i:其值为“0”的二进制位于位示图的第i行 j:其值为“0”的二进制位于位示图的第j行 n:每行的位数 复制代码
③ 修改位示图，让map[i,j] = 1
盘块的回收（两步） ：
①将回收盘块的盘块号转换成位示图中的行号和列号，公式为
i = (b-1)DIV n+1 j = (b-1)MOD n+1 复制代码
②修改位示图，让map[i,j] = 0
（3）成组链接法
在UNIX系统中广泛使用，将空闲表法和空闲链表法相结合成的一种空闲盘块管理方法，克服了表太长的缺点。
空闲盘块的组织：
① 空闲盘块号栈，存储当前可以的一种空闲盘块的盘块号（<=100）以及栈中尚有的盘块数N
② 文件区中的所有空闲盘块被分成若干个组
③ 将每一个组含有的总盘块数N和该组所有的盘块号记入其前一组的第一个盘块的S.free(0)-S.free(99)中
④ 将第一组的盘块总数和所有的盘块号记入空闲盘块号栈中，作为当前可供分配的空闲盘块号。
⑤ 最末一组只有99个可用盘块，某盘块号分别记入前一组的S.free(1)~S.free(99)中，而在S.free(0)中则存放“0”，作为空闲盘块链的结束标志。
全部完结！
