线性索引查找
查找概论
查找表按照操作方式有两大种
- 静态查找表:只做查找操作
- 动态查找表:查找过程中同时进行增删元素
顺序表查找
又称为顺序查找,遍历元素进行查找,
- 算法时间复杂度为O(n)
有序表查找
通过分隔点的不同,引入三种算法
折半查找(二分查找)
前提 : 关键码有序(通常从小到大)
线性表必须使用顺序存储
更适合静态查找表(动态需要在增删后维护)
方法 : 类似于二叉树查找,取中间值比较大小,进入下一区域
进一步在下一区域 ,取中值比较大小….循环
时间复杂度 : O(logn)
插值查找
前提、时间复杂度近似于折半查
用法 : 类似于查找新华字典,会提前寻找一个大致字母的区域
根据查找的关键词字key与查找表中的最大值与最小值的比较后查找
Mid = Begin + ( (End - Begin) / (A[End] - A[Begin]) ) * (X - A[Begin])- Mid：计算得出的元素的位置；
- End：搜索区域内最后一个元素所在的位置；
- Begin：搜索区域内第一个元素所在的位置；
- X：要查找的目标元素；
- A[]：表示整个待搜索序列
适用: 表较长,关键字分布比较均匀
斐波那切查找
算法核心
- 斐波那契查找就是在二分查找的基础上根据斐波那契数列进行分割的。在斐波那契数列找一个等于略大于查找表中元素个数的数F[n]，将原查找表扩展为长度为Fn，完成后进行斐波那契分割，即F[n]个元素分割为前半部分F[n-1]个元素，后半部分F[n-2]个元素，找出要查找的元素在那一部分并递归，直到找到。
- 优势 :
- 查找以加法进行运算(插值为四则运算,折半为加法和除法)
- 时间复杂度虽然为 O(logn),但平均性能大于折半(目标为1时为极端情况,会劣于前者)
线性索引查找
针对海量数据,关键码也不一定按照有序排列,不能遍历或者半遍历元素，就引入了索引
- 索引即为将一个关键字和它对应的记录关联的过程
- 分为线性、树形、多级索引，这里主要介绍线性索引
线性索引即为将索引项集合组织为线性结构，也陈之为索引表,重点介绍以下几种
- 稠密索引
- 分块索引
- 倒排索引
稠密索引
数据的每一个记录对应一个索引项
优点: 数据项是无序的,索引项是有序的
可以对索引项进行有序查找
缺点 : 每一次查询需要在磁盘中读取更多内存,数据庞大时(上亿级别)
查询性能反而下降
分块索引
类似如图书馆藏书管理体系.将数据集分成了若干块,各自建立索引项,指向各自的块内元素
块内无序 : 理论上可以有序更好,但是需要花费不成正比的维护成本,故不做要求
快间有序 : 第N块所有元素的关键字永远全部小于第N+1块里的每个元素
最大关键码 : 每个块中关键字最大的元素关键码值
块长 : 每个块内元素的个数
块首指针 : 指向块首元素
- 方法 : 在块间使用有序查找,在块内使用顺序查找(遍历)
- 时间复杂度 : ASLw=√n + 1 (介于顺序查找和折半查找之间)
倒排索引
通用结构
- 次关键码 : 类似于搜索引擎中的关键字
- 记录号表 : 类似于搜索引擎中对应出的整体文章标号(同一个关键词出现的次数)
其中记录号表存储的具有相同次关键词的所有的记录的记录号(可以是指向记录的指针或者是该记录的关键字)
- 优点 : 查找非常快
- 缺点 : 维护比较困难,每一个记录号都将对应好几个文章,插入删除需要额外的处理
运用实例
Elasticsearch : 功能类似一个数据库,能高效的从大量数据中搜索匹配指定关键字的内容.常常用于搜索
