在子表中,所有对象可能按关键码有序地存 放,也可能无序地存放。但所有这些子表必 须分块有序,后一个子表中所有对象的关键码 均大于前一个子表中所有对象的关键码。它 们都存放在数据区中。 另外建立一个索引表。索引表中每一表目叫 做索引项,它记录了子表中最大关键码m key以及该子表在数据区中的起始位置ob addl 第i个索引项是第i个子表的索引项,i=0 ,-1。这样的索引结构叫做索引顺序结 构
◼ 在子表中, 所有对象可能按关键码有序地存 放, 也可能无序地存放。但所有这些子表必 须分块有序, 后一个子表中所有对象的关键码 均大于前一个子表中所有对象的关键码。它 们都存放在数据区中。 ◼ 另外建立一个索引表。索引表中每一表目叫 做索引项，它记录了子表中最大关键码max _key以及该子表在数据区中的起始位置obj _ addr。 ◼ 第 i 个索引项是第 i 个子表的索引项, i = 0, 1, …, n-1。这样的索引结构叫做索引顺序结 构
索引表 数据区 133 子表11221213302933 248 子表2364244483940 380 498 子表3607456798066 max max子表4921828898194 ey aaal 对索引顺序结构进行搜索时,一般分为两级 搜索: ◆先在索引表ⅠD中搜索给定值K,确定满足 IDi-1. ma key<KsDi. max kej
◼ 对索引顺序结构进行搜索时，一般分为两级 搜索: ◆ 先在索引表 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个子表中按给定值搜索要求 的对象。 索引表是按mxke有序的,且长度也不大, 可以折半搜索,也可以顺序搜索 各子表内各个对象如果也按对象关键码有序 可以采用折半搜索或顺序搜索;如果不是按 对象关键码有序,只能顺序搜索
的 i 值, 即待查对象可能在的子表的序号。 ◆ 然后再在第 i 个子表中按给定值搜索要求 的对象。 ◼ 索引表是按max_key有序的, 且长度也不大, 可以折半搜索，也可以顺序搜索。 ◼ 各子表内各个对象如果也按对象关键码有序, 可以采用折半搜索或顺序搜索; 如果不是按 对象关键码有序, 只能顺序搜索
索引顺序搜索的搜索成功时的平均搜索长度 ASL Indexed ASL ndex +ASL Sublist 其中,ASL Index 是在索引表中搜索子表位置的 平均搜索长度, ASL是在子表内搜索对 象位置的搜索成功的平均搜索长度 设把长度为n的表分成均等的b个子表,每 个子表s个对象,则b=「n/。又设表中每 个对象的搜索概率相等,则每个子表的搜索 概率为1/b,子表内各对象的搜索概率为1/s。 若对索引表和子表都用顺序搜索,则索引顺 序搜索的搜索成功时的平均搜索长度为 aSLIndexs=(b+1)/2+(s+)2=(b+s)2+1
◼ 索引顺序搜索的搜索成功时的平均搜索长度 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。这个值比顺序搜索强,但 比折半搜索差。但如果子表存放在外存时, 还要受到页块大小的制约 若采用折半搜索确定对象所在的子表,则搜 索成功时的平均搜索长度为 AL Indexed ASLIndex t AsL SUblist ≈log2(b+1)-1+(+1)2 ≈log2(1+n/s)+s/2
◼ 索引顺序搜索的平均搜索长度与表中的对象 个数 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