【学习笔记】数据结构（十二）

文件

12.1 有关文件的基本概念

文件(file) 是由大量性质相同的记录组成的集合。

可按其记录的类型不同而分成两类:

• 操作系统的文件

  仅是一维的连续的字符序列，无结构、无解释。

  是记录的集合，这个记录仅是一个字符组，用户为了存取、加工方便，把文件中的信息划分成若干组， 每一组信息称为一个逻辑记录，且可按顺序编号。

• 数据库文件

  是带有结构的记录的集合；这类记录是由一个或多个数据项组成的 集合。

  数据项是最基本的不可分的数据单位，也 是文件中可使用的数据的最小单位。

  可按记录中关键字的多少分成

  • 单关键字文件

    若文件 中的记录只有一个惟一标识记录的主关键字，则称单关键字文件

  • 多关键字文件

    若文件中的记录除了含有一个主关键字外，还含有若干个次关键字，则称为多关键字文件，记录中所有非关键字 的数据项称为记录的属性。

可按记录的另一特性分成两类:

• 定长记录文件

  若文件中每个记录含有的信息长度相同，则称这类记录为定长记录，由这类记录组成的文件称做定长记录文件；

• 不定长记录文件

  若文件中含有信息长度不等的不定长记录，则称不定长记录文件。

记录的逻辑结构和物理结构

• 记录的逻辑结构是指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方式。

  学号	姓名	年龄	班级
  101	张三	20	计算机
  102	李四	21	数学

• 记录的物理结构是数据在物理存储器上存储的方式，是数据的物理表示和组织

  • 物理结构应考虑提高存储空间的利用率和减少存取记录的时间

  • 计算机实际存储的可能是：

    101(学号), 张三(姓名), 20(年龄), 计算机(班级)
    102(学号), 李四(姓名), 21(年龄), 数学(班级)

  • 一个物理记录指的是计算机用一条I/O命令进行读写的 基本数据单位

• 在物理记录和逻辑记录之间可能存在下列 3种关系：

  • 一个物理记录存放一个逻辑记录。
  • 一个物理记录包含多个逻辑记录。
  • 多个物理记录表示一个逻辑记录。

文件的操作（运算）

• 检索

  文件的检索有下列 3 种方式：

  • 顺序存取：存取下一个逻辑记录。

  • 直接存取：存取第 i个逻辑记录。

    以上两种存取方式都是根据记录序号（即记录存入文件时的顺序编号）或记录的相对 位置进行存取的。

  • 按关键字存取：给定一个值，查询一个或一批关键字与给定值相关的记录。

  对数据库文件可以有如下4种查询方式：

  • 简单询问：查询关键字等于给定值的记录。
  • 区域询问：查询关键字属某个区域内的记录。
  • 函数询问：给定关键字的某个函数。
  • 布尔询问：以上3种询问用布尔运算组合起来的询问。

• 修改

  包括插入一个记录、删除一个记录和更新一个记录3种操作

• 文件的操作可以有实时和批量两种不同方式。

  通常实时处理对应答时间要求严格， 应在接收询问之后几秒钟内完成检索和修改，而批量处理则不然。

文件的物理结构

• 文件在存储介质（磁盘或磁带）上的组织方式称为文件的物理结构

• 组织方式基本方式有3种：顺序组织、随机组织和链组织。

12.2 顺序文件

顺序文件：物理记录的顺序和逻辑记录的顺序是一致的

连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的

串联文件：物理记录之间的次序由指针相链表示

顺序文件的特点：

• 存取第 i 个记录，必须先搜索在它之前的 i-1 个记录。
• 插人新的记录时只能加在文件的末尾。
• 若要更新文件中的某个记录，则必须将整个文件进行复制。

顺序文件的优缺点：

磁带是一种典型的顺序存取设备，因此存储在磁带上的文件只能是顺序文件。磁带文件适合于文件的数据量甚大、平时记录变化少、只作批量修改的情况。

磁带文件作修改过程：

一般需用另一条复制带将原带上不变的记录复制一遍，同时在复制的过程中插入新的记录和用更改后的新记录代替原记录写入。

磁带文件的批处理过程例子：

若某个顺序文件，其记录修改的频率较低，则用批处理并不适宜，此时可另建立一个附加文件，以存储新插入和更新后的记录，待附加文件增大到一定程度时再进行批处 理。在检索时可以先查主文件，若不成功再查附加文件，或反之。

12.3 索引文件

除了文件本身（称做数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表是索引表。这类包括文件数据区和索引表两大部分的文件称做 索引文件 。

索引表中的每一项称做 索引项 。索引项总是按关键字（或逻辑记录号）顺序排列

若数据区中的记录也按关键字顺序排列，则称 索引顺序文件 。

若数据区中的记录不按关键字顺序排列，则称 索引非顺序文件 。

索引文件的检索方式：直接存取或按关键字（进行简单询问）存取

索引文件的检索过程：

• 首先，查找索引表，若索引表上存在该记录，则 根据索引项的指示读取外存上该记录；

• 否则说明外存上不存在该记录，也就不需要访问外存。

由于索引项的长度比记录小得多，则通常可将索引表一次读入内存；索引文件中检索只访问外存两次，一次读索引，一次读记录。

索引表也很大，以致一个物理块容纳不下。检索时要多次访问外存。可以对索引表建立一个索引，称为查找表。检索记录时，先查找查找表，再查索引表，然后读取记录。若查 找表中项目还多，则可建立更高一级的索引。

上述的多级索引是一种静态索引，各级索引均为顺序表结构。

当数据文件在使用过程中记录变动较多时，应采用动态索引：

• 二叉排序树（或平衡树）：索引表不大
• m叉的B-树：索引表很大，查找索引时需多次访问外存。【m的取决于索引项的多少和缓冲区的大小】
• 双链表：索引表不大
• Trie树：索引表很大

索引文件的修改：

• 删除一个记录时，仅需删去相应的索引项；
• 插入一个记录时，应将记录置于数据区的末尾，同时在索引表中插入索引项；
• 更新记录时，应将更新后 的记录置于数据区的末尾，同时修改索引表中相应的索引项。

索引文件只能是磁盘文件

由于数据文件中记录不按关键字顺序排列，对每个记录建立一个索引项，这种索引表称之为稠密索引

• 优点：查找效率高，因为每条记录都有对应的索引。
• 缺点：索引文件占用的空间较大。

如果数据文件中的记录按关键字顺序有序，对一组记录建立一个索引项，这种索引表称之为非稠密索引

• 优点：索引文件较小，存储开销低。
• 缺点：查找效率较低。

12.4 ISAM文件和VSAM文件

12.4.1 ISAM文件

索引顺序存取方法ISAM (Indexed Sequential Access Method) 是一种专 为磁盘存取设计的文件组织方式。

磁盘是以盘组、柱面和磁道三级地址存取的设备， 则可对磁盘上的数据文件建立盘组、柱面和磁道三级索引

磁道索引： 磁道索引项由两部分组成：基本索引项和溢出索引项，每一部分都包括关键字和指针两项，前者表示该磁道中最末一个记录的关键字（在此 为最大关键字），后者指示该磁道中第一个记录的位置

磁道索引放在每个柱面的第一道上

柱面索引： 每一个索引项也由关键字和指针两部分组成，前者表示该柱面中最末一个记录的关键字（最大关键字），后者指示该柱面上的磁道索引位置。

柱面索引应放在数据文件的中间位置的柱面上

每个柱面上还开辟有一个 溢出区 ；并且，磁道索引项中有 溢出索引项，这是为插人记录所设置的： ISAM文件中记录是按关键宇顺序存放的， 则在插入记录时需移动记录，并将同一磁道上最末一个记录移至溢出区，同时修改磁道索引项。

溢出区可有3种设置方法：

• 集中存放一一整个文件设一个大的单一的溢出 区；
• 分散存放一一每个柱面设一个溢出区；
• 集中与分散相结合——溢出时记录先移 至每个柱面各自的溢出区，待满之后再使用公共溢出区。

每个柱面的基本区是顺序存储结构，而溢出区是链表结构

同一磁道溢出的记录由指针相链，该磁道索引的溢出索引项中的关键字指示该磁道溢出的记录的最大关键字；而 指针则指示在溢出区中的第一个记录。

ISAM文件删除记录：

• 找到待删除的记录，在其存储位置上作删除标记即可，而不需要移动记录或改变指针。
• 【注意：但在经过多次的增删后，文件的结构可能变得很不合理。此时，大量的记录进入溢出区，而基本区中又浪费很多空间。】因此，通常需要周期地整理ISAM文件。把记录读入内存，重新排列，复制成一个新的 ISAM文件，填满基本区而空出溢出区

12.4.2 VSAM文件

虚拟存储存取方法VSAM (Virtual Storage Access Method)

VSAM文件既可在顺序集中进行顺序存取，又可从 最高层的索引（B+树的根结点）出发进行按关键字存取

在 VSAM文件中，记录可以是不定长的，则在 控制区间 中除了存放记录本身以外，还有每个记录的控制信息（如记录的长度等）和整个区间的控制信息（如区间中存有的记录数等）

VSAM文件插入操作：

没有溢出区，解决插入的办法是在初建文件时留有空间。

• 一是每个控制区间内不填满记录，在最末一个记录和控制信息之间留有空隙；
• 二是在每个控制区域中有一些完全空的控制区间，并在顺序集的索引中指明这些空区间。

记录插入已满的控制区间，要进行控制区间的分裂，即将近乎一半的记录移到同一控制区域中全空的控制区间中，并修改顺序集中相应索引。控制区域中已经没有全空的控制区间，则要进行控制区域的分裂，很少发生此情况。

VSAM文件删除操作：

需将同一控制区间中较删除记录关键字大的记录向前移动，把空间留给以后插入的新记录。若整个控制区间变空，则需修改顺序集中相应的索 引项。

VSAM文件优点：

动态地分配和释放存储空间，不需要对文件进行重组，并能较快 地对插入的记录进行查找，查找一个后插入记录的时间与查找一个原有记录的时间是 相同的。

12.5 直接存取文件(散列文件)

利用杂凑(Hash)法进行组织的文件。根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故 又称散列文件。

若干个记录组成一个存储单位，在散列文件中，这个存储单位叫做 桶(Bucket) 。假若一个桶能存放 m 个记录——m个同义词的记录可以存放在同一地址的桶中，而当第 m+1 个同义词出现时 发生”溢出“ 。处理溢出主要采用链地址法。当发生“溢出“时，需要将第m+1个同义词存放到另一个桶中，通常称此桶为 ＂溢出桶” ；相对地，称前m个同义词存放的桶为 “基桶＂ 。溢出桶和基桶大小相同，相互之 间用指针相链接。同一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面上。

文件查找：

• 步骤：
  • 根据给定值求得哈希地址（即基桶号），将基桶的记录读入内存进行顺序查找，
    • 若找到关键字等于给定值的记录，则检索成功；
    • 否则，若基桶内没有填满记录或其指针域为空，则文件内不含有待查记录；
    • 否则根据指针域的值的指示将溢 出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。
• 时间： T = a(t_e + t_i)
  • a为存取桶数的期望值（相当于哈希表中的平均查找长度），对链地址处理溢出来 说 a = 1 + a/2
  • t_e为存取一个桶所需的时间
  • t_i为在内存中顺序查找一个记录所需时间。
• α 装载因子 α = n / (b * m)
  • n为文件的记录数，
  • b为桶数，
  • m为桶的容量

优缺点：

• 优点是：文件随机存放，记录不需进行排序；插入、删除方便，存 取速度快，不需要索引区，节省存储空间。
• 缺点是：不能进行顺序存取，只能按关键字 机存取，且询问方式限于简单询问，并且在经过多次的插入、删除之后，也可能造成文件结 构不合理，即溢出桶满而基桶内多数为被删除的记录。此时亦需重组文件。

12.6 多关键字文件

多关键字文件的特点: 在对文件进行检索操作时，不仅对主关键字进行简单询间， 还经常需要对次关键字进行其他类型的询问检索。

次关键字索引可以是稠密的，也 可以是非稠密的；索引表可以是顺序表，也可以是树表。

12.6.1 多重表文件

多重表文件(Multilist File) 的特点是：记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引（称为主索引）；对每一个次关键字项建立次关键字索引（称为次索引），所有具有同一次关键字的记录构成一个链表。主索引为非稠密索引，次索引为稠密索引。每个索引项包括次关键字、头指针和链表长度。

12.6.2 倒排文件

倒排文件和多重表文件的区别在于次关键字索引的结构不同。

倒排文件中 的次关键字索引为 倒排表，具有相同次关键字的记录之间不设指针相链，而在倒排表中该次关键字的一项中存放这些记录的物理记录号，且是有序排列的。

参考：

教材：严蔚敏《数据结构》（C语言版）.pdf