二分法检索性能分析 二分法检索性能分析(续) ■最大检索长度为 成功的平均检索长度为: ■失败的检索长度是 停止在内部叶结点 nt-log,(n+l)-I 优缺点 (n+1) 优点:平均与最大检索长度相近,检索速度快 停止在外部空结点,则加 缺点:要排序、顺序存储,不易更新(插/删 叔新有,盘 张 9.1.3分块检索 分块检索思想 顺序与二分法的折衷 ■“按块有序” 既有较快的检索 a设线性表中共有n个数据元素,将表分 又有较灵活的更改 不需要均匀 ■每一块中的关键码不一定有序 但前一块中的量大关键码必须小于后 订恤 张铭趣 张帖 索引表 分块检索分两个阶段 索引表 (1)确定待查元素所在的块 各块中的最大关键码 (2)在块内检索待查的元素 及各块起始位置 可能还需要块中元素个数(每一块可 分块检索——索引顺序结构 ■索引表是一个递增有序表 由于表是分块有序的 权新有,种 耍4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 二分法检索性能分析 „ 最大检索长度为 „ 失败的检索长度是 „ 停止在内部叶结点 或 „ 停止在外部空结点，则加1 ⎣ ⎦ log（2 n + 1） ⎡ ⎤ log（2 n + 1） 15 18 22 51 7 8 9 2 1 3 4 88 60 93 35 17 5 ⎡ ⎤ log（2 n +1） 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 二分法检索性能分析（续） „ 成功的平均检索长度为： (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 − = ⋅ ∑ = + = + − ≈ +− 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 9.1.3 分块检索 „ 顺序与二分法的折衷 „ 既有较快的检索 „ 又有较灵活的更改 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 分块检索思想 „ “按块有序” „ 设线性表中共有n个数据元素，将表分 成b块 „ 不需要均匀 „ 每一块可能不满 „ 每一块中的关键码不一定有序 „ 但前一块中的最大关键码必须小于后 一块中的最小关键码 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 索引表 „ 索引表 „ 各块中的最大关键码 „ 及各块起始位置 „ 可能还需要块中元素个数（每一块可 能不满） „ 索引表是一个递增有序表 „ 由于表是分块有序的 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 分块检索分两个阶段 „ （1）确定待查元素所在的块 „ （2）在块内检索待查的元素 分块检索——索引顺序结构