第十章文件
10.1 文件的基本概念
10.2 顺序文件
10.3 索引文件
10.1.2 文件的逻辑结构
10.1.1 文件及其类别
10.1.3 文件的物理结构
10.3.2 索引顺序文件
10.4 直接存取文件
10.5.1 多重表文件
10.5.2 倒排文件
10.5 多关键字文件
10.3.1 索引文件
10.6 本章小结
10.1.1 文件及其类别
10.1 文件的基本概念
文件（ file）是根据特定的目的而收集在一起的有关数
据的集合。文件按其内部结构而分为流式文件和记录
式文件。
把能够区分文件中各记录的数据项称为关键字
若文件中的记录只有一个唯一标识记录的主关键字则
称单关键字文件；若文件中的记录除了含有一个主关
键字之外，还含有若干个次关键字，则称为多关键字
文件。
定长记录文件和不定长记录文件
记录的逻辑结构是指记录在用户或应用程序员面
前呈现的方式，是用户对数据的表示和存取方式。
记录的物理结构是数据在物理存储器上存储的方
式，是数据的物理表示和组织
逻辑记录的大小是由使用要求定的。在物理记录之间
可能存在下列 3种对应关系：
⑴ 一个物理记录存放一个逻辑记录；
⑵ 一个物理记录包含多个逻辑记录；
⑶ 多个物理记录表示一个逻辑记录。
文件的逻辑结构
文件可看成是以记录为数据元素的一种线性结构
文件的操作
文件的操作主要有两类：检索和维护修改
?文件的检索
文件的检索有下列 3种方式
⑴ 顺序存取：存取下一个逻辑记录；
⑵ 直接存取：存取第 i 个逻辑记录。
⑶ 按关键字存取：给定一个值，查询一个或一批关
键字与给定值相关的记录。
10.1.2文件的逻辑结构
文件可以有如下 4种查询方式
⑴ 简单询问：查询关键字等于给定值的记录
⑵ 区域询问：查询关键字属于某个区域的记录
⑶ 函数询问：给定关键字的某个函数。
⑷ 布尔询问。以上 3种询问用布尔运算组合起来的询
问
文件的维护操作主要是指：
① 对文件进行记录的插入、删除及修改等更新操作。
② 为提高文件的效率，进行再组织操作，
③ 文件被破坏后的恢复操作，以及文件中数据的安全
保护等
文件的操作方式：
文件的操作可分为实时的和批量的两种不同方式。
① 实时处理：对应答时间要求严格。应在接收询问之
后几秒钟内完成检索和修改。
② 批量处理：响应时间要求宽松一些，不同的文件系
统有不同的要求。响应时间不是一个重要因素。采用
这种方式时，操作要求被随机地放在一个事务文件中，
直到收到适当数量的操作或经过适当的一段时间，才
对事务文件中的全部操作一并处理。在批处理中，一
般地，将对文件操作要求组成的文件称为事务文件，
将被操作的文件称为主文件。
10.1.3 文件的物理结构
文件的物理结构 (亦称文件的存储结构 )：文件在存储介
质（磁盘或磁带）上组织方式称为文件的物理结构。
基本组织方式有 3种：顺序组织，随机组织和链组织。
文件的物理结构 (亦称文件的存储结构 )：文件在存储介
质（磁盘或磁带）上组织方式称为文件的物理结构。
基本组织方式有 3种：顺序组织，随机组织和链组织。
磁带信息的存取
磁带存储器早在 20世纪 50年代初就广泛使用，其优点
是存储容量大，使用方便，价格便宜。
在磁带上读 /写一块信息所需的时间由两部分组成：
Ti/o=ta+n*tw
其中,ta为延迟时间，读 /写头到达传输信息所在物
理块起始位置所需时间； tw为传输一个字符的时间。
磁盘是一种直接存取的设备（ DASD）。它是以存取时
间变化不大为特征的。它不象磁带那样只能进行顺序
存取，而可以直接存取任何字符组。
在磁盘上读 /写一块信息所需的时间由 3部分组成：
Ti/o=tseek+tla+n*twm
其中,tseek为寻查时间，即读 /写头定位的时间； tla为
等待时间，即等待信息块的初始位置旋转到读 /写头下
的时间； twm为传输时间；
文件组织效率的评价标准
评价一个文件组织的效率，是执行文件操作所花费的
时间和文件组织所需的存储空间。
10.2 顺序文件
顺序文件是记录按其在文件中的逻辑顺序依次进入存
储介质建立的，即顺序文件中物理记录的顺序和逻辑
记录的顺序是一致的 。
?顺序文件是根据记录的序号（或相对位置）来进行
存取的文件组织方式。它的特点是：
⑴ 存取第 i个记录，必须先存取前面的 i-1个记录；
⑵ 插入新的记录时只能加在文件的末尾；
⑶ 若要更新文件中的某个记录，必须将整个文件进
行复制。
优点是连续存取速度快，因此主要用于只进行顺序存取
，批量修改的情况。若对应答时间要求不严格时亦可进
行直接存取
终 端
修 改 请 求
事 务
文 件
排 序
有 序 的
事 务 文
件
主 文 件
新 主 文
件
磁 带 文 件 批 处 理 示 意 图
磁带是一种典型的顺序存取的设备，因此存储在磁带
上的文件只能是顺序文件。磁带文件适合于文件的数
量甚大、平时记录变化少，只作批量修改的情况 。
??磁盘上的顺序文件的批处理和磁带文件类似，只是
当修改项中没有插入、且更新时 事务文件不增加记录
的长度时，可以不建立新的主文件，而直接修改原来
的主文件即可。显然，磁盘文件的批处理可以在一台
磁盘组上进行
??顺序文件进行顺序查找类似于第 9章讨论的顺序查找，
其平均查找长度为
。
10.3 索引文件
10.3.1 索引文件
?索引文件
索引文件由主文件和索引表构成。主文件：文件本身。
索引表：在文件本身外建立的一张表，它指明逻辑记
录和物理记录之间的一一对应关系。
?索引表组成
索引表由若干索引项组成。一般索引项由主关键字和
该关键字所在记录的物理地址组成。
最常用的索引顺序文件,ISAM文件和 VSAM文件
索引文件的存储
索引文件在存储器上分为两个区：索引区和数据区。
索引区存放索引表，数据区存放主文件。
索引文件的建立
建立索引文件的过程：（ 1）按输入记录的先后次序建
立数据区和索引表。其中索引表中关键字是无序的。
（ 2）待全部记录输入完毕后对索引表进行排序，排序
后的索引表和主文件一起就形成了索引文件。
职工号 姓名 其他
03 丁一
10 王二
07 张三
05 李四
06 陈平
12 刘宁
14 李丽
09 赵宁
物理地址
表 1 数据文件
101
102
103
104
105
106
107
108
关键字 物理地址
03 101
10 102
07 103
05 104
06 105
12 106
14 107
09 108
物理地址
201
202
202
203
203
201
201
202
表 2 排序前的索引区
关键字 物理地址
03 101
05 104
06 105
07 103
09 108
10 102
12 106
14 107
物理地址
201
202
202
203
203
201
201
202
表 3 排序后的索引区
索引文件的建立
索引文件的操作
1．检索操作 2．更新操作
利用查找表建立多级索引
当记录数目很大时，索引表也很大，以致于一个物理
块容纳不下查询索引仍要多次访问外存，为此，可以
对索引表建立一个索引，称为查找表
若查找表中项目很多，则可建立再高一级的索引。通
常最高可有 4级索引：数据文件 → 索引表 → 查找表 → 第
二查找表 → 第三查找表。而检索过程从最高一级索引
即第三查找表开始，仅需 5次访问外存。
动态索引
上述的多级索引是一种静态索引，各级索引均为顺序表
结构，其结构简单，但修改很不方便，每次修改都要重
组索引。因此，当数据文件在使用过程中记录变动较多
时，利用二叉排序树 (或 AVL树 ),B树 (或其变型 )等树表
结构建立的索引，为动态索引
（ 1）树表特点
（ 2）树表结构选择
（ 3） 外存的索引表的查找性能评价
⒈ ISAM 文件
它是一种专为磁盘存取文件设计的文件组织方式，采
用静态索引结构。由于磁盘是以盘组、柱面和磁道三
级地址存取的设备，则可对磁盘上的数据文件建立盘
组、柱面和磁道多级索引
10.3.2索引顺序文件
ISAM文件的组成
ISAM文件由多级主索引、柱面索引、磁道索引和主
文件组成
ISAM文件的检索
从主索引出发，找到相应的柱面索引；从柱面索引找到
记录所在柱面的磁道索引；从磁道索引找到记录所在磁
道的起始地址，在该磁道上进行顺序查找，直到找到为
止。若找不到，则无此记录；若记录在溢出区，从磁道
索引项的溢出索引项中得到溢出链表的头指针，然后对
该表进行顺序查找。
ISAM文件的插入操作
首先找到插入的磁道。若磁道不满，记录插入该磁道的适
当位置；若磁道满，记录或者插在磁道上，或者插入到该
磁道的溢出链表上。插入后，可能要修改磁道索引中的基
本索引项和溢出索引项。
删除记录的操作
在其存储位置上作删除标记即可, 而不需要移动记录或
改变指针 。
在经过多次的增删后
大量的记录进入溢出区, 而基本区中又浪费很多的空间 。
把记录读入内存重新排列 。
⒉ VSAM文件
这种存取方法利用了操作系统的分页功能，与机器无
关。它的存储单位 — 控制区域和控制区间是逻辑的，
与柱面、磁道等设备的存储单位没有必然的联系。
VASM文件的结构由 3部分组成：索引集，顺序集和数
据集
在 VASM文件中，记录可以是不定长的，则在控制区
间中除了存放记录本身以外，还有每个记录的控制信
息和整个区间的控制信息。
VASM 文件中没有溢出区，解决插入的办法是在初建
文件时留有空间
…
…
…
…
索 引 集
顺 序 集
数 据 集
B + - 树
控 制 区 域
控 制 区 间
V S A M 文 件 的 结 构 示 意 图
直接存取文件的组织方式
直接存取文件指的是利用 Hash法进行组织的文件。它类
似于 Hash表，即根据文件关键字的特点设计 Hash函
数和处理冲突的方法将记录散列到存储设备上，故又
称散列文件。
10.4 直接存取文件
基桶和溢出桶
7
1
23
24
18
5
27
2
4
26
6
09
12
Λ
Λ
Λ
Λ
Λ
0
1
2
3
4
5
6
直接存取文件示例
16 Λ
19 33 Λ
桶编号
基桶
溢出桶
散列文件的查找操作
在散列文件中查找的过程：
（ 1） 根据给定值求出散列桶地址 ；
（ 2） 将基桶的记录读入内存，进行顺序查找；
（ 3） 若找到关键字等于给定值的记录，则检索成
功；否则，读人溢出桶的记录继续进行查找。
散列文件的删除操作
在散列文件中删去一个记录，仅需对被删记录作删除
标记即可。
散列文件的优点：
文件随机存放，记录不需进行排序；插入、删除
方便；
存取速度快；不需要索引区，节省存储空间。
散列文件的缺点：
不能进行顺序存取，只能按关键字随机存取；询
问方式限于简单询问；在经过多次插入、删除
后，可能造成文件结构不合理，需要重新组织
文件
多重表文件的组织方式,
对每个需要查询的次关键字建立一个索引, 同时将具有
相同次关键字的记录链接成一个链表, 并将此链表的头
指针, 链表长度及次关键字作为索引表的一个索引项 。
通常多重表文件的主文件是一个顺序文件 。
10.5 多关键字文件
10.5.1 多重表文件
多重表的更新操作
插入新记录：
相同次关键字链表不按主关键字大小链接时，在主文件
中插入新记录后，将记录在各个次关键字链表中插在
链表的头指针之后即可。
删除记录：
在删去一个记录的同时，需在每个次关键字的链表中删
去该记录
倒排文件的组织方式和特点
在次关键字索引中，具有相同次关键字的记录之间不进
行链接，而是列出具有该次关键字记录的物理地址。
倒排文件中的次关键字索引称做倒排表。倒排表和主
文件一起就构成了倒排文件
10.5.2 倒排文件
倒排文件的查询
处理复杂的多关键字查询时，可在倒排表中先完成查
询的交、并等逻辑运算，得到结果后再对记录进行存取。
这样不必对每个记录随机存取，把对记录的查询转换为
地址集合的运算，从而提高查找速度。
倒排文件的更新
在插入和删除记录时，还要修改倒排表。
列出主关键字的倒排表的特点：
① 存取速度较慢；
② 主关键字可看成是记录的符号地址，对于存储具有相
对独立性。
倒排文件与一般文件组织的区别
在一般的文件组织中，是先找记录，然后再找到该记录
所含的各次关键字；而倒排文件中，是先给定次关键字，
然后查找含有该次关键字的各个记录，这种文件的查找
次序正好与一般文件的查找次序相反，因此称之为 "倒
排 "。
倒排文件的缺点是维护困难，因为在同一索引表中，不
同的关键字其记录数不同，各倒排表的长度不等，同一
倒排表中各项长度也不等。
10.6本章小结
本章的基本内容是：有关文件的基本概念，文件逻辑结
构与物理结构的关系，各种文件（顺序文件、索引文件、
索引顺序文件、散列文件、多重表文件和倒排文件）的
构造方法及文件操作在其上的实现 。
本章要求如下：
1,掌握文件基本概念，文件的分类，逻辑结构与物理结
构的关系。
2,熟悉顺序文件、随机文件、直接存取文件和多关键字
文件的概念。在各类文件上如何实现检索，插入和删除
等操作 。
10.1 文件的基本概念
10.2 顺序文件
10.3 索引文件
10.1.2 文件的逻辑结构
10.1.1 文件及其类别
10.1.3 文件的物理结构
10.3.2 索引顺序文件
10.4 直接存取文件
10.5.1 多重表文件
10.5.2 倒排文件
10.5 多关键字文件
10.3.1 索引文件
10.6 本章小结
10.1.1 文件及其类别
10.1 文件的基本概念
文件（ file）是根据特定的目的而收集在一起的有关数
据的集合。文件按其内部结构而分为流式文件和记录
式文件。
把能够区分文件中各记录的数据项称为关键字
若文件中的记录只有一个唯一标识记录的主关键字则
称单关键字文件；若文件中的记录除了含有一个主关
键字之外，还含有若干个次关键字，则称为多关键字
文件。
定长记录文件和不定长记录文件
记录的逻辑结构是指记录在用户或应用程序员面
前呈现的方式，是用户对数据的表示和存取方式。
记录的物理结构是数据在物理存储器上存储的方
式，是数据的物理表示和组织
逻辑记录的大小是由使用要求定的。在物理记录之间
可能存在下列 3种对应关系：
⑴ 一个物理记录存放一个逻辑记录；
⑵ 一个物理记录包含多个逻辑记录；
⑶ 多个物理记录表示一个逻辑记录。
文件的逻辑结构
文件可看成是以记录为数据元素的一种线性结构
文件的操作
文件的操作主要有两类：检索和维护修改
?文件的检索
文件的检索有下列 3种方式
⑴ 顺序存取：存取下一个逻辑记录；
⑵ 直接存取：存取第 i 个逻辑记录。
⑶ 按关键字存取：给定一个值，查询一个或一批关
键字与给定值相关的记录。
10.1.2文件的逻辑结构
文件可以有如下 4种查询方式
⑴ 简单询问：查询关键字等于给定值的记录
⑵ 区域询问：查询关键字属于某个区域的记录
⑶ 函数询问：给定关键字的某个函数。
⑷ 布尔询问。以上 3种询问用布尔运算组合起来的询
问
文件的维护操作主要是指：
① 对文件进行记录的插入、删除及修改等更新操作。
② 为提高文件的效率，进行再组织操作，
③ 文件被破坏后的恢复操作，以及文件中数据的安全
保护等
文件的操作方式：
文件的操作可分为实时的和批量的两种不同方式。
① 实时处理：对应答时间要求严格。应在接收询问之
后几秒钟内完成检索和修改。
② 批量处理：响应时间要求宽松一些，不同的文件系
统有不同的要求。响应时间不是一个重要因素。采用
这种方式时，操作要求被随机地放在一个事务文件中，
直到收到适当数量的操作或经过适当的一段时间，才
对事务文件中的全部操作一并处理。在批处理中，一
般地，将对文件操作要求组成的文件称为事务文件，
将被操作的文件称为主文件。
10.1.3 文件的物理结构
文件的物理结构 (亦称文件的存储结构 )：文件在存储介
质（磁盘或磁带）上组织方式称为文件的物理结构。
基本组织方式有 3种：顺序组织，随机组织和链组织。
文件的物理结构 (亦称文件的存储结构 )：文件在存储介
质（磁盘或磁带）上组织方式称为文件的物理结构。
基本组织方式有 3种：顺序组织，随机组织和链组织。
磁带信息的存取
磁带存储器早在 20世纪 50年代初就广泛使用，其优点
是存储容量大，使用方便，价格便宜。
在磁带上读 /写一块信息所需的时间由两部分组成：
Ti/o=ta+n*tw
其中,ta为延迟时间，读 /写头到达传输信息所在物
理块起始位置所需时间； tw为传输一个字符的时间。
磁盘是一种直接存取的设备（ DASD）。它是以存取时
间变化不大为特征的。它不象磁带那样只能进行顺序
存取，而可以直接存取任何字符组。
在磁盘上读 /写一块信息所需的时间由 3部分组成：
Ti/o=tseek+tla+n*twm
其中,tseek为寻查时间，即读 /写头定位的时间； tla为
等待时间，即等待信息块的初始位置旋转到读 /写头下
的时间； twm为传输时间；
文件组织效率的评价标准
评价一个文件组织的效率，是执行文件操作所花费的
时间和文件组织所需的存储空间。
10.2 顺序文件
顺序文件是记录按其在文件中的逻辑顺序依次进入存
储介质建立的，即顺序文件中物理记录的顺序和逻辑
记录的顺序是一致的 。
?顺序文件是根据记录的序号（或相对位置）来进行
存取的文件组织方式。它的特点是：
⑴ 存取第 i个记录，必须先存取前面的 i-1个记录；
⑵ 插入新的记录时只能加在文件的末尾；
⑶ 若要更新文件中的某个记录，必须将整个文件进
行复制。
优点是连续存取速度快，因此主要用于只进行顺序存取
，批量修改的情况。若对应答时间要求不严格时亦可进
行直接存取
终 端
修 改 请 求
事 务
文 件
排 序
有 序 的
事 务 文
件
主 文 件
新 主 文
件
磁 带 文 件 批 处 理 示 意 图
磁带是一种典型的顺序存取的设备，因此存储在磁带
上的文件只能是顺序文件。磁带文件适合于文件的数
量甚大、平时记录变化少，只作批量修改的情况 。
??磁盘上的顺序文件的批处理和磁带文件类似，只是
当修改项中没有插入、且更新时 事务文件不增加记录
的长度时，可以不建立新的主文件，而直接修改原来
的主文件即可。显然，磁盘文件的批处理可以在一台
磁盘组上进行
??顺序文件进行顺序查找类似于第 9章讨论的顺序查找，
其平均查找长度为
。
10.3 索引文件
10.3.1 索引文件
?索引文件
索引文件由主文件和索引表构成。主文件：文件本身。
索引表：在文件本身外建立的一张表，它指明逻辑记
录和物理记录之间的一一对应关系。
?索引表组成
索引表由若干索引项组成。一般索引项由主关键字和
该关键字所在记录的物理地址组成。
最常用的索引顺序文件,ISAM文件和 VSAM文件
索引文件的存储
索引文件在存储器上分为两个区：索引区和数据区。
索引区存放索引表，数据区存放主文件。
索引文件的建立
建立索引文件的过程：（ 1）按输入记录的先后次序建
立数据区和索引表。其中索引表中关键字是无序的。
（ 2）待全部记录输入完毕后对索引表进行排序，排序
后的索引表和主文件一起就形成了索引文件。
职工号 姓名 其他
03 丁一
10 王二
07 张三
05 李四
06 陈平
12 刘宁
14 李丽
09 赵宁
物理地址
表 1 数据文件
101
102
103
104
105
106
107
108
关键字 物理地址
03 101
10 102
07 103
05 104
06 105
12 106
14 107
09 108
物理地址
201
202
202
203
203
201
201
202
表 2 排序前的索引区
关键字 物理地址
03 101
05 104
06 105
07 103
09 108
10 102
12 106
14 107
物理地址
201
202
202
203
203
201
201
202
表 3 排序后的索引区
索引文件的建立
索引文件的操作
1．检索操作 2．更新操作
利用查找表建立多级索引
当记录数目很大时，索引表也很大，以致于一个物理
块容纳不下查询索引仍要多次访问外存，为此，可以
对索引表建立一个索引，称为查找表
若查找表中项目很多，则可建立再高一级的索引。通
常最高可有 4级索引：数据文件 → 索引表 → 查找表 → 第
二查找表 → 第三查找表。而检索过程从最高一级索引
即第三查找表开始，仅需 5次访问外存。
动态索引
上述的多级索引是一种静态索引，各级索引均为顺序表
结构，其结构简单，但修改很不方便，每次修改都要重
组索引。因此，当数据文件在使用过程中记录变动较多
时，利用二叉排序树 (或 AVL树 ),B树 (或其变型 )等树表
结构建立的索引，为动态索引
（ 1）树表特点
（ 2）树表结构选择
（ 3） 外存的索引表的查找性能评价
⒈ ISAM 文件
它是一种专为磁盘存取文件设计的文件组织方式，采
用静态索引结构。由于磁盘是以盘组、柱面和磁道三
级地址存取的设备，则可对磁盘上的数据文件建立盘
组、柱面和磁道多级索引
10.3.2索引顺序文件
ISAM文件的组成
ISAM文件由多级主索引、柱面索引、磁道索引和主
文件组成
ISAM文件的检索
从主索引出发，找到相应的柱面索引；从柱面索引找到
记录所在柱面的磁道索引；从磁道索引找到记录所在磁
道的起始地址，在该磁道上进行顺序查找，直到找到为
止。若找不到，则无此记录；若记录在溢出区，从磁道
索引项的溢出索引项中得到溢出链表的头指针，然后对
该表进行顺序查找。
ISAM文件的插入操作
首先找到插入的磁道。若磁道不满，记录插入该磁道的适
当位置；若磁道满，记录或者插在磁道上，或者插入到该
磁道的溢出链表上。插入后，可能要修改磁道索引中的基
本索引项和溢出索引项。
删除记录的操作
在其存储位置上作删除标记即可, 而不需要移动记录或
改变指针 。
在经过多次的增删后
大量的记录进入溢出区, 而基本区中又浪费很多的空间 。
把记录读入内存重新排列 。
⒉ VSAM文件
这种存取方法利用了操作系统的分页功能，与机器无
关。它的存储单位 — 控制区域和控制区间是逻辑的，
与柱面、磁道等设备的存储单位没有必然的联系。
VASM文件的结构由 3部分组成：索引集，顺序集和数
据集
在 VASM文件中，记录可以是不定长的，则在控制区
间中除了存放记录本身以外，还有每个记录的控制信
息和整个区间的控制信息。
VASM 文件中没有溢出区，解决插入的办法是在初建
文件时留有空间
…
…
…
…
索 引 集
顺 序 集
数 据 集
B + - 树
控 制 区 域
控 制 区 间
V S A M 文 件 的 结 构 示 意 图
直接存取文件的组织方式
直接存取文件指的是利用 Hash法进行组织的文件。它类
似于 Hash表，即根据文件关键字的特点设计 Hash函
数和处理冲突的方法将记录散列到存储设备上，故又
称散列文件。
10.4 直接存取文件
基桶和溢出桶
7
1
23
24
18
5
27
2
4
26
6
09
12
Λ
Λ
Λ
Λ
Λ
0
1
2
3
4
5
6
直接存取文件示例
16 Λ
19 33 Λ
桶编号
基桶
溢出桶
散列文件的查找操作
在散列文件中查找的过程：
（ 1） 根据给定值求出散列桶地址 ；
（ 2） 将基桶的记录读入内存，进行顺序查找；
（ 3） 若找到关键字等于给定值的记录，则检索成
功；否则，读人溢出桶的记录继续进行查找。
散列文件的删除操作
在散列文件中删去一个记录，仅需对被删记录作删除
标记即可。
散列文件的优点：
文件随机存放，记录不需进行排序；插入、删除
方便；
存取速度快；不需要索引区，节省存储空间。
散列文件的缺点：
不能进行顺序存取，只能按关键字随机存取；询
问方式限于简单询问；在经过多次插入、删除
后，可能造成文件结构不合理，需要重新组织
文件
多重表文件的组织方式,
对每个需要查询的次关键字建立一个索引, 同时将具有
相同次关键字的记录链接成一个链表, 并将此链表的头
指针, 链表长度及次关键字作为索引表的一个索引项 。
通常多重表文件的主文件是一个顺序文件 。
10.5 多关键字文件
10.5.1 多重表文件
多重表的更新操作
插入新记录：
相同次关键字链表不按主关键字大小链接时，在主文件
中插入新记录后，将记录在各个次关键字链表中插在
链表的头指针之后即可。
删除记录：
在删去一个记录的同时，需在每个次关键字的链表中删
去该记录
倒排文件的组织方式和特点
在次关键字索引中，具有相同次关键字的记录之间不进
行链接，而是列出具有该次关键字记录的物理地址。
倒排文件中的次关键字索引称做倒排表。倒排表和主
文件一起就构成了倒排文件
10.5.2 倒排文件
倒排文件的查询
处理复杂的多关键字查询时，可在倒排表中先完成查
询的交、并等逻辑运算，得到结果后再对记录进行存取。
这样不必对每个记录随机存取，把对记录的查询转换为
地址集合的运算，从而提高查找速度。
倒排文件的更新
在插入和删除记录时，还要修改倒排表。
列出主关键字的倒排表的特点：
① 存取速度较慢；
② 主关键字可看成是记录的符号地址，对于存储具有相
对独立性。
倒排文件与一般文件组织的区别
在一般的文件组织中，是先找记录，然后再找到该记录
所含的各次关键字；而倒排文件中，是先给定次关键字，
然后查找含有该次关键字的各个记录，这种文件的查找
次序正好与一般文件的查找次序相反，因此称之为 "倒
排 "。
倒排文件的缺点是维护困难，因为在同一索引表中，不
同的关键字其记录数不同，各倒排表的长度不等，同一
倒排表中各项长度也不等。
10.6本章小结
本章的基本内容是：有关文件的基本概念，文件逻辑结
构与物理结构的关系，各种文件（顺序文件、索引文件、
索引顺序文件、散列文件、多重表文件和倒排文件）的
构造方法及文件操作在其上的实现 。
本章要求如下：
1,掌握文件基本概念，文件的分类，逻辑结构与物理结
构的关系。
2,熟悉顺序文件、随机文件、直接存取文件和多关键字
文件的概念。在各类文件上如何实现检索，插入和删除
等操作 。
