数据结构与算法4第九章检索 第九章检索 令基本概念 任课教员:张铭 9.1线性表的检索 http://db.pku.edu.cn/mzhang/ds 令92集合的检索 zhang@db.pku.edu.cn 北京大学信息科学与技术学院 令93散列表的检索 网络与信息系统研究所 9.4总结 ⊙版权所有,转载或翻印必究 张铭 叔省。斩就即究 基本概念 基本概念(续) 检索:在一组记录集合中找到关键码 预排序 值等于给定值的某个 或者找到 关键码值符合特定条件的某些记录的 排序算法本身比较费时 过程 ■只是预处理(在检索之前已经完成) ■建立索引 检索的效率非常重要 检索时充分利用辅助索引信息 牺牲一定的空间 尤其对于大数据量 从而提高检索效率 需要对数据进行特殊的存储处理 气斯有 京大富息美 张铭 基本概念(续) 平均检索长度(AsL) 散列技术 关键码的比较:检索运算的主要操作 把数据组织到一个表中 均检索长度( Average Search Length) 根据关健码的值来确定表中每个记录的位置 ∷靈被衡法关的的你较次数 缺点: ·一般也不允许出现重复关键码 ASL= PC 散列方法不适合于基于磁盘的应用程 序时,我们可以选择B树方法 P为检索第个元素的概率 c为找到第个元素所需的关键码值与 给定值的比较次数 真大_息单 张铭 回1 数据结构与算法 第九章 检索 任课教员：张 铭 http://db.pku.edu.cn/mzhang/DS/ mzhang@db.pku.edu.cn 北京大学信息科学与技术学院 网络与信息系统研究所 ©版权所有，转载或翻印必究 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 2 第九章 检索 „ 基本概念 „ 9.1 线性表的检索 „ 9.2 集合的检索 „ 9.3 散列表的检索 „ 9.4 总结 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 3 基本概念 „ 检索：在一组记录集合中找到关键码 值等于给定值的某个记录，或者找到 关键码值符合特定条件的某些记录的 过程 „ 检索的效率非常重要 „ 尤其对于大数据量 „ 需要对数据进行特殊的存储处理 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 4 基本概念（续） „ 预排序 „ 排序算法本身比较费时 „ 只是预处理（在检索之前已经完成） „ 建立索引 „ 检索时充分利用辅助索引信息 „ 牺牲一定的空间 „ 从而提高检索效率 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 5 基本概念（续） „ 散列技术 „ 把数据组织到一个表中 „ 根据关键码的值来确定表中每个记录的位置 „ 缺点： „ 不适合进行范围查询 „ 一般也不允许出现重复关键码 „ 当散列方法不适合于基于磁盘的应用程 序时，我们可以选择B树方法 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 6 平均检索长度（ASL） „ 关键码的比较：检索运算的主要操作 „ 平均检索长度(Average Search Length) „ 检索过程中对关键码的平均比较次数 „ 衡量检索算法优劣的时间标准 1 n i i i A SL P C = = ∑ Pi 为检索第i个元素的概率 Ci 为找到第i个元素所需的关键码值与 给定值的比较次数