分块检索—一索引顺序结构 01 234567891Ⅱ卫11 212139823444382448680744983 link 0612 224886 索引表中每个索引项有两个域 块内最大关键码 块起始位置 北京大学信息学院 版权所有,转载或翻印必究 Page 26
北京大学信息学院 ©版权所有，转载或翻印必究 Page 26 分块检索——索引顺序结构 ◼ 索引表中每个索引项有两个域 ◼ 块内最大关键码 ◼ 块起始位置
分块检索性能分析 分块检索为两级检索 先在索引表中确定待查元素所在 的块 设在索引表中确定块号的时间开销是 ASL 然后在块内检索待查的元素。 在块中查找记录的时间开销为ASL ASL (n)=ASLb ASL 北京大学信息学院 版权所有,转载或翻印必究 Page 27
北京大学信息学院 ©版权所有，转载或翻印必究 Page 27 分块检索性能分析 ◼ 分块检索为两级检索 ◼ 先在索引表中确定待查元素所在 的块； ◼ 设在索引表中确定块号的时间开销是 ASLb ◼ 然后在块内检索待查的元素。 ◼ 在块中查找记录的时间开销为ASLw ◼ ASL(n) = ASLb + ASLw
分块检索性能分析(续1) 索引表是按块内最大关键码有序的, 且长度也不大,可以二分检索,也 可以顺序检索 各子表内各个记录不是按记录关键 码有序,只能顺序检索 北京大学信息学院 版权所有,转载或翻印必究 Page 28
北京大学信息学院 ©版权所有，转载或翻印必究 Page 28 分块检索性能分析(续1) ◼ 索引表是按块内最大关键码有序的， 且长度也不大，可以二分检索，也 可以顺序检索 ◼ 各子表内各个记录不是按记录关键 码有序，只能顺序检索
分块检索性能分析(续2) 假设在索引表中用顺序检索,在块内 也用顺序检索 b+1 s+1 ASL,= b ASL 2 2 AsI 6+1 5+1 b+s 2 2 2 2 n+s +1 2S 当s=√n时,ASL取最小值, ASL 1+1 北京大学信息学院 版权所有,转载或翻印必究 Page 29
北京大学信息学院 ©版权所有，转载或翻印必究 Page 29 分块检索性能分析(续2) ◼ 假设在索引表中用顺序检索，在块内 也用顺序检索 ◼ 当s= 时，ASL取最小值， ASL = +1 ≈1 ASL 2 b b + = n n n 1 ASL 2 s w + = 2 1 1 ASL 1 2 2 2 1 2 b s b s n s s + + + = + = + + = +
分块检索性能分析(续3) 当n=10,000时 顺序检索5,000次 二分法检索14次 分块检索100次 如果数据块(子表)存放在外存时,还 会受到页块大小的制约 此时往往以外存一个I/O读取的数据( 页)作为一块 北京大学信息学院 版权所有,转载或翻印必究 Page 30
北京大学信息学院 ©版权所有，转载或翻印必究 Page 30 分块检索性能分析(续3) ◼ 当n=10,000时 ◼ 顺序检索5,000次 ◼ 二分法检索14次 ◼ 分块检索100次 ◼ 如果数据块（子表）存放在外存时，还 会受到页块大小的制约 ◼ 此时往往以外存一个Ｉ/Ｏ读取的数据（一 页）作为一块