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