文件管理-----第二篇

1、Operating SystemOperating SystemPage 12021-7-3 Operating SystemOperating SystemPage 22021-7-3 q文件和文件系統(tǒng)文件和文件系統(tǒng) q文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu) q外存分配方式外存分配方式 q目錄管理目錄管理 q文件存儲(chǔ)空間的管理文件存儲(chǔ)空間的管理 q文件共享與文件保護(hù)文件共享與文件保護(hù) q數(shù)據(jù)一致性控制數(shù)據(jù)一致性控制 Operating SystemOperating SystemPage 32021-7-3 q文件邏輯結(jié)構(gòu)的類(lèi)型文件邏輯結(jié)構(gòu)的類(lèi)型 q順序文件順序文件 q索引文件索引文件 q索引順序文件

2、索引順序文件 q直接文件和哈希文件直接文件和哈希文件 Operating SystemOperating SystemPage 42021-7-3 q文件組織的兩種觀點(diǎn)文件組織的兩種觀點(diǎn) v用戶(hù)觀點(diǎn)用戶(hù)觀點(diǎn)（邏輯結(jié)構(gòu)）：研究的是用戶(hù)思維中的（邏輯結(jié)構(gòu)）：研究的是用戶(hù)思維中的 抽象文件，也叫邏輯文件。其目的是為用戶(hù)提供抽象文件，也叫邏輯文件。其目的是為用戶(hù)提供 一種結(jié)構(gòu)清晰、使用簡(jiǎn)便的邏輯組織。用戶(hù)按此一種結(jié)構(gòu)清晰、使用簡(jiǎn)便的邏輯組織。用戶(hù)按此 去存儲(chǔ)、檢索和加工處理有關(guān)文件信息。去存儲(chǔ)、檢索和加工處理有關(guān)文件信息。 v實(shí)現(xiàn)觀點(diǎn)實(shí)現(xiàn)觀點(diǎn)（物理結(jié)構(gòu)）：研究的是存儲(chǔ)在物理設(shè)（物理結(jié)構(gòu)）：研究的是存儲(chǔ)

3、在物理設(shè) 備介質(zhì)上的實(shí)際文件，即物理文件。其目的是選備介質(zhì)上的實(shí)際文件，即物理文件。其目的是選 擇一些性能良好、設(shè)備利用率高的物理結(jié)構(gòu)。系擇一些性能良好、設(shè)備利用率高的物理結(jié)構(gòu)。系 統(tǒng)按此和外部設(shè)備打交道，控制信息的傳輸。統(tǒng)按此和外部設(shè)備打交道，控制信息的傳輸。 q對(duì)邏輯結(jié)構(gòu)的要求對(duì)邏輯結(jié)構(gòu)的要求 v提高檢索速度提高檢索速度 v便于修改便于修改 v降低文件的存儲(chǔ)費(fèi)用降低文件的存儲(chǔ)費(fèi)用 Operating SystemOperating SystemPage 52021-7-3 q有結(jié)構(gòu)文件有結(jié)構(gòu)文件 記錄式文件記錄式文件 v按記錄長(zhǎng)度分按記錄長(zhǎng)度分 定長(zhǎng)記錄定長(zhǎng)記錄 變長(zhǎng)記錄變長(zhǎng)記錄 v根據(jù)用

4、戶(hù)和系統(tǒng)管理需要分根據(jù)用戶(hù)和系統(tǒng)管理需要分 順序文件順序文件 索引文件索引文件 索引順序文件索引順序文件 q無(wú)結(jié)構(gòu)文件無(wú)結(jié)構(gòu)文件 v流式文件流式文件 其長(zhǎng)度以字節(jié)為單位其長(zhǎng)度以字節(jié)為單位 v采用讀寫(xiě)指針來(lái)指出下一個(gè)要訪問(wèn)的字符采用讀寫(xiě)指針來(lái)指出下一個(gè)要訪問(wèn)的字符 v如如 源程序、源程序、 可執(zhí)行文件、可執(zhí)行文件、 庫(kù)函數(shù)庫(kù)函數(shù)等等 Operating SystemOperating SystemPage 62021-7-3 6.1.2 文件類(lèi)型和文件系統(tǒng)模型文件類(lèi)型和文件系統(tǒng)模型 1. 文件類(lèi)型文件類(lèi)型 （1）。這是由若干個(gè)記錄所構(gòu)成的文件，故又這是由若干個(gè)記錄所構(gòu)成的文件，故又 稱(chēng)為稱(chēng)為。根

5、據(jù)記錄的長(zhǎng)度是定長(zhǎng)的還是可改變的。根據(jù)記錄的長(zhǎng)度是定長(zhǎng)的還是可改變的 又可進(jìn)一步分為定長(zhǎng)記錄文件和可變長(zhǎng)記錄文件。又可進(jìn)一步分為定長(zhǎng)記錄文件和可變長(zhǎng)記錄文件。 （2）。直接由字符序列所構(gòu)成的文件，故稱(chēng)為直接由字符序列所構(gòu)成的文件，故稱(chēng)為 。 Operating SystemOperating SystemPage 72021-7-3 Operating SystemOperating SystemPage 82021-7-3 6.2.1 文件邏輯結(jié)構(gòu)的類(lèi)型文件邏輯結(jié)構(gòu)的類(lèi)型 1. 有結(jié)構(gòu)文件有結(jié)構(gòu)文件 ：文件中所有記錄的文件中所有記錄的的，所有記錄中的，所有記錄中 的各數(shù)據(jù)項(xiàng)，都處在相同的位置

6、，具有相同的順序和長(zhǎng)度。的各數(shù)據(jù)項(xiàng)，都處在相同的位置，具有相同的順序和長(zhǎng)度。 ：指文件中各記錄的指文件中各記錄的。 ：由一系列記錄按某種順序排列所形成的文件，其由一系列記錄按某種順序排列所形成的文件，其 中的記錄通常是中的記錄通常是。 ：當(dāng)記錄為當(dāng)記錄為時(shí)，通常為之建立一張索引表，時(shí)，通常為之建立一張索引表， 并為每個(gè)記錄設(shè)置一張表項(xiàng)，以加快對(duì)記錄的檢索速度。并為每個(gè)記錄設(shè)置一張表項(xiàng)，以加快對(duì)記錄的檢索速度。 ：是是 ，它為文件建立，它為文件建立 一張索引表，為每一組記錄中的第一個(gè)記錄設(shè)置一個(gè)表項(xiàng)。一張索引表，為每一組記錄中的第一個(gè)記錄設(shè)置一個(gè)表項(xiàng)。 Operating SystemOpera

7、ting SystemPage 92021-7-3 q文件邏輯結(jié)構(gòu)的類(lèi)型文件邏輯結(jié)構(gòu)的類(lèi)型 q順序文件順序文件 q索引文件索引文件 q索引順序文件索引順序文件 q直接文件和哈希文件直接文件和哈希文件 Operating SystemOperating SystemPage 102021-7-3 q邏輯記錄的排序邏輯記錄的排序 v串結(jié)構(gòu)串結(jié)構(gòu) 各記錄之間的順序與關(guān)鍵字無(wú)關(guān)各記錄之間的順序與關(guān)鍵字無(wú)關(guān) 通常由時(shí)間來(lái)決定通常由時(shí)間來(lái)決定 存在問(wèn)題存在問(wèn)題 v順序結(jié)構(gòu)順序結(jié)構(gòu) 文件中的所有記錄按關(guān)鍵字文件中的所有記錄按關(guān)鍵字(詞詞)排列排列 記錄號(hào)記錄號(hào)學(xué)號(hào)學(xué)號(hào)姓名姓名性別性別出生時(shí)間出生時(shí)間 11趙

8、趙 23錢(qián)錢(qián) 34孫孫 45李李 56周周 620吳吳 Operating SystemOperating SystemPage 112021-7-3 q對(duì)對(duì)順序文件順序文件(Sequential File)的讀的讀/寫(xiě)操作寫(xiě)操作 R0 R1 R2 R3 Ri L L L L L L 2L 3L 4L L (i1)L Rptr (a) 定定長(zhǎng)長(zhǎng)記記錄錄文文件件 L0 R0 L1 R1 Ri Wptr (b)變變長(zhǎng)長(zhǎng)記記錄錄文文件件 Li 00 L0 L01 L1 L0L12 Li (Lk1) i1 k 0 (Lk1) i k 0 記錄長(zhǎng)度記錄長(zhǎng)度 記錄記錄 起始地址起始地址 Operating

9、 SystemOperating SystemPage 122021-7-3 q順序文件的優(yōu)缺點(diǎn)順序文件的優(yōu)缺點(diǎn) v優(yōu)點(diǎn)優(yōu)點(diǎn) 結(jié)構(gòu)簡(jiǎn)單，容易實(shí)現(xiàn)結(jié)構(gòu)簡(jiǎn)單，容易實(shí)現(xiàn) 順序文件的最佳應(yīng)用場(chǎng)合，是在對(duì)諸記錄進(jìn)行順序文件的最佳應(yīng)用場(chǎng)合，是在對(duì)諸記錄進(jìn)行 批量存取批量存取時(shí)，即每次要讀或?qū)懸淮笈涗洉r(shí)，即每次要讀或?qū)懸淮笈涗?只有順序文件才能存儲(chǔ)在磁帶上，并能有效地只有順序文件才能存儲(chǔ)在磁帶上，并能有效地 工作工作 v缺點(diǎn)缺點(diǎn) 如果用戶(hù)如果用戶(hù)(程序程序)要求要求查找或修改查找或修改單個(gè)記錄，單個(gè)記錄， 順順 序文件所表現(xiàn)出來(lái)的序文件所表現(xiàn)出來(lái)的性能就可能很差性能就可能很差 如果想如果想增加或刪除增加

10、或刪除一個(gè)記錄，一個(gè)記錄， 都比較困難都比較困難 （需（需移動(dòng)移動(dòng)大量數(shù)據(jù)）大量數(shù)據(jù)） 創(chuàng)建文件必須給出大小，不利于動(dòng)態(tài)增長(zhǎng)創(chuàng)建文件必須給出大小，不利于動(dòng)態(tài)增長(zhǎng) Operating SystemOperating SystemPage 132021-7-3 q文件邏輯結(jié)構(gòu)的類(lèi)型文件邏輯結(jié)構(gòu)的類(lèi)型 q順序文件順序文件 q索引文件索引文件 q索引順序文件索引順序文件 q直接文件和哈希文件直接文件和哈希文件 Operating SystemOperating SystemPage 142021-7-3 q對(duì)對(duì)定長(zhǎng)記錄定長(zhǎng)記錄文件，如果要查找第文件，如果要查找第i個(gè)記錄，個(gè)記錄， 可直可直 接根據(jù)下式

11、計(jì)算來(lái)獲得第接根據(jù)下式計(jì)算來(lái)獲得第i個(gè)記錄相對(duì)于第一個(gè)記個(gè)記錄相對(duì)于第一個(gè)記 錄首址的地址錄首址的地址 Ai = iL q對(duì)于對(duì)于可變長(zhǎng)度記錄可變長(zhǎng)度記錄的文件，要查找其第的文件，要查找其第i個(gè)記錄時(shí)，個(gè)記錄時(shí)， 須首先計(jì)算出該記錄的首地址，須首先計(jì)算出該記錄的首地址，Li為第為第i個(gè)記錄長(zhǎng)個(gè)記錄長(zhǎng) 度度 1 0 i i ii iLA Operating SystemOperating SystemPage 152021-7-3 索索引引號(hào)號(hào) 0 長(zhǎng)長(zhǎng)度度 m指指針針 ptr m0 1m1 - imi - 索索引引表表 R0 R1 - Ri - 邏邏輯輯文文件件 索引文件的組織索引文件的組織

12、索引本身是一個(gè)定長(zhǎng)記錄的順序文件，主文件中每個(gè)記錄在索引本身是一個(gè)定長(zhǎng)記錄的順序文件，主文件中每個(gè)記錄在 索引表中占一個(gè)表項(xiàng)，可采用快速查找算法，如字典索引表中占一個(gè)表項(xiàng)，可采用快速查找算法，如字典 Operating SystemOperating SystemPage 172021-7-3 6.2.3 索引文件索引文件 2、索引文件的檢索步驟：、索引文件的檢索步驟： （1）根據(jù)用戶(hù)提供的關(guān)鍵字，利用折半查找法去檢索索）根據(jù)用戶(hù)提供的關(guān)鍵字，利用折半查找法去檢索索 引表，從中找到相應(yīng)的表項(xiàng)；引表，從中找到相應(yīng)的表項(xiàng)； （2）再利用該表項(xiàng)中給出的指向記錄的指針值，去訪問(wèn)）再利用該表項(xiàng)中給出的指

13、向記錄的指針值，去訪問(wèn) 所需記錄。所需記錄。 （3）要向索引文件中增加一個(gè)記錄，便須對(duì)索引表進(jìn)行）要向索引文件中增加一個(gè)記錄，便須對(duì)索引表進(jìn)行 修改。修改。 3、優(yōu)點(diǎn)、優(yōu)點(diǎn) 檢索速度快，主要用于對(duì)信息處理的及時(shí)性要求較高檢索速度快，主要用于對(duì)信息處理的及時(shí)性要求較高 的場(chǎng)合。的場(chǎng)合。 4、缺點(diǎn)、缺點(diǎn) 存儲(chǔ)費(fèi)用高，因?yàn)槌酥魑募?，還需配置一張索引存儲(chǔ)費(fèi)用高，因?yàn)槌酥魑募猓€需配置一張索引 表，且每個(gè)記錄都有一個(gè)索引項(xiàng)。表，且每個(gè)記錄都有一個(gè)索引項(xiàng)。 Operating SystemOperating SystemPage 182021-7-3 q文件邏輯結(jié)構(gòu)的類(lèi)型文件邏輯結(jié)構(gòu)的類(lèi)型 q順序

14、文件順序文件 q索引文件索引文件 q索引順序文件索引順序文件 q直接文件和哈希文件直接文件和哈希文件 Operating SystemOperating SystemPage 192021-7-3 q索引順序文件（索引順序文件（Index Sequential File）是最是最 常見(jiàn)的一種邏輯文件組織形式，是常見(jiàn)的一種邏輯文件組織形式，是順序文件與索順序文件與索 引文件的結(jié)合引文件的結(jié)合 q克服了變長(zhǎng)記錄文件不便于直接存取的缺點(diǎn)，代克服了變長(zhǎng)記錄文件不便于直接存取的缺點(diǎn)，代 價(jià)也不太大價(jià)也不太大 q將順序文件中的所有記錄分為若干個(gè)將順序文件中的所有記錄分為若干個(gè)組組，為，為每組每組 中的第一

15、個(gè)記錄中的第一個(gè)記錄建立索引項(xiàng)，其中含有該記錄的建立索引項(xiàng)，其中含有該記錄的 鍵值及指向該記錄的指針鍵值及指向該記錄的指針 Operating SystemOperating SystemPage 202021-7-3 鍵鍵 An Qi Bao Rong Chen Lin 邏輯地址邏輯地址姓 名姓 名 An Qi An Kang 其它屬性其它屬性 Bao Rong 邏輯文件邏輯文件 索引順序文件索引順序文件 Operating SystemOperating SystemPage 212021-7-3 Operating SystemOperating SystemPage 222021-7-

16、3 q對(duì)順序文件檢索對(duì)順序文件檢索 v若記錄數(shù)據(jù)為若記錄數(shù)據(jù)為N，則檢索一條記錄時(shí)，最好的情況，則檢索一條記錄時(shí)，最好的情況 是第一條記錄即為所求；最壞的情況是最后一條是第一條記錄即為所求；最壞的情況是最后一條 記錄為所求；平均檢索記錄為所求；平均檢索N/2條記錄條記錄 q對(duì)索引文件檢索對(duì)索引文件檢索 v可采用折半查找等方法，平均查找可采用折半查找等方法，平均查找 條記錄條記錄 q對(duì)索引順序文件檢索對(duì)索引順序文件檢索 v索引文件與順序文件的結(jié)合索引文件與順序文件的結(jié)合 N 鍵值鍵值 15010025 20 12.5 Operating SystemOperating SystemPage 23

17、2021-7-3 6.2.4 索引順序文件索引順序文件 Operating SystemOperating SystemPage 242021-7-3 q文件邏輯結(jié)構(gòu)的類(lèi)型文件邏輯結(jié)構(gòu)的類(lèi)型 q順序文件順序文件 q索引文件索引文件 q索引順序文件索引順序文件 q直接文件和哈希文件直接文件和哈希文件 Operating SystemOperating SystemPage 252021-7-3 q鍵值轉(zhuǎn)換鍵值轉(zhuǎn)換(Key to address transformation) v由記錄鍵值到記錄物理地址的轉(zhuǎn)換由記錄鍵值到記錄物理地址的轉(zhuǎn)換 q直接文件直接文件 v根據(jù)給定的記錄鍵值，直接獲得指定記錄的物根據(jù)給定的記錄鍵值，直接獲得指定記錄的物 理地址理地址 q哈希哈希(Hash)文件文件 v利用哈希函數(shù)將記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地利用哈希函數(shù)將記錄鍵值轉(zhuǎn)換為相應(yīng)記錄的地 址址 Oper