1、2021/3/91 目前常用的外存分配方法有：目前常用的外存分配方法有：（1 1）連續組織方式）連續組織方式（2 2）鏈接組織方式）鏈接組織方式（3 3）索引組織方式）索引組織方式。8.1 外存的組織方式外存的組織方式2021/3/928.1.1連續組織方式連續組織方式要求為每一個文件分配一組相鄰接的盤塊。要求為每一個文件分配一組相鄰接的盤塊。把邏輯記錄中的記錄，順序地存儲到鄰接的各物把邏輯記錄中的記錄，順序地存儲到鄰接的各物理盤塊中，這樣形成的物理文件稱為理盤塊中，這樣形成的物理文件稱為順序文件順序文件。2021/3/9331145728242016128329131721252961014

2、1822263011151923270目錄目錄Filecounttrmaillistfstart01419286length23642圖圖8-1 磁盤空間的連續組織磁盤空間的連續組織8.1.1連續組織方式連續組織方式2021/3/94主要優點：主要優點：順序訪問容易。順序訪問容易。支持直接存取。支持直接存取。訪問速度快。訪問速度快。8.1.1連續組織方式連續組織方式要求有連續的存儲空間。要求有連續的存儲空間。必須事先知道文件的長度。必須事先知道文件的長度。不能靈活地刪除和插入記錄。不能靈活地刪除和插入記錄。不利于動態增長的文件。不利于動態增長的文件。主要缺點：主要缺點：2021/3/958.1

3、.2鏈接組織方式鏈接組織方式 Linked Allocation 鏈接組織方式鏈接組織方式消除了外部碎片消除了外部碎片，故可以顯著地，故可以顯著地提高提高外存空間的利用率外存空間的利用率，且，且無需事先知道文件長度無需事先知道文件長度。此。此外，文件的外，文件的插入、刪除，也十分方便插入、刪除，也十分方便。 這樣形成的物理文件稱為這樣形成的物理文件稱為鏈接文件鏈接文件。 鏈接方式又可分為鏈接方式又可分為隱式鏈接隱式鏈接和和顯式鏈接顯式鏈接兩種方式。兩種方式。2021/3/96在文件目錄的每個目錄項中，都須含有指向連接在文件目錄的每個目錄項中，都須含有指向連接文件第一個盤塊和最后一個盤塊的指針。

4、文件第一個盤塊和最后一個盤塊的指針。在每個盤塊中都含有一個指向下一個盤塊的指針。在每個盤塊中都含有一個指向下一個盤塊的指針。1. 隱式鏈接隱式鏈接 Implicit Link8.1.2鏈接組織方式鏈接組織方式2021/3/97221814106231272319151173048121620242815913172125293026目錄File start endjeep 9 25圖圖8-2磁盤空間的鏈接組織方式磁盤空間的鏈接組織方式1. 隱式鏈接隱式鏈接2021/3/98：只適合于順序訪問，對隨機訪問極其低效；通過鏈接指針將一大批離散的盤塊鏈接起來，可靠性差。 8.1.2鏈接組織方式鏈接組織

5、方式1. 隱式鏈接隱式鏈接2021/3/992.顯式鏈接顯式鏈接 Explicit Link 把用于鏈接文件物理塊的指針放在內存的一張鏈接表中。把用于鏈接文件物理塊的指針放在內存的一張鏈接表中。整個磁盤僅設置一張。整個磁盤僅設置一張。 表的序號是物理盤塊號。在每個表項中，存放鏈接指針。表的序號是物理盤塊號。在每個表項中，存放鏈接指針。 凡是屬于某一文件的第一個盤塊號，均作為文件地址被凡是屬于某一文件的第一個盤塊號，均作為文件地址被填入相應文件的填入相應文件的FCBFCB的的“物理地址物理地址”字段中。字段中。 此表為此表為（File Allocation Table) File Allocat

6、ion Table) 。8.1.2鏈接組織方式鏈接組織方式2021/3/910MS-DOS的文件物理結構的文件物理結構對于對于200MB200MB的硬盤，若盤的硬盤，若盤塊的大小為塊的大小為KB,KB,每個表項需每個表項需2.52.5個字節，個字節，故需占用故需占用500KB500KB。FCB A2.顯式鏈接顯式鏈接FCB BFAT01234567891011圖圖8-3 8-3 顯式鏈接方式顯式鏈接方式2021/3/911兩個問題：兩個問題：不能支持高效的直接存取。不能支持高效的直接存取。FATFAT需占用較大的內存空間。需占用較大的內存空間。2.顯式鏈接顯式鏈接2021/3/9121.單級索

7、引分配單級索引分配 索引分配方法索引分配方法為每個文件分配一索引塊（表）索引塊（表），把分配給該文件的所有盤塊號，都記錄在該索引塊中。在建立一個文件時，須在為之建立的目錄項中，填上指向該索引塊的指針。 這樣形成的物理文件稱為這樣形成的物理文件稱為鏈接文件鏈接文件。2021/3/913File 塊序號 jeep 19目錄91611025-1-1-119048121628242016312723191511732510141822263091317212529圖圖8-6 索引組織方式索引組織方式1.單級索引分配單級索引分配2021/3/9148.1.4 小結小結(1)連續組織方式連續組織方式 可隨機存取，訪問速度快，順序訪問容易。可隨機存取，訪問速度快，順序訪問容易。 要求連續存儲空間，需事先知道文件長度。要求連續存儲空間，需事先知道文件長度。(2)鏈接組織方式鏈接組織方式不要求連續存儲空間，插入刪除方便，無需知道文件不要求連續存儲空間，插入刪除方便，無需知道文件長度長度。隨機存取效率低，隨機存取效率低，FATFAT表占較大內存空間。表占較大內存空間。(3)索引分配方式索