这些信息在数据表或文件中都存在,但都不是 关键码,为回答以上问题,只能到表或文件中 去顺序搜索,搜索效率极低。 因此,除主关键码外,可以把一些经常搜索的 属性设定为次关键码,并针对每一个作为次关 键码的属性,建立次索引。 在次索引中,列出该属性的所有取值,并对每 个取值建立有序链表,把所有具有相同属性 值的对象按存放地址递增的顺序或按主关键码 递增的顺序链接在一起。 次索引的索引项由次关键码、链表长度和链表 本身等三部分组成
为了回答上述的查询,我们可以分别建立“性 别”、“婚否”和“职务”次索引。 "职工号"主索引"性别"次索引 婚否"次索引 职务"次索引 主关鏈码地址次关鏈码计数|指针|次关码计数指针|次关码计数|指针 310男15十-10已婚 3教师 0814女3080未婚3108行政助理124 171340 241实验员247 24 47 51 4730 83 83 51380 3 83 9520
(1)列出所有教师的名单; (2)已婚的女性职工有哪些人? 通过顺序访问“职务”次索引中的“教师” 链,可以回答上面的查询(1) 通过对“性别”和“婚否”次索引中的“女 性”链和“已婚”链进行求“交”运算,就 能够找到所有既是女性又已婚的职工对象, 从而回答上面的查询(2) 0010 0 AND11001…0101 000 0000
1 0 1 1 1 … … 1 0 1 1 1 0 0 1 0 … … 0 1 0 0 A N D 1 1 0 0 1 … … 0 1 0 1 1 0 0 0 0 … … 0 0 0 0
倒排表或倒排文件是一种次索引的实现。在 倒排表中所有次关键码的链都保存在次索引 中,仅通过搜索次索引就能找到所有具有相 同属性值的对象。 在次索引中记录对象存放位置的指针可以用 主关键码表示,可以通过搜索次索引确定该 对象的主关键码,再通过搜索主索引确定对 象的存放地址。 在倒排表中各个属性链表的长度大小不 管理起来比较困难。为此引入单元式倒排表
在单元式倒排表中,索引项中不存放对象的 存储地址,存放该对象所在硬件区域的标识。 硬件区域可以是磁盘柱面、磁道或一个页块, 以一次I/O操作能存取的存储空间作为硬件 区域为最好。为使索引空间最小,在索引中 标识这个硬件区域时可以使用一个能转换成 地址的二进制数,整个次索引形成一个(二进 制数的)位矩阵。 ■例如,对于记录学生信息的文件,次索引可 以是如图所示的结构。二进位的值为1的硬件 区域包含具有该次关键码的对象