靜態(tài)表查找

只做查找操作的查找表應(yīng)用線性表結(jié)構(gòu)來(lái)組織數(shù)據(jù)膳凝，用順序查找算法艳汽。如果對(duì)主關(guān)鍵字排序赠法，可以折半查找等高效查找壶愤。

順序表查找（線性查找）

有序表查找

關(guān)鍵碼有序

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

前提：關(guān)鍵碼有序淑倾，線性表順序存儲(chǔ)最壞查找 int(log2n)+1 次時(shí)間復(fù)雜度O(logn)不適用于頻繁執(zhí)行插入刪除的數(shù)據(jù)集mid = (low + high)/2 = low + 0.5(high - low)

差值查找

mid = low + (high - low) * (key - a[low]) / (a[high] - a[low])時(shí)間復(fù)雜度O(logn)對(duì)于關(guān)鍵字分布均勻的查找表來(lái)說(shuō)，性能比折半查找好的多征椒。

斐波納挈查找

mid = low + F[k - 1] - 1時(shí)間復(fù)雜度O(logn)平均性能優(yōu)于折半查找娇哆。算法復(fù)雜度低

三種有序表的查找本質(zhì)上是分割點(diǎn)的選擇不同，各有優(yōu)劣勃救。

動(dòng)態(tài)表查找

可以進(jìn)行插入刪除的查找表

二叉排序樹（BST碍讨，二叉查找樹，二叉搜索樹）

中序遍歷時(shí)得到有序序列有利于插入刪除操作剪芥，插入刪除時(shí)無(wú)需移動(dòng)元素位置垄开。查找性能取決于二叉排序樹的深度（形狀）插入操作發(fā)生在葉子節(jié)點(diǎn)上。不平衡的二叉排序樹查找效率非常低税肪，因此溉躲，希望二叉排序樹是比較平衡的榜田，即深度與完全二叉樹相同（int(log2n)+1），查找的時(shí)間復(fù)雜度為O(logn)

平衡二叉樹（AVL樹）

每個(gè)節(jié)點(diǎn)的左子樹和右子樹高度差<=1平衡的二叉排序樹锻梳，查找箭券，插入，刪除疑枯，時(shí)間復(fù)雜度都是O(logn)

在元素非常多的時(shí)候辩块，要么使樹的度非常大，要么樹的高度非常大=》多路查找樹

多路查找樹

每個(gè)節(jié)點(diǎn)度>=2且每個(gè)節(jié)點(diǎn)可以存儲(chǔ)多個(gè)元素2-3樹荆永，2-3-4樹废亭，B樹，B+樹

2-3樹

• 一個(gè)2節(jié)點(diǎn)包含一個(gè)元素和兩個(gè)孩子（或沒(méi)有孩子）具钥。2結(jié)點(diǎn)要么有兩個(gè)孩子豆村，要么沒(méi)有子節(jié)點(diǎn)。

• 一個(gè)3節(jié)點(diǎn)包含一大一小兩個(gè)元素和三個(gè)子節(jié)點(diǎn)（或沒(méi)有孩子）骂删。

2-3-4樹

同2-3樹

B樹

image

減少了必須訪問(wèn)節(jié)點(diǎn)和數(shù)據(jù)塊的數(shù)量，從而提高了性能宁玫。這種數(shù)據(jù)結(jié)構(gòu)是為了內(nèi)外存交互準(zhǔn)備的粗恢。

B+樹

image

散列表查找

不需要比較，直接通過(guò)關(guān)鍵字得到記錄在內(nèi)存中的存儲(chǔ)位置欧瘪。存儲(chǔ)位置 = f（關(guān)鍵字）f = 散列函數(shù) = 哈希函數(shù)時(shí)間復(fù)雜度：O(1)用統(tǒng)一函數(shù) f 算出地址再存儲(chǔ)眷射。散列技術(shù)既是一種存儲(chǔ)方法，又是一種查找方法佛掖。散列是面向查找的存儲(chǔ)結(jié)構(gòu)沖突： key1≠key2 , f(key1) = f(key2)

處理沖突的方法：

• 開放定址法

• 再散列函數(shù)法

• 鏈地址法（平均查找性能較好）

• 公共溢出區(qū)法

索引按照結(jié)構(gòu)可以分為線性索引凭迹、樹形索引、多級(jí)索引苦囱。

線性索引（索引表）

每個(gè)索引項(xiàng)至少包含一個(gè)關(guān)鍵字和對(duì)應(yīng)記錄在存儲(chǔ)器中的位置。查找快脾猛，插入刪除難

稠密索引

數(shù)據(jù)集中的每個(gè)記錄對(duì)應(yīng)一個(gè)索引項(xiàng)索引項(xiàng)是按照關(guān)鍵碼有序的排（意味著可以用有序表查找）空間代價(jià)大撕彤，不適用于非常大的數(shù)據(jù)集

分塊索引

塊間有序，塊內(nèi)無(wú)序每塊對(duì)應(yīng)一個(gè)索引項(xiàng)索引項(xiàng)結(jié)構(gòu)：

• 最大關(guān)鍵碼 存儲(chǔ)塊中最大關(guān)鍵字猛拴，使得它之后的下一塊的最小關(guān)鍵字也能比它大羹铅。

• 存儲(chǔ)塊中的記錄個(gè)數(shù)（用于循環(huán)）

• 指向塊首數(shù)據(jù)元素的指針（用于開始進(jìn)行遍歷）

最佳情況下（分塊數(shù)=塊中記錄數(shù)）平均查找長(zhǎng)度：n**0.5 +1總的來(lái)說(shuō)，分塊索引兼顧了對(duì)細(xì)分塊不需要有序的情況下愉昆，大大增加了整體查找速度职员，普遍用于數(shù)據(jù)庫(kù)表查找等技術(shù)中。

倒排索引

廣泛用于搜索引擎中索引表中每一項(xiàng)都包括一個(gè)屬性值和具有該屬性值的各記錄的地址跛溉。源于實(shí)際應(yīng)用中需要根據(jù)屬性（或字段焊切、次關(guān)鍵碼）的值來(lái)確定記錄位置扮授，查找記錄。而不是由記錄確定屬性值专肪。查找速度非成膊快