1. 查找的基本概念
衡量一個(gè)查找算法的時(shí)間效率的標(biāo)準(zhǔn)是：在查找過(guò)程中，關(guān)鍵字的平均次數(shù)，這個(gè)標(biāo)準(zhǔn)為平均查找長(zhǎng)度ASL；
2. 順序查找法
1) 在順序表上的查找（非等概率查找）:若等概率，則平均ASL為（n+1）/2;若非等概率，則求出期望
2) 在線性鏈表上的查找
3. 折半查找
1) 折半查找過(guò)程，關(guān)鍵序列有序，則二叉排序樹(shù)一定，即判定樹(shù)。
2) 若是關(guān)鍵碼無(wú)序，仍可構(gòu)造二叉排序樹(shù)，進(jìn)而計(jì)算每個(gè)關(guān)鍵碼的平均ASL。
3) 若是關(guān)鍵碼無(wú)序，仍可構(gòu)造二叉排序樹(shù)，建立過(guò)程中，可以調(diào)整為平衡二叉樹(shù)。進(jìn)而計(jì)算每個(gè)關(guān)鍵碼的平均ASL。
4. B樹(shù)
1) 線性索引：所有子表，分塊有序，后一個(gè)子表的所有關(guān)鍵字大于前面一個(gè)子表中所有元素的關(guān)鍵字。另外，在建立一張索引表，索引項(xiàng)記錄了各子表的最大關(guān)鍵值以及所在的位置，因此，各個(gè)索引項(xiàng)在索引表中的序號(hào)與各個(gè)子表的塊號(hào)一一對(duì)應(yīng)。對(duì)索引順序結(jié)構(gòu)進(jìn)行查找時(shí)，分為兩級(jí)查找。先通過(guò)索引項(xiàng)確定子表，然后在子表中查找。
2) 多級(jí)索引和m叉查找樹(shù)：有多級(jí)索引構(gòu)成一個(gè)m叉查找樹(shù)，樹(shù)中的每一個(gè)分支節(jié)點(diǎn)表示索引塊，他最多存放m個(gè)索引塊，每個(gè)索引塊分別給出各子樹(shù)節(jié)點(diǎn)的最大關(guān)鍵字和節(jié)點(diǎn)地址。
3) B樹(shù)為二叉排序樹(shù)
4) B-樹(shù)的概念：根節(jié)點(diǎn)至少有2個(gè)子樹(shù)；非根的非中終端接點(diǎn)有m/2個(gè)結(jié)點(diǎn)；含有k個(gè)結(jié)點(diǎn)的子樹(shù)種有k-1個(gè)關(guān)鍵字。
5) B+樹(shù)的概念：B+樹(shù)是-B的一種變形，它與B樹(shù)的區(qū)別在于有k個(gè)關(guān)鍵字的結(jié)點(diǎn)必然有K棵子樹(shù)，非葉子結(jié)點(diǎn)僅僅具有索引作用，而跟記錄有關(guān)的關(guān)鍵字都在葉子結(jié)點(diǎn)中。跟B樹(shù)的查找類似，但是也有不同。由于跟記錄有關(guān)的信息存放在葉結(jié)點(diǎn)中，查找時(shí)若在上層已找到待查的關(guān)鍵碼，并不停止，而是繼續(xù)沿指針向下一直查到葉結(jié)點(diǎn)層的關(guān)鍵碼。此外，B+樹(shù)的所有葉結(jié)點(diǎn)構(gòu)成一個(gè)有序鏈表，可以按照關(guān)鍵碼排序的次序遍歷全部記錄。上面兩種方式結(jié)合起來(lái)，使得B+樹(shù)非常適合范圍檢索。
5. 散列查找
1) 散列表的概念:表項(xiàng)的存儲(chǔ)位置與表項(xiàng)關(guān)鍵字之間確立一個(gè)對(duì)應(yīng)的關(guān)系函數(shù)。
2) 常見(jiàn)散列函數(shù)：除留余數(shù)法。
3) 解決沖突的方法：線性探測(cè)法，二次探測(cè)法，拉鏈法
4) 效率分析：查找成功的平均查找長(zhǎng)度；查找失敗的平均查找長(zhǎng)度；