數據查找

根據查詢要求從一個計算機檔案或資料庫中提取所需要的數據的技術，這是數據處理的基本技術之一。如果要查找的數據全部放在計算機記憶體儲器中，這種查找即稱為內查找；若要查找的數據不在記憶體而在外存儲器中，這種查找便稱為外查找。數據一般按照數據項、記錄、檔案三級組織在一定的結構之中。用於組織檔案的基本數據項稱為關鍵字。所謂從檔案中查找數據是指根據給定的關鍵字值在檔案中找出包含該關鍵字值的記錄。對於不同的檔案結構和查詢要求，需要用不同的查找技術。

順序檔案數據查找 對於順序檔案，常用的查找方法有線性查找、對分查找、跳步查找和機率查找。

基本介紹

• 中文名：數據查找
• 外文名：data search
• 領域：計算機技術
• 主要方法：線性查、找對分查找、跳步查找

英語譯文

data search

常見數據查找方法

線性查找

把給定的關鍵字值與檔案中的記錄逐個進行比較，直至找到與之匹配的記錄為止。若檔案中記錄數為N，則查找一個記錄平均比較次數為(N+1)/2。此法簡單，但效率較低。

對分查找

此法要求被查找的檔案中記錄是按關鍵字值大小順序排列的。將檔案一分為二，把給定關鍵字值與中點的記錄比較，若匹配，則查找成功；否則判斷所要查找的記錄可能在上半部分，還是在下半部分。然後，對確定的部分繼續上述過程，直至找到要求的記錄，查找成功；或最後只剩下一個記錄仍不能匹配，查找失敗。若檔案中記錄數為N,則查到一個記錄的最多比較次數為log2N。

跳步查找

先用大步跳過一部分記錄，再用較小的步長或順序查找方法在較小的範圍內找到要查找的記錄。

機率查找

將給定的關鍵字值按某種公式或算法估算出要查記錄的近似位置，然後再用線性查找法確定其準確位置。

隨機檔案數據查找

對於隨機檔案，如果是計算定址結構的檔案可以採用直接查找的方法，即利用關鍵字值和記錄位置之間的對應關係直接找到該記錄。如果是索引結構的檔案，先用上述方法查找索引，在索引中找到相應關鍵字值後，再由索引表上對應的地址找到相應的記錄。不同查找方法的效率很不相同，這主要取決於檔案結構和查詢問題的特點，查詢算法本身也是重要影響因素。