衡量一個查找算法的時間效率的標(biāo)準(zhǔn)是：在查找過程中，關(guān)鍵字的平均次數(shù)，這個標(biāo)準(zhǔn)為平均查找長度ASL；

2. 順序查找法

1) 在順序表上的查找（非等概率查找）:若等概率，則平均ASL為（n+1）/2;若非等概率，則求出期望

2) 在線性鏈表上的查找

3. 折半查找

1) 折半查找過程，關(guān)鍵序列有序，則二叉排序樹一定，即判定樹。

2) 若是關(guān)鍵碼無序，仍可構(gòu)造二叉排序樹，進而計算每個關(guān)鍵碼的平均ASL。

3) 若是關(guān)鍵碼無序，仍可構(gòu)造二叉排序樹，建立過程中，可以調(diào)整為平衡二叉樹。進而計算每個關(guān)鍵碼的平均ASL。

4. B樹

1) 線性索引：所有子表，分塊有序，后一個子表的所有關(guān)鍵字大于前面一個子表中所有元素的關(guān)鍵字。另外，在建立一張索引表，索引項記錄了各子表的最大關(guān)鍵值以及所在的位置，因此，各個索引項在索引表中的序號與各個子表的塊號一一對應(yīng)。對索引順序結(jié)構(gòu)進行查找時，分為兩級查找。先通過索引項確定子表，然后在子表中查找。

2) 多級索引和m叉查找樹：有多級索引構(gòu)成一個m叉查找樹，樹中的每一個分支節(jié)點表示索引塊，他最多存放m個索引塊，每個索引塊分別給出各子樹節(jié)點的最大關(guān)鍵字和節(jié)點地址。

3) B樹為二叉排序樹

4) B-樹的概念：根節(jié)點至少有2個子樹；非根的非中終端接點有m/2個結(jié)點；含有k個結(jié)點的子樹種有k-1個關(guān)鍵字。

5) B+樹的概念：B+樹是-B的一種變形，它與B樹的區(qū)別在于有k個關(guān)鍵字的結(jié)點必然有K棵子樹，非葉子結(jié)點僅僅具有索引作用，而跟記錄有關(guān)的關(guān)鍵字都在葉子結(jié)點中。跟B樹的查找類似，但是也有不同。由于跟記錄有關(guān)的信息存放在葉結(jié)點中，查找時若在上層已找到待查的關(guān)鍵碼，并不停止，而是繼續(xù)沿指針向下一直查到葉結(jié)點層的關(guān)鍵碼。此外，B+樹的所有葉結(jié)點構(gòu)成一個有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。上面兩種方式結(jié)合起來，使得B+樹非常適合范圍檢索。

5. 散列查找

1) 散列表的概念:表項的存儲位置與表項關(guān)鍵字之間確立一個對應(yīng)的關(guān)系函數(shù)。

2) 常見散列函數(shù)：除留余數(shù)法。

3) 解決沖突的方法：線性探測法，二次探測法，拉鏈法

4) 效率分析：查找成功的平均查找長度；查找失敗的平均查找長度；