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) 效率分析：查找成功的平均查找長度；查找失敗的平均查找長度；