当文件的记录中含多个关键码时，经常需要对记录的"次码"（或辅键，指记录的某些重要属性）或"多码（多辅键）的组合"进行检索时，文件的组织方式应该同时考虑如何便于进行次码或多码组合的查询，称这类文件为"多关键码文件"。如右侧所示为多关键码文件一例，其中"考号"为"主码"，"总分"和"数学"成绩为次码。假设该文件为索引顺序文件，则当需按"总分"进行检索时，只能依次存取各个记录比较它们的"总分"是否满足条件直至找到相应记录。为此应该为这类文件在主文件之外另建立"次码索引"，例如右侧是为"总分"建立的次码索引表。可见次码索引的特点是，对应每个次码值的记录可能有多个，因此每个"次码索引项"应该包含一个次码值和一个线性表，线性表中的记录含有相同的次码值。对线性表的不同组织方法得到两种不同的多关键码文件："倒排文件"和"多重表文件"。 ・倒排文件 在倒排文件中，为每个需要进行检索的次码建立一个"倒排表"，倒排表中具有相同次码的记录构成一个顺序表。当按次码进行检索时，首先从相应的次码倒排表中得到记录的主码信息，然后从主索引存取相应记录。这种倒排表的优点是对于主文件的存储具有相对的独立性，无论主文件中记录的存储位置如何变化都不需要修改次码索引，对于多码组合查询，也可以先对由每个次码得到的多个主码集合进行集合运算，最后只要对得到的满足多码检索要求的主码进行存取。但如果主文件为散列文件，对文件进行的操作不改变记录的存储位置，则在次码倒排表中也可以不是记录的主码，而是记录所在的"页块地址"，其优点是可以根据倒排表直接存取记录，而不需要再按主码进行检索。 ・多重表文件 多重表文件的特点是，主文件为"串联文件"(即按主码顺序利用指针链接为表结构)，并建立主码的非稠密索引-主索引，对每一个次码建立次索引，所有具有同一次码值的记录链接为一个链表，链表的头指针和链表的长度以及次码值构成一个索引项。多重表易于构造和插入记录，但删除记录时要修改所有次索引链表。在进行多码组合查询时，应选择长度最短的次索引，依次存取记录直至找到满足所有条件的记录为止。 多关键码文件中的次索引本身可以是顺序表（如上述的总分次索引），也可以是树表或哈希表。 |
|