倒排文件

倒排文件和多重表文件的区别在于次关键字索引的结构不同。在次关键字索引中，具有相同次关键字的记录之间不进行链接，而是列出具有该次关键字记录的物理地址。倒排文件中的次关键字索引称做倒排表，倒排表和主文件一起就称为倒排文件。

在一般文件组织中，是先找记录，然后再找到该记录所含的次关键字；而倒排文件中，是先给定次关键字，然后查找含有该次关键字的各个记录，这种文件的查找次序正好与一般文件的查找相反，因此称之为“倒排”。其实多重索引文件实际上也是倒排，只是索引的方法不同。

以上一节中表1中的文件为例，两个次关键字的倒排表如表1、2所示。

表1 班级编号倒排表

表2 校区倒排表

在倒排表中，各索引项的物理地址是有序的。在倒排文件中查找记录是非常快的，特别是对某一些查找，不用读取记录就可得到结果，如在文件中查找北京校区3月份开班的学科，则直接求取两个倒排表中“03”和“北京”两个次关键字的交集即可得到。

倒排文件的主要优点就是在处理复杂多关键字时查找时，可在倒排表上先完成交、并等逻辑运算，得到结果后再对记录进行存取，这样不必对每个记录随机存取，把记录的查询转换为地址集合的运算，从而提高查找记录。

在倒排文件中插入和删除记录时有些麻烦，它需要将改动修改到倒排表。而且倒排表维护起来比较困难，因为在同一倒排表中，不同关键字的记录个数不同，各倒排表的长度也不同，同一倒排表中各项长度也不等。