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

1、n 静态索引结构静态索引结构n 动态索引结构动态索引结构n 散列散列n 可扩充散列可扩充散列静态索引结构静态索引结构n 示例：示例： 有一个存放职工信息的数据表有一个存放职工信息的数据表 , 每一每一 个职工对象有近个职工对象有近 1k 字节的信息字节的信息 , 正好占据一正好占据一 个页块的存储空间个页块的存储空间 。当数据对象个数当数据对象个数 n 很大时很大时 , 如果用无序表形如果用无序表形式的静态搜索结构存储式的静态搜索结构存储 , 采用顺序搜索采用顺序搜索 , 则搜索则搜索效率极低。如果采用有序表存储形式的静态搜效率极低。如果采用有序表存储形式的静态搜索结构索结构 , 则插入新记录

2、进行排序则插入新记录进行排序 , 时间开销也很时间开销也很可观。这时可采用索引方法来实现存储和搜索可观。这时可采用索引方法来实现存储和搜索。 线性索引线性索引 (Linear Index List)100140180220260300340380key addr03 18008 14017 34024 26047 30051 38083 10095 220职工号 姓名 性别 职务 婚否 83 张珊 女 教师 已婚 08 李斯 男 教师 已婚 . 03 王鲁 男 教务员 已婚 .95 刘琪 女 实验员 未婚 .24 岳跋 男 教师 已婚 .47 周斌 男 教师 已婚 .17 胡江 男 实验员 未

3、婚 .51 林青 女 教师 未婚 . 索引表 数据表n 假设内存工作区仅能容纳假设内存工作区仅能容纳 64k 字节的数据字节的数据 , 在某一时刻内存最多可容纳在某一时刻内存最多可容纳 64 个对象以供个对象以供搜索。搜索。n 如果对象总数有如果对象总数有 14400 个个 , 不可能把所有对不可能把所有对象的数据一次都读入内存。无论是顺序搜索象的数据一次都读入内存。无论是顺序搜索或折半搜索或折半搜索 , 都需要多次读取外存记录。都需要多次读取外存记录。n 如果在索引表中每一个索引项占如果在索引表中每一个索引项占 4个字节个字节 , 每每个索引项索引一个职工对象个索引项索引一个职工对象 , 则

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

5、 稠稠密索引密索引 结构，这时的索引结构叫做索引非顺结构，这时的索引结构叫做索引非顺序结构。序结构。n 稀疏索引：稀疏索引： 当对象在外存中有序存放时，可当对象在外存中有序存放时，可以把所有以把所有 n 个对象分为个对象分为 b 个子表个子表 (块块 )存放，存放，一个索引项对应数据表中一组对象一个索引项对应数据表中一组对象 (子表子表 )。n 在子表中在子表中 , 所有对象所有对象 可能按关键码有序地存可能按关键码有序地存放放 , 也可能无序地存放也可能无序地存放 。 但所有这些子表但所有这些子表 必必须分块有序须分块有序 , 后一个子表中所有对象的关键码后一个子表中所有对象的关键码均大于前

6、一个子表中所有对象的关键码均大于前一个子表中所有对象的关键码 。 它它们都存放在数据区中。们都存放在数据区中。n 另外建立一个索引表。索引表中每一表目叫另外建立一个索引表。索引表中每一表目叫做做 索引项索引项 ， 它记录了子表中它记录了子表中 最大关键码最大关键码 max _key以及该子表以及该子表 在数据区中的起始位置在数据区中的起始位置 obj _ addr。n 第第 i 个索引项是第个索引项是第 i 个子表的索引项个子表的索引项 , i = 0, 1, , n-1。 这样的索引结构叫做这样的索引结构叫做 索引顺序结构索引顺序结构。n 对索引顺序结构进行搜索时，一般分为两级对索引顺序结构

7、进行搜索时，一般分为两级搜索搜索 :u 先在先在 索引表索引表 ID 中搜索给定值中搜索给定值 K, 确定满足确定满足IDi-1.max_key K IDi.max_key22 12 13 30 29 3336 42 44 48 39 4060 74 56 79 80 6692 82 88 98 94 子表 1子表 2子表 3子表 4数据区数据区33488098索引表索引表1234max_ max_key addr的的 i 值值 , 即待查对象可能在的子表的序号即待查对象可能在的子表的序号。u 然后再在第然后再在第 i 个子表中按给定值搜索要求个子表中按给定值搜索要求的对象。的对象。n 索引表

8、是按索引表是按 max_key有序的有序的 , 且长度也不大且长度也不大 ,可以折半搜索，也可以顺序搜索。可以折半搜索，也可以顺序搜索。n 各子表内各个对象如果也按对象关键码有序各子表内各个对象如果也按对象关键码有序, 可以采用折半搜索或顺序搜索可以采用折半搜索或顺序搜索 ; 如果不是按如果不是按对象关键码有序对象关键码有序 , 只能顺序搜索。只能顺序搜索。n 索引顺序搜索的搜索成功时的平均搜索长度索引顺序搜索的搜索成功时的平均搜索长度ASLIndexSeq = ASLIndex + ASLSubListn 其中其中 , ASLIndex 是在索引表中搜索子表位置的是在索引表中搜索子表位置的平

9、均搜索长度平均搜索长度 ， ASLSubList 是在子表内搜索对是在子表内搜索对象位置的搜索成功的平均搜索长度象位置的搜索成功的平均搜索长度 。n 设把长度为设把长度为 n 的表分成均等的的表分成均等的 b 个子表，每个子表，每个子表个子表 s 个对象，则个对象，则 b = n/s。 又设表中每又设表中每个对象的搜索概率相等，则每个子表的搜索个对象的搜索概率相等，则每个子表的搜索概率为概率为 1/b， 子表内各对象的搜索概率为子表内各对象的搜索概率为 1/s。n 若对若对 索引表索引表 和和 子表子表 都用都用 顺序搜索顺序搜索 ，则索引顺，则索引顺序搜索的搜索成功时的平均搜索长度为序搜索的

10、搜索成功时的平均搜索长度为ASLIndexSeq = (b+1)/2+(s+1)/2 = (b+s)/2 +1n 索引顺序搜索的平均搜索长度与索引顺序搜索的平均搜索长度与 表中的对象表中的对象个数个数 n 有关，与有关，与 每个子表中的对象个数每个子表中的对象个数 s 有有关。在给定关。在给定 n 的情况下，的情况下， s 应选择多大？应选择多大？n 用数学方法可导出用数学方法可导出 , 当当 s = 时时 , ASLIndexSeq取极小值取极小值 +1。这个值比顺序搜索强，但。这个值比顺序搜索强，但比折半搜索差。但如果子表存放在外存时，比折半搜索差。但如果子表存放在外存时，还要受到页块大小的制约。还要受到页块大小的制约。n 若采用折半搜索确定对象所在的子表若采用折半搜索确定对象所在的子表 , 则搜则搜索成功时的平均搜索长度为索成功时的平均搜索长度为ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2(1+n / s ) + s/2