第七、八章 文件（一）

1、文件管理：

把所管理的程序和数据组织成一系列的文件，并能进行合理的存储、使用等操作。

2、基本概念：

数据项：描述对象某种属性的字符集；是数据组织中可以命名的最小逻辑数据单位。

记录：一组相关数据项集合，描述对象某方面的属性；

关键字：一个记录中的一个或几个数据项的集合，用于唯一的标识一个记录。

文件：由创建者定义的、具有文件名的一组相关元素的集合。

3、文件系统模型：

4、文件操作：

1）创建/删除文件

2）读、写

3）设置文件读写位置，实现随机存取（尤其适用于记录文件）

4）打开”与“关闭”：        文件读/写操作 = 检索 + 读/写。

     一次检索到文件后就在内存中记录其位置，避免重复检索。被记录下位置的文件就是“打开”文件；

5）其他操作：改名、改所属用户、改访问权限等属性的操作。     

5、文件的逻辑结构 ：

1、有结构文件（记录式）

 ①定长记录

 ②变长记录

任何组织记录：

顺序文件。         系统需按该类型记录“长度”，通常定长。
索引文件。         系统需为文件建立索引表。
索引顺序文件。  建索引表，记录每组记录的第一个记录位置
直接文件。
定长记录 适合组织成 顺序文件（顺序文件不等于 定长，变长文件也可以是顺序文件）

变长记录 适合组织成 索引文件

较大文件可组织成 索引顺序文件

①顺序文件：1.1 串结构：按记录形成的时间顺序串行排序

                                 1.1.1 具体的寻址过程：

                                           第i条记录地址（定长） ：     读写指针 + 记录长度： ptr + i*L

                                          第i条记录地址（变长） ：     扫描或读取前面0~i-1条记录

                                          第i条记录地址（变长） ：变长记录数据前用1字节保存每条记录长度，顺序扫描，但不用把记录全扫描完   

                      1.2顺序结构：按关键字排序，可按关键字检索

                                     1.2.1  定长：  结合折半查找算法等提高检索速度

                                     1.2.2 变长：  从第1个记录开始顺序扫描，直到扫描到要检索的关键字标识的记录

 

②索引文件：

              索引表内容：     索引号、长度、记录地址指针

              一个索引文件可以有多个索引表

             适用于变长记录，可提高检索速度，实现直接存取 索引表增加了存储开销

③索引顺序文件：

既方便，又要降低存储索引表的开销

检索一条记录的过程：

                 先计算记录是在第几组，然后再检索索引确定组在哪里后，在组内顺序查找。

④直接文件：

   给定键值（如学号）不需顺序检索直接得到记录的物理地址

2、无结构文件（字符流式）

字节为单位，利用读写指针依次访问。

系统对该类文件不需格式处理。

6、外存分配方式

 6.1：方式

连续分配
链接分配（不连续）
索引分配
1）连续分配    (适用于变化不大顺序访问的文件    ep:对换区)

逻辑文件中的记录顺序与存储器中文件占用盘块的顺序一致。

一个文件对于一个fcb

优点：     顺序访问容易，读写速度快

缺点： 会产生外存碎片。

           创建文件时要给出文件大小；

2）链接分配

可以为每一个文件分配一组不相邻的盘块。

设置链接指针，将同属于一个文件的多个离散盘块链接成一个链表

优点： 离散分配，消除外部碎片，提高利用率

            同时适用于文件的动态增长；修改容易

          2.1 隐式链接    链接信息隐含记录在外存盘块数据中；

                                    每个盘块拿出若干字节，记录指向下一盘块号的指针。

                                    缺点：只能顺着盘块读取，可靠性低

          2.2 显式链接  （FAT）

                                   记录盘块链接的指针显示地记录为一张链接表

                                   所有已分配的盘块号都记录在其中，称文件分配表

                                   FAT 开始在外存，运行后在内存（为了提高文件系统访问速度，FAT一般常驻内存）

                                  外存有多少盘块，FAT就有多少项

               FAT 相关计算：

                         表项个数     =  盘块个数         =  容量 / 盘块大小

                         表项大小，决定于盘块数量编号需要的位数

                         FAT表大小 = 表项个数 * 表项大小

3）索引分配

         ①单级索引分配     适合大文件

                                        中、小型文件用索引分配较浪费，只需若干链接即可

          ②多级索引     若索引盘块数量较少用指针链接的方式即可；

                                   若索引盘块较多，需对索引盘块也采用索引方式管理，形成多级索引

          ③混合组织索引（增量式索引组织方式）

                       一个索引结点定义为13个地址：

                                   iaddr（0）~iaddr（9）存放直接地址，即存文件数据的盘块号；

                                   iaddr（10）存放单级索引的索引盘块号； 剩余的用于文件较大时存放多级索引数据。

                                   iaddr（11）存放二级索引的主索引盘块号

                                   iaddr（12）存放三级索引的主索引盘块号

6.2 结构

 用的磁盘分配方式决定了文件的  “物理结构”  

 顺序结构；链接式结构；索引式结构。

7、存储空间的管理

  7.1典型的管理方法：

      1）空闲表和空闲链表法 ：

               空闲表：  常用于连续分配管理方式

               空闲链表法： 将所有空闲盘区拉成一条空闲链。

                        根据构成链所用基本元素的不同，可把链表分成两种形式：

                                空闲盘块链 ：将磁盘上的所有空闲空间，以盘块为单位拉成一条链。

                                 空闲盘区链：将所有空闲盘区拉成一条链

            为提高检索速度，可以采用显式方法，为空闲盘区建立一张链表放在内存中。

       2）位示图法  ：

       磁盘上的所有盘块都有一个二进制位与之对应，这样由所有盘块所对应的位构成一个集合，称为位示图。

      优点：从位示图中很容易找到一个或一组相邻接的空闲盘块。 但限于容量问题，常用于微型机和小型机中。   

       3）成组链接法

            中心思想：

                所有盘块按规定大小划分为组；

                组间建立链接；

                组内的盘块借助一个系统栈可快速处理，且支持离散分配回收。