概念
查找表: 同一类型的数据元素( 或记录 ) 构成的集合;
关键字: 数据元素中各个数据项的值, 又称键值;
主关键: 唯一标识一个记录的关键字;
次关键字: 可以识别多个记录的关键字;
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/search-concept-1.png" width="568" />查找: 给定某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录);
查找表按着操作分为静态查找表和动态查找表
- 静态查找表: 只做查找操作;
- 动态查找表: 在查找过程中同事对数据进行操作( 新增,修改或删除 );
- 面对查找要还有结构, 对于不用的罗辑需要做不同的结构,比如:线性表,树等等.
顺序查找(线性查找)
按着顺序从前到后或从后到前逐个查找, 时间复杂度是O(n),
有序查找
二分查找( 拆半查找 ), 时间复杂度为 O(logn);
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/search-binary-1.png" width="558" />
插值查找
- 将二分查找的 mid = （low+high）/ 2, 即 mid = low + 1/2 * (high - low);
- 插值查找将 以上的1/2变为 (key - a[low]) / (a[high] - a[low])
- 即: mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)
- 根据关键字在整个有序表中所处的位置，让mid值的变化更靠近关键字key，这样也就间接地减少了比较次数;
- 适合于分布均匀的有序查找;
斐波那契查找 ( 黄金比例查找 )
- 黄金比例又称黄金分割，是指事物各部分间一定的数学比例关系，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1
- 斐波那契数列 F(n) = F(n-1)+F(n-1);
- 1 1 2 3 5 8 13 21 34 55 89 ....
- 5/8=0.625, 8/13=0.615,13/21=0.619, 55/89=0.618...
- 随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中.
- 黄金分割的原理来确定mid的位置: mid = low+F[k-1]-1;
分析以上三种有序查找方式的分割点 mid
- 拆半查找： mid = (low+high)/2, 加法与除法运算；
- 插值查找： mid = low+(high-low)*(key-a[low])/(a[hign]-a[low])，复杂的四则运算；
- 斐波那契查找： mid = low+F[k-1]-1; 只有减法运算；
比较以上三种有序查找，查找的时间复杂度都是log(n)，但是在海量数据的查找过程中，性能上斐波那契查找是最优秀的；
线性索引查找
索引定义： 把一个关键字与它对应的记录相关联的过程；
索引技术： 是组织大型数据以及磁盘文件的一种重要技术；
一个索引由若干个索引项组成，一个索引项至少包含关键字和对应的记录在存储器中的地址；
**索引分类,按着结构分为：线性索引，树形索引，多级索引； **
- 线性索引： 将索引项集合组织为线性结构（也称索引表），分为以下三种：
* 稠密索引
* 分块索引
* 倒排索引
稠密索引
- 索引项数量 = 数据记录数量；
- 索引表按着关键码有序排列，可以对索引表使用拆半、插值、斐波那契等有序查找找到要查找记录的地址，然后根据指针地址找到对应的真实数据记录；
- 适合数据量小的情况;
- 下图：左侧代表索引表，右侧代表真实记录；
<img src="https://raw.githubusercontent.com/liangxifeng833/my_program/master/images/datastruct/line-dense-index.png" width="" />
分块索引
- 索引项数量<数据记录数量, 所以索引表占用内存资源小;
- 将数据集分块, 块间有序, 比如: 第二块所有记录的关键字均大于第一块中所有记录的关键字, 第三块大于第二块;
- 分块索引: 对于分块有序的数据集,将每块对应一个索引项;
- 比顺序查找O(n)快，比二分O(logn)慢;
- 索引项结构:
- 最大关键码(数据记录中每块的最大关键字)
- 块中的记录总数
-
指向块首数据元素的指针
倒排索引
- 由属性（字段、关键字）的值确定记录的位置。
- 索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址
- 优点：查找记录快
- 缺点：记录号不定长, 新增/修改/删除操作时维护成本较大;
- 例如：通过文章中的单词找到对应的文章;
- 文章1： it is what it is
- 文章2：what is it
- 文章3：it is a banana
| 关键字 | 所在文章 |
|---|---|
| a | 2 |
| banana | 2 |
| is | 0,1,2 |
| it | 0,1,2 |
| what | 0,1 |
以上查找方式都是静态查找, 特别是有序查找对于新增/修改/删除操作复杂, 所以就有了以下的动态查找;
动态查找
- 概念: 在查找的过程对数据进行新增/修改/删除等操作;
- 二叉排序树-BST:
- 平衡二叉树-AVL
- 多路查找树-B树
