913分块检索 顺序与二分法的折衷 既有较快的检索 又有较灵活的更改 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 21
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 9.1.3 分块检索 顺序与二分法的折衷 既有较快的检索 又有较灵活的更改
分块检索思想 “按块有序” 设线性表中共有n个数据元素,将表分 成b块 不需要均匀 每一块可能不满 每一块中的关键码不一定有序 但前一块中的最大关键码必须小于后 块中的最小关键码 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 22
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 分块检索思想 “按块有序” 设线性表中共有n个数据元素，将表分 成b块 不需要均匀 每一块可能不满 每一块中的关键码不一定有序 但前一块中的最大关键码必须小于后 一块中的最小关键码
索引表 索引表 各块中的最大关键码 及各块起始位置 可能还需要块中元素个数(每一块可 能不满) 索引表是一个递增有序表 由于表是分块有序的 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 Page 23
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 索引表 索引表 各块中的最大关键码 及各块起始位置 可能还需要块中元素个数（每一块可 能不满） 索引表是一个递增有序表 由于表是分块有序的
分块检索分两个阶段 (1)确定待查元素所在的块 (2)在块内检索待查的元素 分块检索——索引顺序结构 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 24
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 分块检索分两个阶段 （1）确定待查元素所在的块 （2）在块内检索待查的元素 分块检索——索引顺序结构
分块检索—索引顺序结构 01234567891011121314151617 2212|13 342418248 8608074 49 86 link: 0612■块内最大关键码 Key: 224886 块起始位置 size:|365块内有效元素个数 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 块内有效元素个数