File
和表类似，文件是大量记录的集合。
- 存储在主存储器(内存储器)中的记录集合为表；
- 存储在二级存储器(外存储器)中的记录集合为文件。
本文讨论文件在外存储器中的表示方法及其各种运算的实现。
一、一些基本概念
文件及其类别
文件：大量性质相同的记录组成的集合。根据记录的类型不同，可分为操作系统的文件和数据库文件两类。
- 操作系统中的文件是一维的连续的字符序列，无结构，无解释。它也是记录的集合，这个记录仅是一个字符组，用户为了存储、加工方便，把文件中的信息划分称若干组，每一组信息称为一个逻辑记录，且可按顺序编号；
- 数据库中的文件是带有结构的记录的集合；这类记录由一个或多个数据项组成的集合，它也是文件中可存取的数据的基本单位。数据项是最基本的不可分的数据单位，也是文件中可使用的数据的最小单元。
如下图，为一个数据库文件，每个学生的情况是一个记录，它由10个数据项组成。
根据文件中每个记录所含信息的长度是否相等，可分为定长记录文件和不定长记录文件。
- 定长记录文件：文件中每个记录含有的信息长度相同；
- 不定长记录文件：文件中含有信息长度不等的不定长记录。
数据库文件中，可按记录中关键字的多少，划分为单关键字文件和多关键字文件。
- 单关键字文件： 文件中的记录只有一个唯一标识记录的主关键字；
- 多关键字文件：文件中的记录除了含有一个主关键字外，还含有若干个次关键字；
记录中所有非关键字的数据项称为记录的属性。
记录的逻辑结构和物理结构
- 记录的逻辑结构：指记录在用户或应用程序员面前呈现的方式，是用户对数据的表示和存取方法；
- 记录的物理结构：指记录在物理存储器上存储的方式，是数据的物理表示和组织。
记录的逻辑结构着眼于用户使用方便； 记录的物理结构应考虑提高存储空间的利用率和减少存取记录的时间(根据不同的需要以及设备本身的特性有多种方式)
物理记录(指计算机用一条I/O命令进行读写的基本数据单位)对于固定的设备和操作系统，它的大小基本不变；而逻辑记录的大小是由使用要求定的。在物理记录和逻辑记录之间可能存在下面三种关系：
- 一个物理记录存放一个逻辑记录；
- 一个物理记录包含多个逻辑记录；
-
多个物理记录表示一个逻辑记录。
逻辑连续而物理不连续的记录之间用指针相连接。
文件的操作
文件的操作分为两类：检索和修改。
文件的3中检索方式：
- 顺序存取。存取下一个逻辑记录。
- 直接存取。存取第i个逻辑记录。
- 按关键字存取。给定一个值，查询一个或一批关键字与给定值相关的记录。
按关键字存取中，对于数据库文件，有4种查询方式：
- 简单询问。查询关键字等于给定值的记录；
- 区域询问。查询关键字属某个区域内的记录；
- 函数询问。给定关键字的某个函数(例如查询总分在全体学生的平均分以上的记录或处于中值的记录)；
- 布尔询问。上述三种询问用布尔运算组合起来的询问。
文件的修改包括如下三种方式：
- 插入一个记录；
- 删除一个记录；
- 更新一个记录。
文件的操作可以分为实时和批量两种不同方式。
通常实时处理对应答时间要求严格，应在接受询问几秒内完成检索和修改，而批量处理则不然。(不同的文件系统其使用有不同的要求)
文件的物理结构
文件在存储介质(磁盘或磁带)上的组织方式称为文件的物理结构。
文件可以有各种各样的组织方式，其基本方式有3种：顺序组织、随机组织和链组织。
一个特定的文件应采用何种物理结构应综合考虑各方面的因素，如：存储介质的类型、记录的类型、大小和关键字的数目以及对文件作何种操作等。
下面将介绍几种常用的文件的物理结构。
顺序文件
顺序文件是记录按其在文件中的逻辑顺序依次进入存储介质而建立的(即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的).
- 连续文件：次序相继的两个物理记录在存储介质上的存储位置是相邻的；
- 串联文件：物理记录之间的次序由指针相链表示。
顺序文件是根据记录的序号或记录的相对位置来进行存取的文件组织方式。它的特点是：
- 存取第
i个记录，必须先搜索在它之前的i-1个记录； - 插入新的记录时，只能加在文件的末尾；
- 若要更新文件中的某个记录，则必须要将整个文件进行复制。
由于顺序文件的优点是连续存取的速度快，因此主要用于只进行顺序存取、批量修改的情况。(若对应答时间要求不严时亦可进行直接存取)
磁带
磁带是一种典型的顺序存储设备(存储在磁带上的文件只能是顺序文件)。
磁带文件适合于文件的数据量大、平时记录变化少、只做批量修改的情况。
在对磁带文件作修改时，一般需要用另一条复制带将原带上不变的记录复制一遍，同时在复制的过程中插入新的记录和用更改后的新纪录代替原记录写入。
为了修改方便起见，要求待复制的顺序文件按关键字有序(若非数据库文件，则可将逻辑记录号作为关键字)
批量处理
磁盘文件的批量处理过程如下进行：
待修改的原始文件称作主文件，存放在一条磁带上，所有的修改请求集中构成一个文件，称作事务文件，存放在另一台磁带上，尚需第三台磁带作为新的主文件的存储介质。主文件按关键字自小到大(或自大至小)顺序有序，事务文件必须和主文件有相同的有序关系。
- 首先对事务文件进行排序；
- 然后将主文件和事务文件归并成一个新的主文件。
如何归并？
- 顺序读出主文件与事务文件中的记录，比较它们的关键字并分别进行处理。
- 对于关键字不匹配的主文件中的记录，则直接将其写入新主文件中；
- “更改”和“删除”记录时，要求其关键字相匹配：
-
- “删去”不用写入；
-
- “更改”要将更改后的新记录写入新主文件。
- “插入”时不要求关键字相匹配：
-
- “插入”直接将事务文件上要插入的记录写到新主文件的适当位置。
时间复杂度
下面分析批处理算法的时间。
假设主文件包含n个记录，事务文件包含m个文件。一般情况下，事务文件较小，可以进行内部排序，则时间复杂度为O(mlogm)。内部归并的时间复杂度为O(n+m)，则总的内部处理的时间为O(mlogm+n)。假设所有的输入/输出都是通过缓冲区进行的，并假设缓冲区大小为s(个记录)，则整个批处理过程中读/写外存的次数为。(此数为考虑全部修改项为插入时的上界)
磁盘
磁盘上顺序文件的批处理和磁带文件类似，只是当修改项中没有插入，且更新时不增加记录的长度时，可以不建立新的主文件，直接修改原来的主文件即可。(显然，磁盘文件的批处理可以在一台磁盘组上进行)
对顺序文件进行顺序查找，其平均查找长度为(n'+1)/2，其中n'为文件所含物理记录的数目(相对外存读/写而言，内存查找的时间可以忽略不计)。
对磁盘文件可以进行分块查找或折半查找(对不定长文件不能进行折半查找)。但是，若文件很大，在磁盘上占多个柱面时，折半查找引起磁头来回移动，增加寻查时间。。
假若某个顺序文件，其记录修改的频率较低，则用批处理并不合适，此时可另建一个附加文件，以存储新插入和更新后的记录，待附加文件增大到一定程度时再进行批处理。检索时可以先查主文件，若不成功再查附加文件。
索引文件
除了文件本身(称作数据区)，另建立一张指示逻辑记录和物理记录之间一一对应关系的表——索引表。
这类包含文件数据区和索引表两大部分的文件称作索引文件。
索引表中的每一项称作索引项。
不论主文件是否按关键字有序，索引表中的索引项总是按关键字(或逻辑记录号)顺序排列。
- 索引顺序文件。若数据区中的记录也按关键字顺序排序，则称为索引顺序文件。
- 索引非顺序文件。数据区中记录不按关键字顺序排列，则称为索引非顺序文件。
索引表的生成
索引表由系统程序自动生成。
在记录输入建立数据区的同时建立一个索引表，表中的索引项按记录输入的先后次序排列，待全部记录输入完毕后再对索引表进行排序。
索引文件的检索
索引文件的检索方式为直接存取或者按关键字(进行简单询问)存取，检索过程和分块查找类似。
步骤
应分为两步：首先，查找索引表。若索引表上存在该记录，则根据索引项的指示读取外存上该记录；否则说明外存上不存在该记录，也就不需要访问外存。
由于索引项的长度比记录小得多，通产可将索引表一次读入内存，由此在索引文件中进行检索只访问外存两次，即一次读索引，一次读记录。 另外，由于索引表有序，查找索引表可用折半查找法。
索引文件的修改
- 删除。删除一个记录时，仅需删去相应的索引项；
- 插入。插入一个记录时，将记录置于数据区的末尾，同时在索引表中插入索引项；
- 更新。更新一个记录时，将更新后的记录置于数据区的末尾，同时修改索引表中相应的索引项。
查找表
当记录数目很大时，索引表也很大(以至于一个物理块容纳不下)。在这种情况下，查阅索引仍需要多次访问外存。为此，可以对索引表建立一个索引，称为查找表。
若查找表中项目还多，则可建立更高一级的索引。
通常最高可有四级索引：数据文件->索引表->查找表->第二查找表->第三查找表。此时，检索过程从最高一级的索引(第三查找表)开始，仅需访问5次内存。
静、动态索引
前文所介绍的多级索引，是一种静态索引(各级索引均为顺序表结构)。
静态索引的特点：此结构简单，但修改很不方便，每次修改都要重组索引。
当数据文件在使用过程中记录变动较多时，应采用动态索引。
动态索引，如二叉排序树(或二叉平衡树)、B-树、键树，这些都是树表结构，插入、删除都很方便。又由于它本身是层次结构，所以也不需要建立多级索引，而且建立索引表的过程即为排序的过程。
- 通常，当数据文件的记录数不是很多时，内存容量足以容纳整个索引表时可采用二叉排序树(平衡树)作索引；
- 反之，当文件很大时，索引表(树表)本身也在外存，则查找索引时需多次访问外存，并且，访问外存的次数恰为查找路径上的结点数。显然，为了减少访问外存的次数，就应尽量缩减索引表的深度。此时宜采用
m叉B-树作索引表; - 另，关于键树：索引表不大时，采用双链表(此时索引表在内存)；反之，采用Tire树。
对外存中索引表的查找效能主要取决于访问外存次数，即索引表的深度。
索引表文件只能 磁盘文件。
是否“稠密”
- 稠密索引。有序数据文件中记录不按关键字顺序排列，则必须对每个记录建立一个索引项，如此建立的索引表称之为稠密索引。
- 非稠密索引。如果数据文件中的记录按关键字顺序有序，则可对一组记录建立一个索引项，这种索引表称之为非稠密索引。
稠密索引特点：可以在索引表中进行“预查找”(即，从索引表即可确定待查记录是否存在或作某些逻辑运算)； 非稠密索引特点：不能进行“预查找”，但索引表占用的存储空间少，管理要求低。
ISAM文件 和 VSAM文件
两种有用的索引顺序文件，详情点击超链接 ISAM文件和VSAM文件 跳转。
直接存取文件(散列文件)
直接存取文件：使用杂凑(Hash)法进行组织的文件。类似Hash Table，即根据文件中关键字的特点设计一种哈希函数和处理冲突的方法将记录散列到存储设备上，故而又称散列文件。
与哈希表的区别：对于文件来说，磁盘上的文件记录通常是成组存放。若干个记录组成一个存储单元，在散列文件中，这个存储单位叫做桶(Bucket)。
假设一个桶能放m个记录(m个同义词的记录可以存放在统一地址的桶中)，当第m+1个同义词出现才发生“溢出”(处理溢出可采用哈希表中处理冲突的各种方式，但对散列文件，主要采用链地址法)。
溢出的处理
- 发生溢出时，需要将第m+1个同义词存放到另一个桶(溢出桶)中(相对地，称前m个同义词存放的桶为基桶)。
- 溢出桶和基桶大小相同，相互之间用指针链接(当基桶中没有找到待查记录时，就顺指针所指到溢出桶中进行查找)。
- (希望统一散列地址的溢出桶和基桶在磁盘上的物理位置不要相距太远，最好在同一柱面。)
桶的容量
m=3，桶数b=7
操作
查找操作步骤
根据给定值求得哈希地址(基桶号)，将基桶的记录读入内存进行顺序查找；
若 找到关键字等于给定值的记录，则检索成功；
否则 若 基桶内没有填满记录或其指针域为空，则文件内不含有代查记录；
否则 根据指针域的值的指示将溢出桶的记录读入内存继续进行顺序查找，直至检索成功或不成功。
总的查找时间：T = a (te + ti)
存取桶数的期望值(相对于哈希表中的平均查找长度)，对链地址法处理溢出来说，a = 1 + alpha / 2
装载因子：alpha = n / (b * m)
te为存取一个桶所需的时间；ti为在内存中顺序查找一个记录所需的时间；n为文件的记录数，b为桶数，m为桶的容量。
显然，增加m -> 减少alpha -> 也就使得a减小(此时虽使ti增大，但是te >> ti) -> 总时间T仍然减少。
删除操作步骤
和哈希表一样，仅需对被删记录作一标记即可。
直接存取文件的优缺点
优点：
- 文件随机存放，记录不需进行排序；
- 插入、删除操作，存取速度快，不需要索引区，节省存储空间；
缺点：
- 不能进行顺序存取，只能按关键字随机存取；
- 询问方式仅限于简单询问；
- 在经过多次的插入、删除之后，可能造成文件结构不合理(溢出桶满而基桶多数为被删除的记录)，此时需重组文件。
多关键字文件
多关键字文件的特点：在对文件进行检索操作时，不仅对主关键字进行简单询问，还经常需要对次关键字进行其他类型的询问检索。
对多关键字文件，除了按前文中讨论的方法组织文件之外，尚需建立一系列的次关键字索引。
次关键字索引可以是稠密的，也可以是非稠密的；索引表可以是顺序表，也可以是树表。和主关键字索引表不同，每个索引项应包含次关键字、具有同一次关键字的多个记录的主关键字或物理记录号。
下面是两种多关键字文件的组织方式。
多重表文件(Multilist File)
特点
记录按主关键字的顺序构成一个串联文件，并建立主关键字的索引(主索引)；对每一个次关键字项建立次关键字索引(次索引)，所有具有同一次关键字的记录构成一个链表。
主索引为非稠密索引，次索引为稠密索引。每个索引项包含次关键字、头指针和链表长度。
3个次关键字项。这些次关键索引(次索引)的存在，使处理各种次关键字的询问更加容易。
多重链表易于构造，也易于修改。
操作
如果不要求保持链表的某种次序，插入新记录：将记录插在链表的头指针之后。删去一个记录：在每个次关键字的链表中删去该记录。
倒排文件
倒排文件和多重表文件的区别在于次关键字索引的结构不同。
通常称倒排文件中的次关键字为倒排表，具有相同次关键字的记录之间不设指针相连，而在倒排表中该关键字的一项中存放这些记录的物理记录号。
优缺点
优点：检索记录较快。
- 特别是对于某些询问，不用读取记录，就可得到解答。比如对索引中的记录号作求“交”的集合元算。
- 插入和删除记录时：倒排表也要做相应的修改，值得注意的是倒排表中具有同一次关键字的记录号是有序排列的，则修改时要做相应移动。
- 若数据文件非串链文件，而是索引顺序文件(如ISAM文件)，则倒排表中应存放记录的主关键字而不是物理记录号。
缺点：维护困难
- 在同一索引表中，不同的关键字其记录数不同，各倒排表的长度不同，同一倒排表中各项长度也不等。
