1. 查找的基本概念
衡量一个查找算法的时间效率的标准是：在查找过程中，关键字的平均次数，这个标准为平均查找长度ASL；
2. 顺序查找法
1) 在顺序表上的查找（非等概率查找）:若等概率，则平均ASL为（n+1）/2;若非等概率，则求出期望
2) 在线性链表上的查找
3. 折半查找
1) 折半查找过程，关键序列有序，则二叉排序树一定，即判定树。
2) 若是关键码无序，仍可构造二叉排序树，进而计算每个关键码的平均ASL。
3) 若是关键码无序，仍可构造二叉排序树，建立过程中，可以调整为平衡二叉树。进而计算每个关键码的平均ASL。
4. B树
1) 线性索引：所有子表，分块有序，后一个子表的所有关键字大于前面一个子表中所有元素的关键字。另外，在建立一张索引表，索引项记录了各子表的最大关键值以及所在的位置，因此，各个索引项在索引表中的序号与各个子表的块号一一对应。对索引顺序结构进行查找时，分为两级查找。先通过索引项确定子表，然后在子表中查找。
2) 多级索引和m叉查找树：有多级索引构成一个m叉查找树，树中的每一个分支节点表示索引块，他最多存放m个索引块，每个索引块分别给出各子树节点的最大关键字和节点地址。
3) B树为二叉排序树
4) B-树的概念：根节点至少有2个子树；非根的非中终端接点有m/2个结点；含有k个结点的子树种有k-1个关键字。
5) B+树的概念：B+树是-B的一种变形，它与B树的区别在于有k个关键字的结点必然有K棵子树，非叶子结点仅仅具有索引作用，而跟记录有关的关键字都在叶子结点中。跟B树的查找类似，但是也有不同。由于跟记录有关的信息存放在叶结点中，查找时若在上层已找到待查的关键码，并不停止，而是继续沿指针向下一直查到叶结点层的关键码。此外，B+树的所有叶结点构成一个有序链表，可以按照关键码排序的次序遍历全部记录。上面两种方式结合起来，使得B+树非常适合范围检索。
5. 散列查找
1) 散列表的概念:表项的存储位置与表项关键字之间确立一个对应的关系函数。
2) 常见散列函数：除留余数法。
3) 解决冲突的方法：线性探测法，二次探测法，拉链法
4) 效率分析：查找成功的平均查找长度；查找失败的平均查找长度；