=Lidx[mid] firstloc;∥块的下界 j=计Lidx[mi] count1;∥块的上界 temp=Leem-们 ∥保存左邻元素 Lelem[i-1]= key ∥设置监视哨 for(k=j; L elem[kl=key k-) ∥顺序查找 Lele[i-们]=temp; ∥放回左邻元素 if (k<i return error ∥未找到 return k. “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 i = L.idx[mid].firstloc; // 块的下界 j = i+ L.idx[mid].count-1; // 块的上界 temp = L.elem[i-1]; // 保存左邻元素 L.elem[i-1] = key; // 设置监视哨 for (k=j; L.elem[k]!=key; k--) ; // 顺序查找 L.elem[i-1]=temp; // 放回左邻元素 if (k<i) return ERROR; // 未找到 return k; }
分块检索性能分析 分块检索为两级检索 口先在索引表中确定待查元素所在的块; 设在索引表中确定块号的时间开销是ASLb 口然后在块内检索待查的元素。 在块中查找记录的时间开销为ASLw Asl(n =aslb aslo “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 分块检索性能分析 ◼ 分块检索为两级检索 ❑ 先在索引表中确定待查元素所在的块； ◼ 设在索引表中确定块号的时间开销是ASLb ❑ 然后在块内检索待查的元素。 ◼ 在块中查找记录的时间开销为ASLw ◼ ASL(n) = ASLb + ASLw
分块检索性能分析(续2) 假设在索引表中用顺序检索,在块内也用顺序 索 b+1 s+1 ASL ASL b 6+1 s+1 b+s ASL +1 2 n+s 2S 当s=√n时,ASL取最小值, ASL=mn+1≈ “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 分块检索性能分析(续2) ◼ 假设在索引表中用顺序检索，在块内也用顺序 检索 ◼ 当s = 时，ASL取最小值， ASL = +1 ≈ 1 ASL 2 b b + = 1 ASL 2 s w + = 2 1 1 ASL 1 2 2 2 1 2 b s b s n s s + + + = + = + + = + n n n
分块检索性能分析(续3) 当m=10,000时 口顺序检索5,000次 口二分法检索14次 口分块检索100次 如果数据块(子表)存放在外存时,还会受到 页块大小的制约 口此时往往以外存一个I/O读取的数据(一页) 作为一块 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 分块检索性能分析(续3) ◼ 当n=10,000时 ❑ 顺序检索5,000次 ❑ 二分法检索14次 ❑ 分块检索100次 ◼ 如果数据块（子表）存放在外存时，还会受到 页块大小的制约 ❑ 此时往往以外存一个Ｉ/Ｏ读取的数据（一页） 作为一块
分块检索性能分析(续4) 若采用二分法检索确定记录所在的子表,则检 索成功时的平均检索长度为 ASl=ASli+ ASL ≈log2(b+1)-1+(+1)/2 ≈log2(1+n/s)+s2 “十一五”国家缀规划教材。张铭,王腾蛟,赵海￡,《飙据结构与算法》,高教社,B0.6
“十一五”国家级规划教材。张铭，王腾蛟，赵海燕，《数据结构与算法》，高教社，2008. 6。 分块检索性能分析(续4) ◼ 若采用二分法检索确定记录所在的子表，则检 索成功时的平均检索长度为 ASL= ASLb+ ASLw log2 (b+1)-1 + (s+1)/2 log2 (1+n / s ) + s/2