数据结构与算法 第九章检索 任课教员:张铭 httpi//db.pku.edu.cn/mzhang/ds zhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有,转载或翻印必究
数据结构与算法 第九章 检索 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究
第九章检索 令基本概念 9.1线性表的检索 9.2集合的检索 令9.3散列表的检索 9.4总结 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 第九章 检索 基本概念 9.1 线性表的检索 9.2 集合的检索 9.3 散列表的检索 9.4 总结
基本概念 ■检索:在一组记录集合中找到关键码 值等于给定值的某个记录,或者找到 关键码值符合特定条件的某些记录的 过程 检索的效率非常重要 尤其对于大数据量 需要对数据进行特殊的存储处理 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 3
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 基本概念 检索：在一组记录集合中找到关键码 值等于给定值的某个记录，或者找到 关键码值符合特定条件的某些记录的 过程 检索的效率非常重要 尤其对于大数据量 需要对数据进行特殊的存储处理
基本概念(续) 预排序 排序算法本身比较费时 只是预处理(在检索之前已经完成) 建立索引 检索时充分利用辅助索引信息 牺牲一定的空间 从而提高检索效率 北京大学信息学院 张铭编写 版权所有,转载或翻印必究
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 基本概念（续） 预排序 排序算法本身比较费时 只是预处理（在检索之前已经完成） 建立索引 检索时充分利用辅助索引信息 牺牲一定的空间 从而提高检索效率
基本概念(续) ■散列技术 把数据组织到一个表中 根据关键码的值来确定表中每个记录的位置 n缺点 不适合进行范围查询 一般也不允许出现重复关键码 当散列方法不适合于基于磁盘的应用程 序时,我们可以选择B树方法 北京大学信息学院 张铭编写 版权所有,转载或翻印必究 age 5
北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 基本概念（续） 散列技术 把数据组织到一个表中 根据关键码的值来确定表中每个记录的位置 缺点： 不适合进行范围查询 一般也不允许出现重复关键码 当散列方法不适合于基于磁盘的应用程 序时，我们可以选择B树方法