計算機(jī)操作系統(tǒng)（第二版）課件：文件結(jié)構(gòu)

文件的結(jié)構(gòu)和存取文件邏輯結(jié)構(gòu)文件物理結(jié)構(gòu)文件存取難點

6.2.1文件的邏輯結(jié)構(gòu)1、解釋說明什么是邏輯結(jié)構(gòu)2、分析說明設(shè)計邏輯結(jié)構(gòu)要考慮的因素3、解釋說明文件邏輯結(jié)構(gòu)的分類4、有結(jié)構(gòu)文件的分類

（1）順序文件概念，如何檢索記錄？分析優(yōu)缺點？

（2）索引文件概念，如何檢索記錄？分析優(yōu)缺點？

（3）索引順序文件概念，如何檢索記錄？分析優(yōu)缺點？

（4）直接文件和散列文件概念，簡單分析優(yōu)缺點？6.2文件的結(jié)構(gòu)和存取

6.2.1文件的邏輯結(jié)構(gòu)設(shè)計原則操作手段簡單易用提高文件信息的檢索速度方便文件內(nèi)容的修改數(shù)據(jù)空間緊湊降低文件的存儲費(fèi)用系統(tǒng)靈活性姓名*手機(jī)號碼*郵箱6.2文件的結(jié)構(gòu)和存取

比如設(shè)計數(shù)據(jù)庫表時，為提高表中記錄檢索速度，你會怎么設(shè)計？對于經(jīng)常修改的表格，添加太多的索引有什么不好？比如SQLServer中兩種字段數(shù)據(jù)類型的區(qū)別：char、varchar

6.2.1文件的邏輯結(jié)構(gòu)2.分類有結(jié)構(gòu)文件：整個文件由若干條記錄構(gòu)成，也稱記錄式文件數(shù)據(jù)組織形式分成數(shù)據(jù)項、記錄和文件三級定長記錄文件與變長記錄文件數(shù)據(jù)庫文件：有結(jié)構(gòu)文件無結(jié)構(gòu)文件：由一組相關(guān)信息組成的有序字符流，也稱流式文件文件長度按字節(jié)計算。對流式文件的訪問，是用讀寫指針指出下一個要訪問的字符。-UNIX、DOS、WINDOWS系統(tǒng)中的文件都是流式文件。6.2文件的結(jié)構(gòu)和存取

6.2.1文件的邏輯結(jié)構(gòu)

6.2文件的結(jié)構(gòu)和存取

6.2.1文件的邏輯結(jié)構(gòu)（自學(xué)）3.有結(jié)構(gòu)文件分類順序文件索引文件索引順序文件直接文件和散列文件6.2文件的結(jié)構(gòu)和存取

有一個順序文件有1000000條記錄，平均查找的記錄數(shù)為500000個，采用索引順序文件結(jié)構(gòu)，則最好情況下平均只需查找（）個記錄。1000025000010005000ABCD提交單選題10分

6.2.2文件的物理結(jié)構(gòu)6.2文件的結(jié)構(gòu)和存取物理結(jié)構(gòu)連續(xù)結(jié)構(gòu)索引結(jié)構(gòu)鏈接結(jié)構(gòu)顯式鏈接隱示鏈接混合索引多級索引單極索引

6.2.2文件的物理結(jié)構(gòu)1、說明連續(xù)文件的概念2、分析連續(xù)文件的性能優(yōu)缺點3、說明鏈接文件的概念4、隱式鏈接文件的概念及性能優(yōu)缺點分析5、說明顯示鏈接文件的概念6、分析顯示鏈接文件性能優(yōu)缺點7、FAT文件系統(tǒng)深入分析：講授8、索引文件：引導(dǎo)講授6.2文件的結(jié)構(gòu)和存取

6.2.2文件的物理結(jié)構(gòu)1.連續(xù)文件連續(xù)文件又稱為順序文件，它是把邏輯文件中的信息順序地存放到一組相鄰接的磁盤塊中而形成的物理文件。6.2文件的結(jié)構(gòu)和存取主要優(yōu)點：順序訪問速度快可隨機(jī)存取主要缺點：磁盤空間會產(chǎn)生碎片文件修改困難

6.2.2文件的物理結(jié)構(gòu)1.連續(xù)文件6.2文件的結(jié)構(gòu)和存取文件名起始塊塊數(shù)count12tr144mail196list284f62

文件目錄項文件名物理地址1230567491011813141512171819162122232025262724list29303128mailcounttrf對于連續(xù)文件，目錄項中文件物理地址存什么內(nèi)容？連續(xù)文件的主要優(yōu)缺點有哪些？

6.2.2文件的物理結(jié)構(gòu)2.鏈接文件一個邏輯上連續(xù)的文件分散存放在多個不連續(xù)的磁盤塊中，再使用鏈接指針將這多個離散的磁盤塊鏈接起來，這樣形成的物理文件稱為鏈接文件（1）隱式鏈接6.2文件的結(jié)構(gòu)和存取主要缺點：文件只能順序存取文件容易丟失隱式鏈接文件的主要優(yōu)缺點有哪些？

6.2.2文件的物理結(jié)構(gòu)2.鏈接文件（2）顯式鏈接

所有鏈接指針統(tǒng)一存放在一張顯示的鏈接表(FAT，F(xiàn)ileAllocationTable，文件分配表)中。一個邏輯磁盤設(shè)置一張表，以物理盤塊號為序，表項內(nèi)容為指向某文件的下一盤塊的指針。6.2文件的結(jié)構(gòu)和存取主要缺點：FAT表占內(nèi)存空間FAT表較大時，隨機(jī)存取效率降低FAT32：0x0FFFFFFF如file1文件分配到2、4、6、1號盤塊主要優(yōu)點：檢索速度快支持隨機(jī)存取顯式鏈接文件的主要優(yōu)缺點有哪些？MS-DOS的文件物理結(jié)構(gòu)6EOF11105EOF0123456789FATFCBA4FCBB91011AB物理塊號文件A占據(jù)哪些磁盤塊？FAT表還可以表示磁盤空間的使用情況某文件系統(tǒng)采用隱式鏈接，文件f1占10個盤塊，假設(shè)該文件的目錄項在內(nèi)存中，則要讀取該文件的第6個塊，需要啟動()次磁盤I/O操作？12610ABCD提交單選題10分引導(dǎo)區(qū)FAT1FAT2根目錄區(qū)數(shù)據(jù)區(qū)FAT文件系統(tǒng)磁盤組織結(jié)構(gòu)：FAT32引導(dǎo)區(qū)主要內(nèi)容：

每扇區(qū)字節(jié)數(shù)；通常512B

每簇扇區(qū)數(shù)；

FAT1的位置；磁盤分區(qū)大?。ㄉ葏^(qū)數(shù)）Fat32數(shù)據(jù)區(qū)

FAT表大?。ㄉ葏^(qū)數(shù)）；根目錄位置；引導(dǎo)區(qū)備份扇區(qū)的位置；文件系統(tǒng)類型6.2.2文件的物理結(jié)構(gòu)2.鏈接文件6.2文件的結(jié)構(gòu)和存取FAT表大小的計算方法：例：一個磁盤分區(qū)大小為20GB，若盤塊大小為1KB，計算該磁盤分區(qū)的FAT表大小。分析：盤塊數(shù)=20GB/1KB=20M塊，則盤塊號大小為3.5B，

FAT表大小=20M×3.5B=70MB注意：早期每個磁盤塊號大小取半個字節(jié)的整數(shù)倍。一個磁盤分區(qū)大小為300GB，若盤塊大小為4KB，則該磁盤分區(qū)的FAT表大小為（）字節(jié)。300M500M262.5M545MABCD提交單選題10分6.2.2文件的物理結(jié)構(gòu)2.鏈接文件

6.2.2文件的物理結(jié)構(gòu)3.索引文件索引表：系統(tǒng)為每個文件建立一張索引表，每個邏輯塊占一個表項，以邏輯塊號為序，表項內(nèi)容為該邏輯塊所對應(yīng)的磁盤塊號。索引塊：存放索引表的盤塊。

索引文件：由數(shù)據(jù)文件和索引表構(gòu)成。6.2文件的結(jié)構(gòu)和存取文件file1分配到4個磁盤塊：10

15

30

40

1230索引表403302151100物理塊邏輯塊9索引塊40301510索引文件的基本概念或基本原理？索引文件的性能優(yōu)缺點？3.索引文件6.2.2文件的物理結(jié)構(gòu)（1）單級索引文件如File_A存放在10＃，17＃，2＃，11＃盤塊中，索引塊為20＃盤塊如果用戶現(xiàn)在要求訪問文件的第3個塊，系統(tǒng)應(yīng)如何找到這個塊的物理地址？即找到存放在哪個磁盤塊上。分析說明單級索引文件的實現(xiàn)原理？假設(shè)某文件系統(tǒng)磁盤塊大小為4KB，每個盤塊號4B，那么單級索引文件結(jié)構(gòu)能支持的最大文件是（）字節(jié)4K4000K4M無法計算ABCD提交單選題10分假設(shè)某文件系統(tǒng)磁盤塊大小為4KB，每個盤塊號4B，若一個文件為10MB，則其索引表大小為（）字節(jié)。10K10M4K無法計算ABCD提交單選題10分6.2.2文件的物理結(jié)構(gòu)3.索引文件（2）多級索引文件分析說明兩級和多級索引文件的實現(xiàn)原理？文件索引表多個一級索引塊二級索引塊三級索引塊兩級索引文件三級索引文件如果文件系統(tǒng)采用二級索引，盤塊大小為4KB，盤塊號為4B，現(xiàn)在要訪問文件File_A的第2000塊，應(yīng)該如何找到該塊的物理地址（盤塊號）？6.2.2文件的物理結(jié)構(gòu)3.索引文件（2）多級索引文件三級索引如果文件系統(tǒng)采用三級索引，磁盤塊大小為4KB，每個盤塊號4B，則能支持的最大文件是多少字節(jié)？答案發(fā)彈幕如果一個文件有4個塊，采用3級索引，要訪問文件的第3塊，需要啟動磁盤I/O多少次？（讀取一個磁盤塊就啟動磁盤I/O一次）答案發(fā)彈幕

UNIXsystemV：i節(jié)點中的物理地址字段iaddr(13):iaddr(0)～iaddr(9):直接地址iaddr(10)：一級索引iaddr(11):二級索引iaddr(12):三級索引設(shè)某文件長度為XB，若盤塊大小為4KB，每個盤塊號4B，則:（1）文件盤塊數(shù)量為：

n=[X/4k]+1（2）每個索引塊能存放的盤塊號數(shù)量：=4K/4=1K(個)6.2.2文件的物理結(jié)構(gòu)3.索引文件（2）混合索引文件Unix、Linux：直接地址，一級索引，二極索引，三級索引混合索引文件data…≤10個數(shù)據(jù)塊i節(jié)點

…iaddr(0)iaddr(1)

…iaddr(8)iaddr(9)iaddr(10)iaddr(11)iaddr(12)datadatadata（1）n≤10:

所有數(shù)據(jù)塊號全部存放在iaddr(0)～iaddr(9)中如果要訪問文件的第3個塊（假設(shè)從1開始計數(shù)），如何獲得其物理地址？文件名i節(jié)點指針文件目錄項混合索引文件(2)10＜n≤1034：iaddr(12)iaddr(11)iaddr(10)iaddr(9)iaddr(8)…iaddr(1)iaddr(0)…i節(jié)點…前10個…≤1024個數(shù)據(jù)塊…一級索引塊前面10個數(shù)據(jù)塊號全部存放在iaddr(0)～iaddr(9)中；剩下的不超過1024個數(shù)據(jù)塊號放在一個一級索引塊中；并將該一級索引塊號存入iaddr(10)中：剩下的1024個數(shù)據(jù)塊的塊號需要幾個一級索引塊來存放？混合索引文件(2)10＜n≤1034：iaddr(12)iaddr(11)iaddr(10)iaddr(9)iaddr(8)…iaddr(1)iaddr(0)…i節(jié)點…前10個…≤1024個數(shù)據(jù)塊…一級索引塊前面10個數(shù)據(jù)塊號全部存放在iaddr(0)～iaddr(9)中；剩下的不超過1024個數(shù)據(jù)塊號放在一個一級索引塊中；并將該一級索引塊號存入iaddr(10)中：如果要訪問文件的第3個塊（假設(shè)從1開始計數(shù)），如何獲得其物理地址？如果要訪問文件的第100個塊（假設(shè)從1開始計數(shù)），如何獲得其物理地址？混合索引文件一級索引塊1024個…前10個…≤1024+1M個數(shù)據(jù)塊…………1024個1024個二級索引塊≤1024個Iaddr(12)Iaddr(11)Iaddr(10)Iaddr(9)Iaddr(8)…Iaddr(1)Iaddr(0)…索引節(jié)點如果要訪問文件的第2000個塊（假設(shè)從1開始計數(shù)），如何獲得其物理地址？剩下的1024+1M個數(shù)據(jù)塊的塊號需要幾個一級索引塊來存放？(3)1034＜n≤1034+1M：前面10個數(shù)據(jù)塊號全部存放在iaddr(0)～iaddr(9)中剩下的不超過1024+1M個數(shù)據(jù)塊號放在不超過1025個一級索引塊第一個一級索引塊號存入iaddr(10)中；剩下的不超過1024個一級索引塊號存入一個二級索引塊中將該二級索引塊號存入iaddr(11)中混合索引文件iaddr(12)iaddr(11)iaddr(10)iaddr(9)iaddr(8)…iaddr(1)iaddr(0)…i節(jié)點…前10個…≤1024+1M+1G數(shù)據(jù)塊(3)1034+1M＜n≤1034+1M+1G前面10個數(shù)據(jù)塊號全部存放在iaddr(0)～iaddr(9)中剩下的1024+1M+1G個數(shù)據(jù)塊的塊號需要幾個一級索引塊來存放？一級索引塊1024個…≤1024+1M+1G個數(shù)據(jù)塊…………1024個1024個混合索引文件(3)1034+1M＜n≤1034+1M+1G剩下的不超過1024+1M+1G個數(shù)據(jù)塊號放在不超過1025+1M個一級索引塊中混合索引文件一級索引塊…1024個1024個1024個…1024個二級索引塊≤1025+1M個iaddr(12)iaddr(11)iaddr(10)iaddr(9)iaddr(8)…iaddr(1)iaddr(0)…i節(jié)點(3)1034+1M＜n≤1034+1M+1G將第一個一級索引塊號存入iaddr(10)中；剩下的不超過1024+1M個一級索引塊號存入≤1025個二級索引塊中混合索引文件…二級索引塊≤1025個≤1024個三級索引塊iaddr(12)iaddr(11)iaddr(10)iaddr(9)iaddr(8)…iaddr(1)iaddr(0)…i節(jié)點(3)1034+1M＜n≤1034+1M+1G再將第一個二級索引塊存入iaddr(11)中；剩下的不超過1024個二級索引塊號存入一個三級索引塊中；最后將該三級索引塊塊號存入iaddr(12)中：混合索引文件…前10個…

≤1024+1M+1G個數(shù)據(jù)塊……………一級索引塊1024個…1024個1024個1024個1024個1024個1024個1024個二級索引塊1024個1024個…Iaddr(12)Iaddr(11)Iaddr(10)Iaddr(9)Iaddr(8)…Iaddr(1)Iaddr(0)…i節(jié)點(3)1034+1M＜n≤1034+1M+1G：總結(jié)≤1024個三級索引塊采用這種文件結(jié)構(gòu)，若每個磁盤塊大小為4KB，每個磁盤塊號長度為4B，則文件系統(tǒng)能支持的最大文件是多大？結(jié)果發(fā)彈幕4TB（三級索引）+4GB（二級索引）+4MB（一級索引）+40KB（直接地址）4.文件物理結(jié)構(gòu)性能特點總結(jié)連續(xù)文件的優(yōu)點是不需要額外的空間開銷，只要在文件目錄中指出文件的大小和首塊的塊號即可，對順序的訪問效率很高。適應(yīng)于順序存取且文件不經(jīng)常修改的情況。缺點是文件動態(tài)地增長和縮小時系統(tǒng)開銷很大；文件創(chuàng)建時要求用戶提供文件的大??；存儲空間浪費(fèi)較大。鏈接文件克服了連續(xù)文件的不足之處，但文件的隨機(jī)訪問系統(tǒng)開銷較大。適應(yīng)于經(jīng)常順序訪問、經(jīng)常修改的文件。索引文件既適應(yīng)于順序訪問，也適應(yīng)于隨機(jī)訪問，是一種比較好的文件物理結(jié)構(gòu)，但要有用于索引表的空間開銷和文件索引的時間開銷。UNIX系統(tǒng)是使用索引結(jié)構(gòu)成功的例子。6.2.2文件的物理結(jié)構(gòu)哪個小組來總結(jié)下？例1：當(dāng)數(shù)據(jù)分別為以下使用要求時，應(yīng)選擇何種

物理文件組織方式，為什么？

（1）快速訪問，不經(jīng)常更新，經(jīng)常隨機(jī)訪問

（2）快速訪問，經(jīng)常更新，經(jīng)常按一定順序訪問；

（3）快速訪問，經(jīng)常更新，經(jīng)常隨機(jī)訪問。

6.2.2文件的物理結(jié)構(gòu)哪個小組來來分析下討論結(jié)果？存放在磁盤上的連續(xù)文件（?

）既可隨機(jī)訪問，又可順序訪問只能隨機(jī)訪問只能順序訪問順序訪問速度快ABCD提交多選題10分在文件系統(tǒng)中,文件的不同物理結(jié)構(gòu)有不同的優(yōu)缺點。在下列文件的物理結(jié)構(gòu)中,（）不具有直接讀寫文件任意一個記錄的能力。連續(xù)文件隱式鏈接顯式鏈接索引文件ABCD提交單選題10分如果一個文件存放在100個數(shù)據(jù)塊中，文件索引信息都在內(nèi)存中，如果不考慮索引信息的保存，則（）不需要做任何磁盤I/O操作。采用連續(xù)分配策略，將最后一個數(shù)據(jù)塊搬到文件頭部采用單級索引分配策略，將最后一個數(shù)據(jù)塊搬到文件頭部采用隱式鏈接分配策略，將最后一個數(shù)據(jù)塊搬到文件頭部采用隱式鏈接分配策略，將第一個數(shù)據(jù)塊插入文件尾部ABCD提交單選題10分為支持CD-ROM中視頻文件的快速隨機(jī)播放，播放性能最好的文件數(shù)據(jù)塊組織方式是（）連續(xù)結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)單級索引結(jié)構(gòu)多級索引結(jié)構(gòu)ABCD提交單選題10分例2：某文件系統(tǒng)采用單級索引文件結(jié)構(gòu)，假定文件索引表的每個表項占3個字節(jié)，存放一個磁盤塊的塊號（磁盤塊的大小為512B）。試問：1）該文件系統(tǒng)能支持的最大文件大小是多少字節(jié)？能管理的最大磁盤空間是多大？2）若采用2級或3級索引，該文件系統(tǒng)能支持的最大文件大小是多少字節(jié)？能管理的最大磁盤空間是多大？6.2.2文件的物理結(jié)構(gòu)分析1）由于索引表占用一個大小為512B的磁盤，所以該文件系統(tǒng)的索引表可以管理512/3=170個表項，而每一個表項對應(yīng)一個物理塊，因此該文件系統(tǒng)可以支持的最大文件為：170*512B=87040B=85K

能管理的最大磁盤空間：224*512B2）若采用二級索引，則是：170*170*512B=7225KB3）若采用三級索引，則是：170*170*170*512B=2456500KB=2398.93M例3：課后自行分析在磁盤上有一個文件系統(tǒng)，磁盤每塊512個字。在文件的目錄項中給出了文件名、第一個索引塊地址、文件長度（塊數(shù)）。在索引塊中（包含第一個索引塊）前面511個字指向文件塊，即第i個索引項（i=0,1，…，510）指向文件的i塊，索引塊中最后一個字指向下一個索引塊，最后一個索引塊中最后一個字為nil。假定目錄在內(nèi)存中，每個文件的邏輯塊均從0開始編號，邏輯塊長與物理塊長相同，對這樣的索引物理結(jié)構(gòu)，系統(tǒng)應(yīng)如何將邏輯塊號轉(zhuǎn)換成物理塊號？6.2.2文件的物理結(jié)構(gòu)例3