一、文件结构

域

• 域是基本的数据单元

• 一个域包含一个值

• 域的长度可以是定长的或变长的

记录

• 一组相关域的集合

• 记录的长度也可以是定长的或变长的

• 整条记录通常都包含一个长度域

文件

具有文件名的一组相似记录的集合

二、文件组织和访问

两种形式的结构

• 文件的逻辑结构

  • 从用户观点出发所观察到的文件组织形式，是用户可以直接处理的数据及其结构，它独立于文件的物理特性，又称为文件组织。

• 文件的物理结构

  • 指文件在外存上的存储组织形式。

选择原则

选择文件组织时，有以下重要原则：

• 快速访问

• 易于修改

• 节约存储空间

• 维护简单

• 可靠性

文件组织

• 堆

• 顺序文件

• 索引顺序文件

• 索引文件

• 直接或散列文件

三、堆

• 堆是最简单的文件组织形式。

• 数据按它们到达的顺序被收集。

• 堆的目的仅仅是积累大量的数据并保存。

• 堆文件没有结构。

• 堆对记录的访问是通过穷举查找方式进行的。

四、顺序文件

• 每条记录都使用一种固定的格式

• 所有记录都具有相同的长度，并且由相同数量、长度固定的域按特定顺序组成

• 每个域的域名和长度是该文件结构的属性。

• 关键域：记录的唯一标识

• 记录按关键域来存储

逻辑记录的排序

• 按记录录入的时间排序：串结构。

• 按关键字排序：顺序结构。

后一种情况更有利于提高查询速度。如可用折半查找法等。

对顺序文件的读/写操作

• 定长记录顺序文件：例顺序读

  • 易于定位，甚至可随机读取。

• 变长记录：不易定位，只能顺序读取。

顺序文件的优缺点

• 批处理时效率是所有逻辑文件中最高的。

• 可存在于磁带上。

• 交互应用时“效率低”(如要查找单个记录)，尤其是对变长记录的顺序文件。

• 增加、删除记录涉及到排序问题,开销大。

  • 事务文件(log)，用于存放将更新到主文件的记录。

五、索引顺序文件

• 克服顺序文件缺点的一种常用方法

• 保留了顺序文件的关键特征：记录按照关键域的顺序组织

• 增加了两个特征：

  • 用于支持随机访问的文件索引：提供了快速接近目标记录的查找能力
  • 溢出文件：类似于顺序文件中使用的日志文件，但溢出文件中的记录可根据它前面记录的指针进行定位

对索引顺序文件进行检索步骤：

• 首先也是利用用户(程序)所提供的关键字以及某种查找算法去检索索引表，找到该记录所在记录组中第一个记录的表项，从中得到该记录组第一个记录在主文件中的位置。

• 再利用顺序查找法去查找主文件，从中找到所要求的记录。

如果在一个顺序文件中所含有的记录数为N，则为检索到具有指定关键字的记录，平均须查找N/2个记录；但对于索引顺序文件，则为能检索到具有指定关键字的记录，平均只要查找$\sqrt{N}$个记录数，因而其检索效率S比顺序文件约提高$\frac{\sqrt{N}}{2}$倍。

例如，有一个顺序文件含有10000个记录，平均须查找的记录数为5000个。但对于索引顺序文件，则平均只须查找100个记录。可见，它的检索效率是顺序文件的50倍。

六、索引文件

• 顺序文件和索引顺序文件都只允许按记录的唯一关键字检索记录，这不符合某些应用需要按多个字段检索记录的要求

• 采用多索引的结构，成为查找条件的每个域都可能有一个索引

• 两种类型的索引：

  • 完全索引：包含主文件中每条记录的索引项
  • 部分索引：只包含那些有感兴趣域的记录的索引项

• 由变长记录组成的顺序文件不容易直接存取，因此，为其建立一有序的索引表，对索引采用折半查找，速度更快。

• 特点

  • 提高了速度，增加了存储开销——放索引文件。
  • 增、删记录时，对索引表作相应的修改。

七、直接和哈希文件

直接文件

而对于直接文件，则可根据给定的记录键值，直接获得指定记录的物理地址。换言之，记录键值本身就决定了记录的物理地址。

哈希(Hash)文件

这是目前应用最为广泛的一种直接文件，它利用Hash函数(或称散列函数)，可将记录键值转换为相应记录的地址。

A=H(k)