計(jì)算機(jī)操作系統(tǒng)教程_第四版_(張堯?qū)W著)_清華大學(xué)出版社_第8章

1、第第7章章 文件系統(tǒng)文件系統(tǒng)7.1 文件系統(tǒng)的概念文件系統(tǒng)的概念7.2 文件的邏輯結(jié)構(gòu)與存取方法文件的邏輯結(jié)構(gòu)與存取方法7.3 文件的物理結(jié)構(gòu)與存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)與存儲(chǔ)設(shè)備7.4 文件存儲(chǔ)空間管理文件存儲(chǔ)空間管理7.5 文件目錄管理文件目錄管理7.6 文件存取控制文件存取控制7.7 文件的使用文件的使用7.8 文件系統(tǒng)的層次模型文件系統(tǒng)的層次模型本章小結(jié)本章小結(jié)習(xí)題習(xí)題對(duì)大多數(shù)用戶來(lái)說(shuō)，文件系統(tǒng)是操作系統(tǒng)中最直接對(duì)大多數(shù)用戶來(lái)說(shuō)，文件系統(tǒng)是操作系統(tǒng)中最直接可見(jiàn)的部分。計(jì)算機(jī)的重要作用之一就是能快速處可見(jiàn)的部分。計(jì)算機(jī)的重要作用之一就是能快速處理大量信息理大量信息,從而從而,信息的組織、存取

2、和保管就成為信息的組織、存取和保管就成為一個(gè)極為重要的內(nèi)容。文件系統(tǒng)是計(jì)算機(jī)組織、存一個(gè)極為重要的內(nèi)容。文件系統(tǒng)是計(jì)算機(jī)組織、存取和保存信息的重要手段。本章主要討論文件的組取和保存信息的重要手段。本章主要討論文件的組織結(jié)構(gòu)、存取結(jié)構(gòu)、保護(hù)以及文件系統(tǒng)空間管理等織結(jié)構(gòu)、存取結(jié)構(gòu)、保護(hù)以及文件系統(tǒng)空間管理等問(wèn)題。問(wèn)題。7.1 文件系統(tǒng)的概念文件系統(tǒng)的概念1. 文件系統(tǒng)的引入文件系統(tǒng)的引入操作系統(tǒng)對(duì)計(jì)算機(jī)的管理包括兩個(gè)方面：硬件資源操作系統(tǒng)對(duì)計(jì)算機(jī)的管理包括兩個(gè)方面：硬件資源的管理和軟件資源的管理。硬件資源的管理包括的管理和軟件資源的管理。硬件資源的管理包括CPU 的管理、存儲(chǔ)器的管理、設(shè)備管理等，

3、主要的管理、存儲(chǔ)器的管理、設(shè)備管理等，主要解決硬件資源的有效和合理利用問(wèn)題。軟件資源的解決硬件資源的有效和合理利用問(wèn)題。軟件資源的管理則包括對(duì)各種系統(tǒng)程序（包括操作系統(tǒng)本身的管理則包括對(duì)各種系統(tǒng)程序（包括操作系統(tǒng)本身的程序）、系統(tǒng)應(yīng)用程序或工具（例如編輯程序、編程序）、系統(tǒng)應(yīng)用程序或工具（例如編輯程序、編譯程序等）、庫(kù)函數(shù)及各種用戶程序和數(shù)據(jù)的管理。譯程序等）、庫(kù)函數(shù)及各種用戶程序和數(shù)據(jù)的管理。圖圖7.1給出了資源管理的分類圖。給出了資源管理的分類圖。圖圖7.1 操作系統(tǒng)的軟硬件管理操作系統(tǒng)的軟硬件管理顯然，用戶使用計(jì)算機(jī)來(lái)完成自己的某件任務(wù)時(shí)，顯然，用戶使用計(jì)算機(jī)來(lái)完成自己的某件任務(wù)時(shí)，要碰

4、到下列問(wèn)題：要碰到下列問(wèn)題：(1) 使用現(xiàn)有的軟件資源來(lái)協(xié)助完成自己的任務(wù)。使用現(xiàn)有的軟件資源來(lái)協(xié)助完成自己的任務(wù)。 例例如，如， 編輯、編輯、 編譯及鏈接程序來(lái)生成目標(biāo)代碼；編譯及鏈接程序來(lái)生成目標(biāo)代碼； 利利用系統(tǒng)調(diào)用庫(kù)函數(shù)與實(shí)用程序來(lái)減少編程工作用系統(tǒng)調(diào)用庫(kù)函數(shù)與實(shí)用程序來(lái)減少編程工作, 避避開(kāi)與硬件有關(guān)的部分等。開(kāi)與硬件有關(guān)的部分等。(2) 編制完成的或未完成的程序存放在什么地方編制完成的或未完成的程序存放在什么地方,需要需要訪問(wèn)的數(shù)據(jù)存放在什么地方，從而使得人們可以再訪問(wèn)的數(shù)據(jù)存放在什么地方，從而使得人們可以再利用已有的軟件資源。利用已有的軟件資源。事實(shí)上，這兩個(gè)問(wèn)題是一個(gè)怎樣對(duì)軟件

5、資源（程序事實(shí)上，這兩個(gè)問(wèn)題是一個(gè)怎樣對(duì)軟件資源（程序和數(shù)據(jù)）進(jìn)行透明存放，并能令這些程序和數(shù)據(jù)做和數(shù)據(jù)）進(jìn)行透明存放，并能令這些程序和數(shù)據(jù)做到召之即來(lái)的問(wèn)題。在早期的計(jì)算機(jī)系統(tǒng)中，由于到召之即來(lái)的問(wèn)題。在早期的計(jì)算機(jī)系統(tǒng)中，由于硬件資源的限制，只能用卡片或紙帶來(lái)存放程序或硬件資源的限制，只能用卡片或紙帶來(lái)存放程序或數(shù)據(jù)。這些卡片和紙帶都分別編號(hào)存放，當(dāng)用戶需數(shù)據(jù)。這些卡片和紙帶都分別編號(hào)存放，當(dāng)用戶需要使用它們時(shí)，再把這些卡片和紙帶放在讀卡機(jī)上要使用它們時(shí)，再把這些卡片和紙帶放在讀卡機(jī)上輸入計(jì)算機(jī)。輸入計(jì)算機(jī)。顯然，這些人工干預(yù)的控制和保存軟件資源的方法顯然，這些人工干預(yù)的控制和保存軟件資源

6、的方法不可能做到透明存取，極大地限制了計(jì)算機(jī)的處理不可能做到透明存取，極大地限制了計(jì)算機(jī)的處理能力和能力和 CPU等計(jì)算機(jī)硬件的利用率。等計(jì)算機(jī)硬件的利用率。大容量直接存取的磁盤存儲(chǔ)器以及順序存取的磁帶大容量直接存取的磁盤存儲(chǔ)器以及順序存取的磁帶存儲(chǔ)器等的出現(xiàn)，為程序和數(shù)據(jù)等軟件資源的透明存儲(chǔ)器等的出現(xiàn)，為程序和數(shù)據(jù)等軟件資源的透明存取提供了物質(zhì)基礎(chǔ)。這導(dǎo)致了對(duì)軟件資源管理質(zhì)存取提供了物質(zhì)基礎(chǔ)。這導(dǎo)致了對(duì)軟件資源管理質(zhì)的飛躍的飛躍文件系統(tǒng)的出現(xiàn)。文件系統(tǒng)把相應(yīng)的程文件系統(tǒng)的出現(xiàn)。文件系統(tǒng)把相應(yīng)的程序和數(shù)據(jù)看作文件，并把它們存放在磁盤或磁帶等序和數(shù)據(jù)看作文件，并把它們存放在磁盤或磁帶等大容量存儲(chǔ)

7、介質(zhì)上，從而做到對(duì)程序和數(shù)據(jù)的透明大容量存儲(chǔ)介質(zhì)上，從而做到對(duì)程序和數(shù)據(jù)的透明存取。這里，透明存取是指不必了解文件存放的物存取。這里，透明存取是指不必了解文件存放的物理結(jié)構(gòu)和查找方法等與存取介質(zhì)有關(guān)的部分，只需理結(jié)構(gòu)和查找方法等與存取介質(zhì)有關(guān)的部分，只需給定一個(gè)代表某段程序或數(shù)據(jù)的文件名，文件系統(tǒng)給定一個(gè)代表某段程序或數(shù)據(jù)的文件名，文件系統(tǒng)就會(huì)自動(dòng)地完成對(duì)與給定文件名相對(duì)應(yīng)文件的有關(guān)就會(huì)自動(dòng)地完成對(duì)與給定文件名相對(duì)應(yīng)文件的有關(guān)操作。操作。文件系統(tǒng)必須完成下列工作：文件系統(tǒng)必須完成下列工作：(1) 為了合理的存放文件，必需對(duì)磁盤等輔助存儲(chǔ)器為了合理的存放文件，必需對(duì)磁盤等輔助存儲(chǔ)器空間空間 (或

8、稱文件空間或稱文件空間) 進(jìn)行統(tǒng)一管理。在用戶創(chuàng)建進(jìn)行統(tǒng)一管理。在用戶創(chuàng)建新文件時(shí)為其分配空閑區(qū)，而在用戶刪除或修改某新文件時(shí)為其分配空閑區(qū)，而在用戶刪除或修改某個(gè)文件時(shí)個(gè)文件時(shí),回收和調(diào)整存儲(chǔ)區(qū)。回收和調(diào)整存儲(chǔ)區(qū)。(2) 為了實(shí)現(xiàn)按名存取，需要有一個(gè)用戶可見(jiàn)的文件為了實(shí)現(xiàn)按名存取，需要有一個(gè)用戶可見(jiàn)的文件邏輯結(jié)構(gòu)，用戶按照文件邏輯結(jié)構(gòu)所給定的方式進(jìn)邏輯結(jié)構(gòu)，用戶按照文件邏輯結(jié)構(gòu)所給定的方式進(jìn)行信息的存取和加工。這種邏輯結(jié)構(gòu)是獨(dú)立于物理行信息的存取和加工。這種邏輯結(jié)構(gòu)是獨(dú)立于物理存儲(chǔ)設(shè)備的。存儲(chǔ)設(shè)備的。(3) 為了便于存放和加工信息，文件在存儲(chǔ)設(shè)備上應(yīng)為了便于存放和加工信息，文件在存儲(chǔ)設(shè)備上應(yīng)

9、按一定的順序存放。這種存放方式被稱為文件的物按一定的順序存放。這種存放方式被稱為文件的物理結(jié)構(gòu)。理結(jié)構(gòu)。(4) 完成對(duì)存放在存儲(chǔ)設(shè)備上的文件信息的查找。完成對(duì)存放在存儲(chǔ)設(shè)備上的文件信息的查找。(5) 完成文件的共享和提供保護(hù)功能。完成文件的共享和提供保護(hù)功能。2. 文件與文件系統(tǒng)的概念文件與文件系統(tǒng)的概念(1) 文件文件 上面已說(shuō)過(guò)，文件是一段程序或數(shù)據(jù)的集合。這是上面已說(shuō)過(guò)，文件是一段程序或數(shù)據(jù)的集合。這是一種較為模糊的說(shuō)法。在計(jì)算機(jī)系統(tǒng)中，文件被解一種較為模糊的說(shuō)法。在計(jì)算機(jī)系統(tǒng)中，文件被解釋為一組賦名的相關(guān)聯(lián)字符流的集合，或者是相關(guān)釋為一組賦名的相關(guān)聯(lián)字符流的集合，或者是相關(guān)聯(lián)記錄聯(lián)記錄

10、( 一個(gè)有意義的信息單位一個(gè)有意義的信息單位 )的集合。的集合。文件的兩種解釋定義了兩種文件形式。賦名的字符文件的兩種解釋定義了兩種文件形式。賦名的字符流文件是一種無(wú)結(jié)構(gòu)文件或流式文件。目前常用的流文件是一種無(wú)結(jié)構(gòu)文件或流式文件。目前常用的操作系統(tǒng)，例如操作系統(tǒng)，例如 UNIX 操作系統(tǒng)，操作系統(tǒng)，MS-DOS等均采等均采用無(wú)結(jié)構(gòu)文件形式。無(wú)結(jié)構(gòu)文件由于采用字符流方用無(wú)結(jié)構(gòu)文件形式。無(wú)結(jié)構(gòu)文件由于采用字符流方式，與源程序、目標(biāo)代碼等在形式上是一致的，因式，與源程序、目標(biāo)代碼等在形式上是一致的，因此，該方式適用于源程序、目標(biāo)代碼等文件。由相此，該方式適用于源程序、目標(biāo)代碼等文件。由相關(guān)聯(lián)記錄組成

11、的文件中的有些基本信息單位是記錄。關(guān)聯(lián)記錄組成的文件中的有些基本信息單位是記錄。記錄是由記錄是由 N (N 1) 個(gè)字節(jié)組成的具有特定意義的個(gè)字節(jié)組成的具有特定意義的信息單位。記錄式文件主要用于信息管理。信息單位。記錄式文件主要用于信息管理。在有些操作系統(tǒng)中，從字符流文件的角度出發(fā)，設(shè)在有些操作系統(tǒng)中，從字符流文件的角度出發(fā)，設(shè)備也被看作是賦予特殊文件名的文件。從而，系統(tǒng)備也被看作是賦予特殊文件名的文件。從而，系統(tǒng)可以對(duì)設(shè)備和文件實(shí)施統(tǒng)一管理，以致大大簡(jiǎn)化設(shè)可以對(duì)設(shè)備和文件實(shí)施統(tǒng)一管理，以致大大簡(jiǎn)化設(shè)備管理程序和文件系統(tǒng)的接口設(shè)計(jì)。備管理程序和文件系統(tǒng)的接口設(shè)計(jì)。用戶文件名由用戶給定，它是一個(gè)

12、字母數(shù)字串，有用戶文件名由用戶給定，它是一個(gè)字母數(shù)字串，有些系統(tǒng)規(guī)定必須是英文字母打頭且允許一些其他的些系統(tǒng)規(guī)定必須是英文字母打頭且允許一些其他的符號(hào)出現(xiàn)在文件名的非打頭部分。例如符號(hào)出現(xiàn)在文件名的非打頭部分。例如a.out，ccdos.exe均為合法文件名。均為合法文件名。(2) 文件系統(tǒng)文件系統(tǒng) 操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)稱為文件操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)稱為文件系統(tǒng)。它負(fù)責(zé)為用戶建立文件，撤消、讀寫、修改系統(tǒng)。它負(fù)責(zé)為用戶建立文件，撤消、讀寫、修改和復(fù)制文件，還負(fù)責(zé)完成對(duì)文件的按名存取和進(jìn)行和復(fù)制文件，還負(fù)責(zé)完成對(duì)文件的按名存取和進(jìn)行存取控制。存取控制。文件系統(tǒng)具有以

13、下特點(diǎn)：文件系統(tǒng)具有以下特點(diǎn)： 友好的用戶接口，用戶只對(duì)文件進(jìn)行操作，而不友好的用戶接口，用戶只對(duì)文件進(jìn)行操作，而不管文件結(jié)構(gòu)和存放的物理位置。管文件結(jié)構(gòu)和存放的物理位置。 對(duì)文件按名存取，對(duì)用戶透明。對(duì)文件按名存取，對(duì)用戶透明。 某些文件可以被多個(gè)用戶或進(jìn)程所共享。某些文件可以被多個(gè)用戶或進(jìn)程所共享。 文件系統(tǒng)大都使用磁盤、磁帶和光盤等大容量存文件系統(tǒng)大都使用磁盤、磁帶和光盤等大容量存儲(chǔ)器作為存儲(chǔ)介質(zhì)，因此，可存儲(chǔ)大量信息。儲(chǔ)器作為存儲(chǔ)介質(zhì)，因此，可存儲(chǔ)大量信息。3. 文件的分類文件的分類在文件系統(tǒng)中，為了有效、方便地管理文件，常常在文件系統(tǒng)中，為了有效、方便地管理文件，常常把文件按其性質(zhì)和

14、用途等進(jìn)行分類。把文件按其性質(zhì)和用途等進(jìn)行分類。按文件的性質(zhì)和用途可以分為三類：按文件的性質(zhì)和用途可以分為三類：(1) 系統(tǒng)文件系統(tǒng)文件該類文件只允許用戶通過(guò)系統(tǒng)調(diào)用來(lái)執(zhí)行它們，而該類文件只允許用戶通過(guò)系統(tǒng)調(diào)用來(lái)執(zhí)行它們，而不允許對(duì)其進(jìn)行讀寫和修改。不允許對(duì)其進(jìn)行讀寫和修改。 這些文件主要由操這些文件主要由操作系統(tǒng)核心和各種系統(tǒng)應(yīng)用程序和數(shù)據(jù)所組成。作系統(tǒng)核心和各種系統(tǒng)應(yīng)用程序和數(shù)據(jù)所組成。(2) 庫(kù)文件庫(kù)文件該類文件允許用戶對(duì)其進(jìn)行讀取、執(zhí)行，該類文件允許用戶對(duì)其進(jìn)行讀取、執(zhí)行， 但不允許但不允許對(duì)其進(jìn)行修改。庫(kù)文件主要由各種標(biāo)準(zhǔn)子程序庫(kù)組對(duì)其進(jìn)行修改。庫(kù)文件主要由各種標(biāo)準(zhǔn)子程序庫(kù)組成。如成

15、。如 C 語(yǔ)言子程序庫(kù)、語(yǔ)言子程序庫(kù)、FORTRAN子程序庫(kù)等。子程序庫(kù)等。 (3) 用戶文件用戶文件用戶文件是用戶委托文件系統(tǒng)保存的文件。這類文用戶文件是用戶委托文件系統(tǒng)保存的文件。這類文件只由文件的所有者或所有者授權(quán)的用戶才能使用。件只由文件的所有者或所有者授權(quán)的用戶才能使用。用戶文件主要由源程序、目標(biāo)程序、用戶數(shù)據(jù)庫(kù)等用戶文件主要由源程序、目標(biāo)程序、用戶數(shù)據(jù)庫(kù)等組成。組成。另外，按組織形式，文件又可被畫(huà)分為以下三類：另外，按組織形式，文件又可被畫(huà)分為以下三類：(1) 普通文件普通文件普通文件既包括系統(tǒng)文件，也包括用戶文件和庫(kù)函普通文件既包括系統(tǒng)文件，也包括用戶文件和庫(kù)函數(shù)文件、實(shí)用程序文

16、件。普通文件主要是指組織格數(shù)文件、實(shí)用程序文件。普通文件主要是指組織格式為系統(tǒng)中所規(guī)定的最一般格式的文件，例如由字式為系統(tǒng)中所規(guī)定的最一般格式的文件，例如由字符流組成的文件。符流組成的文件。(2) 目錄文件目錄文件目錄文件是由文件的目錄信息構(gòu)成的特殊文件。即目錄文件是由文件的目錄信息構(gòu)成的特殊文件。即該文件的內(nèi)容不是各種程序或應(yīng)用數(shù)據(jù)，而是用來(lái)該文件的內(nèi)容不是各種程序或應(yīng)用數(shù)據(jù)，而是用來(lái)檢索普通文件的目錄信息。檢索普通文件的目錄信息。(3) 特殊文件特殊文件在在 UNIX 系統(tǒng)中，所有的輸入、輸出設(shè)備都被看作系統(tǒng)中，所有的輸入、輸出設(shè)備都被看作特殊文件。這組特殊文件在使用形式上與普通文件特殊文

17、件。這組特殊文件在使用形式上與普通文件相同，如查找目錄、存取操作等。相同，如查找目錄、存取操作等。除了按文件的用途和組織形式來(lái)分類外，還可以按除了按文件的用途和組織形式來(lái)分類外，還可以按文件中的信息流向或文件的保護(hù)級(jí)別等分類。例如，文件中的信息流向或文件的保護(hù)級(jí)別等分類。例如，按信息流向可把文件分為：輸入文件、輸出文件、按信息流向可把文件分為：輸入文件、輸出文件、以及輸入以及輸入/ 輸出文件等。按文件的保護(hù)級(jí)別又可分輸出文件等。按文件的保護(hù)級(jí)別又可分為：只讀文件、讀寫文件、可執(zhí)行文件和不保護(hù)文為：只讀文件、讀寫文件、可執(zhí)行文件和不保護(hù)文件等。件等。文件的分類主要是便于系統(tǒng)對(duì)不同的文件進(jìn)行不同文

18、件的分類主要是便于系統(tǒng)對(duì)不同的文件進(jìn)行不同的管理，從而提高處理速度和起到保護(hù)與共享的作的管理，從而提高處理速度和起到保護(hù)與共享的作用。例如，一個(gè)系統(tǒng)文件在讀入內(nèi)存時(shí)將被放在內(nèi)用。例如，一個(gè)系統(tǒng)文件在讀入內(nèi)存時(shí)將被放在內(nèi)存的某一固定區(qū)且享受高的保護(hù)級(jí)別，從而不必像存的某一固定區(qū)且享受高的保護(hù)級(jí)別，從而不必像一般的用戶文件那樣只有在內(nèi)存用戶可用區(qū)分得相一般的用戶文件那樣只有在內(nèi)存用戶可用區(qū)分得相應(yīng)的空閑區(qū)之后才能被調(diào)入內(nèi)存。應(yīng)的空閑區(qū)之后才能被調(diào)入內(nèi)存。7.2 文件的邏輯結(jié)構(gòu)與存取方法文件的邏輯結(jié)構(gòu)與存取方法7.2.1 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是用戶可見(jiàn)結(jié)構(gòu)。文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是用

19、戶可見(jiàn)結(jié)構(gòu)。文件的邏輯結(jié)構(gòu)可分為兩大類：字符流式的無(wú)結(jié)構(gòu)文件和記錄式的可分為兩大類：字符流式的無(wú)結(jié)構(gòu)文件和記錄式的有結(jié)構(gòu)文件。在文件系統(tǒng)設(shè)計(jì)時(shí)，選擇何種邏輯結(jié)有結(jié)構(gòu)文件。在文件系統(tǒng)設(shè)計(jì)時(shí)，選擇何種邏輯結(jié)構(gòu)才能更有利于用戶對(duì)文件信息的操作呢？一般情構(gòu)才能更有利于用戶對(duì)文件信息的操作呢？一般情況下，選取文件的邏輯結(jié)構(gòu)應(yīng)遵循下述原則：況下，選取文件的邏輯結(jié)構(gòu)應(yīng)遵循下述原則：(1) 當(dāng)用戶對(duì)文件信息進(jìn)行修改操作時(shí)，給定的邏輯當(dāng)用戶對(duì)文件信息進(jìn)行修改操作時(shí)，給定的邏輯結(jié)構(gòu)應(yīng)能盡量減少對(duì)已存儲(chǔ)好的文件信息的變動(dòng)。結(jié)構(gòu)應(yīng)能盡量減少對(duì)已存儲(chǔ)好的文件信息的變動(dòng)。(2) 當(dāng)用戶需要對(duì)文件信息進(jìn)行操作時(shí)，給定的邏輯

20、當(dāng)用戶需要對(duì)文件信息進(jìn)行操作時(shí)，給定的邏輯結(jié)構(gòu)應(yīng)使文件系統(tǒng)在盡可能短的時(shí)間內(nèi)查找到需要結(jié)構(gòu)應(yīng)使文件系統(tǒng)在盡可能短的時(shí)間內(nèi)查找到需要查找的記錄或基本信息單位。查找的記錄或基本信息單位。(3) 應(yīng)使文件信息占據(jù)最小的存儲(chǔ)空間。應(yīng)使文件信息占據(jù)最小的存儲(chǔ)空間。(4) 應(yīng)是便于用戶進(jìn)行操作的。應(yīng)是便于用戶進(jìn)行操作的。顯然，對(duì)于字符流的無(wú)結(jié)構(gòu)文件來(lái)說(shuō)，查找文件中顯然，對(duì)于字符流的無(wú)結(jié)構(gòu)文件來(lái)說(shuō)，查找文件中的基本信息單位，例如某個(gè)單詞，是比較困難的。的基本信息單位，例如某個(gè)單詞，是比較困難的。但反過(guò)來(lái)，字符流的無(wú)結(jié)構(gòu)文件管理簡(jiǎn)單，用戶可但反過(guò)來(lái)，字符流的無(wú)結(jié)構(gòu)文件管理簡(jiǎn)單，用戶可以方便地對(duì)其進(jìn)行操作。所以

21、，那些對(duì)基本信息單以方便地對(duì)其進(jìn)行操作。所以，那些對(duì)基本信息單位操作不多的文件較適于采用字符流的無(wú)結(jié)構(gòu)方式，位操作不多的文件較適于采用字符流的無(wú)結(jié)構(gòu)方式，例如，源程序文件、目標(biāo)代碼文件等。例如，源程序文件、目標(biāo)代碼文件等。除了字符流的無(wú)結(jié)構(gòu)方式外，記錄式的有結(jié)構(gòu)文件除了字符流的無(wú)結(jié)構(gòu)方式外，記錄式的有結(jié)構(gòu)文件可把文件中的記錄按各種不同的方式排列，構(gòu)成不可把文件中的記錄按各種不同的方式排列，構(gòu)成不同的邏輯結(jié)構(gòu)，以便用戶對(duì)文件中的記錄進(jìn)行修改、同的邏輯結(jié)構(gòu)，以便用戶對(duì)文件中的記錄進(jìn)行修改、追加、查找和管理等操作。追加、查找和管理等操作。記錄是一個(gè)具有特定意義的信息單位，它由該記錄記錄是一個(gè)具有特定

22、意義的信息單位，它由該記錄在文件中的邏輯地址在文件中的邏輯地址(相對(duì)位置相對(duì)位置) 與記錄名所對(duì)應(yīng)的與記錄名所對(duì)應(yīng)的一組鍵、屬性及其屬性值所組成。圖一組鍵、屬性及其屬性值所組成。圖7.2是一個(gè)記是一個(gè)記錄的組成例。錄的組成例。圖圖7.2 記錄組成例記錄組成例圖中，圖中，1296是名為是名為R 的記錄在文件中的邏輯地址，的記錄在文件中的邏輯地址，姓名姓名 : A 是該記錄的鍵，而是該記錄的鍵，而 性別性別，出生出生年月年月，工資工資 等是該記錄的屬性，緊跟在這等是該記錄的屬性，緊跟在這些后面的是屬性值。一個(gè)記錄可以有多個(gè)鍵名，每些后面的是屬性值。一個(gè)記錄可以有多個(gè)鍵名，每個(gè)鍵名可對(duì)應(yīng)于多項(xiàng)屬性。

23、再者，根據(jù)各系統(tǒng)設(shè)計(jì)個(gè)鍵名可對(duì)應(yīng)于多項(xiàng)屬性。再者，根據(jù)各系統(tǒng)設(shè)計(jì)的要求不一樣，記錄既可以是定長(zhǎng)的，也可以是變的要求不一樣，記錄既可以是定長(zhǎng)的，也可以是變長(zhǎng)的。記錄的長(zhǎng)度可以短到一個(gè)字符，也可以長(zhǎng)到長(zhǎng)的。記錄的長(zhǎng)度可以短到一個(gè)字符，也可以長(zhǎng)到一個(gè)文件，這要由系統(tǒng)設(shè)計(jì)人員確定。一個(gè)文件，這要由系統(tǒng)設(shè)計(jì)人員確定。常用的記錄式結(jié)構(gòu)文件有以下幾種常用的記錄式結(jié)構(gòu)文件有以下幾種:(1) 連續(xù)結(jié)構(gòu)；連續(xù)結(jié)構(gòu)； (2) 多重結(jié)構(gòu)；多重結(jié)構(gòu)； (3) 轉(zhuǎn)置結(jié)構(gòu)；轉(zhuǎn)置結(jié)構(gòu)； (4) 順順序結(jié)構(gòu)。序結(jié)構(gòu)。下面分別介紹這幾種結(jié)構(gòu)。下面分別介紹這幾種結(jié)構(gòu)。(1) 連續(xù)結(jié)構(gòu)連續(xù)結(jié)構(gòu)連續(xù)結(jié)構(gòu)是一種把記錄按生成的先后順序連續(xù)

24、排列連續(xù)結(jié)構(gòu)是一種把記錄按生成的先后順序連續(xù)排列的邏輯結(jié)構(gòu)。連續(xù)結(jié)構(gòu)的特點(diǎn)是適用性強(qiáng)，可用于的邏輯結(jié)構(gòu)。連續(xù)結(jié)構(gòu)的特點(diǎn)是適用性強(qiáng)，可用于所有文件所有文件 ，且記錄的排列順序與記錄的內(nèi)容無(wú)關(guān)。，且記錄的排列順序與記錄的內(nèi)容無(wú)關(guān)。這有利于記錄的追加與變更。但是，連續(xù)結(jié)構(gòu)文件這有利于記錄的追加與變更。但是，連續(xù)結(jié)構(gòu)文件的搜索性能較差，例如要找出某個(gè)指定鍵的記錄時(shí)，的搜索性能較差，例如要找出某個(gè)指定鍵的記錄時(shí)，系統(tǒng)必須對(duì)文件全體進(jìn)行搜索。系統(tǒng)必須對(duì)文件全體進(jìn)行搜索。(2) 多重結(jié)構(gòu)多重結(jié)構(gòu) 如果把記錄按鍵和記錄名排列成行列式結(jié)構(gòu)，則一如果把記錄按鍵和記錄名排列成行列式結(jié)構(gòu)，則一個(gè)包含個(gè)包含n個(gè)記錄名、

25、個(gè)記錄名、m個(gè)個(gè)(mn)個(gè)鍵的文件構(gòu)成一個(gè)鍵的文件構(gòu)成一m*n維行列式維行列式(如圖如圖7.3)。其中，如果第。其中，如果第i(1im) 行行和第和第j(1jn) 列所對(duì)應(yīng)的位置上為列所對(duì)應(yīng)的位置上為1，則表示鍵，則表示鍵Ki在記錄在記錄 R中中; 反之反之,則表示鍵則表示鍵Ki不在記錄不在記錄 Rj 中。另中。另外，同一個(gè)鍵也可以同時(shí)屬于不同記錄。外，同一個(gè)鍵也可以同時(shí)屬于不同記錄。圖圖7.3 文件的記錄名和鍵構(gòu)成的行列式文件的記錄名和鍵構(gòu)成的行列式顯然，如果只按行列式結(jié)構(gòu)來(lái)排列記錄，將會(huì)浪費(fèi)顯然，如果只按行列式結(jié)構(gòu)來(lái)排列記錄，將會(huì)浪費(fèi)較多的存儲(chǔ)空間。從而，我們把行列式中那些為零較多的存儲(chǔ)空

26、間。從而，我們把行列式中那些為零的項(xiàng)去掉，并以鍵的項(xiàng)去掉，并以鍵Ki為隊(duì)首，以包含鍵為隊(duì)首，以包含鍵Ki的記錄為的記錄為隊(duì)列元素來(lái)構(gòu)成一個(gè)記錄隊(duì)列。對(duì)于一個(gè)有隊(duì)列元素來(lái)構(gòu)成一個(gè)記錄隊(duì)列。對(duì)于一個(gè)有m個(gè)鍵個(gè)鍵的隊(duì)列來(lái)說(shuō)，這樣的隊(duì)列有的隊(duì)列來(lái)說(shuō)，這樣的隊(duì)列有m個(gè)。這個(gè)。這m個(gè)隊(duì)列構(gòu)成個(gè)隊(duì)列構(gòu)成了該文件的多重結(jié)構(gòu)了該文件的多重結(jié)構(gòu)(multi_list)。如圖。如圖7.4所示。所示。(3) 轉(zhuǎn)置結(jié)構(gòu)轉(zhuǎn)置結(jié)構(gòu) 在圖在圖7.4的多重結(jié)構(gòu)中，每個(gè)隊(duì)列中和鍵直接相連的的多重結(jié)構(gòu)中，每個(gè)隊(duì)列中和鍵直接相連的只有一個(gè)記錄。這種結(jié)構(gòu)雖然在探索時(shí)要優(yōu)于連續(xù)只有一個(gè)記錄。這種結(jié)構(gòu)雖然在探索時(shí)要優(yōu)于連續(xù)結(jié)構(gòu)，但在探索某

27、一特定記錄時(shí)，必須在找到該記結(jié)構(gòu)，但在探索某一特定記錄時(shí)，必須在找到該記錄所對(duì)應(yīng)的鍵之后，再在該鍵所對(duì)應(yīng)的隊(duì)列中順序錄所對(duì)應(yīng)的鍵之后，再在該鍵所對(duì)應(yīng)的隊(duì)列中順序查找。與此相反，轉(zhuǎn)置結(jié)構(gòu)把含有相同鍵的記錄指查找。與此相反，轉(zhuǎn)置結(jié)構(gòu)把含有相同鍵的記錄指針全部指向該鍵，也就是說(shuō)，把所有與同一鍵對(duì)應(yīng)針全部指向該鍵，也就是說(shuō)，把所有與同一鍵對(duì)應(yīng)的記錄的指針連續(xù)地置于目錄中該鍵的位置下的記錄的指針連續(xù)地置于目錄中該鍵的位置下(圖圖7.5)。轉(zhuǎn)置結(jié)構(gòu)最適合于給定鍵后的記錄搜索。轉(zhuǎn)置結(jié)構(gòu)最適合于給定鍵后的記錄搜索。圖圖7.4 文件的多重結(jié)構(gòu)文件的多重結(jié)構(gòu) 圖圖7.5 文件的轉(zhuǎn)置結(jié)構(gòu)文件的轉(zhuǎn)置結(jié)構(gòu)(4) 順序結(jié)

28、構(gòu)順序結(jié)構(gòu)如果系統(tǒng)要求按某種優(yōu)先順序來(lái)搜索或追加、刪除如果系統(tǒng)要求按某種優(yōu)先順序來(lái)搜索或追加、刪除記錄，則最好采用順序結(jié)構(gòu)。如果給定了順序規(guī)定記錄，則最好采用順序結(jié)構(gòu)。如果給定了順序規(guī)定(例如按字母順序例如按字母順序)，則把文件中的鍵按規(guī)定的順序，則把文件中的鍵按規(guī)定的順序排列起來(lái)就形成了順序結(jié)構(gòu)文件。例如，把人民日排列起來(lái)就形成了順序結(jié)構(gòu)文件。例如，把人民日?qǐng)?bào)上登載的新聞按年月日為鍵做成記錄放入文件中，報(bào)上登載的新聞按年月日為鍵做成記錄放入文件中，并以時(shí)間先后順序組成文件。這樣，如果要處理某并以時(shí)間先后順序組成文件。這樣，如果要處理某段時(shí)間內(nèi)所發(fā)生的大事等問(wèn)題，就會(huì)變得非常簡(jiǎn)單。段時(shí)間內(nèi)所發(fā)

29、生的大事等問(wèn)題，就會(huì)變得非常簡(jiǎn)單。例如用戶想了解兩伊戰(zhàn)爭(zhēng)的情況，則只要把例如用戶想了解兩伊戰(zhàn)爭(zhēng)的情況，則只要把1990年年8 月月19日開(kāi)始的兩個(gè)月內(nèi)的有關(guān)記錄搜索到就行了。日開(kāi)始的兩個(gè)月內(nèi)的有關(guān)記錄搜索到就行了。7.2.2 存取方法存取方法用戶通過(guò)對(duì)文件的存取來(lái)完成對(duì)文件的修改、追加用戶通過(guò)對(duì)文件的存取來(lái)完成對(duì)文件的修改、追加和搜索等操作。常用的存取方法有三種：和搜索等操作。常用的存取方法有三種：(1) 順序存取法順序存取法(2) 隨機(jī)存取法隨機(jī)存取法(直接存取法直接存取法)(3) 按鍵存取法按鍵存取法 順序存取是按照文件的邏輯地址順序存取。在記錄順序存取是按照文件的邏輯地址順序存取。在記錄

30、式文件中，這反映為按記錄的排列順序來(lái)存取，例式文件中，這反映為按記錄的排列順序來(lái)存取，例如，若當(dāng)前讀取的記錄為如，若當(dāng)前讀取的記錄為Ri，則下一次讀取的記錄，則下一次讀取的記錄被自動(dòng)地確定為被自動(dòng)地確定為Ri的下一個(gè)相鄰的記錄的下一個(gè)相鄰的記錄Ri+1。在無(wú)。在無(wú)結(jié)構(gòu)的字符流文件中，順序存取反映當(dāng)前讀寫指針結(jié)構(gòu)的字符流文件中，順序存取反映當(dāng)前讀寫指針的變化。在存取完一段信息之后，讀寫指針自動(dòng)加的變化。在存取完一段信息之后，讀寫指針自動(dòng)加或減去該段信息長(zhǎng)度，以便指出下次存取時(shí)的位置?；驕p去該段信息長(zhǎng)度，以便指出下次存取時(shí)的位置。隨機(jī)存取法允許用戶根據(jù)記錄的編號(hào)來(lái)存取文件的隨機(jī)存取法允許用戶根據(jù)記

31、錄的編號(hào)來(lái)存取文件的任一記錄，或者是根據(jù)存取命令把讀寫指針移到欲任一記錄，或者是根據(jù)存取命令把讀寫指針移到欲讀寫處來(lái)讀寫。讀寫處來(lái)讀寫。UNIX系統(tǒng)以及系統(tǒng)以及MS-DOS等操作系等操作系統(tǒng)都采用順序存取和隨機(jī)存取等兩種方法。統(tǒng)都采用順序存取和隨機(jī)存取等兩種方法。按鍵存取是一種用在復(fù)雜文件系統(tǒng)，特別是數(shù)據(jù)庫(kù)按鍵存取是一種用在復(fù)雜文件系統(tǒng)，特別是數(shù)據(jù)庫(kù)管理系統(tǒng)中的存取方法。文件的存取是根據(jù)給定的管理系統(tǒng)中的存取方法。文件的存取是根據(jù)給定的鍵或記錄名進(jìn)行的。按鍵存取法首先搜索到要進(jìn)行鍵或記錄名進(jìn)行的。按鍵存取法首先搜索到要進(jìn)行存取的記錄的邏輯位置，再將其轉(zhuǎn)換到相應(yīng)的物理存取的記錄的邏輯位置，再將其

32、轉(zhuǎn)換到相應(yīng)的物理地址后進(jìn)行存取。下面，介紹按鍵存取的搜索方法。地址后進(jìn)行存取。下面，介紹按鍵存取的搜索方法。對(duì)文件進(jìn)行搜索的目的是要查找出特定記錄所對(duì)應(yīng)對(duì)文件進(jìn)行搜索的目的是要查找出特定記錄所對(duì)應(yīng)的邏輯地址，以便將其轉(zhuǎn)換為相應(yīng)的物理地址，實(shí)的邏輯地址，以便將其轉(zhuǎn)換為相應(yīng)的物理地址，實(shí)現(xiàn)對(duì)文件的操作?，F(xiàn)對(duì)文件的操作。對(duì)文件的搜索包括兩種：鍵的搜索和記錄的搜索。對(duì)文件的搜索包括兩種：鍵的搜索和記錄的搜索。對(duì)鍵的搜索是在用戶給定所要搜索的鍵名和記錄之對(duì)鍵的搜索是在用戶給定所要搜索的鍵名和記錄之后，確定該鍵名在文件中的位置；而記錄的搜索則后，確定該鍵名在文件中的位置；而記錄的搜索則是在搜索到所要查找的

33、鍵之后，在含有該鍵的所有是在搜索到所要查找的鍵之后，在含有該鍵的所有記錄中查找出所需要的記錄。顯然，對(duì)于不同的邏記錄中查找出所需要的記錄。顯然，對(duì)于不同的邏輯結(jié)構(gòu)的文件，其搜索方法和搜索效率都是不一樣輯結(jié)構(gòu)的文件，其搜索方法和搜索效率都是不一樣的。對(duì)指定記錄的。對(duì)指定記錄Ri的搜索過(guò)程如圖的搜索過(guò)程如圖7.6所示。所示。對(duì)于給定的對(duì)于給定的Ri,首先首先,系統(tǒng)確定系統(tǒng)確定Ri所對(duì)應(yīng)鍵名的記錄隊(duì)所對(duì)應(yīng)鍵名的記錄隊(duì)列。如果在所查找的文件中不存在這樣的隊(duì)列，則列。如果在所查找的文件中不存在這樣的隊(duì)列，則搜索算法結(jié)束返回，從而無(wú)法搜索到搜索算法結(jié)束返回，從而無(wú)法搜索到Ri。如果找到。如果找到Ri，則返

34、回其所對(duì)應(yīng)的邏輯地址。如果找不到，則返回其所對(duì)應(yīng)的邏輯地址。如果找不到Ri，則返回?zé)o法找到則返回?zé)o法找到Ri的有關(guān)信息。的有關(guān)信息。圖圖7.6 記錄記錄 Ri的搜索過(guò)程的搜索過(guò)程對(duì)鍵或記錄的搜索與其他數(shù)據(jù)搜索問(wèn)題一樣，都屬對(duì)鍵或記錄的搜索與其他數(shù)據(jù)搜索問(wèn)題一樣，都屬于表格搜索問(wèn)題。有許多搜索算法用來(lái)解決表格搜于表格搜索問(wèn)題。有許多搜索算法用來(lái)解決表格搜索問(wèn)題。這些算法可以大致分為三種類型。即，索問(wèn)題。這些算法可以大致分為三種類型。即，(1) 線性搜索法線性搜索法(linear search)，(2) 散列法散列法(hash coding)，(3) 二分搜索法二分搜索法(binary searc

35、h algorithm)。下面分別簡(jiǎn)單地介紹這幾種搜索算法。下面分別簡(jiǎn)單地介紹這幾種搜索算法。(1) 線性搜索法線性搜索法它從第一個(gè)鍵或記錄開(kāi)始，依次和所要搜索的鍵或它從第一個(gè)鍵或記錄開(kāi)始，依次和所要搜索的鍵或記錄相比較，直到找到所需要的記錄為止。線性搜記錄相比較，直到找到所需要的記錄為止。線性搜索法所需要的搜索時(shí)間與所搜索的表格大小的索法所需要的搜索時(shí)間與所搜索的表格大小的 1/2成正比。這是因?yàn)檎业揭粋€(gè)所需要的記錄平均要和成正比。這是因?yàn)檎业揭粋€(gè)所需要的記錄平均要和表中登記的總項(xiàng)數(shù)的表中登記的總項(xiàng)數(shù)的1/2項(xiàng)比較后才能得到。項(xiàng)比較后才能得到。線性搜索法的搜索效率較低，在文件中記錄個(gè)數(shù)較線性

36、搜索法的搜索效率較低，在文件中記錄個(gè)數(shù)較多時(shí)不宜采用。多時(shí)不宜采用。(2) 散列法散列法散列搜索法被被廣泛用于現(xiàn)代操作系統(tǒng)的數(shù)據(jù)查找。散列搜索法被被廣泛用于現(xiàn)代操作系統(tǒng)的數(shù)據(jù)查找。散列法的核心思想是定義一個(gè)散列函數(shù)散列法的核心思想是定義一個(gè)散列函數(shù)h(k)，使得，使得對(duì)于給定的鍵對(duì)于給定的鍵k，散列函數(shù)，散列函數(shù)h(k)將其變換為將其變換為 k所對(duì)應(yīng)所對(duì)應(yīng)的邏輯地址。的邏輯地址。在使用散列函數(shù)進(jìn)行搜索時(shí)，有時(shí)會(huì)出現(xiàn)兩個(gè)不同在使用散列函數(shù)進(jìn)行搜索時(shí)，有時(shí)會(huì)出現(xiàn)兩個(gè)不同的輸入值變換到同一地址的問(wèn)題。即對(duì)于的輸入值變換到同一地址的問(wèn)題。即對(duì)于k1!=k2，有有h(k1)=h(k2)=A。顯然，。顯然

37、，k1和和k2 中，至少有一個(gè)與中，至少有一個(gè)與 A中的內(nèi)容不一致。也就是說(shuō)，由散列變換得到的中的內(nèi)容不一致。也就是說(shuō)，由散列變換得到的結(jié)果并不是所要搜索的鍵。這種問(wèn)題稱為散列沖突。結(jié)果并不是所要搜索的鍵。這種問(wèn)題稱為散列沖突。解決散列沖突的方法是采用多次散列探索。例如，解決散列沖突的方法是采用多次散列探索。例如，設(shè)第設(shè)第i 次散列變換的結(jié)果為次散列變換的結(jié)果為hi(k)，i=2,3，則可令，則可令hi(k) =(h1(k) +di)(mod t)這里，這里，t 為被搜索表格長(zhǎng)度，為被搜索表格長(zhǎng)度，di為第為第i 次搜索所得地址次搜索所得地址與第與第1次搜索所得地址之間的距離。次搜索所得地址之

38、間的距離。di的取值方法的取值方法很多，最簡(jiǎn)單的方法是設(shè)很多，最簡(jiǎn)單的方法是設(shè)di為為i的線性函數(shù)，即的線性函數(shù)，即di=a*i(a為一大于零的常數(shù)為一大于零的常數(shù))。這種方法稱線性散列。這種方法稱線性散列法。但是，使用線性散列法并不能完全解決散列沖法。但是，使用線性散列法并不能完全解決散列沖突問(wèn)題。例如，對(duì)于突問(wèn)題。例如，對(duì)于i!=j，k=1,2，如果，如果 hi(k1)=hj(k2)，則存在，則存在 hi+k(k1)=hj+k(k2)。解決散列沖突的另一個(gè)方法是生成一組隨機(jī)數(shù)解決散列沖突的另一個(gè)方法是生成一組隨機(jī)數(shù)r1,r2，rn，且令，且令di=ri。顯然，除了。顯然，除了 h1(k1)

39、=h1(k2)可能存在之外，可能存在之外，h1(k1)=h1+k(k2)的可能的可能性很小，不過(guò)，使用隨機(jī)數(shù)的方法需要占用一定的性很小，不過(guò)，使用隨機(jī)數(shù)的方法需要占用一定的存儲(chǔ)空間來(lái)生成和存放隨機(jī)數(shù)組。存儲(chǔ)空間來(lái)生成和存放隨機(jī)數(shù)組。還有一個(gè)解決散列沖突的方法是采用平方散列函數(shù)還有一個(gè)解決散列沖突的方法是采用平方散列函數(shù)方法。即令：方法。即令：hi(k) =(h1(k)+c*(i*i)(mod t) 這里，這里，t是一個(gè)表示被搜索表格長(zhǎng)度的素?cái)?shù)，是一個(gè)表示被搜索表格長(zhǎng)度的素?cái)?shù)，c 是一是一個(gè)大于零的常數(shù)?？梢宰C明，對(duì)于個(gè)大于零的常數(shù)?？梢宰C明，對(duì)于j1(mod t)，即，即使有使有 h1(k1)

40、=hj(k2)，那么，對(duì)于，那么，對(duì)于i=1,2，t-1，有，有 hi(k1)!=hj+i(k2)。(3) 二分搜索法二分搜索法 對(duì)于順序結(jié)構(gòu)排列的鍵或記錄來(lái)說(shuō)，二分搜索法具對(duì)于順序結(jié)構(gòu)排列的鍵或記錄來(lái)說(shuō)，二分搜索法具有較高的搜索效率。有較高的搜索效率。設(shè)鍵設(shè)鍵K0,K1,K2，Kn(n1)按鍵間距按鍵間距d排列，如果排列，如果K0的邏輯位置為的邏輯位置為a0，則有，則有Ki的邏輯位置為的邏輯位置為a0+i*d。二分搜索法首先把所要搜的鍵與隊(duì)列的首尾鍵相比二分搜索法首先把所要搜的鍵與隊(duì)列的首尾鍵相比較較,如果和其中之一相等，則返回所搜索到的鍵的如果和其中之一相等，則返回所搜索到的鍵的邏輯位置。

41、否則，再與隊(duì)列邏輯位置。否則，再與隊(duì)列1/2處的鍵比較，如果處的鍵比較，如果所要搜索的鍵正好等于該鍵的話所要搜索的鍵正好等于該鍵的話,則返回該鍵的邏則返回該鍵的邏輯地址；否則，如果所要搜索的鍵輯地址；否則，如果所要搜索的鍵K 小于位于隊(duì)列小于位于隊(duì)列中央的鍵的話，則繼續(xù)搜索左邊的半個(gè)隊(duì)列。如果中央的鍵的話，則繼續(xù)搜索左邊的半個(gè)隊(duì)列。如果所要搜索的鍵所要搜索的鍵K大于位于隊(duì)列中央的鍵的話大于位于隊(duì)列中央的鍵的話,則繼續(xù)則繼續(xù)搜索右邊的半個(gè)隊(duì)列。這樣，每次用以中央鍵畫(huà)分搜索右邊的半個(gè)隊(duì)列。這樣，每次用以中央鍵畫(huà)分的部分組成新的隊(duì)列反復(fù)進(jìn)行上述搜索操作，直到的部分組成新的隊(duì)列反復(fù)進(jìn)行上述搜索操作，直

42、到找到為止。這一搜索過(guò)程如圖找到為止。這一搜索過(guò)程如圖7.7所示。所示。二分搜索法的好處是搜索效率高。與線性搜索法相二分搜索法的好處是搜索效率高。與線性搜索法相比，當(dāng)比，當(dāng) n(表長(zhǎng)表長(zhǎng))=16時(shí)時(shí),它比線性搜索法約快二倍它比線性搜索法約快二倍; 當(dāng)當(dāng) n=1 024 時(shí)，其平均搜索速度要快時(shí)，其平均搜索速度要快50倍。不過(guò)，二倍。不過(guò)，二分搜索法需要事先把搜索對(duì)象按一定順序排列。分搜索法需要事先把搜索對(duì)象按一定順序排列。圖圖7.7 二分搜索法的搜索過(guò)程二分搜索法的搜索過(guò)程7.3 文件的物理結(jié)構(gòu)與存儲(chǔ)設(shè)備文件的物理結(jié)構(gòu)與存儲(chǔ)設(shè)備文件系統(tǒng)采用哪種存取方法和邏輯結(jié)構(gòu)，實(shí)際上是文件系統(tǒng)采用哪種存取方

43、法和邏輯結(jié)構(gòu)，實(shí)際上是和物理存儲(chǔ)介質(zhì)有關(guān)的。因此，本節(jié)介紹文件的物和物理存儲(chǔ)介質(zhì)有關(guān)的。因此，本節(jié)介紹文件的物理結(jié)構(gòu)，同時(shí)也介紹常用的文件存儲(chǔ)設(shè)備。理結(jié)構(gòu)，同時(shí)也介紹常用的文件存儲(chǔ)設(shè)備。7.3.1 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)在文件系統(tǒng)中，文件的存儲(chǔ)設(shè)備通常畫(huà)分為若干個(gè)在文件系統(tǒng)中，文件的存儲(chǔ)設(shè)備通常畫(huà)分為若干個(gè)大小相等的物理塊，每塊長(zhǎng)為大小相等的物理塊，每塊長(zhǎng)為 512 或或 1024字節(jié)。字節(jié)。與此相對(duì)應(yīng)，為了有效地利用存儲(chǔ)設(shè)備和便于系統(tǒng)與此相對(duì)應(yīng)，為了有效地利用存儲(chǔ)設(shè)備和便于系統(tǒng)管理管理,一般把文件信息也畫(huà)分為與物理存儲(chǔ)設(shè)備的一般把文件信息也畫(huà)分為與物理存儲(chǔ)設(shè)備的物理塊大小相等的邏輯塊。

44、從而，以塊作為分配和物理塊大小相等的邏輯塊。從而，以塊作為分配和傳送信息的基本單位。顯然，對(duì)于字符流的無(wú)結(jié)構(gòu)傳送信息的基本單位。顯然，對(duì)于字符流的無(wú)結(jié)構(gòu)文件來(lái)說(shuō)，每一個(gè)物理塊中存放長(zhǎng)度相等的文件信文件來(lái)說(shuō)，每一個(gè)物理塊中存放長(zhǎng)度相等的文件信息息(存儲(chǔ)文件尾部信息的物理塊除外存儲(chǔ)文件尾部信息的物理塊除外)。但是，對(duì)于。但是，對(duì)于記錄式文件來(lái)說(shuō)，由于記錄長(zhǎng)度既可以是固定的，記錄式文件來(lái)說(shuō)，由于記錄長(zhǎng)度既可以是固定的，也可以是可變的，而且其長(zhǎng)度不一定剛好等于其物也可以是可變的，而且其長(zhǎng)度不一定剛好等于其物理塊的長(zhǎng)度，從而給由記錄的邏輯地址到物理地址理塊的長(zhǎng)度，從而給由記錄的邏輯地址到物理地址的變換帶

45、來(lái)了額外的負(fù)擔(dān)。的變換帶來(lái)了額外的負(fù)擔(dān)。這里，為了簡(jiǎn)單起見(jiàn)，假設(shè)文件系統(tǒng)中每個(gè)記錄的這里，為了簡(jiǎn)單起見(jiàn)，假設(shè)文件系統(tǒng)中每個(gè)記錄的長(zhǎng)度是固定的，且其長(zhǎng)度正好等于物理塊的長(zhǎng)度。長(zhǎng)度是固定的，且其長(zhǎng)度正好等于物理塊的長(zhǎng)度。從而，對(duì)于記錄式文件來(lái)說(shuō)，利用上節(jié)討論的搜索從而，對(duì)于記錄式文件來(lái)說(shuō)，利用上節(jié)討論的搜索算法得到的邏輯地址正好與文件的邏輯塊號(hào)一一對(duì)算法得到的邏輯地址正好與文件的邏輯塊號(hào)一一對(duì)應(yīng)，這就簡(jiǎn)化了所討論問(wèn)題的條件。應(yīng)，這就簡(jiǎn)化了所討論問(wèn)題的條件。文件的物理結(jié)構(gòu)是指文件在存儲(chǔ)設(shè)備上的存放方法。文件的物理結(jié)構(gòu)是指文件在存儲(chǔ)設(shè)備上的存放方法。事實(shí)上，由于文件的物理結(jié)構(gòu)決定了文件信息在存事實(shí)上，

46、由于文件的物理結(jié)構(gòu)決定了文件信息在存儲(chǔ)設(shè)備上的存儲(chǔ)位置，因此，文件信息的邏輯塊號(hào)儲(chǔ)設(shè)備上的存儲(chǔ)位置，因此，文件信息的邏輯塊號(hào)(邏輯地址邏輯地址) 到物理塊號(hào)到物理塊號(hào)(物理地址物理地址) 的變換也是由文的變換也是由文件的物理結(jié)構(gòu)決定的。件的物理結(jié)構(gòu)決定的。常用的文件物理結(jié)構(gòu)如下：常用的文件物理結(jié)構(gòu)如下：(1) 連續(xù)文件連續(xù)文件連續(xù)文件是一種最簡(jiǎn)單的物理文件結(jié)構(gòu)，它把一個(gè)連續(xù)文件是一種最簡(jiǎn)單的物理文件結(jié)構(gòu)，它把一個(gè)在邏輯上連續(xù)的文件信息依次存放到物理塊中。在邏輯上連續(xù)的文件信息依次存放到物理塊中。在圖在圖7.8中，一個(gè)邏輯塊號(hào)為中，一個(gè)邏輯塊號(hào)為 0,1,2,3的文件依次存放的文件依次存放在物理

47、塊在物理塊 10,11,12,13中。中。連續(xù)文件結(jié)構(gòu)的優(yōu)點(diǎn)是一旦知道了文件在文件存儲(chǔ)連續(xù)文件結(jié)構(gòu)的優(yōu)點(diǎn)是一旦知道了文件在文件存儲(chǔ)設(shè)備上的起址和文件長(zhǎng)度，就能很快地進(jìn)行存取。設(shè)備上的起址和文件長(zhǎng)度，就能很快地進(jìn)行存取。這是因?yàn)槲募倪壿媺K號(hào)到物理塊號(hào)的變換可以非這是因?yàn)槲募倪壿媺K號(hào)到物理塊號(hào)的變換可以非常簡(jiǎn)單地完成。但是連續(xù)文件結(jié)構(gòu)在建立文件時(shí)必常簡(jiǎn)單地完成。但是連續(xù)文件結(jié)構(gòu)在建立文件時(shí)必須在文件說(shuō)明信息中確定文件信息長(zhǎng)度，且以后不須在文件說(shuō)明信息中確定文件信息長(zhǎng)度，且以后不能動(dòng)態(tài)增長(zhǎng)。而且在文件進(jìn)行某些部分的刪除后，能動(dòng)態(tài)增長(zhǎng)。而且在文件進(jìn)行某些部分的刪除后，又會(huì)留下無(wú)法使用的零頭空間。因

48、此，連續(xù)文件結(jié)又會(huì)留下無(wú)法使用的零頭空間。因此，連續(xù)文件結(jié)構(gòu)不宜用來(lái)存放用戶文件、數(shù)據(jù)庫(kù)文件等經(jīng)常被修構(gòu)不宜用來(lái)存放用戶文件、數(shù)據(jù)庫(kù)文件等經(jīng)常被修改的文件。改的文件。圖圖7.8 連續(xù)文件結(jié)構(gòu)連續(xù)文件結(jié)構(gòu)(2) 串聯(lián)文件串聯(lián)文件克服連續(xù)文件的缺點(diǎn)的辦法之一是采用串聯(lián)文件結(jié)克服連續(xù)文件的缺點(diǎn)的辦法之一是采用串聯(lián)文件結(jié)構(gòu)。串聯(lián)文件結(jié)構(gòu)用非連續(xù)的物理塊來(lái)存放文件信構(gòu)。串聯(lián)文件結(jié)構(gòu)用非連續(xù)的物理塊來(lái)存放文件信息。這些非連續(xù)的物理塊之間沒(méi)有順序關(guān)系，其中息。這些非連續(xù)的物理塊之間沒(méi)有順序關(guān)系，其中每個(gè)物理塊設(shè)有一個(gè)指針，指向其后續(xù)連接的另一每個(gè)物理塊設(shè)有一個(gè)指針，指向其后續(xù)連接的另一個(gè)物理塊，從而使得存放

49、同一文件的物理塊鏈接成個(gè)物理塊，從而使得存放同一文件的物理塊鏈接成一個(gè)串聯(lián)隊(duì)列。圖一個(gè)串聯(lián)隊(duì)列。圖7.9給出了串聯(lián)文件的物理結(jié)構(gòu)。給出了串聯(lián)文件的物理結(jié)構(gòu)。顯然，使用串聯(lián)文件結(jié)構(gòu)時(shí)，不必在文件說(shuō)明信息顯然，使用串聯(lián)文件結(jié)構(gòu)時(shí)，不必在文件說(shuō)明信息中指明文件的長(zhǎng)度，只需指明該文件的第一個(gè)塊號(hào)中指明文件的長(zhǎng)度，只需指明該文件的第一個(gè)塊號(hào)就行了。串聯(lián)文件結(jié)構(gòu)的另一個(gè)特點(diǎn)是文件長(zhǎng)度可就行了。串聯(lián)文件結(jié)構(gòu)的另一個(gè)特點(diǎn)是文件長(zhǎng)度可以動(dòng)態(tài)地增長(zhǎng)，只要調(diào)整連接指針就可在任何一個(gè)以動(dòng)態(tài)地增長(zhǎng)，只要調(diào)整連接指針就可在任何一個(gè)信息塊之間插入或刪除一個(gè)信息塊。信息塊之間插入或刪除一個(gè)信息塊。圖圖7.9 串聯(lián)文件的物理結(jié)

50、構(gòu)串聯(lián)文件的物理結(jié)構(gòu)用串聯(lián)文件結(jié)構(gòu)時(shí)，邏輯塊到物理塊的轉(zhuǎn)換由系統(tǒng)用串聯(lián)文件結(jié)構(gòu)時(shí)，邏輯塊到物理塊的轉(zhuǎn)換由系統(tǒng)沿串聯(lián)隊(duì)列查找與邏輯塊號(hào)對(duì)應(yīng)的物理塊號(hào)的辦法沿串聯(lián)隊(duì)列查找與邏輯塊號(hào)對(duì)應(yīng)的物理塊號(hào)的辦法完成。例如，在圖完成。例如，在圖7.9的文件結(jié)構(gòu)中，如果用戶所的文件結(jié)構(gòu)中，如果用戶所要進(jìn)行操作的邏輯塊號(hào)為要進(jìn)行操作的邏輯塊號(hào)為2，則系統(tǒng)從第一個(gè)物理，則系統(tǒng)從第一個(gè)物理塊塊20開(kāi)始，一直沿串聯(lián)隊(duì)列搜索到隊(duì)列中邏輯塊號(hào)開(kāi)始，一直沿串聯(lián)隊(duì)列搜索到隊(duì)列中邏輯塊號(hào)為為2的第三塊時(shí)，得到其所對(duì)應(yīng)的物理塊號(hào)為的第三塊時(shí)，得到其所對(duì)應(yīng)的物理塊號(hào)為22。由于串聯(lián)文件結(jié)構(gòu)只能按隊(duì)列中的串聯(lián)指針順序搜由于串聯(lián)文件結(jié)構(gòu)

51、只能按隊(duì)列中的串聯(lián)指針順序搜索，因此，串聯(lián)文件結(jié)構(gòu)的搜索效率較低。串連文索，因此，串聯(lián)文件結(jié)構(gòu)的搜索效率較低。串連文件結(jié)構(gòu)一般只適用于邏輯上連續(xù)的文件，且存取方件結(jié)構(gòu)一般只適用于邏輯上連續(xù)的文件，且存取方法應(yīng)該是順序存取的。否則，為了讀取某個(gè)信息塊法應(yīng)該是順序存取的。否則，為了讀取某個(gè)信息塊而造成的磁頭大幅度移動(dòng)將花去較多的時(shí)間。因此，而造成的磁頭大幅度移動(dòng)將花去較多的時(shí)間。因此，串聯(lián)文件結(jié)構(gòu)不適宜隨機(jī)存取。串聯(lián)文件結(jié)構(gòu)不適宜隨機(jī)存取。(3) 索引文件索引文件第三種文件物理結(jié)構(gòu)是索引結(jié)構(gòu)。索引結(jié)構(gòu)要求系第三種文件物理結(jié)構(gòu)是索引結(jié)構(gòu)。索引結(jié)構(gòu)要求系統(tǒng)為每個(gè)文件建立一張索引表，表中每一欄目指出統(tǒng)為

52、每個(gè)文件建立一張索引表，表中每一欄目指出文件信息所在的邏輯塊號(hào)和與之對(duì)應(yīng)的物理塊號(hào)。文件信息所在的邏輯塊號(hào)和與之對(duì)應(yīng)的物理塊號(hào)。索引表的物理地址則由文件說(shuō)明信息項(xiàng)給出。索引索引表的物理地址則由文件說(shuō)明信息項(xiàng)給出。索引結(jié)構(gòu)如圖結(jié)構(gòu)如圖7.10所示。所示。索引文件結(jié)構(gòu)既可以滿足文件動(dòng)態(tài)增長(zhǎng)的要求，又索引文件結(jié)構(gòu)既可以滿足文件動(dòng)態(tài)增長(zhǎng)的要求，又可以較為方便和迅速地實(shí)現(xiàn)隨機(jī)存取。因?yàn)橛嘘P(guān)邏可以較為方便和迅速地實(shí)現(xiàn)隨機(jī)存取。因?yàn)橛嘘P(guān)邏輯塊號(hào)和物理塊號(hào)的信息全部放在一個(gè)集中的索引輯塊號(hào)和物理塊號(hào)的信息全部放在一個(gè)集中的索引表中，而不是像串聯(lián)文件結(jié)構(gòu)那樣分散在各個(gè)物理表中，而不是像串聯(lián)文件結(jié)構(gòu)那樣分散在各個(gè)

53、物理塊中。塊中。圖圖7.10 索引文件示意圖索引文件示意圖在很多情況下，有的文件很大，文件索引表也就較在很多情況下，有的文件很大，文件索引表也就較大。如果索引表的大小超過(guò)了一個(gè)物理塊，那么我大。如果索引表的大小超過(guò)了一個(gè)物理塊，那么我們必須象處理其他文件的存放那樣決定索引表的物們必須象處理其他文件的存放那樣決定索引表的物理存放方式，但這不利于索引表的動(dòng)態(tài)增加；索引理存放方式，但這不利于索引表的動(dòng)態(tài)增加；索引表也可按串聯(lián)方式存放，但這卻增加了存放索引表表也可按串聯(lián)方式存放，但這卻增加了存放索引表的時(shí)間開(kāi)銷。一種較好的解決辦法是采用間接索引的時(shí)間開(kāi)銷。一種較好的解決辦法是采用間接索引(多重索引多重

54、索引)，也就是在索引表所指的物理塊中存放，也就是在索引表所指的物理塊中存放的不是文件信息，而是裝有這些信息的物理塊地址。的不是文件信息，而是裝有這些信息的物理塊地址。這樣，如果一個(gè)物理塊可裝下這樣，如果一個(gè)物理塊可裝下n個(gè)物理塊地址的話，個(gè)物理塊地址的話，則經(jīng)過(guò)一級(jí)間接索引，可尋址的文件長(zhǎng)度將變?yōu)閯t經(jīng)過(guò)一級(jí)間接索引，可尋址的文件長(zhǎng)度將變?yōu)?n*n 塊。如果文件長(zhǎng)度還大于塊。如果文件長(zhǎng)度還大于 n*n塊的話，還可以塊的話，還可以進(jìn)行類似的擴(kuò)充，即二級(jí)間接索引。其原理如圖進(jìn)行類似的擴(kuò)充，即二級(jí)間接索引。其原理如圖7.11。圖圖7.11 多重索引結(jié)構(gòu)多重索引結(jié)構(gòu)不過(guò)，大多數(shù)文件不需要進(jìn)行多重索引，也

55、就是說(shuō)，不過(guò)，大多數(shù)文件不需要進(jìn)行多重索引，也就是說(shuō)，這些文件所占用的物理塊數(shù)的塊號(hào)可以放在一個(gè)物這些文件所占用的物理塊數(shù)的塊號(hào)可以放在一個(gè)物理塊內(nèi)。如果對(duì)這些文件也采用多重索引，則顯然理塊內(nèi)。如果對(duì)這些文件也采用多重索引，則顯然會(huì)降低文件的存取速度。因此，在實(shí)際系統(tǒng)中，總會(huì)降低文件的存取速度。因此，在實(shí)際系統(tǒng)中，總是把索引表的頭幾項(xiàng)設(shè)計(jì)成直接尋址方式，也就是是把索引表的頭幾項(xiàng)設(shè)計(jì)成直接尋址方式，也就是這幾項(xiàng)所指的物理塊中存放的是文件信息；而索引這幾項(xiàng)所指的物理塊中存放的是文件信息；而索引表的后幾項(xiàng)設(shè)計(jì)成多重索引，也就是間接尋址方式。表的后幾項(xiàng)設(shè)計(jì)成多重索引，也就是間接尋址方式。在文件較短時(shí)，

56、就可利用直接尋址方式找到物理塊在文件較短時(shí)，就可利用直接尋址方式找到物理塊號(hào)而節(jié)省存取時(shí)間。號(hào)而節(jié)省存取時(shí)間。索引結(jié)構(gòu)既適用于順序存取，也適用于隨機(jī)存取。索引結(jié)構(gòu)既適用于順序存取，也適用于隨機(jī)存取。索引結(jié)構(gòu)的缺點(diǎn)是由于使用了索引表而增加了存儲(chǔ)索引結(jié)構(gòu)的缺點(diǎn)是由于使用了索引表而增加了存儲(chǔ)空間的開(kāi)銷。另外，在存取文件時(shí)需要至少訪問(wèn)存空間的開(kāi)銷。另外，在存取文件時(shí)需要至少訪問(wèn)存儲(chǔ)器二次以上。其中，一次是訪問(wèn)索引表，另一次儲(chǔ)器二次以上。其中，一次是訪問(wèn)索引表，另一次是根據(jù)索引表提供的物理塊號(hào)訪問(wèn)文件信息。由于是根據(jù)索引表提供的物理塊號(hào)訪問(wèn)文件信息。由于文件在存儲(chǔ)設(shè)備的訪問(wèn)速度較慢，因此，如果把索文件在

57、存儲(chǔ)設(shè)備的訪問(wèn)速度較慢，因此，如果把索引表放在存儲(chǔ)設(shè)備上，勢(shì)必大大降低文件的存取速引表放在存儲(chǔ)設(shè)備上，勢(shì)必大大降低文件的存取速度。一種改進(jìn)的方法是，當(dāng)對(duì)某個(gè)文件進(jìn)行操作之度。一種改進(jìn)的方法是，當(dāng)對(duì)某個(gè)文件進(jìn)行操作之前，系統(tǒng)預(yù)先把索引表放入內(nèi)存。這樣，文件的存前，系統(tǒng)預(yù)先把索引表放入內(nèi)存。這樣，文件的存取就可直接在內(nèi)存通過(guò)索引表確定物理地址塊號(hào)，取就可直接在內(nèi)存通過(guò)索引表確定物理地址塊號(hào)，而訪問(wèn)磁盤的動(dòng)作只需要一次。而訪問(wèn)磁盤的動(dòng)作只需要一次。7.3.2 文件存儲(chǔ)設(shè)備文件存儲(chǔ)設(shè)備常用的存儲(chǔ)設(shè)備有磁盤、光盤、磁帶等。其中磁盤常用的存儲(chǔ)設(shè)備有磁盤、光盤、磁帶等。其中磁盤又可分為硬盤和軟盤。由于存儲(chǔ)設(shè)

58、備的特性決定了又可分為硬盤和軟盤。由于存儲(chǔ)設(shè)備的特性決定了文件的存取設(shè)備和方法，因此，這里介紹以磁帶為文件的存取設(shè)備和方法，因此，這里介紹以磁帶為代表的順序存儲(chǔ)設(shè)備和以磁盤為代表的直接存儲(chǔ)設(shè)代表的順序存儲(chǔ)設(shè)備和以磁盤為代表的直接存儲(chǔ)設(shè)備的特性及有關(guān)存取方法。備的特性及有關(guān)存取方法。1. 順序存取設(shè)備順序存取設(shè)備磁帶是一種最典型的順序存取設(shè)備。順序存取設(shè)備磁帶是一種最典型的順序存取設(shè)備。順序存取設(shè)備只有在前面的物理塊被存取訪問(wèn)過(guò)之后，才能存取只有在前面的物理塊被存取訪問(wèn)過(guò)之后，才能存取后續(xù)的物理塊的內(nèi)容。而且，為了在存取一個(gè)物理后續(xù)的物理塊的內(nèi)容。而且，為了在存取一個(gè)物理塊時(shí)讓磁帶機(jī)提前加速和不

59、停止在下一個(gè)物理塊的塊時(shí)讓磁帶機(jī)提前加速和不停止在下一個(gè)物理塊的位置上，磁帶的兩相鄰的物理塊之間設(shè)計(jì)有一個(gè)間位置上，磁帶的兩相鄰的物理塊之間設(shè)計(jì)有一個(gè)間隙將它們隔開(kāi)隙將它們隔開(kāi)(圖圖7.12)。圖圖7.12 磁帶的結(jié)構(gòu)磁帶的結(jié)構(gòu)磁帶設(shè)備的存取速度或數(shù)據(jù)傳輸率與下列因素有關(guān)：磁帶設(shè)備的存取速度或數(shù)據(jù)傳輸率與下列因素有關(guān)：(1) 信息密度信息密度(字符數(shù)字符數(shù)/英寸英寸)(2) 磁帶帶速磁帶帶速(英寸英寸/秒秒)(3) 塊間間隙塊間間隙 如果帶速高，信息密度大，且所需塊間隙如果帶速高，信息密度大，且所需塊間隙(磁頭啟動(dòng)磁頭啟動(dòng)和停止時(shí)間和停止時(shí)間) 小的話，則磁帶存取速度和數(shù)據(jù)傳輸小的話，則磁帶存

60、取速度和數(shù)據(jù)傳輸率高，反之亦然。率高，反之亦然。另外，由磁帶的讀寫方式可知，只有當(dāng)?shù)诹硗?，由磁帶的讀寫方式可知，只有當(dāng)?shù)趇塊被存取塊被存取之后，才能對(duì)第之后，才能對(duì)第i+1塊進(jìn)行存取操作。因此，某個(gè)塊進(jìn)行存取操作。因此，某個(gè)特定記錄或物理塊的存取訪問(wèn)與該物理塊到磁頭當(dāng)特定記錄或物理塊的存取訪問(wèn)與該物理塊到磁頭當(dāng)前位置的距離有很大關(guān)系。如果相距甚遠(yuǎn)，則要花前位置的距離有很大關(guān)系。如果相距甚遠(yuǎn)，則要花費(fèi)很長(zhǎng)的存取時(shí)間來(lái)移動(dòng)磁頭。因此，如果按隨機(jī)費(fèi)很長(zhǎng)的存取時(shí)間來(lái)移動(dòng)磁頭。因此，如果按隨機(jī)方式或按鍵存取方式存取磁帶上的文件信息的話，方式或按鍵存取方式存取磁帶上的文件信息的話，其效率不會(huì)很高。但是，磁