倒排表( averted Index list 」对包含有大量数据对象的数据表或文件进行 搜索时,最常用的是针对对象的主关键码建 立索引。主关键码可以唯一地标识该对象 用主关键码建立的索引叫做主索引。 主索引的每个索引项给出对象的关键码和对 象在表或文件中的存放地址。 对象关键码ke对象存放地址adr 但在实际应用中有时需要针对其它属性进行 搜索。例如,查询如下的职工信息: (1)列出所有教师的名单;
对象关键码 key 对象存放地址 addr
(2)已婚的女性职工有哪些人? 这些信息在数据表或文件中都存在,但都不 是关键码,为回答以上问题,只能到表或文 件中去顺序搜索,搜索效卒极低。 因此,除主关键码外,可以把一些经常搜索 的属性设定为次关键码,并针对每一个作为 次关键码的属性,建立次索引。 在次索引中,列出该属性的所有取值,并对 每一个取值建立有序链表,把所有具有相同 属性值的对象按存放地址递增的顺序或按主 关键码递增的顺序链接在一起
次索引的索引项由次关键码、链表长度和链 表本身等三部分组成。 例如,为了回答上述的查询,我们可以分别 建立“性别”、“婚否”和“职务”次索引。 性别次索引 次关键码男|女 计数53 地址指针 指针0308172447518395
性别次索引 次关键码 男 女 计 数 5 3 地址指针 指针 03 08 17 24 47 51 83 95
婚否次索引 次关键码已婚未婚」 计数53 地址指针 指针|0308244783175195 职务次索引 次关键码教师教务员实验员 计数」51 2 地址指针 指针08|24|47|51|830317|95
婚否次索引 次关键码 已婚 未婚 计 数 5 3 地址指针 指针 03 08 24 47 83 17 51 95 职务次索引 次关键码 教师 教务员 实验员 计 数 5 1 2 地址指针 指针 08 24 47 51 83 03 17 95
(1)列出所有教师的名单; (2)已婚的女性职工有哪些人? 通过顺序访问“职务”次索引中的“教师” 链,可以回答上面的查询(1) 通过对“性别”和“婚否”次索引中的“女 性”链和“已婚”链进行求“交”运算,就 能够找到所有既是女性又已婚的职工对象, 从而回答上面的查询(2) g倒排表是次索引的一种实现。在表中所有次 关键码的链都保存在次索引中,仅通过搜索 次索引就能找到所有具有相同属性值的对象