分块检索性能分析 分块检索为两级检索 先在索引表中确定待查元素所在 的块; n设在索引表中确定块号的时间开销是 ASL 然后在块内检索待查的元素。 在块中查找记录的时间开销为ASLw ASL (n)=ASLb ASL 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 26
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 分块检索性能分析 分块检索为两级检索 先在索引表中确定待查元素所在 的块； 设在索引表中确定块号的时间开销是 ASLb 然后在块内检索待查的元素。 在块中查找记录的时间开销为ASLw ASL(n) = ASLb + ASLw
分块检索性能分析(续1) ■索引表是按块内最大关键码有序 的,且长度也不大,可以二分检 索,也可以顺序检索 各子表内各个记录不是按记录关键 码有序,只能顺序检索 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 分块检索性能分析(续1) 索引表是按块内最大关键码 索引表是按 有序 的，且长度也不大，可以二分检 的，且长度也不大，可以二分检 索，也可以顺序检索 索，也可以顺序检索 各子表内各个记录不是按记录关键 各子表内各个记录不是按记录关键 码有序，只能顺序检索 码有序，只能顺序检索
分块检索性能分析(续2) 假设在索引表中用顺序检索,在块内 也用顺序检索 ASL_6+ ASL S+ 2 2 ASL=b+l+$+I-b+s+1 2 2 2 S +1 2S n当s=√n时,ASL取最小值, ASL=√n+1≈ 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 分块检索性能分析(续2) 假设在索引表中用顺序检索，在块内 也用顺序检索 当s= 时，ASL取最小值， ASL = +1 ≈ 1 ASL 2 b b + = n n n 1 ASL 2 s w + = 2 1 1 ASL 1 22 2 1 2 b s bs n s s + + + = += + + = +
分块检索性能分析(续3) 当n=10,000时 顺序检索5,000次 二分法检索14次 分块检索100次 如果数据块(子表)存放在外存时,还 会受到页块大小的制约 此时往往以外存一个I/O读取的数据( 页)作为一块 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 分块检索性能分析(续3) 当n=10,000时 顺序检索5,000次 二分法检索14次 分块检索100次 如果数据块（子表）存放在外存时，还 会受到页块大小的制约 此时往往以外存一个Ｉ/Ｏ读取的数据（一 页）作为一块
分块检索性能分析(续4 若采用二分法检索确定记录所在 的子表,则检索成功时的平均检 索长度为 ASL= ASL + ASL ≈log2(b+1)-1+(s+1)2 ≈log2(1+n/s)+s2 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 30
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 分块检索性能分析(续4) 若采用二分法检索确定记录所在 若采用二分法检索确定记录所在 的子表，则检索成功时的平均检 的子表，则检索成功时的平均检 索长度为 ASL= ASLb + ASLw ≈ log2 (b+1)-1 + (s+1)/2 ≈ log2(1+n / s ) + s/2