第十章索引与散列 静态索引结构 动态索引结构 散列
1 ◼ 静态索引结构 ◼ 动态索引结构 ◼ 散列
静态索引结构 当数据对象个数n很大时,可采用索引方法 来实现存储和搜索。 线性索引( Linear index list) 示例:有一个存放职工信息的数据表,每 个职工对象有近1字节的信息,正好占据一 个页块的存储空间。 假设内存工作区仅能容纳64k字节的数据, 在某一时刻内存最多可容纳64个对象以供 搜索
2 静态索引结构 ◼ 示例：有一个存放职工信息的数据表, 每一 个职工对象有近 1k 字节的信息, 正好占据一 个页块的存储空间。 ◼ 假设内存工作区仅能容纳64k 字节的数据, 在某一时刻内存最多可容纳 64 个对象以供 搜索。 当数据对象个数 n 很大时, 可采用索引方法 来实现存储和搜索。 线性索引 (Linear Index List)
索引表 数据表 kevladd 职工号姓名性别职务婚否 032k 083张删女教师已婚 08k1k08李斯男教师已婚 k2k03王鲁男槨务员己婚 244kN,3k95刘琪女实验员未婚 475k 424岳跋男教师已婚 517kN5k47周斌男教师已婚 830X'6k17胡江男实验员未婚 953k 7ks1林青女教师未婚
3 0 1k 2k 3k 4k 5k 6k 7k key addr 03 2k 08 1k 17 6k 24 4k 47 5k 51 7k 83 0 95 3k 职工号 姓名 性别 职务 婚否 83 张珊 女 教师 已婚 … 08 李斯 男 教师 已婚 ... 03 王鲁 男 教务员 已婚 ... 95 刘琪 女 实验员 未婚 ... 24 岳跋 男 教师 已婚 ... 47 周斌 男 教师 已婚 ... 17 胡江 男 实验员 未婚 ... 51 林青 女 教师 未婚 ... 索引表 数据表
如果对象总数有14400个,不可能把所有对 象的数据一次都读入内存。无论是顺序搜 索或折半搜索,都需要多次读取外存记录。 如果在索引表中每一个索引项占4个字节, 索引项给出一个职工对象的关键码及其存 储地址,用以索引一个职工对象,则14400 个索引项需要56.25k字节,在内存中可以容 纳所有的索引项。 这样只需从外存中把索引表读入内存,经过 搜索索引后确定了职工对象的存储地址,再 经过1次读取对象操作就可以完成搜索
4 ◼ 如果对象总数有 14400 个, 不可能把所有对 象的数据一次都读入内存。无论是顺序搜 索或折半搜索, 都需要多次读取外存记录。 ◼ 如果在索引表中每一个索引项占4 个字节, 索引项给出一个职工对象的关键码及其存 储地址，用以索引一个职工对象, 则 14400 个索引项需要 56.25k 字节, 在内存中可以容 纳所有的索引项。 ◼ 这样只需从外存中把索引表读入内存, 经过 搜索索引后确定了职工对象的存储地址, 再 经过 1 次读取对象操作就可以完成搜索
稠密索引:一个索引项对应数据表中一个对 象的索引结构。当对象在外存中按加入顺序 存放而不是按关键码有序存放时必须采用稠 密索引结构,这时的索引结构叫做索引非顺 序结构。 稀疏索引:当对象在外存中有序存放时,可 以把所有n个对象分为b个子表(块存放 一个索引项对应数据表中一组对象(子表) 第i个索引项是第i个子表的索引项,i=0, 1,…n-1。这种索引结构叫做索引顺序结构
5 ◼ 稠密索引：一个索引项对应数据表中一个对 象的索引结构。当对象在外存中按加入顺序 存放而不是按关键码有序存放时必须采用稠 密索引结构，这时的索引结构叫做索引非顺 序结构。 ◼ 稀疏索引：当对象在外存中有序存放时，可 以把所有 n 个对象分为 b 个子表(块)存放， 一个索引项对应数据表中一组对象(子表)。 ◼ 第 i 个索引项是第 i 个子表的索引项, i = 0, 1, …, n-1。这种索引结构叫做索引顺序结构
索引表 数据区 133 子表12212133012933 248 子表2364244483940 380 498 子表3607456798066 max max子表492182889894 key addr 对索引顺序结构进行搜索时,一般分为两级 搜索: ◆先在索引表ⅠD中搜索给定值K,确定满足 IDi-1 max key<ksDe. max key
6 ◼ 对索引顺序结构进行搜索时，一般分为两级 搜索: ◆ 先在索引表 ID 中搜索给定值 K, 确定满足 ID[i-1].max_key < K ID[i].max_key 22 12 13 30 29 33 36 42 44 48 39 40 60 74 56 79 80 66 92 82 88 98 94 子表1 子表2 子表3 子表4 数据区 33 48 80 98 索引表 1 2 3 4 max_ max_ key addr
的i值,即待查对象可能在的子表的序号。 ◆然后再在第i个子表中按给定值搜索要求 的对象。 索引表是按 max key有序的,且长度也不大, 可以折半搜索,也可以顺序搜索。 各子表内各个对象如果也按对象关键码有序, 可以采用折半搜索或顺序搜索;如果不是按 对象关键码有序,只能顺序搜索
7 的 i 值, 即待查对象可能在的子表的序号。 ◆ 然后再在第 i 个子表中按给定值搜索要求 的对象。 ◼ 索引表是按max_key有序的, 且长度也不大, 可以折半搜索，也可以顺序搜索。 ◼ 各子表内各个对象如果也按对象关键码有序, 可以采用折半搜索或顺序搜索; 如果不是按 对象关键码有序, 只能顺序搜索
索引顺序搜索的搜索成功时的平均搜索长度 ASL Indexed ASL Index +ASL Sublist 其中,ASL Index 是在索引表中搜索子表位置的 平均搜索长度, ASL是在子表内搜索对 象位置的搜索成功的平均搜索长度 设把长度为n的表分成均等的b个子表,每 个子表s个对象,则b=ms又设表中每 个对象的搜索概率相等,则每个子表的搜索 概率为1/b,子表内各对象的搜索概率为1/s。 若对索引表和子表都用顺序搜索,则索引顺 序搜索的搜索成功时的平均搜索长度为 ASLIndexseg=(b+1)2+(s+)2=(b+s)/2+1
8 ◼ 索引顺序搜索的搜索成功时的平均搜索长度 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=n时, AsLIndexse 取极小值√n+1。这个值比顺序搜索强,但 比折半搜索差。但如果子表存放在外存时, 还要受到页块大小的制约 若采用折半搜索确定对象所在的子表,则搜 索成功时的平均搜索长度为 ASL Indexed ASLInder ASL SUblist ≈log2(b+1)-1+(+1)2 ≈log2(1+n/s)+s2
9 ◼ 索引顺序搜索的平均搜索长度与表中的对象 个数 n 有关，与每个子表中的对象个数s 有 关。在给定 n 的情况下，s 应选择多大？ ◼ 用数学方法可导出, 当 s = 时, ASLIndexSeq 取极小值 +1。这个值比顺序搜索强，但 比折半搜索差。但如果子表存放在外存时， 还要受到页块大小的制约。 ◼ 若采用折半搜索确定对象所在的子表, 则搜 索成功时的平均搜索长度为 ASLIndexSeq = ASLIndex + ASLSubList log2 (b+1)-1 + (s+1)/2 log2 (1+n / s ) + s/2 n n
m路静态搜索树 当数据对象数目特别大,索引表本身很大 在内存中放不下,需要分批多次读取外存才 能把索引表搜索一遍。 此时,可以建立索引的索引(二级索引。二级 索引中一个索引项对应一个索引块,登记该 索引块的最大关键码及该索引块的存储地址。 如果二级索引在内存中也放不下,需要分为 许多块多次从外存读入。可以建立二级索引 的索引(三级索引)。这时,访问外存次数等 于读入索引次数再加上1次读取对象
10 m 路静态搜索树 ◼ 当数据对象数目特别大，索引表本身很大， 在内存中放不下，需要分批多次读取外存才 能把索引表搜索一遍。 ◼ 此时, 可以建立索引的索引(二级索引)。二级 索引中一个索引项对应一个索引块，登记该 索引块的最大关键码及该索引块的存储地址。 ◼ 如果二级索引在内存中也放不下，需要分为 许多块多次从外存读入。可以建立二级索引 的索引(三级索引)。这时，访问外存次数等 于读入索引次数再加上1次读取对象