第章搅蒙与散测 静态索引结构 动态索引结构 Trie树 a散列( Hashing
静态索引结构 当数据对象个数n很大时,如果用无序表形式 的静态搜索结构存储,采用顺序搜索,则搜索效 率极低。如果采用有序表存储形式的静态搜索结 构,则插入新记录进行排序,时间开销也很可观。 这时可采用索引方法来实现存储和搜索。 线性索引 Linear ndex list) n示例:有一个存放职工信息的数据表,每一个 职工对象有近1k字节的信息,正好占据一个页 块的存储空间
索引表 数据表 关键码地址 职工号|姓名性别职务|婚否|其它 10183张珊女教师|已婚|… 李斯男|教师已婚 17340 180103王鲁男行政助理|已婚{…… 24260 29刘琪女实验员|未婚 2024岳跋「男「教师|已婚 30(41周惠男教师「已婚 3100 34017胡江男「实验员|未婚 9522 3051}林青女教师未婚…
■假设内存工作区仅能容纳64k字节的数据,在 某一时刻内存最多可容纳64个对象以供搜索。 如果对象总数有14400个,不可能把所有对象 的数据一次都读入内存。无论是顺序搜索或对 分搜索,都需要多次读取外存记录。 如果在索引表中每一个索引项占4个字节,每个 索引项索引一个职工对象,则14400个索引项 需要56.25k字节,在内存中可以容纳所有的索 引项。 这样只需从外存中把索引表读入内存,经过搜 索索引后确定了职工对象的存储地址,再经过 1次读取对象操作就可以完成搜索
稠密索引:一个索引项对应数据表中一个对象 的索引结构。当对象在外存中按加入顺序存放 而不是按关键码有序存放时必须采用稠密索引 结构,这时的索引结构叫做索引非顺序结构 稀疏索引:当对象在外存中有序存放时,可以 把所有n个对象分为b个子表(块)存放,一个 索引项对应数据表中一组对象(子表)。 n在子表中,所有对象可能按关键码有序地存放, 也可能无序地存放。但所有这些子表必须分块 有序,后一个子表中所有对象的关键码均大于 前一个子表中所有对象的关键码。它们都存放 在数据区中。另外建立一个索引表
索引表中每一表目叫做索引项,它记录了子表 中最大关键码 max key以及该子表在数据区中 的起始位置 obj addr 索引表max_ key obj_addr ⅠD 子表12212139302938125 子表242|44138344036484739 498 子表3|605874567279668078 子表4929794828198 各个索引项在索引表中的序号与各个子表的块 号有一一对应的关系:第i个索引项是第i个 子表的索引项,i=0,1,,.n-1。这样的索引结 构叫做索引顺序结构
对索引顺序结构进行搜索时,一般分为两级 搜索。 ◆先在索引表⑩D中搜索给定值K,确定满足 DF1. max key<ksDi. max key 的i值,即待查对象可能在的子表的序号 ◆然后再在第i个子表中按给定值搜索要求 的对象。 索引表是按 max key有序的,且长度也不大, 可以对分搜索,也可以顺序搜索。 各子表内各个对象如果也按对象关键码有序, 可以采用对分搜索或顺序搜索;如果不是按 对象关键码有序,只能顺序搜索
索引顺序搜索的搜索成功时的平均搜索长度 ASLIndexseg =ASLindex+ AsLSublist 其中,ASL ndex 是在索引表中搜索子表位置的 平均搜索长度, ASL是在子表内搜索对象 位置的搜索成功的平均搜索长度。 设把长度为n的表分成均等的b个子表,每个 子表s个对象,则b=「n/s。又设表中每个对 象的搜索概率相等,则每个子表的搜索概率为 1/b,子表内各对象的搜索概率为1/s 若对索引表和子表都用顺序搜索,则索引顺序 搜索的搜索成功时的平均搜索长度为 ASLInderse=(b+1)/2+(s+1)2=(b+s)/2+1
索引顺序搜索的平均搜索长度不仅与表中的对 象个数n有关,而且与每个子表中的对象个数 s有关。在给定n的情况下,s应选择多大? 利用数学方法可以导出,当s=、√m时, asLIndexs取极小值√n+1。这个值比顺序搜 索强,但比对分搜索差。但如果子表存放在外 存时,还要受到页块大小的制约。 若采用对分搜索确定对象所在的子表,则搜索 成功时的平均搜索长度为 ASLIndexSegASLIndex AsLSubList ≈log2(b+1)-1+(+1)/2 A log(1+n/s)+s/2
n n
倒排表( Inverted Index list 对包含有大量数据对象的数据表或文件进行搜 索时,最常用的是针对对象的主关键码建立索 引。主关键码可以唯一地标识该对象。用主关 键码建立的索引叫做主索引。 n主索引的每个索引项给出对象的关键码和对象 在表或文件中的存放地址。 对象关键码Ae对隶存放地址adl 但在实际应用中有时需要针对其它属性进行搜 索。例如,查询如下的职工信息: (1)列出所有教师的名单; (2)已婚的女性职工有哪些人?
对象关键码 key 对象存放地址 addr