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