一 查找概论:
当今时代,在互联网上查找信息是家常便饭,所有这些需要被查的数据所在的集合,我们给他一个统称 叫 查找表.
查找表定义: 查找表是由同一类型的数据元素或记录构成的集合.
关键字:
树数据元素中某个数据项的值,又称为键值,或关键码.
- 若此关键字可以唯一的标识一个记录,则称此关键字为主关键字或主关键码.即对不同的记录,其主关键字均不相同.
- 对于那些 可以识别多个数据元素的关键字,我们称为次关键字,或次关键码
查找:
就是根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素或记录.
若查找不成功,查找的结果可给出一个”空”记录或者”空指针”.
查找表按照操作方式分为2种:静态表查找和动态表查找.
静态表查找:(只做查找操作的查找表)
- 查询某个”特定的”数据元素是否在查找表中
- 检索某个”特定的”数据元素和各种属性.
动态表查找:(在查找过程中同时插入查找表中不存在的数据元素,或者从查找表中傻女胡已经存在的某个数据元素)
- 查找时插入数据元素
- 查找时删除数据元素
为了提高查找的效率,我们需要专门为查找操作设置数据结构,这种面向查找操作的数据结构称为查找结构.
从逻辑上来说,查找所基于的数据结构是集合,集合中的记录之间没有本质关系.但为了提高查找性能,我们就不得不改变数据元素之间的关系,在存储时可以将查找集合组织成 表 或 树等结构.
- 对于静态查找表来说,我们一般使用线性表结构来组织数据,这样可以使用顺序查找算法,如果在对主关键字排序,则可以使用折半查找等算法进行高效地查找.
- 对于动态查找表,则会复杂一些,可以考虑二叉排序树的查找技术.
二 顺序表查找
例子:一堆杂乱的书堆中,查找某一本书,如果将这些书的集合排列整齐,这样就构成一个线性表.
顺序查找:又叫线性查找,是最基本的查找技术,他的查找过程是:从表中第一个(或最后一个)记录开始,逐个进行记录的关键字个给定值比较,若某个关键字和给定值相等,则查找成功,如果直到最后一个(或第一个)记录,其关键字和给定值比较都不等时,则表中没有所查找的记录,查找不成功.
三 有序表查找
接着一中的开篇例子,如果对书进行排序,比如书名拼音排序,则查找的效率会更高.
1 折半查找:又称为二分查找
引子:在酒桌上一个小游戏,在1-100之间的自然数,两人之间,一人在心中任意记一个数,另一人猜同时可以问记数的那个人其给出的数相对正确的数是大了还是小了,在7次内猜出该数,则成功,否则失败,普通人一想,怎么可能,100个数,100中可能,但是若使用折半查找则完胜.
定义:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键字相等,则查找成功,否则若给定值小于中间记录,则在中间记录的左半区域继续折半查找;若给定值大于中间记录,则在中间记录的右半区域继续折半查找;不断重复这些操作,直到查找成功或者查找失败(无此记录).
2 插值查找:
为什么一定要折半查找而不是折四分之一呢或者更多呢?比如当你使用牛津词典查阅单词时,比如”apple”,你肯定不会傻乎乎的折半查找,而是有目的的查阅.
再比如取值范围为1-100000,之间100个元素从小到大均匀分布的数组,查找5,我们肯定也不会折半查找,肯定是从数组下标较小的开始查找.
结论:折半查找还是有优化的空间.
折半查找中有这样的等式:
算法科学家改进后为:
这个就是插值插值,根据要查找的关键字Key与查找表中的最大值 最小值的关键字比较后的查找方法,其核心就在于插值的计算公式:(key-a[low])/(a[high]-a[low]).
3 裴波那契查找:
涉及到裴波那契数列,暂时不做研究,这3种查找不同的是分割点的选择不同.
四 线性索引查找
引子:前面都是有序查找,但事实上很多数据都是增长很快的,比如大型论坛的帖子和回复总数,每天都;是成百上千万条,服务器的日志信息记录也可能是海量的数据,要保证记录全部是按照当中的某个关键字有序,其时间代价是非常高昂的,所以这种数据都是按先后顺序存储的.对于这样的查找表,我们怎么快速查找到需要的数据呢?
办法就是 “索引”.
数据结构的最终目的就是提高数据的处理速度.索引就是为了加快查找速度而设计的一种数据结构.
索引就是把一个关键字与他对应的记录相关联的过程,一个索引由若干个索引项构成.每个索引至少应包含关键字和其对应的记录在存储器中位置等信息.
索引技术是组织大型数据库以及磁盘文件的一种重要技术.
索引按照结构可以分为:线性索引 树形索引 多级索引.
线性索引:将索引项集合组织为线性结构,也称为索引表.我们重点介绍:稠密索引 分块索引 倒排索引
4.1 稠密索引:在线性索引中,将数据集中的每个记录对应一个索引项.
个人感觉类似 书的目录一样.
但是如果数据量非常大,比如上亿条数据,那么索引的数据规模也会很大,这样这种方法就不适合了.
4.2 分块索引:就是把数据集的记录分成了若干块,并且这些快需要满足2个条件:
- 块内无序,当然有序更理想,不过若付出大量的时间和空间的代价,所以一般不要求有序.
- 块间有序.比如图书馆的书架上贴的关键字是按英语字母表顺序排列的.但是书架内的书与书之间可以无序.
分块索引的索引项结构分为3个数据项:
- 最大关键码,存储每一块中的最大关键字.
- 存储了块中的记录的个数
- 用于指向块首数据元素的指针,便于开始对这一块中记录进行遍历.
4.3 倒排索引:
