静态索引结构动态索引结构散列可扩充散列.ppt

《静态索引结构动态索引结构散列可扩充散列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、静态索引结构动态索引结构散列可扩充散列第十章索引与散列静态索引结构示例：有一个存放职工信息的数据表,每一个职工对象有近1k字节的信息,正好占据一个页块的存储空间。当数据对象个数n很大时,如果用无序表形式的静态搜索结构存储,采用顺序搜索,则搜索效率极低。如果采用有序表存储形式的静态搜索结构,则插入新记录进行排序,时间开销也很可观。这时可采用索引方法来实现存储和搜索。线性索引(LinearIndexList)100140180220260300340380keyaddr03180081401734024260473

2、00513808310095220职工号姓名性别职务婚否83张珊女教师已婚…08李斯男教师已婚...03王鲁男教务员已婚...95刘琪女实验员未婚...24岳跋男教师已婚...47周斌男教师已婚...17胡江男实验员未婚...51林青女教师未婚...索引表数据表假设内存工作区仅能容纳64k字节的数据,在某一时刻内存最多可容纳64个对象以供搜索。如果对象总数有14400个,不可能把所有对象的数据一次都读入内存。无论是顺序搜索或折半搜索,都需要多次读取外存记录。如果在索引表中每一个索引项占4个字节,每个索引项索引一

3、个职工对象,则14400个索引项需要56.25k字节,在内存中可以容纳所有的索引项。这样只需从外存中把索引表读入内存,经过搜索索引后确定了职工对象的存储地址,再经过1次读取对象操作就可以完成搜索。稠密索引：一个索引项对应数据表中一个对象的索引结构。当对象在外存中按加入顺序存放而不是按关键码有序存放时必须采用稠密索引结构，这时的索引结构叫做索引非顺序结构。稀疏索引：当对象在外存中有序存放时，可以把所有n个对象分为b个子表(块)存放，一个索引项对应数据表中一组对象(子表)。在子表中,所有对象可能按关键码有序地存放,

4、也可能无序地存放。但所有这些子表必须分块有序,后一个子表中所有对象的关键码均大于前一个子表中所有对象的关键码。它们都存放在数据区中。另外建立一个索引表。索引表中每一表目叫做索引项，它记录了子表中最大关键码max_key以及该子表在数据区中的起始位置obj_addr。第i个索引项是第i个子表的索引项,i=0,1,…,n-1。这样的索引结构叫做索引顺序结构。对索引顺序结构进行搜索时，一般分为两级搜索:先在索引表ID中搜索给定值K,确定满足ID[i-1].max_key

5、29333642444839406074567980669282889894子表1子表2子表3子表4数据区33488098索引表1234max_max_keyaddr的i值,即待查对象可能在的子表的序号。然后再在第i个子表中按给定值搜索要求的对象。索引表是按max_key有序的,且长度也不大,可以折半搜索，也可以顺序搜索。各子表内各个对象如果也按对象关键码有序,可以采用折半搜索或顺序搜索;如果不是按对象关键码有序,只能顺序搜索。索引顺序搜索的搜索成功时的平均搜索长度ASLIndexSeq=ASLIndex+AS

6、LSubList其中,ASLIndex是在索引表中搜索子表位置的平均搜索长度，ASLSubList是在子表内搜索对象位置的搜索成功的平均搜索长度。设把长度为n的表分成均等的b个子表，每个子表s个对象，则b=n/s。又设表中每个对象的搜索概率相等，则每个子表的搜索概率为1/b，子表内各对象的搜索概率为1/s。若对索引表和子表都用顺序搜索，则索引顺序搜索的搜索成功时的平均搜索长度为ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1索引顺序搜索的平均搜索长度与表中的对象个数n有关，与每个子

7、表中的对象个数s有关。在给定n的情况下，s应选择多大？用数学方法可导出,当s=时,ASLIndexSeq取极小值+1。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，还要受到页块大小的制约。若采用折半搜索确定对象所在的子表,则搜索成功时的平均搜索长度为ASLIndexSeq=ASLIndex+ASLSubListlog2(b+1)-1+(s+1)/2log2(1+n/s)+s/2倒排表(InvertedIndexList)对包含有大量数据对象的数据表或文件进行搜索时，最常用的是针对对象的主关键码

8、建立索引。主关键码可以唯一地标识该对象。用主关键码建立的索引叫做主索引。主索引的每个索引项给出对象的关键码和对象在表或文件中的存放地址。但在实际应用中有时需要针对其它属性进行搜索。例如，查询如下的职工信息：(1)列出所有教师的名单；对象关键码key对象存放地址addr(2)已婚的女性职工有哪些人？这些信息在数据表或文件中都存在，但都不是关键码，为回答以上问题，只能到表或文件中去顺序搜索