分块检索——索引顺序结构 分块检索性能分析 2345678910ll12131151617 分块检索为两级检索 先在索引表中确定待查元素所在 设在索引表中确定块号的时间开销是 ae H ■块内最大关键码 ■块起始位置 ■块内有效元素个数 然后在块内检索待查的元素。 在块中查找记录的时间开销为A ASL (n) 叔新有,盘 张幽 分块检索性能分析(续1) 分块检索性能分析(续2) 索引表是按块内最大关键码有序 假设在索引表中用顺序检索,在块内 的,且长度也不大,可以二分检 索,也可以顺序检索 ASL ASL:6+l+5+I=b+s ■各子表内各个记录不是按记录关键 码有序,只能顺序检索 当s=√n时,ASL取最小值 订恤 张铭趣 张帖 分块检索性能分析(续3) 分块检索性能分析(续4) ■当n=10,000时 若采用二分法检索确定记录所在 顺序检索5,000次 二分法检索14次 的子表,则检索成功时的平均检 分块检索100次 索长度为 ■如果数据块(子表)存放在外存时,还 ASL=ASL,+ ASLw 会受到页块大小的制约 此时往往以外存一个I/O读取的数据(一 ≈log2(b+1)-1+(s+1)/2 页)作为 ≈log2(1+n/s)+s2 学恤息 权新有,种 耍5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 25 link: Key: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 22 12 13 33 42 44 38 24 48 60 80 74 49 86 22 48 86 0 6 12 分块检索——索引顺序结构 „ 块内最大关键码 „ 块起始位置 Size: 3 6 5 „ 块内有效元素个数 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 分块检索性能分析 „ 分块检索为两级检索 „ 先在索引表中确定待查元素所在 的块； „ 设在索引表中确定块号的时间开销是 ASLb „ 然后在块内检索待查的元素。 „ 在块中查找记录的时间开销为ASLw „ ASL(n) = ASLb + ASLw 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 分块检索性能分析(续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 + + + = += + + = + 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 分块检索性能分析(续3) „ 当n=10,000时 „ 顺序检索5,000次 „ 二分法检索14次 „ 分块检索100次 „ 如果数据块（子表）存放在外存时，还 会受到页块大小的制约 „ 此时往往以外存一个Ｉ/Ｏ读取的数据（一 页）作为一块 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 分块检索性能分析(续4) „ 若采用二分法检索确定记录所在 的子表，则检索成功时的平均检 索长度为 ASL= ASLb + ASLw ≈ log2 (b+1)-1 + (s+1)/2 ≈ log2(1+n / s ) + s/2