二分法检索性能分析(续) ■成功的平均检索长度为: ASL≈1 (∑i·22) Nn+10g2(n+1)-1 ≈log2(n+1) (n>50) ■优缺点 优点:平均检索长度与最大检索长度相近,检索速度快 缺点:要排序、顺序存储,不易更新(插/删) 北京大学信息学院 版权所有,转载或翻印必究 Page 21
北京大学信息学院 ©版权所有，转载或翻印必究 Page 21 二分法检索性能分析（续） ◼ 成功的平均检索长度为： (n > 50) ◼ 优缺点 ◼ 优点：平均检索长度与最大检索长度相近，检索速度快 ◼ 缺点：要排序、顺序存储，不易更新(插/删) 1 1 ASL ( 2 ) 1 1 log ( 1) 1 2 log ( 1) 1 2 j i i n i n n n n − = = + = + − + −
91.3分块检索 顺序与二分法的折衷 既有较快的检索 又有较灵活的更改 北京大学信息学院 版权所有,转载或翻印必究 Page 22
北京大学信息学院 ©版权所有，转载或翻印必究 Page 22 9.1.3 分块检索 ◼ 顺序与二分法的折衷 ◼ 既有较快的检索 ◼ 又有较灵活的更改
分块检索思想 “按块有序” 设线性表中共有n个数据元素,将表分 成b块 不需要均匀 每一块可能不满 每一块中的关键码不一定有序 a但前,块中的最大关键码必须小于后 块中的最小关键码 北京大学信息学院 版权所有,转载或翻印必究 Page 23
北京大学信息学院 ©版权所有，转载或翻印必究 Page 23 分块检索思想 ◼ “按块有序” ◼ 设线性表中共有n个数据元素，将表分 成b块 ◼ 不需要均匀 ◼ 每一块可能不满 ◼ 每一块中的关键码不一定有序 ◼ 但前一块中的最大关键码必须小于后 一块中的最小关键码
索引表 各块中的最大关键码 及各块起始位置 可能还需要块中元素个数(每一块可 能不满) 索引表是一个递增有序表 由于表是分块有序的 北京大学信息学院 版权所有,转载或翻印必究 Page 24
北京大学信息学院 ©版权所有，转载或翻印必究 Page 24 ◼ 索引表 ◼ 各块中的最大关键码 ◼ 及各块起始位置 ◼ 可能还需要块中元素个数（每一块可 能不满） ◼ 索引表是一个递增有序表 ◼ 由于表是分块有序的
分块检索分两个阶段 (1)确定待查元素所在的块 (2)在块内检索待查的元素 北京大学信息学院 版权所有,转载或翻印必究 Page 25
北京大学信息学院 ©版权所有，转载或翻印必究 Page 25 分块检索分两个阶段 ◼ （1）确定待查元素所在的块 ◼ （2）在块内检索待查的元素