2001 -- 12 --31
华中科技大学计算机学院 (16)数据结构第 12章 文 件内存不能永久性保存数据，以及容量有限，所以需要数据以文件形式存放到外部存储器中。
12.1 文件的基本概念文件,由大量性质相同的记录组成的集合。
记录,文件中可存取的基本数据单位，它有若干个数据项组成。
数据项,最基本的不可再分的数据单位。数据项的名称称为 记录的域 。
关键字,能够区分文件中各记录的域。
主关键字 -----可以唯一地标识一个记录的关键字 ；
次关键字 -----不能 唯一地标识一个记录的关键字 。
文件分类,
按记录类型划分：
（ 1） 流式文件,由一维的连续的字符（字节）序列组成，无结构，无解释。如 C源程序。此时的记录为单个字符（字节）。
（ 2） 记录文件,记录是由一个或多个数据项组成的集合。如,db,dbf文件。
按记录长度划分：
（ 1） 定长记录文件,文件中每个记录含有的信息长度相同。
（ 2） 不定长记录文件,文件有含有长度不等的记录组成。
记录的逻辑结构和物理结构,
逻辑结构,呈现在用户和应用程序员面前的数据组织形式，
是用户对数据的表示和存取方式。着眼于用户使用方便。
物理结构,数据在物理存储器上存储的方式，是数据的物理表示和组织。应考虑提高存储空间的利用率和减少存取记录的时间。
物理记录,是计算机用一条 I/O命令进行读写的基本数据单位。
对固定的设备和操作系统，它的大小基本上是固定不变的。
逻辑记录和物理记录的三种关系：
（ 1）一个物理记录存放一个逻辑记录；
（ 2）一个物理记录存放多个逻辑记录；
（ 3）多个物理记录存放一个逻辑记录；
用户读写记录是对逻辑记录，而操作系统对物理记录。
文件的操作,（ 1）检索； （ 2）修改。
文件的检索一般有三种,
（ 1） 顺序存取,从当前位置开始，存取下一个逻辑记录；
（ 2） 直接存取,存取第 i个逻辑记录；
以上两种存取方式都是根据记录的序号（即记录存入文件时的序号）或记录的相对位置进行存取。
（ 3） 按关键字存取,给定一个值，查询一个或一批关键字与给定值相关的记录。
对数据库文件的查询有四种：
（ a） 简单查询：查询关键字等于给定值的记录；
（ b） 区域查询：查询关键字属于某个区域的记录；
（ c） 函数查询：给定关键字的某个函数；例如查询平均分以上的记录。
（ d） 布尔查询：以上三种查询用布尔运算组合起来的查询。
例如查询总分 600以上并且数学在 100分以上，或总分在平均分以下并且外语在 98分以上的所有记录。
文件的修改包括,
(1) 插入一个记录； (2) 删除一个记录； (3) 更新一个记录。
文件的操作有两种方式：
（ 1）实时：应答时间要求严格，要求在给定时间内完成。
（ 2）批量。
文件组织的三种基本形式：
（ 1）顺序组织；（ 2）随机组织；（ 3）链组织。
12.2 顺序文件顺序文件 （ Sequential File)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录和逻辑记录的顺序是一致的。
如果次序相继的两个物理记录在存储介质上的存储位置是相邻的，则又成 连续文件 。
如果两个物理记录之间的次序有指针链表示，则称 串联文件 。
顺序文件是根据记录序号或记录的相对位置来进行存取的文件组织方式，特点：
（ 1）存取第 i个记录，必须搜索在它之前的 i-1个记录；
（ 2）插入新的记录只能在文件尾；
（ 3）若要更新文件中的某个记录，必须将整个文件复制。
顺序文件的优点是连续存取速度快，在查找和修改都是成批处理的情况下，以顺序文件为佳。
顺序文件的分类：
（ 1） 按关键字排列；
（ 2） 未按关键字排列，仅按先后次序。
顺序文件的操作,
（ 1）顺序存取：从文件的第 1个记录依次顺序存取，存取效率很高。
（ 2）随机存取：对指定的记录进行存取，但这种要求对顺序文件来说，极不方便，存取效率很低。
（ 3）按关键字存取：需从文件的第 1个记录开始查找，一般情况下，存取效率不高。
12.3 索引文件除文件自身（称作数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表：索引表。这类包括文件数据区和索引表两大部分的文件称为 索引文件 。
索引表的每一项称为 索引项 。
不论主文件是否按关键字有序，索引表中的索引项总是按关键字顺序排列。若数据区中的记录也按关键字顺序排列，则称 索引顺序文件,反之，称 索引非顺序文件 。
物理记录号 职工号 姓名 职务 其它
101 29 张三 教授 。
102 05 李四 讲师 。
103 02 王红 助教 。
104 38 。 。 。
105 31 。 。 。
106 43 。 。 。
107 17 。 。 。
108 50 。 。 。
109 49 。 。 。
110 47 。 。 。
111 56 。 。 。
(a) 文件数据区关键字 物理记录号
02 103
05 102
17 107
29 101
31 105
38 104
43 106
47 110
49 109
50 108
56 111
(b) 索引表
12.4 索引顺序文件索引顺序文件 是指记录按关键字顺序存放的索引文件。其存储结构分三个区,索引区、基本记录区和溢出区 。
基本记录区是按记录的关键字排序的。因此不必为每一个记录保存一个索引项，而只要 把记录区分块,通常是一个磁道作为一块,每块记录设一个索引项 。保存该块的最大关键字值。
溢出记录区是为了解决插入问题而设置的，在这种文件中，
由于记录按关键字值顺序存放，因此，如果新增记录要插入到两个原有记录之间时，需要调整记录区，如果当前块已满，则最后一记录被调整出当前块，放入溢出记录区。溢出区采用链表结构。
基本索引项 溢出索引项关键字值 指针 关键字值 指针基本数据区每一块设一个索引项，登记该块内的最后一个记录的关键字值和该块记录的首地址。
溢出数据区的记录用指针链接，从基本数据区同一块中溢出的记录形成一个链表，基本数据区有多少个块，溢出区就可能有多少个链表。
溢出区索引项登记该块的第一个溢出记录的关键字值
（作为本块的关键字值的上界）和该块最近溢出的记录在溢出区的地址。
基本索引项 溢出索引项 基本索引项 溢出索引项
90 T2,1 / 145 T3,1 /
1记录 2记录 3记录 4记录 5记录
R50 R60 R70 R80 R90 T 2
R100 R130 R135 R140 R145 T 3
T4
索引基本区溢出区索引顺序文件存储示意图基本索引项 溢出索引项 基本索引项 溢出索引项
80 T2,1 90 T4,1 145 T3,1 /
1记录 2记录 3记录 4记录 5记录
R50 R60 R65 R70 R80 T 2
R100 R130 R135 R140 R145 T 3
R90 / T4
索引基本区溢出区插入 R65后，基本数据区的 R70 到 R90 后移,R90到溢出区基本索引项 溢出索引项 基本索引项 溢出索引项
80 T2,1 90 T4,1 140 T3,1 145 T4,2
1记录 2记录 3记录 4记录 5记录
R50 R60 R65 R70 R80 T 2
R95 R100 R130 R135 R140 T 3
R90 / R145 / T4
索引基本区溢出区插入 R95后，基本数据区的 R100 到 R145 后移,R145到溢出区基本索引项 溢出索引项 基本索引项 溢出索引项
80 T2,1 90 T4,3 140 T3,1 145 T4,2
1记录 2记录 3记录 4记录 5记录
R50 R60 R65 R70 R80 T 2
R95 R100 R130 R135 R140 T 3
R90 / R145 / R83 T4,1 T4
索引基本区溢出区插入 R83时，因 80<83<90,所以直接加入到溢出区
12.5 多关键字文件多关键字文件的特点,对文件进行检索操作时，不仅对主关键字进行简单询问，还经常对次关键字进行其它类型的询问检索。
如下页表格中，学号为主关键字，专业、已修学分、选修课目等为次关键字。允许的查询：
根据学号查询某学生的信息；
查询已修学分 400分以上的学生；
查询已修学分 400分以上计算机专业的学生人数；
其他查询为此，对多关键字文件，可建立一系列的次关键字索引。
姓名 学号 专业 已修学分 选修课目王 文 1350 软件 412 丙 丁马小燕 1351 软件 398 甲 丙阮 森 1352 计算机 436 乙 丙 丁苏明明 1353 应用 402 甲 丙田 水 1354 计算机 384 乙 丁杨 青 1355 应用 356 甲薛平平 1356 软件 398 甲 乙崔子健 1357 软件 408 甲 丙王 洪 1358 应用 370 甲 丁刘 倩 1359 应用 364 甲学生信息表
12.5.1 多重表文件多重表文件的特点,记录按主关键字的顺序构成一个串联文件。并建立主关键字的索引（成为主索引），主索引为非稠密索引。如下页图所示为一个多重链表文件，记录按学号链接，
为查找方便，分成三个链表。
对每一个次关键字建立一个稠密索引。相同次关键字的记录形成一个链表。
12.5.1 多重表文件多重表文件的特点,记录按主关键字的顺序构成一个串联文件。并建立主关键字的索引（成为主索引），主索引为非稠密索引。如下页图所示为一个多重链表文件，记录按学号链接，
为查找方便，分成三个链表。
对每一个次关键字建立一个稠密索引。相同次关键字的记录形成一个链表。
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
主关键字头指针
1353 01
1357 05
1359 09
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 头指针 长度软件 01 4
计算机 03 2
应用 04 4
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 头指针 长度
350～ 399 06 6
400～ 499 04 4
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 头指针 长度甲 02 7
乙 03 3
丙 01 5
丁 01 4
12.5.2 倒排表文件倒排文件和多重文件的区别在次关键字索引的结构不同，
通常，称倒排文件中的次关键字索引为 倒排表,具有相同次关键字的记录之间不设指针相链。而在倒排表中该次关键字的一项中存放这些记录的物理记录号。
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 记录物理地址软件 01,02,07,08
计算机 03,05
应用 04,06,09,10
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 记录物理地址
350～ 399 02,05,06,07,09,10
400～ 499 01,03,04,08
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 记录物理地址甲 02,04,06,07,08,09,10
乙 03,05,07
丙 01,02,03,04,08
丁 01,03,05,09
操作方法：
查询已修学分 400分以上计算机专业的学生人数时，查询 400分以上的项得集合 {01,03,04,08},查询计算机专业的项得集合
{03,05}，求交集，得符合条件的仅仅 1人,03号记录。
插入记录 {“李明”,1360，“计算机”,400,{甲，乙 }}到 11
号记录位置时，根据次关键字在相应项中填入新记录的物理记录号。
华中科技大学计算机学院 (16)数据结构第 12章 文 件内存不能永久性保存数据，以及容量有限，所以需要数据以文件形式存放到外部存储器中。
12.1 文件的基本概念文件,由大量性质相同的记录组成的集合。
记录,文件中可存取的基本数据单位，它有若干个数据项组成。
数据项,最基本的不可再分的数据单位。数据项的名称称为 记录的域 。
关键字,能够区分文件中各记录的域。
主关键字 -----可以唯一地标识一个记录的关键字 ；
次关键字 -----不能 唯一地标识一个记录的关键字 。
文件分类,
按记录类型划分：
（ 1） 流式文件,由一维的连续的字符（字节）序列组成，无结构，无解释。如 C源程序。此时的记录为单个字符（字节）。
（ 2） 记录文件,记录是由一个或多个数据项组成的集合。如,db,dbf文件。
按记录长度划分：
（ 1） 定长记录文件,文件中每个记录含有的信息长度相同。
（ 2） 不定长记录文件,文件有含有长度不等的记录组成。
记录的逻辑结构和物理结构,
逻辑结构,呈现在用户和应用程序员面前的数据组织形式，
是用户对数据的表示和存取方式。着眼于用户使用方便。
物理结构,数据在物理存储器上存储的方式，是数据的物理表示和组织。应考虑提高存储空间的利用率和减少存取记录的时间。
物理记录,是计算机用一条 I/O命令进行读写的基本数据单位。
对固定的设备和操作系统，它的大小基本上是固定不变的。
逻辑记录和物理记录的三种关系：
（ 1）一个物理记录存放一个逻辑记录；
（ 2）一个物理记录存放多个逻辑记录；
（ 3）多个物理记录存放一个逻辑记录；
用户读写记录是对逻辑记录，而操作系统对物理记录。
文件的操作,（ 1）检索； （ 2）修改。
文件的检索一般有三种,
（ 1） 顺序存取,从当前位置开始，存取下一个逻辑记录；
（ 2） 直接存取,存取第 i个逻辑记录；
以上两种存取方式都是根据记录的序号（即记录存入文件时的序号）或记录的相对位置进行存取。
（ 3） 按关键字存取,给定一个值，查询一个或一批关键字与给定值相关的记录。
对数据库文件的查询有四种：
（ a） 简单查询：查询关键字等于给定值的记录；
（ b） 区域查询：查询关键字属于某个区域的记录；
（ c） 函数查询：给定关键字的某个函数；例如查询平均分以上的记录。
（ d） 布尔查询：以上三种查询用布尔运算组合起来的查询。
例如查询总分 600以上并且数学在 100分以上，或总分在平均分以下并且外语在 98分以上的所有记录。
文件的修改包括,
(1) 插入一个记录； (2) 删除一个记录； (3) 更新一个记录。
文件的操作有两种方式：
（ 1）实时：应答时间要求严格，要求在给定时间内完成。
（ 2）批量。
文件组织的三种基本形式：
（ 1）顺序组织；（ 2）随机组织；（ 3）链组织。
12.2 顺序文件顺序文件 （ Sequential File)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录和逻辑记录的顺序是一致的。
如果次序相继的两个物理记录在存储介质上的存储位置是相邻的，则又成 连续文件 。
如果两个物理记录之间的次序有指针链表示，则称 串联文件 。
顺序文件是根据记录序号或记录的相对位置来进行存取的文件组织方式，特点：
（ 1）存取第 i个记录，必须搜索在它之前的 i-1个记录；
（ 2）插入新的记录只能在文件尾；
（ 3）若要更新文件中的某个记录，必须将整个文件复制。
顺序文件的优点是连续存取速度快，在查找和修改都是成批处理的情况下，以顺序文件为佳。
顺序文件的分类：
（ 1） 按关键字排列；
（ 2） 未按关键字排列，仅按先后次序。
顺序文件的操作,
（ 1）顺序存取：从文件的第 1个记录依次顺序存取，存取效率很高。
（ 2）随机存取：对指定的记录进行存取，但这种要求对顺序文件来说，极不方便，存取效率很低。
（ 3）按关键字存取：需从文件的第 1个记录开始查找，一般情况下，存取效率不高。
12.3 索引文件除文件自身（称作数据区）之外，另建立一张指示逻辑记录和物理记录之间一一对应关系的表：索引表。这类包括文件数据区和索引表两大部分的文件称为 索引文件 。
索引表的每一项称为 索引项 。
不论主文件是否按关键字有序，索引表中的索引项总是按关键字顺序排列。若数据区中的记录也按关键字顺序排列，则称 索引顺序文件,反之，称 索引非顺序文件 。
物理记录号 职工号 姓名 职务 其它
101 29 张三 教授 。
102 05 李四 讲师 。
103 02 王红 助教 。
104 38 。 。 。
105 31 。 。 。
106 43 。 。 。
107 17 。 。 。
108 50 。 。 。
109 49 。 。 。
110 47 。 。 。
111 56 。 。 。
(a) 文件数据区关键字 物理记录号
02 103
05 102
17 107
29 101
31 105
38 104
43 106
47 110
49 109
50 108
56 111
(b) 索引表
12.4 索引顺序文件索引顺序文件 是指记录按关键字顺序存放的索引文件。其存储结构分三个区,索引区、基本记录区和溢出区 。
基本记录区是按记录的关键字排序的。因此不必为每一个记录保存一个索引项，而只要 把记录区分块,通常是一个磁道作为一块,每块记录设一个索引项 。保存该块的最大关键字值。
溢出记录区是为了解决插入问题而设置的，在这种文件中，
由于记录按关键字值顺序存放，因此，如果新增记录要插入到两个原有记录之间时，需要调整记录区，如果当前块已满，则最后一记录被调整出当前块，放入溢出记录区。溢出区采用链表结构。
基本索引项 溢出索引项关键字值 指针 关键字值 指针基本数据区每一块设一个索引项，登记该块内的最后一个记录的关键字值和该块记录的首地址。
溢出数据区的记录用指针链接，从基本数据区同一块中溢出的记录形成一个链表，基本数据区有多少个块，溢出区就可能有多少个链表。
溢出区索引项登记该块的第一个溢出记录的关键字值
（作为本块的关键字值的上界）和该块最近溢出的记录在溢出区的地址。
基本索引项 溢出索引项 基本索引项 溢出索引项
90 T2,1 / 145 T3,1 /
1记录 2记录 3记录 4记录 5记录
R50 R60 R70 R80 R90 T 2
R100 R130 R135 R140 R145 T 3
T4
索引基本区溢出区索引顺序文件存储示意图基本索引项 溢出索引项 基本索引项 溢出索引项
80 T2,1 90 T4,1 145 T3,1 /
1记录 2记录 3记录 4记录 5记录
R50 R60 R65 R70 R80 T 2
R100 R130 R135 R140 R145 T 3
R90 / T4
索引基本区溢出区插入 R65后，基本数据区的 R70 到 R90 后移,R90到溢出区基本索引项 溢出索引项 基本索引项 溢出索引项
80 T2,1 90 T4,1 140 T3,1 145 T4,2
1记录 2记录 3记录 4记录 5记录
R50 R60 R65 R70 R80 T 2
R95 R100 R130 R135 R140 T 3
R90 / R145 / T4
索引基本区溢出区插入 R95后，基本数据区的 R100 到 R145 后移,R145到溢出区基本索引项 溢出索引项 基本索引项 溢出索引项
80 T2,1 90 T4,3 140 T3,1 145 T4,2
1记录 2记录 3记录 4记录 5记录
R50 R60 R65 R70 R80 T 2
R95 R100 R130 R135 R140 T 3
R90 / R145 / R83 T4,1 T4
索引基本区溢出区插入 R83时，因 80<83<90,所以直接加入到溢出区
12.5 多关键字文件多关键字文件的特点,对文件进行检索操作时，不仅对主关键字进行简单询问，还经常对次关键字进行其它类型的询问检索。
如下页表格中，学号为主关键字，专业、已修学分、选修课目等为次关键字。允许的查询：
根据学号查询某学生的信息；
查询已修学分 400分以上的学生；
查询已修学分 400分以上计算机专业的学生人数；
其他查询为此，对多关键字文件，可建立一系列的次关键字索引。
姓名 学号 专业 已修学分 选修课目王 文 1350 软件 412 丙 丁马小燕 1351 软件 398 甲 丙阮 森 1352 计算机 436 乙 丙 丁苏明明 1353 应用 402 甲 丙田 水 1354 计算机 384 乙 丁杨 青 1355 应用 356 甲薛平平 1356 软件 398 甲 乙崔子健 1357 软件 408 甲 丙王 洪 1358 应用 370 甲 丁刘 倩 1359 应用 364 甲学生信息表
12.5.1 多重表文件多重表文件的特点,记录按主关键字的顺序构成一个串联文件。并建立主关键字的索引（成为主索引），主索引为非稠密索引。如下页图所示为一个多重链表文件，记录按学号链接，
为查找方便，分成三个链表。
对每一个次关键字建立一个稠密索引。相同次关键字的记录形成一个链表。
12.5.1 多重表文件多重表文件的特点,记录按主关键字的顺序构成一个串联文件。并建立主关键字的索引（成为主索引），主索引为非稠密索引。如下页图所示为一个多重链表文件，记录按学号链接，
为查找方便，分成三个链表。
对每一个次关键字建立一个稠密索引。相同次关键字的记录形成一个链表。
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
主关键字头指针
1353 01
1357 05
1359 09
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 头指针 长度软件 01 4
计算机 03 2
应用 04 4
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 头指针 长度
350～ 399 06 6
400～ 499 04 4
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 头指针 长度甲 02 7
乙 03 3
丙 01 5
丁 01 4
12.5.2 倒排表文件倒排文件和多重文件的区别在次关键字索引的结构不同，
通常，称倒排文件中的次关键字索引为 倒排表,具有相同次关键字的记录之间不设指针相链。而在倒排表中该次关键字的一项中存放这些记录的物理记录号。
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 记录物理地址软件 01,02,07,08
计算机 03,05
应用 04,06,09,10
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 记录物理地址
350～ 399 02,05,06,07,09,10
400～ 499 01,03,04,08
记录号 姓名 学号 专业 已修学分
01 王 文 1350 02 软件 02 412 03 丙 02 丁 03
02 马小燕 1351 03 软件 07 398 07 甲 04 丙 03
03 阮 森 1352 04 计算机 05 436 ^ 乙 05 丙 04 丁 05
04 苏明明 1353 ^
…
应用 06 402 08 甲 06 丙 08
05 田 水 1354 06 计算机 ^ 384 02 乙 07 丁 09
06 杨 青 1355 07 应用 09 356 10 甲 07
07 薛平平 1356 08 软件 08 398 ^ 甲 08 乙 ^
08 崔子健 1357 ^ 软件 ^ 408 01 甲 09 丙 ^
09 王 洪 1358 10 应用 10 370 05 甲 10 丁 ^
10 刘 倩 1359 ^ 应用 ^ 364 09 甲 ^
次关键字 记录物理地址甲 02,04,06,07,08,09,10
乙 03,05,07
丙 01,02,03,04,08
丁 01,03,05,09
操作方法：
查询已修学分 400分以上计算机专业的学生人数时，查询 400分以上的项得集合 {01,03,04,08},查询计算机专业的项得集合
{03,05}，求交集，得符合条件的仅仅 1人,03号记录。
插入记录 {“李明”,1360，“计算机”,400,{甲，乙 }}到 11
号记录位置时，根据次关键字在相应项中填入新记录的物理记录号。
