索引顺序搜索的平均搜索长度与表中的对象 个数n有关,与每个子表中的对象个数s有 关。在给定n的情况下,s应选择多大? 用数学方法可导出,当s=n时, AsLIndexse 取极小值√n+1。这个值比顺序搜索强,但 比折半搜索差。但如果子表存放在外存时, 还要受到页块大小的制约 若采用折半搜索确定对象所在的子表,则搜 索成功时的平均搜索长度为 ASL Indexed ASLInder ASL SUblist ≈log2(b+1)-1+(+1)2 ≈log2(1+n/s)+s29 ◼ 索引顺序搜索的平均搜索长度与表中的对象 个数 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