顺序表查找
顺序查找(线性查找)
从表中第一个(或最后一个)记录开始，逐个进行记录的的关键字和给定值比较。
有序表查找
折半查找(二分查找)
切记：表必须是有序的。mid=(low+high)/2。复杂度是0(logn)
可以优化的地方：每次都从1/2处查找，对于有些场景还是不太适合的，<br>比如查找am单词，很显然从字典的前面查找效率更高，所以优化点是从哪里开始折半
插值查找
公式：mid=low+(key-a[low])*(high-low)/a[high]-a[low] ；low和high是数组的下标
适合场景：
表长较大，而关键字分配又比较均匀的查找表，性能比折半查找要好得多。复杂度也是0(logn)
斐波那契查找
构造另外一个斐波那契数列用于辅助
公式：mid=low+F[K-1]-1 ；F是斐波那契数列
比较：平均效率优于折半查找，最坏情况下，效率低于折半
线性索引查找
分块索引
把数据集的记录分成了若干块，满足俩个条件
<ul><li>块内无序</li></ul>
<ul><li>块间有序</li></ul>
倒排索引(P312)
概念：记录号表存储具有相同次关键字的所有记录的记录号<br>(可以指向记录的指针或者该记录的主关键字)
<b>搜索引擎最基础的搜索技术</b>
<b>二叉搜索树(又称二叉查找树/排序数)</b>
特点：
<ul><li>若左子树不为空，则左子树上所有结点值均小于根结点的值</li></ul>
<ul><li>若右子树不为空，则右子树上所有结点的值均大于它的根结点的值</li></ul>
<ul><li>它的左右子树也分别为二叉排序树</li></ul>
优点：
是一个既使得插入和删除效率不错，<br>又可以比较高效率的实现查找的算法
缺点：
极端情况下，会退化成链表。时间复杂度为O(n)
<b>平衡二叉搜索树(AVL树) </b>P(329)
概念：<b>是一种二叉排序树</b>，其中每一个节点<br>的左子树和右子树的<b>高度</b>差绝对值不超过1
优缺点：
维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，<br>更多的地方是用追求局部而不是非常严格整体平衡的红黑树。<br>当然，如果应用场景中对插入删除不频繁，只是对查找要求较高，那么AVL还是较优于红黑树。
多路查找树(B树)
概念：每一个结点的孩子树可以多余俩个，且每一个结点处可以存储多个元素
4种形式
2-3树
每一个结点都具有俩个孩子(称为2结点)，或三个孩子(称为3结点)
<b>B树</b>
一种平衡的多路查找树
所有叶子结点都位于同一层次
<b>B+树</b>
应文件系统那个所需而出的一种B树的变形树
出现在分支节点中的元素会在叶子结点中再次列出，每一个叶子结点都会保存一个指向后一叶子结点的指针
红黑树
概念：一种自平衡二叉查找树，和AVL树类似(并不是真正的平衡二叉树)，<br>都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
适合：适合搜索，插入，删除较多的情况
性质：
每个结点要么是红色，要么是黑色
根结点永远是黑色
所有的叶节点都是空结点(即null)，并且是黑色的
每个红色结点的俩个子结点都是黑色(从每个叶子到跟的路径上不会有俩个连续的红色结点)
从任一结点到其子树中每个叶子结点的路径都包含相同数量的黑色结点
关键性质：
这些性质强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。主要原因在于，<b>性质4导致了路径不能有两个毗连的红色节点，最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点</b>，根据性质5所有<b>最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长</b>
散列表查找(哈希表)
概念：散列技术是在记录的存储位置和它的关键字之间建立一个稳定的对于关系f，<br>使得每个关键字key对于一个存储位置f(key)，f称为散列函数，又称为哈希(Hash)函数
特点
<ul><li><b>在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录</b></li></ul>
<ul><li><b>查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录</b></li></ul>
缺点
有时候俩个关键字不同，但是算出来的地址相同，称为冲突
散列函数构造方法
直接定址法
数字分析法
平方取中法
折叠法
除留余数法
随机数法
