学科分类
目录
数据结构

倒排文件

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

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

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

表1 班级编号倒排表

次关键字 物理地址
03 1,3
05 4,6
06 2
07 5,7

表2 校区倒排表

次关键字 物理地址
北京 1,7
武汉 2,5
南京 3
哈尔滨 4
深圳 6

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

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

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

点击此处
隐藏目录