第九章检索 任课教员:张铭 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树方法
平均检索长度(ASL 关键码的比较 检索运算的主要操作 平均检索长度( Average Search Length) 检索过程中对关键码需要执行的平均 比较次数 是衡量检索算法优劣的时间标准 北京大学信息学院 @版权所有,转载或翻印必究 Page 6
北京大学信息学院 ©版权所有，转载或翻印必究 Page 6 平均检索长度(ASL) ◼ 关键码的比较 ◼ 检索运算的主要操作 ◼ 平均检索长度(Average Search Length) ◼ 检索过程中对关键码需要执行的平均 比较次数 ◼ 是衡量检索算法优劣的时间标准
平均检索长度 AsL是存储结构中对象总数n的函 数,其定义为: ASL=>PCE i=1 P为检索第个元素的概率 G为找到第个元素所需的关键码值与给定值的比较次 数 北京大学信息学院 @版权所有,转载或翻印必究 Page 7
北京大学信息学院 ©版权所有，转载或翻印必究 Page 7 平均检索长度 ◼ ASL是存储结构中对象总数n的函 数，其定义为： ◼ Pi 为检索第i个元素的概率 ◼ Ci 为找到第i个元素所需的关键码值与给定值的比较次 数 1 n i i i ASL PC = =
平均检索长度 假设线性表为(a,bc)检索a、b c的概率分别为04、01、05 顺序检索算法的平均检索长度为 04×1+0.1×2+05×3=21 即平均需要21次给定值与表中关键 码值的比较才能找到待查元素 北京大学信息学院 @版权所有,转载或翻印必究 Page 8
北京大学信息学院 ©版权所有，转载或翻印必究 Page 8 平均检索长度 ◼ 假设线性表为（a, b, c）检索a、b、 c的概率分别为0.4、0.1、0.5 ◼ 顺序检索算法的平均检索长度为 0.4×1+0.1×2+0.5×3 = 2.1 ◼ 即平均需要2.1次给定值与表中关键 码值的比较才能找到待查元素
衡量一个检索算法还需要考虑 算法所需的存储量 算法的复杂性 ■■■ 北京大学信息学院 @版权所有,转载或翻印必究 Page 9
北京大学信息学院 ©版权所有，转载或翻印必究 Page 9 ◼ 衡量一个检索算法还需要考虑 ◼ 算法所需的存储量 ◼ 算法的复杂性 ◼
91基于线性表的检索 911顺序检索 912二分检索 913分块检索 北京大学信息学院 版权所有,转载或翻印必究 Page 10
北京大学信息学院 ©版权所有，转载或翻印必究 Page 10 9.1 基于线性表的检索 ◼ 9.1.1 顺序检索 ◼ 9.1.2 二分检索 ◼ 9.1.3 分块检索