外部查找

在計算機中，存儲器的層次結構一般分為：CPU暫存器、主存、輔存，外部查找是指在輔助設備空間進行數據查找。如在計算機中記憶體的大小是有限的， 如果要查找的數據量太大，無法全部載入到記憶體中，必須藉助輔助存儲設備的空間再進行查找。

基本介紹

• 中文名：外部查找
• 外文名：External Searching
• 學科：計算機科學
• 定義：查找外部存儲設備數據
• 區別：與內部查找不同
• 目的：提高計算機效率
• 原因：數據太大、記憶體大小有限

定義

查找是指在數據序列中尋找符合特定條件的數據。在計算機中，存儲器的層次結構一般分為：CPU暫存器、主存、輔存，外部查找是指在輔助設備空間進行數據查找。進行外部查找的原因：

1. 在計算機中記憶體的大小是有限的， 如果要查找的數據量太大，無法全部載入到記憶體中，必須藉助輔助存儲設備的空間再進行查找；
   

2. 為了提高計算機處理的效率，處理更多的進程，我們一般只載入一部分數據，需要的再到輔存中查找。

查找方法

查找方法在實際運做過程中數據的存儲方式不同，可分為“內部查找”與“外部查找”兩類。這裡是主要是外部查找的方法。

順序查找

順序查找(sequential scarch)又稱線性查找，是‘種最簡單的查找方法。它是指將數據以線性表的形式存儲，用線性表來表示靜態查找表。其基本思想是：從線性表中第一個記錄開始，依次比較每個數據元素的關鍵字，若記錄的關鍵字與給定值相等，則查找成功返回該元素序號；若查完整個線性表都沒有與給定值匹配的元素，則查找失敗。

複雜度分析：

查找成功時的平均查找長度為：（假設每個數據元素的機率相等） ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;

當查找不成功時，需要n+1次比較，時間複雜度為O(n);

所以，順序查找的時間複雜度為O(n)。

折半查找

二分查找又稱折半查找，優點是比較次數少，查找速度快，平均性能好；其缺點是要求待查表為有序表，且插入刪除困難。因此，折半查找方法適用於不經常變動而查找頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查找關鍵字比較，如果兩者相等，則查找成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查找關鍵字，則進一步查找前一子表，否則進一步查找後一子表。重複以上過程，直到找到滿足條件的記錄，使查找成功，或直到子表不存在為止，此時查找不成功。

複雜度分析：最壞情況下，關鍵字比較次數為log2(n+1)，且期望時間複雜度為O(log2n)；

斐波那契查找

基本思想：也是二分查找的一種提升算法，通過運用黃金比例的概念在數列中選擇查找點進行查找，提高查找效率。同樣地，斐波那契查找也屬於一種有序查找算法。

相對於折半查找，一般將待比較的key值與第mid=（low+high）/2位置的元素比較，比較結果分三種情況：

1）相等，mid位置的元素即為所求

2）>，low=mid+1;

3）<，high=mid-1。

斐波那契查找與折半查找很相似，他是根據斐波那契序列的特點對有序表進行分割的。他要求開始表中記錄的個數為某個斐波那契數小1，及n=F(k)-1;

開始將k值與第F(k-1)位置的記錄進行比較(及mid=low+F(k-1)-1),比較結果也分為三種

1）相等，mid位置的元素即為所求

2）>，low=mid+1,k-=2;

說明：low=mid+1說明待查找的元素在[mid+1,high]範圍內，k-=2 說明範圍[mid+1,high]內的元素個數為n-(F(k-1))=Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1個，所以可以遞歸的套用斐波那契查找。

3）<，high=mid-1,k-=1。

說明：low=mid+1說明待查找的元素在[low,mid-1]範圍內，k-=1 說明範圍[low,mid-1]內的元素個數為F(k-1)-1個，所以可以遞歸 的套用斐波那契查找。

複雜度分析：最壞情況下，時間複雜度為O(log2n)，且其期望複雜度也為O(log2n)。

二叉樹查找算法

基本思想：二叉查找樹是先對待查找的數據進行生成樹，確保樹的左分支的值小於右分支的值，然後在就行和每個節點的父節點比較大小，查找最適合的範圍。這個算法的查找效率很高，但是如果使用這種查找方法要首先創建樹。

二叉查找樹（BinarySearch Tree，也叫二叉搜尋樹，或稱二叉排序樹Binary Sort Tree）或者是一棵空樹，或者是具有下列性質的二叉樹：

1）若任意節點的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；

2）若任意節點的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；

3）任意節點的左、右子樹也分別為二叉查找樹。

平衡查找樹之2-3查找樹（2-3 Tree）

2-3查找樹定義：和二叉樹不一樣，2-3樹運行每個節點保存1個或者兩個的值。對於普通的2節點(2-node)，他保存1個key和左右兩個自己點。對應3節點(3-node)，保存兩個Key，2-3查找樹的定義如下：

1）要么為空，要么：

2）對於2節點，該節點保存一個key及對應value，以及兩個指向左右節點的節點，左節點也是一個2-3節點，所有的值都比key要小，右節點也是一個2-3節點，所有的值比key要大。

3）對於3節點，該節點保存兩個key及對應value，以及三個指向左中右的節點。左節點也是一個2-3節點，所有的值均比兩個key中的最小的key還要小；中間節點也是一個2-3節點，中間節點的key值在兩個跟節點key值之間；右節點也是一個2-3節點，節點的所有key值比兩個key中的最大的key還要大。

平衡查找樹之紅黑樹（Red-Black Tree）

2-3查找樹能保證在插入元素之後能保持樹的平衡狀態，最壞情況下即所有的子節點都是2-node，樹的高度為lgn，從而保證了最壞情況下的時間複雜度。但是2-3樹實現起來比較複雜，於是就有了一種簡單實現2-3樹的數據結構，即紅黑樹（Red-Black Tree）。

基本思想：紅黑樹的思想就是對2-3查找樹進行編碼，尤其是對2-3查找樹中的3-nodes節點添加額外的信息。紅黑樹中將節點之間的連結分為兩種不同類型，紅色連結，他用來連結兩個2-nodes節點來表示一個3-nodes節點。黑色連結用來連結普通的2-3節點。特別的，使用紅色連結的兩個2-nodes來表示一個3-nodes節點，並且向左傾斜，即一個2-node是另一個2-node的左子節點。這種做法的好處是查找的時候不用做任何修改，和普通的二叉查找樹相同。

紅黑樹的定義：

紅黑樹是一種具有紅色和黑色連結的平衡查找樹，同時滿足：

·紅色節點向左傾斜

·一個節點不可能有兩個紅色連結

·整個樹完全黑色平衡，即從根節點到所以葉子結點的路徑上，黑色連結的個數都相同。

B樹和B+樹（B Tree/B+Tree）

平衡查找樹中的2-3樹以及其實現紅黑樹。2-3樹種，一個節點最多有2個key，而紅黑樹則使用染色的方式來標識這兩個key。

數據結構對B樹的定義為“在計算機科學中，B樹（B-tree）是一種樹狀數據結構，它能夠存儲數據、對其進行排序並允許以O(log n)的時間複雜度運行進行查找、順序讀取、插入和刪除的數據結構。B樹，概括來說是一個節點可以擁有多於2個子節點的二叉查找樹。與自平衡二叉查找樹不同，B樹為系統最最佳化大塊數據的讀和寫操作。B-tree算法減少定位記錄時所經歷的中間過程，從而加快存取速度。普遍運用在資料庫和檔案系統。

B樹定義：

B樹可以看作是對2-3查找樹的一種擴展，即他允許每個節點有M-1個子節點。

·根節點至少有兩個子節點

·每個節點有M-1個key，並且以升序排列

·位於M-1和M key的子節點的值位於M-1 和M key對應的Value之間

·其它節點至少有M/2個子節點

B+樹定義：

B+樹是對B樹的一種變形樹，它與B樹的差異在於：

• 有k個子結點的結點必然有k個關鍵碼；
  
• 非葉結點僅具有索引作用，跟記錄有關的信息均存放在葉結點中。
  
• 樹的所有葉結點構成一個有序鍊表，可以按照關鍵碼排序的次序遍歷全部記錄。
  

分塊查找

分塊查找又稱索引順序查找，它是順序查找的一種改進方法。
算法思想：將n個數據元素"按塊有序"劃分為m塊（m ≤ n）。每一塊中的結點不必有序，但塊與塊之間必須"按塊有序"；即第1塊中任一元素的關鍵字都必須小於第2塊中任一元素的關鍵字；而第2塊中任一元素又都必須小於第3塊中的任一元素，……
算法流程：
step1 先選取各塊中的最大關鍵字構成一個索引表；
step2 查找分兩個部分：先對索引表進行二分查找或順序查找，以確定待查記錄在哪一塊中；然後，在已確定的塊中用順序法進行查找。

散列查找

哈希函式的規則是：通過某種轉換關係，使關鍵字適度的分散到指定大小的的順序結構中，越分散，則以後查找的時間複雜度越小，空間複雜度越高。

算法流程：

1）用給定的哈希函式構造哈希表；

2）根據選擇的衝突處理方法解決地址衝突；

常見的解決衝突的方法：拉鏈法和線性探測法。

3）在哈希表的基礎上執行哈希查找。

哈希表是一個在時間和空間上做出權衡的經典例子。如果沒有記憶體限制，那么可以直接將鍵作為數組的索引。那么所有的查找時間複雜度為O(1)；如果沒有時間限制，那么我們可以使用無序數組並進行順序查找，這樣只需要很少的記憶體。哈希表使用了適度的時間和空間來在這兩個極端之間找到了平衡。只需要調整哈希函式算法即可在時間和空間上做出取捨。

在外部查找中，查找的數據規模一般很大，為了提高查找效率與速度，一般採用散列查找，分塊查找，B/B+樹查找。