算法與數(shù)據(jù)結(jié)構(gòu)：第十二章 文件

1、數(shù)據(jù)結(jié)構(gòu)-第12章 文件1第十二章 文件12.1 文件的基本概念12.2 順序文件12.3 索引文件12.4 索引順序文件(ISAM文件和VSAM文件)12.5 直接存取文件(散列文件)12.6 多關(guān)鍵字文件本章學(xué)習(xí)重點(diǎn)、習(xí)題數(shù)據(jù)結(jié)構(gòu)-第12章 文件212.1 文件的基本概念12.1.1 文件的概念及其相關(guān)術(shù)語表 存儲(chǔ)在內(nèi)存中的大量記錄的集合。文件 存儲(chǔ)在外存中的大量記錄的集合。不同的范疇中，文件代表不同的意義操作系統(tǒng)中，文件是命名的無結(jié)構(gòu)的字節(jié)序列，其記錄的格式依需要可以靈活劃定。文件管理系統(tǒng)或數(shù)據(jù)庫系統(tǒng)中，文件是命名的性質(zhì)相同的邏輯記錄的集合，每個(gè)記錄由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。文件被放置在外存上

2、。數(shù)據(jù)結(jié)構(gòu)-第12章 文件3數(shù)據(jù)項(xiàng)（字段/屬性） 文件可使用的最小單位主關(guān)鍵字項(xiàng) 其值能唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)的組合；該值稱為主關(guān)鍵字。次關(guān)鍵字項(xiàng) 其值不能唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)；該值稱為次關(guān)鍵字。單關(guān)鍵字文件 文件的記錄只有主關(guān)鍵字多關(guān)鍵字文件 文件的記錄除有主關(guān)鍵字，還含有若干個(gè)次關(guān)鍵字定長(zhǎng)記錄文件 文件中每個(gè)記錄含有的信息長(zhǎng)度相同（所有數(shù)據(jù)項(xiàng)定長(zhǎng)）不定長(zhǎng)記錄文件 文件中每個(gè)記錄含有的信息長(zhǎng)度不一定相同數(shù)據(jù)結(jié)構(gòu)-第12章 文件412.1.2 文件的邏輯結(jié)構(gòu)及操作文件中記錄之間的邏輯關(guān)系 一般看作是線性關(guān)系文件上的主要操作 (1)檢索順序檢索：存取下一個(gè)邏輯記錄直接檢索：存取第i

3、個(gè)邏輯記錄按關(guān)鍵字檢索 簡(jiǎn)單詢問：查詢單個(gè)關(guān)鍵字等于給定值的記錄 范圍詢問：查詢單個(gè)關(guān)鍵字屬于某個(gè)范圍的所有記錄 函數(shù)詢問：規(guī)定單個(gè)關(guān)鍵字的某個(gè)函數(shù)，查詢函數(shù)的值 布爾詢問：以上三種詢問用布爾運(yùn)算(與、或、非)組 (2)修改 對(duì)記錄的插入、刪除，對(duì)記錄某些數(shù)據(jù)項(xiàng)的更新等文件操作的處理方式實(shí)時(shí)批量數(shù)據(jù)結(jié)構(gòu)-第12章 文件512.1.3 文件的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))物理記錄(頁塊)和邏輯結(jié)構(gòu)之間可能存在的關(guān)系一個(gè)物理記錄存放一個(gè)邏輯記錄一個(gè)物理記錄存放多個(gè)邏輯記錄多個(gè)物理記錄存放一個(gè)邏輯記錄文件的常用存儲(chǔ)結(jié)構(gòu)順序組織索引組織散列組織鏈組織12.1.4 文件操作實(shí)現(xiàn)的基本方法 內(nèi)外存交換以物理記錄為單

4、位內(nèi)存外存存取塊號(hào)數(shù)據(jù)結(jié)構(gòu)-第12章 文件612.2 順序文件12.2.1 順序文件的組織方式和特點(diǎn)組織方式 記錄在物理結(jié)構(gòu)中的排列順序與邏輯順序一致。連續(xù)文件：次序相繼的兩個(gè)物理記錄的存儲(chǔ)位置是相鄰的串聯(lián)文件：物理記錄之間次序由指針相鏈表示特點(diǎn) 根據(jù)記錄的序號(hào)或記錄的相對(duì)位置進(jìn)行存取。順序存取時(shí)效率較高。數(shù)據(jù)結(jié)構(gòu)-第12章 文件712.2.2 順序文件上的操作查找順序存取存儲(chǔ)器(磁帶)上的順序文件順序查找 為提高效率，適合于批量檢索。直接存取存儲(chǔ)器(磁盤)上的順序文件順序查找折半查找 適合于較小的有序定長(zhǎng)記錄文件的檢索。查找很大的文件時(shí)(多個(gè)柱面)，磁頭頻繁移動(dòng)，降低時(shí)效。分塊查找 先確定待

5、查關(guān)鍵字所在的塊，進(jìn)而在該塊中順序掃描。數(shù)據(jù)結(jié)構(gòu)-第12章 文件8插入、刪除和更新 由于文件的記錄不易于像內(nèi)存空間的數(shù)據(jù)那樣“移動(dòng)”，通常采用批量處理方式。事務(wù)文件 排序 有序的事務(wù)文件主文件新主文件修改請(qǐng)求原始文件 (有序)在一段時(shí)間內(nèi)使用的記錄數(shù)據(jù)結(jié)構(gòu)-第12章 文件912.3 索引文件12.3.1 索引文件的組織方式 主文件 + 索引表(按主關(guān)鍵字有序) 索引項(xiàng)的結(jié)構(gòu)： 關(guān)鍵字 物理塊號(hào)索引文件只能是磁盤文件索引順序文件：主文件中的記錄按主關(guān)鍵字有序索引非順序文件：主文件中的記錄按主關(guān)鍵字無序稠密索引：主要用于索引非順序文件 主文件中的每個(gè)記錄對(duì)應(yīng)一個(gè)索引項(xiàng)稀疏索引：用于索引順序文件 主

6、文件的每個(gè)頁塊對(duì)應(yīng)一個(gè)索引項(xiàng)數(shù)據(jù)結(jié)構(gòu)-第12章 文件1012.3.2 索引文件上的操作 前提：索引非順序文件，稠密索引查找1)將外存上存放索引文件的索引區(qū)頁塊讀入內(nèi)存，可采用順序或折半查找來查找記錄的物理記錄號(hào)(塊號(hào))2)再將外存上存放該記錄的數(shù)據(jù)區(qū)頁塊讀入內(nèi)存進(jìn)行查找修改插入：將插入的記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引項(xiàng)刪除：刪去相應(yīng)的索引項(xiàng)更新：若主關(guān)鍵字被修改，則需修改對(duì)應(yīng)的索引表項(xiàng)數(shù)據(jù)結(jié)構(gòu)-第12章 文件1112.3.3 多級(jí)索引 當(dāng)外存的一個(gè)頁塊不能容納下索引表時(shí)，通?？梢詾樗饕碓俳⒁粋€(gè)索引，稱為查找表；在此基礎(chǔ)上還可以建立第二查找表、第三查找表、例 主文件 索引表 查找

7、表物理記錄號(hào) 學(xué)號(hào) 姓名 其它 關(guān)鍵字 物理記錄號(hào) 最大 物理 101 07 王得 15 04 103 關(guān)鍵字 塊號(hào) 101 12 謝旺 07 101 12 15 103 04 陳明 12 101 44 16 103 44 胡建 16 22 104 104 37 劉流 37 104 104 22 鄭辰 44 103數(shù)據(jù)結(jié)構(gòu)-第12章 文件12特點(diǎn)為減少訪問外存次數(shù)，應(yīng)盡量減少索引表深度各級(jí)索引均為順序表，結(jié)構(gòu)簡(jiǎn)單；但修改不便，每次更新操作，可能都要重組索引，因此多級(jí)索引適合于靜態(tài)索引當(dāng)文件記錄變動(dòng)較多時(shí)，可采用適合于動(dòng)態(tài)索引的樹表結(jié)構(gòu)，如二叉排序樹、B-樹等形式數(shù)據(jù)結(jié)構(gòu)-第12章 文件1312

8、.4 索引順序文件 索引順序文件是最常用的一種文件組織形式主文件按關(guān)鍵字有序，可以有較高的檢索效率采用稀疏索引，索引占用空間較少12.4.1 ISAM(索引順序存取方法)文件專為磁盤存取文件設(shè)計(jì)的文件組織方式靜態(tài)索引結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)-第12章 文件14ISAM文件的組織方式多級(jí)主索引+柱面索引+磁道(盤面)索引+主文件 主索引 柱面索引 磁道索引 主文件R14 R21 R45 R50磁道索引T1 T2 T8 T9T10柱面C1溢出區(qū)R84 R88 R90 R91磁道索引T1 T2 T8 T9T10柱面C2溢出區(qū)50 T21 60 T92 R7979 C1T1R130130 C2T145087060

9、 53 T91數(shù)據(jù)結(jié)構(gòu)-第12章 文件15ISAM文件上的操作1）查找 讓主索引常駐內(nèi)存1)從主索引出發(fā)，確定相應(yīng)的柱面索引2)讀入柱面索引，確定記錄所在柱面的磁道索引地址3)讀入磁道索引，確定記錄所在的磁道4)在該磁道上查找 從磁道索引項(xiàng)的溢出索引項(xiàng)中得到溢出鏈表的頭指針查找2）插入1) 利用查找確定記錄應(yīng)插入的柱面和磁道2)該磁道不滿，則插入該磁道的適當(dāng)位置上，結(jié)束3)該磁道已滿，視插入記錄的關(guān)鍵字插入磁道，調(diào)整溢出鏈表和磁道索引直接插入溢出鏈表，調(diào)整磁道索引數(shù)據(jù)結(jié)構(gòu)-第12章 文件163）刪除1) 查找待刪除的記錄2)在基本區(qū)時(shí)，在其存儲(chǔ)位置上作刪除標(biāo)記 在溢出區(qū)時(shí)，可從鏈表中取消周期性

10、地集中整理ISAM文件，以保證空間利用率和存取效率。ISAM小結(jié)ISAM文件是一種多叉樹形的索引順序文件葉結(jié)點(diǎn)存放數(shù)據(jù)記錄，組成文件的數(shù)據(jù)區(qū)非葉結(jié)點(diǎn)組成文件的索引區(qū)文件在記錄插入和刪除時(shí)，索引結(jié)構(gòu)不變，是靜態(tài)索引結(jié)構(gòu)主索引和柱面索引在每次檢索時(shí)都需查找，宜放在文件所占的幾個(gè)柱面的居中的柱面上，使磁頭平均移動(dòng)距離最小。數(shù)據(jù)結(jié)構(gòu)-第12章 文件1712.4.2 VSAM(虛擬存儲(chǔ)存取方法)文件此存取方法與存儲(chǔ)設(shè)備無關(guān)B+樹(B-樹的變型)動(dòng)態(tài)索引結(jié)構(gòu)大型索引順序文件的標(biāo)準(zhǔn)，可應(yīng)用于數(shù)據(jù)庫文件VSAM文件的組織方式 59 97 15 44 59 72 97 10 15 20 37 44 51 59

11、63 72 85 91 975710111215sqtroot索引集B+樹順序集數(shù)據(jù)集控制區(qū)域(面)控制區(qū)間(道)數(shù)據(jù)結(jié)構(gòu)-第12章 文件18VSAM文件上的操作1）查找方法1：隨機(jī)查找。方法2：順序查找。2）插入 分為三種情況：所插入的控制區(qū)間未滿 將待插記錄插入合適的位置所插入的控制區(qū)間已滿，但其所在的控制區(qū)域有空閑控制區(qū)間 分裂該控制區(qū)間，將近乎一半的記錄移到全空的控制區(qū)間，并修改順序集中的相應(yīng)索引所插入的控制區(qū)域已滿 分裂控制區(qū)域，一般控制區(qū)域較大，此情況很少數(shù)據(jù)結(jié)構(gòu)-第12章 文件193）刪除 在一個(gè)控制區(qū)間內(nèi)，被刪記錄之后的記錄前移。若該控制區(qū)間變空，回收為空閑區(qū)間，并刪除順序集中

12、的相應(yīng)索引和ISAM文件相比的優(yōu)點(diǎn) 能保持較高的查找效率動(dòng)態(tài)地分配和釋放空間不必隨記錄的變動(dòng)對(duì)文件進(jìn)行再組織數(shù)據(jù)結(jié)構(gòu)-第12章 文件2012.5 直接存取文件（散列文件）12.5.1 散列文件的組織方式類似于散列表處理沖突主要采用拉鏈法桶：一個(gè)存儲(chǔ)單位(一塊/多塊)，可以存放若干個(gè)記錄基桶溢出桶裝載因子： =n/(bm) n：記錄數(shù) b：桶數(shù) m：桶容量0 063 184 1 589 008 5052 3 014 4 930 011 384320 007 123 089 基桶溢出桶桶號(hào)數(shù)據(jù)結(jié)構(gòu)-第12章 文件2112.5.2 散列文件上的操作查找1)由散列函數(shù)求出基桶地址2)將基桶讀入內(nèi)存順序

13、查找3)若未查到，讀入溢出桶繼續(xù)查找插入1)由散列函數(shù)求出基桶地址2)讀入基桶，若基桶未滿，直接插入3)若基桶已滿，但溢出桶有空，插入溢出桶 否則，指定溢出桶空間，插入刪除在被刪記錄上作刪除標(biāo)記數(shù)據(jù)結(jié)構(gòu)-第12章 文件2212.5.3 散列文件的優(yōu)缺點(diǎn)優(yōu)點(diǎn)文件記錄不必排序便于插入、刪除記錄存取速度快節(jié)省存儲(chǔ)空間缺點(diǎn)只能按關(guān)鍵字存取，詢問方式限于簡(jiǎn)單詢問多次插入、刪除記錄會(huì)造成文件結(jié)構(gòu)不合理，需重組文件數(shù)據(jù)結(jié)構(gòu)-第12章 文件2312.6 多關(guān)鍵字文件目的 方便對(duì)次關(guān)鍵字的查詢多關(guān)鍵字文件的概念 包含有多個(gè)次關(guān)鍵字索引的文件兩種主要的組織方式多重表文件倒排文件數(shù)據(jù)結(jié)構(gòu)-第12章 文件2412.6

14、.1 多重表文件組織方式 主文件(主關(guān)鍵字有序順序文件，含有一個(gè)或多個(gè)次關(guān)鍵字鏈表) +主關(guān)鍵字非稠密索引+ 一個(gè)或多個(gè)次關(guān)鍵字索引表 例 次關(guān)鍵字 頭指針 鏈長(zhǎng) 物理記錄號(hào) 學(xué)號(hào) 姓名 成績(jī) 性別 主關(guān)鍵字 頭指針 100 01 78 男 101 03 100 101 02 86 102 男 103 06 103 102 03 89 女 104 09 106 103 04 72 100 男 106 成績(jī) 性別 104 05 65 女 105 60 104 1 男 100 4 105 06 94 女 70 103 2 女 102 3 106 07 83 101 男 80 106 3 90 10

15、5 1數(shù)據(jù)結(jié)構(gòu)-第12章 文件25操作1）查找根據(jù)次關(guān)鍵字的索引，得到次關(guān)鍵字表頭指針若多個(gè)次關(guān)鍵字的布爾“與”，應(yīng)選較短的鏈表進(jìn)行查找2）插入插入主文件，調(diào)整其中的次關(guān)鍵字鏈表修改次關(guān)鍵字索引表3）刪除在主文件刪除記錄，調(diào)整其中的次關(guān)鍵字鏈表修改次關(guān)鍵字索引表優(yōu)缺點(diǎn)易于查找；且不要求保持鏈表的某種順序時(shí)，插入方便刪除記錄處理繁瑣數(shù)據(jù)結(jié)構(gòu)-第12章 文件2612.6.2 倒排文件組織方式 主文件 (主關(guān)鍵字有序順序文件，含有一個(gè)或多個(gè)次關(guān)鍵字鏈表) +主關(guān)鍵字非稠密索引+一個(gè)或多個(gè)次關(guān)鍵字倒排表(索引表) 次關(guān)鍵字 物理地址(或主關(guān)鍵字)序列 例物理記錄號(hào) 學(xué)號(hào) 姓名 成績(jī) 性別 成績(jī)倒排表

16、100 01 78 男 60 104 101 02 86 男 70 100，103 102 03 89 女 80 101，102，106 103 04 72 男 90 105 104 05 65 女 性別倒排表 105 06 94 女 男 100，101，103，106 106 07 83 男 女 102，104，105數(shù)據(jù)結(jié)構(gòu)-第12章 文件27操作1）查找 進(jìn)行多關(guān)鍵字查詢時(shí)，可在倒排表中完成查詢條件的布爾運(yùn)算，最后對(duì)記錄進(jìn)行存取。2）修改 在主文件中插入/刪除/更新記錄，并修改倒排表優(yōu)缺點(diǎn)查詢快，但維護(hù)困難數(shù)據(jù)結(jié)構(gòu)-第12章 文件28本章學(xué)習(xí)重點(diǎn) 掌握文件的概念 了解以下文件的物理結(jié)構(gòu)、查找方法和特點(diǎn) 順序文件 索引文件 散列文件 理解多關(guān)鍵字文件的含義，了解它的兩種常用的存儲(chǔ)結(jié)構(gòu)是多重表文件和倒排文件數(shù)據(jù)結(jié)