查找技术

静态表查找

只做查找操作的查找表应用线性表结构来组织数据，用顺序查找算法。如果对主关键字排序，可以折半查找等高效查找。

顺序表查找（线性查找）

有序表查找

关键码有序

折半查找（二分查找 Binary Search）

前提：关键码有序，线性表顺序存储最坏查找 int(log2n)+1 次时间复杂度O(logn)不适用于频繁执行插入删除的数据集mid = (low + high)/2 = low + 0.5(high - low)

差值查找

mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])时间复杂度O(logn)对于关键字分布均匀的查找表来说，性能比折半查找好的多。

斐波纳挈查找

mid = low + F[k - 1] - 1时间复杂度O(logn)平均性能优于折半查找。算法复杂度低

三种有序表的查找本质上是分割点的选择不同，各有优劣。

动态表查找

可以进行插入删除的查找表

二叉排序树（BST，二叉查找树，二叉搜索树）

中序遍历时得到有序序列有利于插入删除操作，插入删除时无需移动元素位置。查找性能取决于二叉排序树的深度（形状）插入操作发生在叶子节点上。不平衡的二叉排序树查找效率非常低，因此，希望二叉排序树是比较平衡的，即深度与完全二叉树相同（int(log2n)+1），查找的时间复杂度为O(logn)

平衡二叉树（AVL树）

每个节点的左子树和右子树高度差<=1平衡的二叉排序树，查找，插入，删除，时间复杂度都是O(logn)

在元素非常多的时候，要么使树的度非常大，要么树的高度非常大=》多路查找树

多路查找树

每个节点度>=2且每个节点可以存储多个元素2-3树，2-3-4树，B树，B+树

2-3树

• 一个2节点包含一个元素和两个孩子（或没有孩子）。2结点要么有两个孩子，要么没有子节点。

• 一个3节点包含一大一小两个元素和三个子节点（或没有孩子）。

2-3-4树

同2-3树

B树

B树是一种平衡的多路查找树2-3树，2-3-4树都是B树的特例 image

减少了必须访问节点和数据块的数量，从而提高了性能。这种数据结构是为了内外存交互准备的。

B+树

遍历更方便 image

散列表查找

不需要比较，直接通过关键字得到记录在内存中的存储位置。存储位置 = f（关键字）f = 散列函数 = 哈希函数时间复杂度：O(1)用统一函数 f 算出地址再存储。散列技术既是一种存储方法，又是一种查找方法。散列是面向查找的存储结构冲突： key1≠key2 , f(key1) = f(key2)

处理冲突的方法：

• 开放定址法

• 再散列函数法

• 链地址法（平均查找性能较好）

• 公共溢出区法

索引按照结构可以分为线性索引、树形索引、多级索引。

线性索引（索引表）

每个索引项至少包含一个关键字和对应记录在存储器中的位置。查找快，插入删除难

稠密索引

数据集中的每个记录对应一个索引项索引项是按照关键码有序的排（意味着可以用有序表查找）空间代价大，不适用于非常大的数据集

分块索引

块间有序，块内无序每块对应一个索引项索引项结构：

• 最大关键码 存储块中最大关键字，使得它之后的下一块的最小关键字也能比它大。

• 存储块中的记录个数（用于循环）

• 指向块首数据元素的指针（用于开始进行遍历）

最佳情况下（分块数=块中记录数）平均查找长度：n**0.5 +1总的来说，分块索引兼顾了对细分块不需要有序的情况下，大大增加了整体查找速度，普遍用于数据库表查找等技术中。

倒排索引

广泛用于搜索引擎中索引表中每一项都包括一个属性值和具有该属性值的各记录的地址。源于实际应用中需要根据属性（或字段、次关键码）的值来确定记录位置，查找记录。而不是由记录确定属性值。查找速度非常快