計算機操作系統(tǒng)教程_第四版_(張堯?qū)W著)_清華大學出版社_第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)與存儲設備文件的物理結(jié)構(gòu)與存儲設備7.4 文件存儲空間管理文件存儲空間管理7.5 文件目錄管理文件目錄管理7.6 文件存取控制文件存取控制7.7 文件的使用文件的使用7.8 文件系統(tǒng)的層次模型文件系統(tǒng)的層次模型本章小結(jié)本章小結(jié)習題習題對大多數(shù)用戶來說，文件系統(tǒng)是操作系統(tǒng)中最直接對大多數(shù)用戶來說，文件系統(tǒng)是操作系統(tǒng)中最直接可見的部分。計算機的重要作用之一就是能快速處可見的部分。計算機的重要作用之一就是能快速處理大量信息理大量信息,從而從而,信息的組織、存取

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

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

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

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

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

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

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

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

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

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

12、字母數(shù)字串，有用戶文件名由用戶給定，它是一個字母數(shù)字串，有些系統(tǒng)規(guī)定必須是英文字母打頭且允許一些其他的些系統(tǒng)規(guī)定必須是英文字母打頭且允許一些其他的符號出現(xiàn)在文件名的非打頭部分。例如符號出現(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)。它負責為用戶建立文件，撤消、讀寫、修改系統(tǒng)。它負責為用戶建立文件，撤消、讀寫、修改和復制文件，還負責完成對文件的按名存取和進行和復制文件，還負責完成對文件的按名存取和進行存取控制。存取控制。文件系統(tǒng)具有以

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

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

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

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

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

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

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

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

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

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

23、再者，根據(jù)各系統(tǒng)設計個鍵名可對應于多項屬性。再者，根據(jù)各系統(tǒng)設計的要求不一樣，記錄既可以是定長的，也可以是變的要求不一樣，記錄既可以是定長的，也可以是變長的。記錄的長度可以短到一個字符，也可以長到長的。記錄的長度可以短到一個字符，也可以長到一個文件，這要由系統(tǒng)設計人員確定。一個文件，這要由系統(tǒng)設計人員確定。常用的記錄式結(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)的特點是適用性強，可用于的邏輯結(jié)構(gòu)。連續(xù)結(jié)構(gòu)的特點是適用性強，可用于所有文件所有文件 ，且記錄的排列順序與記錄的內(nèi)容無關(guān)。，且記錄的排列順序與記錄的內(nèi)容無關(guān)。這有利于記錄的追加與變更。但是，連續(xù)結(jié)構(gòu)文件這有利于記錄的追加與變更。但是，連續(xù)結(jié)構(gòu)文件的搜索性能較差，例如要找出某個指定鍵的記錄時，的搜索性能較差，例如要找出某個指定鍵的記錄時，系統(tǒng)必須對文件全體進行搜索。系統(tǒng)必須對文件全體進行搜索。(2) 多重結(jié)構(gòu)多重結(jié)構(gòu) 如果把記錄按鍵和記錄名排列成行列式結(jié)構(gòu)，則一如果把記錄按鍵和記錄名排列成行列式結(jié)構(gòu)，則一個包含個包含n個記錄名、

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

26、間。從而，我們把行列式中那些為零的項去掉，并以鍵的項去掉，并以鍵Ki為隊首，以包含鍵為隊首，以包含鍵Ki的記錄為的記錄為隊列元素來構(gòu)成一個記錄隊列。對于一個有隊列元素來構(gòu)成一個記錄隊列。對于一個有m個鍵個鍵的隊列來說，這樣的隊列有的隊列來說，這樣的隊列有m個。這個。這m個隊列構(gòu)成個隊列構(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)中，每個隊列中和鍵直接相連的的多重結(jié)構(gòu)中，每個隊列中和鍵直接相連的只有一個記錄。這種結(jié)構(gòu)雖然在探索時要優(yōu)于連續(xù)只有一個記錄。這種結(jié)構(gòu)雖然在探索時要優(yōu)于連續(xù)結(jié)構(gòu)，但在探索某

27、一特定記錄時，必須在找到該記結(jié)構(gòu)，但在探索某一特定記錄時，必須在找到該記錄所對應的鍵之后，再在該鍵所對應的隊列中順序錄所對應的鍵之后，再在該鍵所對應的隊列中順序查找。與此相反，轉(zhuǎn)置結(jié)構(gòu)把含有相同鍵的記錄指查找。與此相反，轉(zhuǎn)置結(jié)構(gòu)把含有相同鍵的記錄指針全部指向該鍵，也就是說，把所有與同一鍵對應針全部指向該鍵，也就是說，把所有與同一鍵對應的記錄的指針連續(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)先順序來搜索或追加、刪除如果系統(tǒng)要求按某種優(yōu)先順序來搜索或追加、刪除記錄，則最好采用順序結(jié)構(gòu)。如果給定了順序規(guī)定記錄，則最好采用順序結(jié)構(gòu)。如果給定了順序規(guī)定(例如按字母順序例如按字母順序)，則把文件中的鍵按規(guī)定的順序，則把文件中的鍵按規(guī)定的順序排列起來就形成了順序結(jié)構(gòu)文件。例如，把人民日排列起來就形成了順序結(jié)構(gòu)文件。例如，把人民日報上登載的新聞按年月日為鍵做成記錄放入文件中，報上登載的新聞按年月日為鍵做成記錄放入文件中，并以時間先后順序組成文件。這樣，如果要處理某并以時間先后順序組成文件。這樣，如果要處理某段時間內(nèi)所發(fā)生的大事等問題，就會變得非常簡單。段時間內(nèi)所發(fā)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47、塊在物理塊 10,11,12,13中。中。連續(xù)文件結(jié)構(gòu)的優(yōu)點是一旦知道了文件在文件存儲連續(xù)文件結(jié)構(gòu)的優(yōu)點是一旦知道了文件在文件存儲設備上的起址和文件長度，就能很快地進行存取。設備上的起址和文件長度，就能很快地進行存取。這是因為文件的邏輯塊號到物理塊號的變換可以非這是因為文件的邏輯塊號到物理塊號的變換可以非常簡單地完成。但是連續(xù)文件結(jié)構(gòu)在建立文件時必常簡單地完成。但是連續(xù)文件結(jié)構(gòu)在建立文件時必須在文件說明信息中確定文件信息長度，且以后不須在文件說明信息中確定文件信息長度，且以后不能動態(tài)增長。而且在文件進行某些部分的刪除后，能動態(tài)增長。而且在文件進行某些部分的刪除后，又會留下無法使用的零頭空間。因

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

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

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

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

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

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

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

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

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

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

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

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

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