文档介绍：静态索引结构
动态索引结构
散列
可扩充散列
第十章索引与散列
静态索引结构
示例:有一个存放职工信息的数据表, 每一个职工对象有近 1k 字节的信息, 正好占据一个页块的存储空间。
当数据对象个数 n 很大时, 如果用无序表形式的静态搜索结构存储, 采用顺序搜索, 则搜索效率极低。如果采用有序表存储形式的静态搜索结构, 则插入新记录进行排序, 时间开销也很可观。这时可采用索引方法来实现存储和搜索。
线性索引(Linear Index List)
100
140
180
220
260
300
340
380
key addr
03 180
08 140
17 340
24 260
47 300
51 380
83 100
95 220
职工号姓名性别职务婚否
83 张珊女教师已婚…
08 李斯男教师已婚...
03 王鲁男教务员已婚...
95 刘琪女实验员未婚...
24 岳跋男教师已婚...
47 周斌男教师已婚...
17 胡江男实验员未婚...
51 林青女教师未婚...
索引表
数据表
假设内存工作区仅能容纳 64k 字节的数据, 在某一时刻内存最多可容纳 64 个对象以供搜索。
如果对象总数有 14400 个, 不可能把所有对象的数据一次都读入内存。无论是顺序搜索或折半搜索, 都需要多次读取外存记录。
如果在索引表中每一个索引项占4个字节, 每个索引项索引一个职工对象, 则 14400 个索引项需要 字节, 在内存中可以容纳所有的索引项。
这样只需从外存中把索引表读入内存, 经过搜索索引后确定了职工对象的存储地址, 再经过 1 次读取对象操作就可以完成搜索。
稠密索引:一个索引项对应数据表中一个对象的索引结构。当对象在外存中按加入顺序存放而不是按关键码有序存放时必须采用稠密索引结构,这时的索引结构叫做索引非顺序结构。
稀疏索引:当对象在外存中有序存放时,可以把所有 n 个对象分为 b 个子表(块)存放,一个索引项对应数据表中一组对象(子表)。
的 i 值, 即待查对象可能在的子表的序号。
然后再在第 i 个子表中按给定值搜索要求的对象。
索引表是按max_key有序的, 且长度也不大,可以折半搜索,也可以顺序搜索。
各子表内各个对象如果也按对象关键码有序, 可以采用折半搜索或顺序搜索; 如果不是按对象关键码有序, 只能顺序搜索。
索引顺序搜索的搜索成功时的平均搜索长度
ASLIndexSeq = ASLIndex + ASLSubList
其中, ASLIndex 是在索引表中搜索子表位置的平均搜索长度,ASLSubList 是在子表内搜索对象位置的搜索成功的平均搜索长度。
设把长度为 n 的表分成均等的 b 个子表,每个子表 s 个对象,则 b = n/s。又设表中每个对象的搜索概率相等,则每个子表的搜索概率为1/b,子表内各对象的搜索概率为 1/s。
若对索引表和子表都用顺序搜索,则索引顺序搜索的搜索成功时的平均搜索长度为
ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1
索引顺序搜索的平均搜索长度与表中的对象个数 n 有关,与每个子表中的对象个数 s 有关。在给定 n 的情况下,s 应选择多大?
用数学方法可导出, 当 s = 时, ASLIndexSeq取极小值+1。这个值比顺序搜索强,但比折半搜索差。但如果子表存放在外存时,还要受到页块大小的制约。
若采用折半搜索确定对象所在的子表, 则搜索成功时的平均搜索长度为
ASLIndexSeq = ASLIndex + ASLSubList
log2 (b+1)-1 + (s+1)/2
log2(1+n / s ) + s/2