操作系統(tǒng)：第6章文件管理(概念與邏輯物理存儲)

1、2022-2-251現(xiàn)代操作系統(tǒng)現(xiàn)代操作系統(tǒng)第第2020講：第講：第6 6章章 文件管理文件管理( ( 文件與文件系統(tǒng)文件與文件系統(tǒng) ) )主講主講: :朱貴良朱貴良20152022-2-252內(nèi)容提綱內(nèi)容提綱一一 文件與文件系統(tǒng)文件與文件系統(tǒng)二二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)三三 文件的物理結(jié)構(gòu)與存儲設(shè)備文件的物理結(jié)構(gòu)與存儲設(shè)備四四 件的存儲空間管理件的存儲空間管理本節(jié)小結(jié)本節(jié)小結(jié)2022-2-253一一 文件與文件系統(tǒng)文件與文件系統(tǒng)2022-2-255一 文件與文件系統(tǒng)文件與文件系統(tǒng) 【一一】數(shù)據(jù)單位的再認(rèn)識數(shù)據(jù)單位的再認(rèn)識( (位，字節(jié)，字，記錄，文件位，字節(jié)，字，記錄，文件) )，1.

2、1.基本數(shù)據(jù)項：基本數(shù)據(jù)項：描述一對象具體屬性的字符集，是最小的數(shù)據(jù)單位，描述一對象具體屬性的字符集，是最小的數(shù)據(jù)單位，即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。每個基本數(shù)據(jù)項具有一個即原子數(shù)據(jù)，又稱為數(shù)據(jù)元素或字段。每個基本數(shù)據(jù)項具有一個具體的具體的“數(shù)據(jù)名稱數(shù)據(jù)名稱”和和“數(shù)據(jù)類型數(shù)據(jù)類型”。2.2.記錄：記錄：一組相關(guān)數(shù)據(jù)項的集合，用于描述一個對象在某方面的屬一組相關(guān)數(shù)據(jù)項的集合，用于描述一個對象在某方面的屬性。能夠唯一標(biāo)識條記錄的一個或幾個數(shù)據(jù)項，稱為性。能夠唯一標(biāo)識條記錄的一個或幾個數(shù)據(jù)項，稱為“關(guān)鍵字關(guān)鍵字(key(key) )”。通常，只需用一個數(shù)據(jù)項作為關(guān)鍵字。通常，只需用一個數(shù)據(jù)項作

3、為關(guān)鍵字。3.3.文件：文件：文件是指由創(chuàng)建者所定義、具有文件名的一組相關(guān)元素的文件是指由創(chuàng)建者所定義、具有文件名的一組相關(guān)元素的集合。多數(shù)文件是用戶直接可見部分。因而，文件管理是操作系集合。多數(shù)文件是用戶直接可見部分。因而，文件管理是操作系統(tǒng)一個非常重要的內(nèi)容，是最大的數(shù)據(jù)單位統(tǒng)一個非常重要的內(nèi)容，是最大的數(shù)據(jù)單位 2022-2-256一 文件與文件系統(tǒng)文件與文件系統(tǒng)【二二】文件定義與描述文件定義與描述1.1.文件文件定義：定義：文件是指由創(chuàng)建者所定義、文件是指由創(chuàng)建者所定義、是一組被賦名的、是一組被賦名的、在在邏輯上邏輯上具有完整意義、在內(nèi)容存放有嚴(yán)格順序、記錄在某種介質(zhì)上的、有具有完整意

4、義、在內(nèi)容存放有嚴(yán)格順序、記錄在某種介質(zhì)上的、有意義的信息集合。意義的信息集合。2.2.文件的屬性文件的屬性：文件是容納數(shù)據(jù)的容器。是文件系統(tǒng)中最大的數(shù)據(jù)單位。文件是容納數(shù)據(jù)的容器。是文件系統(tǒng)中最大的數(shù)據(jù)單位。 每個文件都具有名稱、每個文件都具有名稱、類型、大小、存儲的具體物理位置。類型、大小、存儲的具體物理位置。文件的建立時間。指文件最后一次的修改時間。文件的建立時間。指文件最后一次的修改時間。文件的組織形式，掩蓋了物理上存放的不連續(xù)性，遮掩了低層文件的組織形式，掩蓋了物理上存放的不連續(xù)性，遮掩了低層物理硬件上的細(xì)節(jié)。物理硬件上的細(xì)節(jié)。2022-2-257一 文件與文件系統(tǒng)文件與文件系統(tǒng)3.

5、3. 文件操作文件操作最基本的文件操作最基本的文件操作包括：包括： (1) (1) 創(chuàng)建文件。系統(tǒng)應(yīng)為分配必要外創(chuàng)建文件。系統(tǒng)應(yīng)為分配必要外存，建立一個目錄項，記錄新文件的文件名、外存、的地址等屬性存，建立一個目錄項，記錄新文件的文件名、外存、的地址等屬性信息。信息。(2) (2) 刪除文件；刪除文件；(3) (3) 讀文件。須在系統(tǒng)調(diào)用中給出文件名和讀文件。須在系統(tǒng)調(diào)用中給出文件名和應(yīng)讀入內(nèi)存的地址。在目錄項中，還須有一個指針用于對文件的讀應(yīng)讀入內(nèi)存的地址。在目錄項中，還須有一個指針用于對文件的讀/ /寫。寫。(4) (4) 寫文件。寫文件。(5) (5) 設(shè)置文件的讀設(shè)置文件的讀/ /寫位

6、置。即為文件的讀寫位置。即為文件的讀/ /寫操寫操作，設(shè)置用于文件讀作，設(shè)置用于文件讀/ /寫操作位置的指針。寫操作位置的指針。 文件的文件的“打開打開”和和“關(guān)閉關(guān)閉”操作操作“打開打開”是指系統(tǒng)將指名文件的屬性從外存拷貝到內(nèi)存，并將文是指系統(tǒng)將指名文件的屬性從外存拷貝到內(nèi)存，并將文件表目中的編號件表目中的編號( (或稱為索引或稱為索引) )返回給用戶。以方便索引查找，從返回給用戶。以方便索引查找，從而避免了對該文件的再次檢索。關(guān)閉文件，即從打開文件表中的而避免了對該文件的再次檢索。關(guān)閉文件，即從打開文件表中的表目上將其刪掉。表目上將其刪掉。 2022-2-258一 文件與文件系統(tǒng)文件與文件

7、系統(tǒng)其它文件操作其它文件操作為了方便用戶使用文件，通常，為了方便用戶使用文件，通常，OSOS都提供了數(shù)條有關(guān)文件操都提供了數(shù)條有關(guān)文件操作的系統(tǒng)調(diào)用，可將這些調(diào)用分成若干類作的系統(tǒng)調(diào)用，可將這些調(diào)用分成若干類: : 最常用的一類是有最常用的一類是有關(guān)對文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的關(guān)對文件屬性進(jìn)行操作的，即允許用戶直接設(shè)置和獲得文件的屬性，如改變已存文件的文件名、改變文件的擁有者屬性，如改變已存文件的文件名、改變文件的擁有者( (文件主文件主) )、改變對文件的訪問權(quán)，以及查詢文件的狀態(tài)改變對文件的訪問權(quán)，以及查詢文件的狀態(tài)( (包括文件類型、包括文件類型、大小和擁有者以及

8、對文件的訪問權(quán)等大小和擁有者以及對文件的訪問權(quán)等) )；另一類是有關(guān)目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改另一類是有關(guān)目錄的，如創(chuàng)建一個目錄，刪除一個目錄，改變當(dāng)前目錄和工作目錄等；此外，還有用于實現(xiàn)文件共享的系變當(dāng)前目錄和工作目錄等；此外，還有用于實現(xiàn)文件共享的系統(tǒng)調(diào)用和用于對文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。統(tǒng)調(diào)用和用于對文件系統(tǒng)進(jìn)行操作的系統(tǒng)調(diào)用等。 2022-2-259一 文件與文件系統(tǒng)文件與文件系統(tǒng)文件記錄1記錄2記錄n數(shù)據(jù)項1數(shù)據(jù)項2數(shù)據(jù)項n圖圖1 1文件、記錄和數(shù)據(jù)項之間的層次關(guān)系示意圖文件、記錄和數(shù)據(jù)項之間的層次關(guān)系示意圖 2022-2-2510一 文件與文件系統(tǒng)文件與文件系統(tǒng)【

9、三三】文件系統(tǒng)文件系統(tǒng)文件系統(tǒng)定義文件系統(tǒng)定義OSOS中與管理文件的軟件和數(shù)據(jù)的集合稱為文件中與管理文件的軟件和數(shù)據(jù)的集合稱為文件系統(tǒng)。其主要功能包括系統(tǒng)。其主要功能包括文件的建立、撤銷、修改、刪除、復(fù)制、移文件的建立、撤銷、修改、刪除、復(fù)制、移動、訪問權(quán)限與存取控制、檢索等：動、訪問權(quán)限與存取控制、檢索等：文件系統(tǒng)功能文件系統(tǒng)功能1.1.為了合理的存放文件，必需對磁盤等輔助存儲器空間為了合理的存放文件，必需對磁盤等輔助存儲器空間 ( (或稱文或稱文件空間件空間) ) 進(jìn)行統(tǒng)一管理。在用戶創(chuàng)建新文件時為其分配空閑區(qū)，進(jìn)行統(tǒng)一管理。在用戶創(chuàng)建新文件時為其分配空閑區(qū)，而在用戶刪除或修改某個文件時，

10、回收和調(diào)整存儲區(qū)。而在用戶刪除或修改某個文件時，回收和調(diào)整存儲區(qū)。2.2.為實現(xiàn)按名存取，需要有一個用戶可見的文件邏輯結(jié)構(gòu)，用戶為實現(xiàn)按名存取，需要有一個用戶可見的文件邏輯結(jié)構(gòu)，用戶按照文件邏輯結(jié)構(gòu)所給定的方式進(jìn)行信息的存取和加工。這種按照文件邏輯結(jié)構(gòu)所給定的方式進(jìn)行信息的存取和加工。這種邏輯結(jié)構(gòu)是獨立于物理存儲設(shè)備的。邏輯結(jié)構(gòu)是獨立于物理存儲設(shè)備的。2022-2-2511一 文件與文件系統(tǒng)文件與文件系統(tǒng)3.3.文件在存儲設(shè)備上的存放順序，稱為文件的物理結(jié)構(gòu)。存儲結(jié)文件在存儲設(shè)備上的存放順序，稱為文件的物理結(jié)構(gòu)。存儲結(jié)構(gòu)的設(shè)計以便于信息存放和加工為目標(biāo)；構(gòu)的設(shè)計以便于信息存放和加工為目標(biāo)；4.

11、4.實現(xiàn)對文件信息的查找。實現(xiàn)對文件信息的查找。5.5.成文件的共享和提供保護(hù)功能。成文件的共享和提供保護(hù)功能。文件系統(tǒng)的特點文件系統(tǒng)的特點1.1.用戶接口友好，用戶只對文件進(jìn)行操作，而不管文件結(jié)構(gòu)和存用戶接口友好，用戶只對文件進(jìn)行操作，而不管文件結(jié)構(gòu)和存放的物理位置。放的物理位置。2.2.對文件按名存取，對用戶透明。對文件按名存取，對用戶透明。3.3.某些文件可以被多個用戶或進(jìn)程所共享。某些文件可以被多個用戶或進(jìn)程所共享。4.4.文件系統(tǒng)一般均可使用磁盤、光盤等大容量存儲介質(zhì)。文件系統(tǒng)一般均可使用磁盤、光盤等大容量存儲介質(zhì)。2022-2-2512一 文件與文件系統(tǒng)文件與文件系統(tǒng)文件系統(tǒng)的三個

12、模型文件系統(tǒng)的三個模型1.1. 最高層：文件系統(tǒng)的兩種類型接口最高層：文件系統(tǒng)的兩種類型接口命令接口命令接口 指作為用戶與文件系統(tǒng)交互的接口。指作為用戶與文件系統(tǒng)交互的接口。 如通過鍵如通過鍵盤輸入命令，與文件系統(tǒng)進(jìn)行交互。盤輸入命令，與文件系統(tǒng)進(jìn)行交互。程序接口程序接口用戶程序與文件系統(tǒng)的專用接口，一般通過專用用戶程序與文件系統(tǒng)的專用接口，一般通過專用的系統(tǒng)調(diào)用命令（函數(shù)接口）進(jìn)行銜接服務(wù)。的系統(tǒng)調(diào)用命令（函數(shù)接口）進(jìn)行銜接服務(wù)。圖2文件系統(tǒng)模型文件系統(tǒng)接口文件系統(tǒng)接口對對象操縱和管理的軟件集合對對象操縱和管理的軟件集合文件管理系統(tǒng)管理的對象及其屬性文件管理系統(tǒng)管理的對象及其屬性用戶（用戶（

13、程序程序）2022-2-2513一 文件與文件系統(tǒng)文件與文件系統(tǒng)2.2. 中間層：對對象操縱和管理的軟件集合：中間層：對對象操縱和管理的軟件集合：這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一這是文件管理系統(tǒng)的核心部分。文件系統(tǒng)的功能大多是在這一層實現(xiàn)的，其中包括層實現(xiàn)的，其中包括: : 對文件存儲空間、讀寫、文件目錄的管對文件存儲空間、讀寫、文件目錄的管理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對文件的理、用于將文件的邏輯地址轉(zhuǎn)換為物理地址的機(jī)制、對文件的管理，以及對文件的共享與保護(hù)等功能。管理，以及對文件的共享與保護(hù)等功能。3. 3. 最低層：文件管理系統(tǒng)管理的對象及其屬性：最

14、低層：文件管理系統(tǒng)管理的對象及其屬性：文件文件它作為文件管理的直接對象。它作為文件管理的直接對象。目錄目錄為方便用戶對文件的存取和檢索而配置的目錄，每個為方便用戶對文件的存取和檢索而配置的目錄，每個目錄項均有文件名及該文件所在的物理地址目錄項均有文件名及該文件所在的物理地址( (或指針或指針) )。磁盤磁盤( (磁帶磁帶) )存儲空間。存儲空間。2022-2-2514一 文件與文件系統(tǒng)文件與文件系統(tǒng)【四四】文件類型文件類型1.1.按用途劃分按用途劃分系統(tǒng)文件系統(tǒng)文件 只允許用戶調(diào)用執(zhí)行，禁止用戶進(jìn)行只允許用戶調(diào)用執(zhí)行，禁止用戶進(jìn)行R/WR/W訪問；訪問；用戶文件用戶文件 泛指由用戶編寫的源代碼

15、與數(shù)據(jù)文件，及其生成泛指由用戶編寫的源代碼與數(shù)據(jù)文件，及其生成的目標(biāo)文件、可執(zhí)行文件或。用戶將其委托的目標(biāo)文件、可執(zhí)行文件或。用戶將其委托OSOS進(jìn)行管理。進(jìn)行管理。庫文件庫文件 標(biāo)準(zhǔn)程序，函數(shù)等標(biāo)準(zhǔn)程序，函數(shù)等( (只能執(zhí)行不能修改只能執(zhí)行不能修改) )。 特殊文件特殊文件 指系統(tǒng)中的各類指系統(tǒng)中的各類I/OI/O設(shè)備，依據(jù)傳輸速度可分為設(shè)備，依據(jù)傳輸速度可分為塊設(shè)備文件和字符設(shè)備文件。前者用于磁盤或光盤等塊設(shè)備的塊設(shè)備文件和字符設(shè)備文件。前者用于磁盤或光盤等塊設(shè)備的I/O I/O 操作。后者用于終端、打印機(jī)等字符設(shè)備的操作。后者用于終端、打印機(jī)等字符設(shè)備的I/O I/O 操作。操作。202

16、2-2-2515一 文件與文件系統(tǒng)文件與文件系統(tǒng)2.2.按按訪問權(quán)限劃分按按訪問權(quán)限劃分R R文件文件 只讀文件；只讀文件；R/WR/W文件文件 可讀可寫文件；可讀可寫文件；E E文件文件 只能執(zhí)行的隱含文件；只能執(zhí)行的隱含文件；3.3.按邏輯結(jié)構(gòu)劃分按邏輯結(jié)構(gòu)劃分記錄文件記錄文件（結(jié)構(gòu)文件）（結(jié)構(gòu)文件） 由若干個相關(guān)記錄組成的文件；由若干個相關(guān)記錄組成的文件；流式文件流式文件（無結(jié)構(gòu)文件）（無結(jié)構(gòu)文件） 由一個字符流組成的文件；由一個字符流組成的文件； 4.4.按照物理結(jié)構(gòu)劃分按照物理結(jié)構(gòu)劃分連續(xù)存放的文件連續(xù)存放的文件 順序文件順序文件不連續(xù)存放的文件不連續(xù)存放的文件 指針鏈接文件、如鏈表

17、、索引文件；指針鏈接文件、如鏈表、索引文件；2022-2-2516一 文件與文件系統(tǒng)文件與文件系統(tǒng)5.5.按組織形式和處理方式分類按組織形式和處理方式分類普通文件普通文件 由由ASCIIASCII碼或二進(jìn)制碼組成的字符文件。一碼或二進(jìn)制碼組成的字符文件。一般用戶建立的源程序文件、數(shù)據(jù)文件、目標(biāo)代碼文件及操般用戶建立的源程序文件、數(shù)據(jù)文件、目標(biāo)代碼文件及操作系統(tǒng)自身代碼文件、庫文件、實用程序文件等都是普通作系統(tǒng)自身代碼文件、庫文件、實用程序文件等都是普通文件，通常存儲在外存儲設(shè)備上。文件，通常存儲在外存儲設(shè)備上。目錄文件目錄文件 由文件目錄組成，也由字符序列構(gòu)成，屬由文件目錄組成，也由字符序列構(gòu)

18、成，屬于系統(tǒng)文件，文件操作與普通文件一樣。其功能在于對文于系統(tǒng)文件，文件操作與普通文件一樣。其功能在于對文件目錄進(jìn)行管理，能夠快速對其它文件的信息進(jìn)行檢索。件目錄進(jìn)行管理，能夠快速對其它文件的信息進(jìn)行檢索。 2022-2-2517一 文件與文件系統(tǒng)文件與文件系統(tǒng)【五五】國內(nèi)外有關(guān)文件管理的學(xué)術(shù)派別觀點簡介國內(nèi)外有關(guān)文件管理的學(xué)術(shù)派別觀點簡介1.1.無定義派無定義派( (強(qiáng)調(diào)文件與強(qiáng)調(diào)文件與OS的整體性的整體性) )該派對文件的研究，側(cè)重于文件系統(tǒng)的實現(xiàn)，側(cè)重于考慮文件該派對文件的研究，側(cè)重于文件系統(tǒng)的實現(xiàn)，側(cè)重于考慮文件系統(tǒng)的客觀性、安全性和保護(hù)機(jī)制方面的研究。系統(tǒng)的客觀性、安全性和保護(hù)機(jī)制方

19、面的研究。 （Wodharer、Taunebaum、Menglier 學(xué)派）學(xué)派）2.2.定義派定義派( (強(qiáng)調(diào)文件與強(qiáng)調(diào)文件與OS可隔離性可隔離性) )系統(tǒng)定義派：系統(tǒng)定義派：該派的主要觀點是從系統(tǒng)角度對文件加以論述，該派的主要觀點是從系統(tǒng)角度對文件加以論述，強(qiáng)調(diào)文件的相對獨立性，主張把文件系統(tǒng)從強(qiáng)調(diào)文件的相對獨立性，主張把文件系統(tǒng)從os中從核心層剝中從核心層剝離出來。對外存進(jìn)行嚴(yán)格定義，突出強(qiáng)調(diào)了內(nèi)外存之間的關(guān)離出來。對外存進(jìn)行嚴(yán)格定義，突出強(qiáng)調(diào)了內(nèi)外存之間的關(guān)系及外存的物理結(jié)構(gòu)。系及外存的物理結(jié)構(gòu)。 ( (孟靜、徐甲同、羅宇孟靜、徐甲同、羅宇) )2022-2-2518一 文件與文件系統(tǒng)

20、文件與文件系統(tǒng)用戶定義派：用戶定義派： 該派強(qiáng)調(diào)了文件對用戶的重要性，如何滿足用該派強(qiáng)調(diào)了文件對用戶的重要性，如何滿足用戶需要對文件加以論述，強(qiáng)調(diào)了外殼命令功能的完整性和用戶需要對文件加以論述，強(qiáng)調(diào)了外殼命令功能的完整性和用戶操作的方便性。戶操作的方便性。( (湯子贏湯子贏 龐麗萍龐麗萍) ) 。 3.3. 研究派研究派( (實現(xiàn)派實現(xiàn)派) )：該派側(cè)重于文件系統(tǒng)的實現(xiàn)研究，擱置爭議，該派側(cè)重于文件系統(tǒng)的實現(xiàn)研究，擱置爭議，從解決問題的角度，如提高查找的速度、方法等。主要析解從解決問題的角度，如提高查找的速度、方法等。主要析解UNIXUNIX、 LinuxLinux。（孫玉芳、劉日升）。（孫玉

21、芳、劉日升）?！玖糠峙捎^點背景分派觀點背景1.1.文件和載體文件和載體( (內(nèi)外存內(nèi)外存) )有關(guān)；有關(guān)；2.2.文件和文件和I/OI/O設(shè)備有關(guān)；設(shè)備有關(guān)；3.3.文件和用戶有關(guān)；文件和用戶有關(guān)；4.4.文件和文件和OSOS有關(guān)有關(guān)以上為個人觀點，僅供參考！以上為個人觀點，僅供參考！二二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)2022-2-2520二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【一一】邏輯與結(jié)構(gòu)的絮語邏輯與結(jié)構(gòu)的絮語1.1.什么是邏輯？什么是邏輯？表示客觀事物發(fā)展的規(guī)律；表示客觀事物發(fā)展的規(guī)律；表示思維的規(guī)律性或規(guī)則；表示思維的規(guī)律性或規(guī)則；形式邏輯；形式邏輯；某種特殊理論、觀點或說法，如：誰先

22、控制海洋誰就將某種特殊理論、觀點或說法，如：誰先控制海洋誰就將控制世界?？刂剖澜纭Ｑ芯克季S形式及其規(guī)律的科學(xué)研究思維形式及其規(guī)律的科學(xué)。邏輯是什么？是客觀事物內(nèi)在之間的關(guān)系！邏輯是什么？是客觀事物內(nèi)在之間的關(guān)系！2022-2-2521二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)2.2. 結(jié)構(gòu)是什么？結(jié)構(gòu)是什么？ 結(jié)構(gòu)即是一種觀念形態(tài)，又是物質(zhì)的一結(jié)構(gòu)即是一種觀念形態(tài)，又是物質(zhì)的一種運動狀態(tài)種運動狀態(tài) ，是人們用來表達(dá)世界存在的形態(tài)和運動狀態(tài)的專，是人們用來表達(dá)世界存在的形態(tài)和運動狀態(tài)的專業(yè)術(shù)語。業(yè)術(shù)語。 3.3.文件的邏輯結(jié)構(gòu)釋疑文件的邏輯結(jié)構(gòu)釋疑 即文件的形態(tài)與變化狀態(tài)！文件即文件的形態(tài)與變化狀態(tài)！文件

23、的邏輯結(jié)構(gòu)是一種字符流形式。是一種無結(jié)構(gòu)的文件組織方式。的邏輯結(jié)構(gòu)是一種字符流形式。是一種無結(jié)構(gòu)的文件組織方式。無結(jié)構(gòu)的基本特征即反映了由字符組成的文件內(nèi)部之間的相互無結(jié)構(gòu)的基本特征即反映了由字符組成的文件內(nèi)部之間的相互關(guān)系，即邏輯關(guān)系，結(jié)構(gòu)形態(tài)。其基本特征是：關(guān)系，即邏輯關(guān)系，結(jié)構(gòu)形態(tài)。其基本特征是： 只有一個基本信息單位；只有一個基本信息單位；查找文件元素信息困難。查找文件元素信息困難。文件管理簡單，方便用戶操作文件管理簡單，方便用戶操作是一種是一種用戶可見的結(jié)構(gòu)。用戶可見的結(jié)構(gòu)。2022-2-2522二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【二二】文件的邏輯結(jié)構(gòu)類型文件的邏輯結(jié)構(gòu)類型有結(jié)構(gòu)文件有

24、結(jié)構(gòu)文件(記錄式結(jié)構(gòu)文件記錄式結(jié)構(gòu)文件)無結(jié)構(gòu)文件無結(jié)構(gòu)文件 只有1個記錄的字符流式文件，簡稱為流失文件1. 定長記錄文件的組織形式 順序文件；2. 變長記錄文件的組織形式 索引文件， 索引順序文件圖圖3 3：文件的邏輯結(jié)構(gòu)類型圖：文件的邏輯結(jié)構(gòu)類型圖2022-2-2523二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)1.1. 有結(jié)構(gòu)文件的類型（有結(jié)構(gòu)文件的類型（記錄式結(jié)構(gòu)文件）記錄式結(jié)構(gòu)文件）1 1）記錄絮語與類型記錄絮語與類型記錄是一個具有特定意義的信息單位，它由記錄自身的邏輯地址記錄是一個具有特定意義的信息單位，它由記錄自身的邏輯地址( (相相對位置對位置) )、及記錄名所對應(yīng)的一組屬性值所組成。、及

25、記錄名所對應(yīng)的一組屬性值所組成。記錄式結(jié)構(gòu)記錄式結(jié)構(gòu) 具有不同的排列方式，因而構(gòu)成兩種不同的邏輯結(jié)具有不同的排列方式，因而構(gòu)成兩種不同的邏輯結(jié)構(gòu)，即定長記錄結(jié)構(gòu)和定長記錄結(jié)構(gòu)。構(gòu)，即定長記錄結(jié)構(gòu)和定長記錄結(jié)構(gòu)。2)2) 定長記錄定長記錄所有記錄的長度都是等長的。定長記錄的處理方便、所有記錄的長度都是等長的。定長記錄的處理方便、開銷小，是目前被廣泛用于數(shù)據(jù)處理中的一種記錄格式。開銷小，是目前被廣泛用于數(shù)據(jù)處理中的一種記錄格式。 3) 3) 變長記錄變長記錄文件中各記錄的長度不等。原因是記錄中的數(shù)據(jù)項文件中各記錄的長度不等。原因是記錄中的數(shù)據(jù)項數(shù)大小長短并不一致，如論文中的題目、摘要、關(guān)鍵詞、內(nèi)容

26、等。數(shù)大小長短并不一致，如論文中的題目、摘要、關(guān)鍵詞、內(nèi)容等。記錄處理之前，其長度可知。記錄處理之前，其長度可知。2022-2-2524二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)2.2.無結(jié)構(gòu)文件無結(jié)構(gòu)文件流式文件流式文件源程序、可執(zhí)行文件、庫函數(shù)等，均為無結(jié)構(gòu)源程序、可執(zhí)行文件、庫函數(shù)等，均為無結(jié)構(gòu)的文件形式，即流式文件。其長度以字節(jié)為單位。的文件形式，即流式文件。其長度以字節(jié)為單位。對流式文件的訪問，則是采用讀對流式文件的訪問，則是采用讀/ /寫指針來指出寫指針來指出下一個要訪問的字符。下一個要訪問的字符。流式文件看做是只有一個流式文件看做是只有一個記錄的記錄式文件的一個特例。記錄的記錄式文件的一個

27、特例。2022-2-2525二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【三三】為快速查找定長記錄而組織文件形式為快速查找定長記錄而組織文件形式 順序文件順序文件1 1邏輯記錄的排序（邏輯記錄的排序（為了實現(xiàn)快速查找需要準(zhǔn)備的基礎(chǔ)知識）為了實現(xiàn)快速查找需要準(zhǔn)備的基礎(chǔ)知識）1 1）串結(jié)構(gòu)排序串結(jié)構(gòu)排序，記錄之間的順序與關(guān)鍵字無關(guān)。其排序通常按照，記錄之間的順序與關(guān)鍵字無關(guān)。其排序通常按照生成記錄的時間的次序進(jìn)行決定的。串結(jié)構(gòu)排序的文件查找記錄生成記錄的時間的次序進(jìn)行決定的。串結(jié)構(gòu)排序的文件查找記錄時由于每次都必須從頭開始，逐個記錄地查找，所以時由于每次都必須從頭開始，逐個記錄地查找，所以效率很低。效率很低。

28、2 2）順序結(jié)構(gòu)排序，順序結(jié)構(gòu)排序，按照關(guān)鍵字按照關(guān)鍵字( (詞詞) )的長短從小到，或從大到小，的長短從小到，或從大到小，或按照其英文字母的順序?qū)⒂涗浥判虻慕Y(jié)構(gòu)，稱為順序結(jié)構(gòu)排序?；虬凑掌溆⑽淖帜傅捻樞?qū)⒂涗浥判虻慕Y(jié)構(gòu)，稱為順序結(jié)構(gòu)排序。 順序結(jié)構(gòu)文件，順序結(jié)構(gòu)文件，則可利用某種有效的查找算法，如折半查找則可利用某種有效的查找算法，如折半查找法、插值查找法、跳步查找法等，因為順序結(jié)構(gòu)文件具有較法、插值查找法、跳步查找法等，因為順序結(jié)構(gòu)文件具有較高的檢索效率，而被廣泛使用。高的檢索效率，而被廣泛使用。 2022-2-2526二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)2 2順序文件的讀順序文件的讀/ /寫

29、操作寫操作順序文件中的記錄可以是定長或變長的。對于定長記錄的順序文順序文件中的記錄可以是定長或變長的。對于定長記錄的順序文件，如果已知當(dāng)前記錄的邏輯地址。在讀一個文件時，設(shè)置一個件，如果已知當(dāng)前記錄的邏輯地址。在讀一個文件時，設(shè)置一個讀指針讀指針RptrRptr，令它指向下一個記錄的首地址，每當(dāng)讀完一個記錄，令它指向下一個記錄的首地址，每當(dāng)讀完一個記錄時，便執(zhí)行：時，便執(zhí)行：Rptr:=Rptr + L Rptr:=Rptr + L ，其中的，其中的L L為記錄長度。同樣在寫為記錄長度。同樣在寫一個文件時，也應(yīng)設(shè)置一個寫指針一個文件時，也應(yīng)設(shè)置一個寫指針WptrWptr，操作同上。，操作同上。

30、對于變長記錄的順序文件的對于變長記錄的順序文件的R/WR/W讀或?qū)懪c定長記錄時的情況基本讀或?qū)懪c定長記錄時的情況基本一樣，故略去不述。定長和變長記錄文件如圖一樣，故略去不述。定長和變長記錄文件如圖4 4所示：所示：3 3順序文件的優(yōu)缺點順序文件的優(yōu)缺點優(yōu)點：適于批量存取，存取效率最高。優(yōu)點：適于批量存取，存取效率最高。 缺點：查找指定記錄速度慢。七次是增加或刪除記錄比較困難。缺點：查找指定記錄速度慢。七次是增加或刪除記錄比較困難。2022-2-2527二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)R0R1R2R3RiLLLLLL2L3L4LiL(i1)LRptr(a) 定長記錄文件L0R0L1R1RiWpt

31、r(b ) 變長記錄文件Li00L0L01L1L0L12Li(Lk1)i1k0(Lk1)ik0圖圖4 4定長和變長記錄文件定長和變長記錄文件 2022-2-2528二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)對于定長記錄，順序文件查找速度最快！對于定長記錄，順序文件查找速度最快！對于不對于不 定長記錄，順序文件查找速度則最慢！定長記錄，順序文件查找速度則最慢！2022-2-2529二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【四四】為快速查找定長記錄而組織文件形式為快速查找定長記錄而組織文件形式 索引文件索引文件1. 1. 索引文件索引文件 對于變長度記錄，通常為之建立一張索引表，并為對于變長度記錄，通常為之建立一張

32、索引表，并為每個記錄設(shè)置一個記錄長度的表項，如，要查找第每個記錄設(shè)置一個記錄長度的表項，如，要查找第N N條記錄，即將前條記錄，即將前面的面的N-1N-1個記錄的長度求和，即可查到第個記錄的長度求和，即可查到第N N條記錄的首地址。條記錄的首地址。2.2. 索引順序文件索引順序文件 是索引文件的改進(jìn)，是索引文件的改進(jìn)，它基本思路是將順序文件它基本思路是將順序文件中的所有記錄分為若干個組中的所有記錄分為若干個組( (例如，例如，5050個記錄為一個組個記錄為一個組) )，為每組建，為每組建立一個組索引表，有多少組，就有多少個組索引表。其次為整個順立一個組索引表，有多少組，就有多少個組索引表。其次

33、為整個順序文件建立一張索引表，該表中僅有組號和每組中的首條記錄地址序文件建立一張索引表，該表中僅有組號和每組中的首條記錄地址建立一個索引項，由該表找到對應(yīng)的組索引表，再按照索引文件的建立一個索引項，由該表找到對應(yīng)的組索引表，再按照索引文件的方式可以很快查到要找的該記錄。如圖方式可以很快查到要找的該記錄。如圖6 6所示。所示。2022-2-2530二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)索引號0長度 m指針 ptrm01m1imi索引表R0R1Ri邏輯文件圖圖5 5索引文件的組織索引文件的組織 2022-2-2531二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)記錄記錄長度184275N132組號組號的首地址1842

34、6276A5NFFD2記錄記錄長度184275N132第1組索引表第1組索引表第N組索引表順序順序+索引索引1表表圖圖5 5：針對不定長記錄的索引順序文件組織表：針對不定長記錄的索引順序文件組織表 湯湯3 P2113 P211圖圖6-56-5是錯誤！是錯誤！2022-2-2532二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)百度百科中的鍵值說百度百科中的鍵值說注冊表中的鍵值就相當(dāng)于系統(tǒng)特有的數(shù)據(jù)庫種的某個關(guān)鍵字段，用特注冊表中的鍵值就相當(dāng)于系統(tǒng)特有的數(shù)據(jù)庫種的某個關(guān)鍵字段，用特定的方法調(diào)用，根據(jù)特有位置的鍵值，判斷程序應(yīng)該執(zhí)行的步驟。定的方法調(diào)用，根據(jù)特有位置的鍵值，判斷程序應(yīng)該執(zhí)行的步驟。鍵值位于注冊表結(jié)

35、構(gòu)鏈末端，它包含當(dāng)前執(zhí)行時用到的實際配置信息鍵值位于注冊表結(jié)構(gòu)鏈末端，它包含當(dāng)前執(zhí)行時用到的實際配置信息和數(shù)據(jù)，其數(shù)據(jù)類型可以是字符串、或二進(jìn)制值、或和數(shù)據(jù)，其數(shù)據(jù)類型可以是字符串、或二進(jìn)制值、或DWORDDWORD（雙字（雙字節(jié)），以適應(yīng)不同環(huán)境的使用需求。節(jié)），以適應(yīng)不同環(huán)境的使用需求。鍵值項是指顯示在鍵值項是指顯示在“注冊表編輯器注冊表編輯器”右側(cè)的項目，每個鍵值項包括名右側(cè)的項目，每個鍵值項包括名稱，類型和數(shù)據(jù)三部分。名稱由除反斜杠之外的任意字符組成。鍵稱，類型和數(shù)據(jù)三部分。名稱由除反斜杠之外的任意字符組成。鍵值項所定義的內(nèi)容即為該鍵值項的值，即值項所定義的內(nèi)容即為該鍵值項的值，即“鍵

36、值鍵值”，其中最多能存，其中最多能存放放64KB64KB大小的數(shù)據(jù)。大小的數(shù)據(jù)。 鍵的含鍵的含 用于標(biāo)識數(shù)據(jù)和控制數(shù)據(jù)的一個和幾個字符，稱為關(guān)鍵字。用于標(biāo)識數(shù)據(jù)和控制數(shù)據(jù)的一個和幾個字符，稱為關(guān)鍵字。 由用戶設(shè)置并操作，用于產(chǎn)生一組代碼或符號的由用戶設(shè)置并操作，用于產(chǎn)生一組代碼或符號的“一個按鍵一個按鍵”。O SO S 中 鍵中 鍵的 含 義的 含 義2022-2-2533二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【五五】直接文件與直接文件與哈希哈希(Hash)文件文件 直接到物理地址中可以訪問的文件簡稱為直接到物理地址中可以訪問的文件簡稱為直接文件！直接文件！根據(jù)給定的記錄根據(jù)給定的記錄鍵值，直接獲得

37、指定記錄的物理地址。這種由記錄鍵值到記錄物理地鍵值，直接獲得指定記錄的物理地址。這種由記錄鍵值到記錄物理地址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換。址的轉(zhuǎn)換被稱為鍵值轉(zhuǎn)換。哈希哈希(Hash)(Hash)文件文件 是目前應(yīng)用最為廣泛的一種是目前應(yīng)用最為廣泛的一種直接文件直接文件。它利用它利用HashHash函數(shù)函數(shù)( (或稱散列函數(shù)或稱散列函數(shù)) )，可將記錄，可將記錄鍵值鍵值轉(zhuǎn)換為相應(yīng)記錄轉(zhuǎn)換為相應(yīng)記錄的地址。但為了實現(xiàn)文件存儲空間的動態(tài)分配，通常由的地址。但為了實現(xiàn)文件存儲空間的動態(tài)分配，通常由HashHash函數(shù)函數(shù)指向一目錄表相應(yīng)表目的指向一目錄表相應(yīng)表目的指針指針，找到指向相應(yīng)記錄的物理塊，找到指向相

38、應(yīng)記錄的物理塊，通常，把通常，把HashHash函數(shù)作為標(biāo)準(zhǔn)函數(shù)存于系統(tǒng)中，供存取文件時調(diào)用。函數(shù)作為標(biāo)準(zhǔn)函數(shù)存于系統(tǒng)中，供存取文件時調(diào)用。 2022-2-2534二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)fHash函數(shù)目錄表鍵值圖6Hash文件的邏輯結(jié)構(gòu)示意圖 2022-2-2535二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【六六】有文件結(jié)構(gòu)的排列模式有文件結(jié)構(gòu)的排列模式 1.1. 連續(xù)模式結(jié)構(gòu)連續(xù)模式結(jié)構(gòu)：按照記錄生成的先后順序排列：按照記錄生成的先后順序排列有利于記錄追加和變更；有利于記錄追加和變更；搜索效率低。搜索效率低。2.2. 多重邏輯模式結(jié)構(gòu)：多重邏輯模式結(jié)構(gòu)：按照按照鍵鍵和記錄名排列成行、列式的一

39、種結(jié)構(gòu)；和記錄名排列成行、列式的一種結(jié)構(gòu)； 此種方法能夠?qū)崿F(xiàn)有效存儲，是非常重要的一種方法。此種方法能夠?qū)崿F(xiàn)有效存儲，是非常重要的一種方法。采用二維表的矩陣模式。采用二維表的矩陣模式。3.3. 轉(zhuǎn)置模式結(jié)構(gòu)：轉(zhuǎn)置模式結(jié)構(gòu)：為方便查找，把列、行進(jìn)行變換的一種結(jié)構(gòu)。為方便查找，把列、行進(jìn)行變換的一種結(jié)構(gòu)。4.4. 排序模式結(jié)構(gòu)：排序模式結(jié)構(gòu)：按照時間、字母等某種順序組織的記錄結(jié)構(gòu)按照時間、字母等某種順序組織的記錄結(jié)構(gòu)2022-2-2536二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【七七】實現(xiàn)文件邏輯結(jié)構(gòu)的原則實現(xiàn)文件邏輯結(jié)構(gòu)的原則 信息變動少；信息變動少； 查找速度快；查找速度快； 文件信息占據(jù)存儲空間最小

40、；文件信息占據(jù)存儲空間最??； 方便用戶操作。方便用戶操作。2022-2-2537二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【八八】文件的存取方法文件的存取方法通過對文件訪問實現(xiàn)文件的修改、追加和搜索等操作，方法有三：通過對文件訪問實現(xiàn)文件的修改、追加和搜索等操作，方法有三：1 1. . 順序存取法：順序存取法：按照文件的邏輯地址順序存取。按照文件的邏輯地址順序存取。2.2. 隨機(jī)存取法隨機(jī)存取法( (直接存取法直接存取法) )：根據(jù)記錄編號訪問文件的任一記錄，根據(jù)記錄編號訪問文件的任一記錄，或根據(jù)存取命令，通過移動指針的方法，實現(xiàn)對文件的讀寫訪問?；蚋鶕?jù)存取命令，通過移動指針的方法，實現(xiàn)對文件的讀寫訪問

41、。3.3. 按鍵存取法（按鍵存取法（表格搜索法）表格搜索法）：按鍵存取是一種用在復(fù)雜文件系統(tǒng)，按鍵存取是一種用在復(fù)雜文件系統(tǒng)，特別是數(shù)據(jù)庫管理系統(tǒng)中，根據(jù)給定的鍵或記錄名進(jìn)行存取的方特別是數(shù)據(jù)庫管理系統(tǒng)中，根據(jù)給定的鍵或記錄名進(jìn)行存取的方法。該方法首先搜索到訪問記錄的邏輯位置，再將其映射到相應(yīng)法。該方法首先搜索到訪問記錄的邏輯位置，再將其映射到相應(yīng)的物理地址后進(jìn)行存取。的物理地址后進(jìn)行存取。2022-2-2538二 文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)【九九】文件的文件的“鍵鍵”搜索算法搜索算法1. 1. 線性搜索法：線性搜索法：從第一個鍵或記錄開始，依次和所要搜索的鍵或記錄從第一個鍵或記錄開始，依次

42、和所要搜索的鍵或記錄相比較，直到找到所需要的記錄為止。線性搜索法的搜索效率較低，相比較，直到找到所需要的記錄為止。線性搜索法的搜索效率較低，在文件中記錄個數(shù)較多時不宜采用。在文件中記錄個數(shù)較多時不宜采用。2.2. 散列法：散列法：散列搜索法被被廣泛用于現(xiàn)代操作系統(tǒng)的數(shù)據(jù)查找。散列散列搜索法被被廣泛用于現(xiàn)代操作系統(tǒng)的數(shù)據(jù)查找。散列法的核心思想是定義一個散列函數(shù)法的核心思想是定義一個散列函數(shù)h(k)h(k)，使得對于給定的鍵，使得對于給定的鍵k k，散，散列函數(shù)列函數(shù)h(k)h(k)將其變換為將其變換為 k k所對應(yīng)的邏輯地址。所對應(yīng)的邏輯地址。3.3. 二分搜索法：二分搜索法：事先把搜索對象按一

43、定順序排列。該方法具有較高的事先把搜索對象按一定順序排列。該方法具有較高的搜索效率。適用于順序結(jié)構(gòu)排列的按照鍵或記錄來進(jìn)行搜索的一種搜索效率。適用于順序結(jié)構(gòu)排列的按照鍵或記錄來進(jìn)行搜索的一種方法。方法。2022-2-2539三三 文件的物理結(jié)構(gòu)與存儲設(shè)備文件的物理結(jié)構(gòu)與存儲設(shè)備 【一一】文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)是指文件在外存上的存放形式文件的物理結(jié)構(gòu)是指文件在外存上的存放形式1. 1. 放到什么介質(zhì)上？放到什么介質(zhì)上？2. 2. 用什么方法存放？用什么方法存放？3. 3. 以什么樣的形式存放？以什么樣的形式存放？4. 4. 怎樣存放是安全的？怎樣存放是安全的？5. 5. 訪問

44、速度與系統(tǒng)的吻合性？訪問速度與系統(tǒng)的吻合性？2022-2-2540三三 文件的物理結(jié)構(gòu)與存儲設(shè)備文件的物理結(jié)構(gòu)與存儲設(shè)備【二二】兩個相關(guān)四個定義兩個相關(guān)四個定義1.1. 兩個相關(guān)兩個相關(guān)文件的物理結(jié)構(gòu)和存儲設(shè)備密切相關(guān)。文件的物理結(jié)構(gòu)和存儲設(shè)備密切相關(guān)。文件的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)密切相關(guān)。文件的物理結(jié)構(gòu)與邏輯結(jié)構(gòu)密切相關(guān)。2.2. 四個定義四個定義物理文件物理文件外存中的存放文件，該文件可以外存中的存放文件，該文件可以R/WR/W訪問；訪問；邏輯文件邏輯文件內(nèi)存中的文件（可以修改的用戶文件）；內(nèi)存中的文件（可以修改的用戶文件）；物理結(jié)構(gòu)物理結(jié)構(gòu)文件在外存上的存放形式文件在外存上的存放形式( (連

45、續(xù)和串聯(lián)連續(xù)和串聯(lián)) )邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)在內(nèi)存上的虛擬存放形式：連續(xù)、順序、多重、在內(nèi)存上的虛擬存放形式：連續(xù)、順序、多重、轉(zhuǎn)置。轉(zhuǎn)置。2022-2-2541三三 文件的物理結(jié)構(gòu)與存儲設(shè)備文件的物理結(jié)構(gòu)與存儲設(shè)備【三三】物理上連續(xù)存儲結(jié)構(gòu)文件（在外存上）物理上連續(xù)存儲結(jié)構(gòu)文件（在外存上）在外存上連續(xù)存放的文件，稱之為連續(xù)文件或順序文件。在外存上連續(xù)存放的文件，稱之為連續(xù)文件或順序文件。優(yōu)點：優(yōu)點： 存儲簡單，存取速度快。存儲簡單，存取速度快。缺點：缺點： 不能總動態(tài)增長，要求用戶給定最大長度。不能總動態(tài)增長，要求用戶給定最大長度?！舅乃摹看?lián)結(jié)構(gòu)文件（又稱鏈結(jié)構(gòu)文件）串聯(lián)結(jié)構(gòu)文件（又稱鏈結(jié)構(gòu)文

46、件）物理塊：物理塊：512B 512B 8KB 8KB，適用于磁帶機(jī)順序存取。，適用于磁帶機(jī)順序存取。優(yōu)點：優(yōu)點： 文件可實現(xiàn)動態(tài)增長，通過改變指針即可以實現(xiàn)信息塊文件可實現(xiàn)動態(tài)增長，通過改變指針即可以實現(xiàn)信息塊的插入或刪除。的插入或刪除。缺點：缺點： 搜索速度慢，不適宜隨機(jī)存取。搜索速度慢，不適宜隨機(jī)存取。2022-2-2542三三 文件的物理結(jié)構(gòu)與存儲設(shè)備文件的物理結(jié)構(gòu)與存儲設(shè)備【五五】外存文件索引法外存文件索引法將多個文件建立一張索引表。將多個文件建立一張索引表。文件控制塊文件控制塊（FCBFCB）中給出索引表的首指針。中給出索引表的首指針。【六六】索引表的多重索引結(jié)構(gòu)索引表的多重索引結(jié)

47、構(gòu)文件索引方法效率低下的原因：文件過大，索引表大文件索引方法效率低下的原因：文件過大，索引表大解決方法解決方法1 1；將索引表的物理塊用串聯(lián)的方式加以連接，但搜索效將索引表的物理塊用串聯(lián)的方式加以連接，但搜索效率低，花費時間多。率低，花費時間多。解決方法解決方法2 2；通過建立多重索引結(jié)構(gòu)解決通過建立多重索引結(jié)構(gòu)解決（張三版（張三版P188P188）索引表置于內(nèi)存；索引表置于內(nèi)存；直接尋址與混合尋址結(jié)構(gòu)。直接尋址與混合尋址結(jié)構(gòu)。2022-2-2543三三 文件的物理結(jié)構(gòu)與存儲設(shè)備文件的物理結(jié)構(gòu)與存儲設(shè)備【七七】文件的直接存取設(shè)備文件的直接存取設(shè)備1.1.硬盤：硬盤：表面劃分為表面劃分為20-1

48、50020-1500個同心圓，每個圓周稱為一個磁道；個同心圓，每個圓周稱為一個磁道；信息只能依序（線性）記錄在每個磁道上；信息只能依序（線性）記錄在每個磁道上； 20-150020-1500個磁道；每個磁道個磁道；每個磁道4-324-32個扇區(qū)；個扇區(qū)； 每個扇區(qū)的大小（既一個弧段），每個扇區(qū)的大?。纫粋€弧段），256-512KB256-512KB；一個扇區(qū)叫一個物理塊；扇區(qū)是硬件設(shè)定的最小存取和尋址單位一個扇區(qū)叫一個物理塊；扇區(qū)是硬件設(shè)定的最小存取和尋址單位2.2.磁盤系統(tǒng)：磁盤系統(tǒng)：盤片；磁臂，磁頭，相關(guān)邏輯電路，主機(jī)通信接口等盤片；磁臂，磁頭，相關(guān)邏輯電路，主機(jī)通信接口等3.3.磁盤訪

49、問時間（通過磁盤訪問時間（通過DMADMA實現(xiàn)）實現(xiàn)）尋道時間尋道時間 尋找磁盤的時間；尋找磁盤的時間；延遲時間延遲時間 訪問扇區(qū)時間；訪問扇區(qū)時間；傳送時間傳送時間 外存到內(nèi)存的時間。外存到內(nèi)存的時間。 2022-2-2544四四 文件的存儲空間管理文件的存儲空間管理導(dǎo)言導(dǎo)言: :有效地進(jìn)行存儲空間管理，才能保證多個用戶有效地進(jìn)行存儲空間管理，才能保證多個用戶共享文件存儲設(shè)備和實現(xiàn)按名存取共享文件存儲設(shè)備和實現(xiàn)按名存取。由于文件存儲設(shè)備是。由于文件存儲設(shè)備是分成若干個大小相等的物理塊，并以塊為單位來交換信息分成若干個大小相等的物理塊，并以塊為單位來交換信息的，因此，文件存儲空間的管理實質(zhì)上是

50、一個空閑塊的組的，因此，文件存儲空間的管理實質(zhì)上是一個空閑塊的組織和管理問題，它包括織和管理問題，它包括空閑塊的組織空閑塊的組織，空閑塊的分配空閑塊的分配與與空空閑塊的回收閑塊的回收等幾個問題。等幾個問題。2022-2-2545四四 文件的存儲空間管理文件的存儲空間管理【一一】空閑文件目錄表空閑文件目錄表 文件名（號）文件名（號）空閑區(qū)號空閑區(qū)號空閑塊數(shù)空閑塊數(shù)空閑塊始地址空閑塊始地址11*H22*H2022-2-2546四四 文件的存儲空間管理文件的存儲空間管理【一一】空閑文件目錄表（續(xù)）空閑文件目錄表（續(xù)）系統(tǒng)為文件分配空閑塊時，若有合適空閑區(qū)則分配，并改寫空閑文件系統(tǒng)為文件分配空閑塊時，

51、若有合適空閑區(qū)則分配，并改寫空閑文件目錄表。否則，把空閑目錄中另一空閑區(qū)也分配給申請者目錄表。否則，把空閑目錄中另一空閑區(qū)也分配給申請者( (連續(xù)文件連續(xù)文件結(jié)構(gòu)除外結(jié)構(gòu)除外) )。若分配的空閑區(qū)項塊數(shù)大于申請者要求，則按實際需求。若分配的空閑區(qū)項塊數(shù)大于申請者要求，則按實際需求分配后，并對該表項進(jìn)行修改。分配后，并對該表項進(jìn)行修改。若一個文件被刪除，則釋放相應(yīng)的存儲物理塊，系統(tǒng)則將被釋放的塊若一個文件被刪除，則釋放相應(yīng)的存儲物理塊，系統(tǒng)則將被釋放的塊號、長度以及第一塊塊號等信息，置入空閑文件目錄。號、長度以及第一塊塊號等信息，置入空閑文件目錄。空閑文件項方法適用于空閑文件項方法適用于連續(xù)文件

52、結(jié)構(gòu)連續(xù)文件結(jié)構(gòu)的文件存儲區(qū)的分配與回收的文件存儲區(qū)的分配與回收。問問? 空閑區(qū)連續(xù)嗎空閑區(qū)連續(xù)嗎? 塊的大小塊的大小=? 分配標(biāo)志分配標(biāo)志? 回收回收?2022-2-2547四四 文件的存儲空間管理文件的存儲空間管理【二二】空閑塊鏈方法空閑塊鏈方法1. 1. 思路思路：將所有空閑塊鏈接在一起，當(dāng)申請空閑塊時，分配程序從鏈將所有空閑塊鏈接在一起，當(dāng)申請空閑塊時，分配程序從鏈頭開始摘取所需要的空閑塊，然后調(diào)整鏈?zhǔn)字羔槨７粗?，?dāng)回收空頭開始摘取所需要的空閑塊，然后調(diào)整鏈?zhǔn)字羔?。反之，?dāng)回收空閑塊時，把釋放的空閑塊逐個插入鏈尾上。閑塊時，把釋放的空閑塊逐個插入鏈尾上。2. 2. 空閑塊鏈接方法空閑塊鏈接方法（因系統(tǒng)而異）（因系統(tǒng)而異）1 1）按空閑區(qū)大小順序鏈接的方法；按空閑區(qū)大小順序鏈接的方法；2 2）按釋放先后順序鏈接的方法；按釋放先后順序鏈接的方法；3 3）按成組鏈接法