在次索引中记录对象存放位置的指针可以 用主关键码表示:可通过搜索次索引确定该 对象的主关键码,再通过搜索主索引确定对 象的存放地址。 在倒排表中各个属性链表的长度大小不一, 管理比较困难。为此引入单元式倒排表。 在单元式倒排表中,索引项中不存放对象的 存储地址,存放该对象所在硬件区域的标识。 硬件区域可以是磁盎柱面、磁道或一个页 块,以一次I/O操作能存取的存储空间作 为硬件区域为最好
为使索引空间最小,在索引中标识这个硬件 区域时可以使用一个能转换成地址的二进 制数,整个次索引形成一个(二进制数的)位 矩阵。 例如,对于记录学生信息的文件,次索引可 以是如图所示的结构。二进位的值为1的 硬件区域包含具有该次关键码的对象 如果在硬件区域1 中有要求的对象。 然后将硬件区域1,∴读入内存,在其 中进行检索,确定就可取出所需对象
硬件区域 12345…251252253254 次关键码1男 10111 1011 ●● (性别女11111 0110 次关鍵码2广东」10010…0 101 010 0 (稀贯)[北京11111…0 上海00111 ●● 0 次关键码3建筑11001…0 (专业)[计算机00111 00 电机10110 011 110 10 ●●。●●● 元式倒琲裴结柯
硬 件 区 域 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 … …… 单元式倒排表结构
0111 ●●●●● 1011 0100 AND11001 ●●0● 0101 10000 0000 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,)(23,1(32,)(41,y(49,y(60,y(95 0206-11151823-29323841454952607795 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