北京大学：《数据结构与算法》课程教学资源（实验班讲义）第九章 检索

数据结构与算法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个元素所需的关键码值与 给定值的比较次数

平均检索长度的例子 检索算法评估的几个问题 ■假设线性表为(a,bc)检索a、 衡量一个检索算法还需要考虑 b、c的概率分别为04、01、05 算法所需的存储量 顺序检索算法的平均检索长度为 n算法的复杂性 04×1+01×2+05×3=2.1 即平均需要21次给定值与表中关键 码值的比较才能找到待查元素 攻大_息单 有,命叠 张铭 叔省。斩就即究 9.1基于线性表的检索 9.1.1顺序检索 1.1顺序检索 ■针对线性表里的所有记录,逐个进 令9.1.2二分检索 行关键码和给定值的比较。 若某个记录的关键码和给定值比较相 9.1.3分块检索 等,则检索成功; 否则检索失败(找遍了仍找不到)。 ■存储:可以顺序、链接 排序要求:无 张帖 顺序检索算法 监视哨”顺序检索算法 template <class Type> class Item i 索成功返回元位量,检索失败统一返回0 template <class Type> int Item(Type value): key value)& ector <item Type getKeyo ireturn key}//取关键码值 dataList, int length, Type e void setKey( Type k key=k}//置关键码 private //将第0个元素设为待检值 //关键码域 dataList0]> setKey(k//设监视哨 string other; /其它域 while(dataList[]->getKeyol=k)i--' /返回元素位置 vector<Item<Type>*> dataList 学恤息 权新有,种

2 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 7 平均检索长度的例子 „ 假设线性表为（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 8 检索算法评估的几个问题 „ 衡量一个检索算法还需要考虑 „ 算法所需的存储量 „ 算法的复杂性 „ ... 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 9 9.1 基于线性表的检索 „ 9.1.1 顺序检索 „ 9.1.2 二分检索 „ 9.1.3 分块检索 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 10 9.1.1 顺序检索 „ 针对线性表里的所有记录，逐个进 行关键码和给定值的比较 。 „ 若某个记录的关键码和给定值比较相 等，则检索成功 ； „ 否则检索失败(找遍了仍找不到)。 „ 存储：可以顺序、链接 „ 排序要求：无 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 11 顺序检索算法 template <class Type> class Item { public: Item(Type value):key(value) {} Type getKey() {return key;} //取关键码值; void setKey(Type k){ key=k;} //置关键码 private: Type key; //关键码域 string other; //其它域 }; vector<Item<Type>*> dataList; 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 12 “监视哨”顺序检索算法 „ 检索成功返回元素位置，检索失败统一返回0; template <class Type> int SeqSearch(vector<Item<Type>*>& dataList,int length, Type k) { int i=length; //将第0个元素设为待检索值 dataList[0]->setKey (k); //设监视哨 while(dataList[i]->getKey()!=k) i--; return i; //返回元素位置 }

顺序检索性能分析 顺序检索平均检索长度 每个关键码是等概率的,Pi=1/n 设检索成功的概率为p,检索失败的概率 q=(1-p ASL +1 +(1-p)(n+1) ∑i (n+1)(1-P/2) 失败时都需要比较n+1次(设置了一个 (n+1)/2<AsI 叔新有,盘 张 顺序检索优缺点 9.1.2二分检索法 ■优点:插入元素可以直接 将任一元素 dataList[i]Key与给定值K 加在表尾⊙(1) 三种情况: (1)Key=K,检寰成功,返回 dataList m缺点:检索时间太长e(n) (2)Key>K,若有则一定排在 dataList[Ol前 (3)Key<K,若右则一定排在 dataList们后 缩小进一步检索的区间 订恤 张铭趣 张帖 二分法检索图示 二分法检索算法 23|4|5678 ype> int Bin Search 17|82235|516088 ector<Item<Type>*>& dataList,int length, Type k) while(low<=high) mid=(low+high)/2 if (k<data List[mid]->getKeyo) 检索关键码181ow=1high=9K=18 区间 else if (k>dat low mid+1 else return mid;//成功返回位置 第二次:mid=2;aray[2]=17(18 turn0;//检紫失败,返回0 =1818 张帖兽

3 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 13 顺序检索性能分析 „ 检索成功 假设检索每个关键码是等概率的，Pi = 1/n „ 检索失败 假设检索失败时都需要比较n+1次（设置了一个 监视哨） Pi n i i n n n i i n i n i n ·() () − = − ∑ = − = − ∑ = = + = ∑ 0 1 1 0 1 1 2 1 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 14 顺序检索平均检索长度 „ 假设检索成功的概率为p，检索失败的概率 为q=(1-p) „ （n+1)/2 < ASL < (n+1) 1 A SL ( 1) 2 1 (1 )( 1) 2 ( 1)(1 / 2) n p qn n p pn n p + = ⋅ +⋅ + + = ⋅ +− + =+ − 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 15 顺序检索优缺点 „优点：插入元素可以直接 加在表尾Θ(1) „缺点：检索时间太长Θ(n) 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 16 9.1.2 二分检索法 „ 将任一元素dataList[i] .Key与给定值K 比较 „ 三种情况： （1）Key = K，检索成功，返回dataList[i] （2）Key > K，若有则一定排在dataList[i]]前 （3）Key < K，若右则一定排在dataList[i]后 „ 缩小进一步检索的区间 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 17 二分法检索算法 template <class Type> int BinSearch (vector<Item<Type>*>& dataList,int length,Type k){ int low=1, high=length, mid; while (low<=high) { mid=(low+high)/2; if (k<dataList[mid]->getKey()) high = mid-1; //右缩检索区间 else if (k>dataList[mid]->getKey()) low = mid+1; //左缩检索区间 else return mid; //成功返回位置 } return 0; //检索失败，返回0 } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 18 检索关键码18 low=1 high=9 K=18 第一次：mid=5; array[5]=35>18 high=4; (low=1) 第二次：mid=2; array[2]=17<18 low=3; (high=4) 第三次：mid=3; array[3]=18=18 mid=3；return 8 二分法检索图示 35 1 2 3 45 6 7 8 9 15 22 51 60 88 93 low mid high 17 18

二分法检索性能分析 二分法检索性能分析(续) ■最大检索长度为 成功的平均检索长度为: ■失败的检索长度是 停止在内部叶结点 nt-log,(n+l)-I 优缺点 (n+1) 优点:平均与最大检索长度相近,检索速度快 停止在外部空结点,则加 缺点:要排序、顺序存储,不易更新(插/删 叔新有,盘 张 9.1.3分块检索 分块检索思想 顺序与二分法的折衷 ■“按块有序” 既有较快的检索 a设线性表中共有n个数据元素,将表分 又有较灵活的更改 不需要均匀 ■每一块中的关键码不一定有序 但前一块中的量大关键码必须小于后 订恤 张铭趣 张帖 索引表 分块检索分两个阶段 索引表 (1)确定待查元素所在的块 各块中的最大关键码 (2)在块内检索待查的元素 及各块起始位置 可能还需要块中元素个数(每一块可 分块检索——索引顺序结构 ■索引表是一个递增有序表 由于表是分块有序的 权新有,种 耍

4 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 19 二分法检索性能分析 „ 最大检索长度为 „ 失败的检索长度是 „ 停止在内部叶结点 或 „ 停止在外部空结点，则加1 ⎣ ⎦ log（2 n + 1） ⎡ ⎤ log（2 n + 1） 15 18 22 51 7 8 9 2 1 3 4 88 60 93 35 17 5 ⎡ ⎤ log（2 n +1） 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 20 二分法检索性能分析（续） „ 成功的平均检索长度为： (n > 50) „ 优缺点 „ 优点：平均与最大检索长度相近，检索速度快 „ 缺点：要排序、顺序存储，不易更新(插/删) 1 1 ASL ( 2 ) 1 1 log ( 1) 1 2 log ( 1) 1 2 j i i n i n n n n − = ⋅ ∑ = + = + − ≈ +− 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 21 9.1.3 分块检索 „ 顺序与二分法的折衷 „ 既有较快的检索 „ 又有较灵活的更改 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 22 分块检索思想 „ “按块有序” „ 设线性表中共有n个数据元素，将表分 成b块 „ 不需要均匀 „ 每一块可能不满 „ 每一块中的关键码不一定有序 „ 但前一块中的最大关键码必须小于后 一块中的最小关键码 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 23 索引表 „ 索引表 „ 各块中的最大关键码 „ 及各块起始位置 „ 可能还需要块中元素个数（每一块可 能不满） „ 索引表是一个递增有序表 „ 由于表是分块有序的 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 24 分块检索分两个阶段 „ （1）确定待查元素所在的块 „ （2）在块内检索待查的元素 分块检索——索引顺序结构

分块检索——索引顺序结构 分块检索性能分析 2345678910ll12131151617 分块检索为两级检索 先在索引表中确定待查元素所在 设在索引表中确定块号的时间开销是 ae H ■块内最大关键码 ■块起始位置 ■块内有效元素个数 然后在块内检索待查的元素。 在块中查找记录的时间开销为A ASL (n) 叔新有,盘 张幽 分块检索性能分析(续1) 分块检索性能分析(续2) 索引表是按块内最大关键码有序 假设在索引表中用顺序检索,在块内 的,且长度也不大,可以二分检 索,也可以顺序检索 ASL ASL:6+l+5+I=b+s ■各子表内各个记录不是按记录关键 码有序,只能顺序检索 当s=√n时,ASL取最小值 订恤 张铭趣 张帖 分块检索性能分析(续3) 分块检索性能分析(续4) ■当n=10,000时 若采用二分法检索确定记录所在 顺序检索5,000次 二分法检索14次 的子表,则检索成功时的平均检 分块检索100次 索长度为 ■如果数据块(子表)存放在外存时,还 ASL=ASL,+ ASLw 会受到页块大小的制约 此时往往以外存一个I/O读取的数据(一 ≈log2(b+1)-1+(s+1)/2 页)作为 ≈log2(1+n/s)+s2 学恤息 权新有,种 耍

5 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 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 „ 块内有效元素个数 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 26 分块检索性能分析 „ 分块检索为两级检索 „ 先在索引表中确定待查元素所在 的块； „ 设在索引表中确定块号的时间开销是 ASLb „ 然后在块内检索待查的元素。 „ 在块中查找记录的时间开销为ASLw „ ASL(n) = ASLb + ASLw 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 27 分块检索性能分析(续1) „ 索引表是按块内最大关键码有序 的，且长度也不大，可以二分检 索，也可以顺序检索 „ 各子表内各个记录不是按记录关键 码有序，只能顺序检索 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 28 分块检索性能分析(续2) „ 假设在索引表中用顺序检索，在块内 也用顺序检索 „ 当s= 时，ASL取最小值， ASL = +1 ≈ 1 ASL 2 b b + = n n n 1 ASL 2 s w + = 2 1 1 ASL 1 22 2 1 2 b s bs n s s + + + = += + + = + 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 29 分块检索性能分析(续3) „ 当n=10,000时 „ 顺序检索5,000次 „ 二分法检索14次 „ 分块检索100次 „ 如果数据块（子表）存放在外存时，还 会受到页块大小的制约 „ 此时往往以外存一个Ｉ/Ｏ读取的数据（一 页）作为一块 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 30 分块检索性能分析(续4) „ 若采用二分法检索确定记录所在 的子表，则检索成功时的平均检 索长度为 ASL= ASLb + ASLw ≈ log2 (b+1)-1 + (s+1)/2 ≈ log2(1+n / s ) + s/2