在次索引中记录对象存放位置的指针可以 用主关键码表示:可通过搜索次索引确定该 对象的主关键码,再通过搜索主索引确定对 象的存放地址。 在倒排表中各个属性链表的长度大小不一, 管理比较困难。为此引入单元式倒排表。 在单元式倒排表中,索引项中不存放对象的 存储地址,存放该对象所在硬件区域的标识。 硬件区叵可以是磁盘柱面、磁道或一个页 块,以一次I/O操作能存取的存储空间作为 硬件区城为最好
◼ 在次索引中记录对象存放位置的指针可以 用主关键码表示: 可通过搜索次索引确定该 对象的主关键码, 再通过搜索主索引确定对 象的存放地址。 ◼ 在倒排表中各个属性链表的长度大小不一, 管理比较困难。为此引入单元式倒排表。 ◼ 在单元式倒排表中, 索引项中不存放对象的 存储地址, 存放该对象所在硬件区域的标识。 ◼ 硬件区域可以是磁盘柱面、磁道或一个页 块, 以一次 I / O 操作能存取的存储空间作为 硬件区域为最好
为使索引空间最小,在索引中标识这个硬件 区域时可以使用一个能转换成地址的二进 制数整个次索引形成一个(二进制数的)位 矩阵。 例如,对于记录学生信息的文件,次索引可 以是如图所示的结构。二进位的值为1的 硬件区域包含具有该次关键码的对象。 如果在硬件区域1,…中有要求的对象。 然后将硬件区域1,∴等读入内存,在其 中进行检索,确定就可取出所需对象
◼ 为使索引空间最小, 在索引中标识这个硬件 区域时可以使用一个能转换成地址的二进 制数,整个次索引形成一个(二进制数的) 位 矩阵。 ◼ 例如, 对于记录学生信息的文件, 次索引可 以是如图所示的结构。二进位的值为1 的 硬件区域包含具有该次关键码的对象。 ◼ 如果在硬件区域1，……中有要求的对象。 然后将硬件区域1，……等读入内存，在其 中进行检索，确定就可取出所需对象
硬件 域 12345…251252253254 次关键码1男 10111 ●。 1011 ●。● 性别)女 0110 次关鍵码2广东10010 (籍贯)北京11111…00-11 ●。非 上海00111 00 次关键码3建筑11001 0101 (专业)[计算机00111…0011… 电机10110 1010 单元式倒排表结构
硬 件 区 域 1 2 3 4 5 … 251 252 253 254 … 次关键码 1 男 1 0 1 1 1 … 1 0 1 1 … (性别) 女 1 1 1 1 1 … 0 1 1 0 … 次关键码 2 广东 1 0 0 1 0 … 0 1 0 0 … (籍贯) 北京 1 1 1 1 1 … 0 0 1 1 … 上海 0 0 1 1 1 … 1 1 0 0 … …… 次关键码 3 建筑 1 1 0 0 1 … 0 1 0 1 … (专业) 计算机 0 0 1 1 1 … 0 0 1 1 … 电机 1 0 1 1 0 … 1 0 1 0 … …… 单元式倒排表结构
1011 10010 ●。●0● 00 AND11001·0101 1000 0000 m路静态搜索树 当数据对象数目特别大,索引表本身也很大 在内存中放不下,需要分批多次读取外存才能 把索引表搜索一遍。 此时,可以建立索引的索引(二级索引)二级 索引可以常驻内存,二级索引中一个索引项对 应一个索引块,登记该索引块的最大关键码及 该索引块的存储地址
m 路静态搜索树 ◼ 当数据对象数目特别大，索引表本身也很大， 在内存中放不下，需要分批多次读取外存才能 把索引表搜索一遍。 ◼ 此时, 可以建立索引的索引(二级索引)。二级 索引可以常驻内存，二级索引中一个索引项对 应一个索引块，登记该索引块的最大关键码及 该索引块的存储地址。 1 0 1 1 1 …… 1 0 1 1 1 0 0 1 0 …… 0 1 0 0 AND 1 1 0 0 1 …… 0 1 0 1 1 0 0 0 0 …… 0 0 0 0
root (23y)(41,1)(95, (06,/)(15,1)(23 (32,1)(41,1(49,(60,(95, 02061115182329323841454952607795 head 如果二级索引在内存中也放不下,需要分为 许多块多次从外存读入。可以建立二级索引 的索引(三级索引)。这时,访问外存次数等 于读入索引次数再加上次读取对象
◼ 如果二级索引在内存中也放不下，需要分为 许多块多次从外存读入。可以建立二级索引 的索引(三级索引)。这时，访问外存次数等 于读入索引次数再加上1次读取对象。 02 06 11 15 18 23 29 32 38 41 45 49 52 60 77 95 (06, ) (15, ) (23, ) (32, ) (41, ) (49, ) (60, ) (95, ) (23, ) (41, ) (95, ) root head