數(shù)據(jù)結(jié)構(gòu)講義課件

1、第十二章 文件 主要內(nèi)容文件的基本概念順序文件索引文件索引順序文件(ISAM文件和VSAM文件)直接存取文件(散列文件)多關(guān)鍵字文件文件的基本概念表 存儲(chǔ)在內(nèi)存中的大量記錄的集合。文件 存儲(chǔ)在外存中的大量記錄的集合。不同的范疇中，文件代表不同的意義操作系統(tǒng)中，文件是命名的無(wú)結(jié)構(gòu)的字節(jié)序列，其記錄的格式依需要可以靈活劃定。文件管理系統(tǒng)或數(shù)據(jù)庫(kù)系統(tǒng)中，文件是命名的性質(zhì)相同的邏輯記錄的集合，每個(gè)記錄由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成。文件被放置在外存上。數(shù)據(jù)項(xiàng)（字段/屬性） 文件可使用的最小單位主關(guān)鍵字項(xiàng) 其值能唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)的組合；該值稱(chēng)為主關(guān)鍵字。次關(guān)鍵字項(xiàng) 其值不能唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng),

2、稱(chē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)度不一定相同文件的基本概念 文件的邏輯結(jié)構(gòu)及操作文件中記錄之間的邏輯關(guān)系 一般看作是線性關(guān)系文件上的主要操作 (1)檢索順序檢索：存取下一個(gè)邏輯記錄直接檢索：存取第i個(gè)邏輯記錄按關(guān)鍵字檢索 簡(jiǎn)單詢(xún)問(wèn)：查詢(xún)單個(gè)關(guān)鍵字等于給定值的記錄 范圍詢(xún)問(wèn)：查詢(xún)單個(gè)關(guān)鍵字屬于某個(gè)范圍的所有記錄 函數(shù)詢(xún)問(wèn)：規(guī)定單個(gè)關(guān)鍵字的某個(gè)函數(shù)，查詢(xún)函數(shù)的值 布爾詢(xún)問(wèn)：以上三種詢(xún)問(wèn)用布爾運(yùn)算(與、或、非)組 (2)修改

3、對(duì)記錄的插入、刪除，對(duì)記錄某些數(shù)據(jù)項(xiàng)的更新等文件操作的處理方式實(shí)時(shí)批量文件的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))物理記錄(頁(yè)塊)和邏輯結(jié)構(gòu)之間可能存在的關(guān)系一個(gè)物理記錄存放一個(gè)邏輯記錄一個(gè)物理記錄存放多個(gè)邏輯記錄多個(gè)物理記錄存放一個(gè)邏輯記錄文件的常用存儲(chǔ)結(jié)構(gòu)順序組織索引組織散列組織鏈組織 文件操作實(shí)現(xiàn)的基本方法 內(nèi)外存交換以物理記錄為單位內(nèi)存外存存取塊號(hào)順序文件順序文件的組織方式和特點(diǎn)組織方式 記錄在物理結(jié)構(gòu)中的排列順序與邏輯順序一致。連續(xù)文件：次序相繼的兩個(gè)物理記錄的存儲(chǔ)位置是相鄰的串聯(lián)文件：物理記錄之間次序由指針相鏈表示特點(diǎn) 根據(jù)記錄的序號(hào)或記錄的相對(duì)位置進(jìn)行存取。 順序存取時(shí)效率較高。順序文件上的查找查

4、找順序存取存儲(chǔ)器(磁帶)上的順序文件順序查找 為提高效率，適合于批量檢索。直接存取存儲(chǔ)器(磁盤(pán))上的順序文件順序查找折半查找 適合于較小的有序定長(zhǎng)記錄文件的檢索。查找很大的文件時(shí)(多個(gè)柱面)，磁頭頻繁移動(dòng)，降低時(shí)效。由于文件的記錄不易于像內(nèi)存空間的數(shù)據(jù)那樣“移動(dòng)”，通常采用批量處理方式。事務(wù)文件 排序 有序的事務(wù)文件主文件新主文件修改請(qǐng)求原始文件 (有序)在一段時(shí)間內(nèi)使用的記錄批量處理方式:增刪改索引文件索引文件的組織方式 主文件 + 索引表(按主關(guān)鍵字有序) 索引項(xiàng)的結(jié)構(gòu)： 關(guān)鍵字 物理塊號(hào)索引文件只能是磁盤(pán)文件索引順序文件：主文件中的記錄按主關(guān)鍵字有序索引非順序文件：主文件中的記錄按主關(guān)鍵

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

6、索引表 查找表物理記錄號(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多級(jí)索引特點(diǎn)為減少訪問(wèn)外存次數(shù)，應(yīng)盡量減少索引表深度各級(jí)索引均為順序表，結(jié)構(gòu)簡(jiǎn)單；但修改不便，每次更新操作，可能都要重組索引，因此多級(jí)索引適合于靜態(tài)索引當(dāng)文件記錄變動(dòng)較多時(shí)，可采用適合于動(dòng)態(tài)索引的樹(shù)表結(jié)構(gòu)，插入刪除方便平衡二叉樹(shù)：內(nèi)存可容納整個(gè)索引表B-樹(shù)：索引表很大時(shí)索

7、引順序文件 索引順序文件是常用的一種文件組織形式主文件按關(guān)鍵字有序，可以有較高的檢索效率采用稀疏索引，索引占用空間較少I(mǎi)SAM(索引順序存取方法)文件專(zhuān)為磁盤(pán)存取文件設(shè)計(jì)的文件組織方式靜態(tài)索引結(jié)構(gòu)ISAM文件的組織方式多級(jí)主索引+柱面索引+磁道(盤(pán)面)索引+主文件 主索引 柱面索引 磁道索引 主文件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 53 T91ISAM文件上的操作1.查找 讓主索引

8、常駐內(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)整磁道索引3.刪除1) 查找待刪除的記錄2)在基本區(qū)時(shí)，在其存儲(chǔ)位置上作刪除標(biāo)記 在溢出區(qū)時(shí)，可從鏈表中取消周期性地集中整理ISAM文件，以保證空間利用率和存取效率。ISAM文件上的操作ISAM小結(jié)ISAM文件是一種多叉樹(shù)

9、形的索引順序文件葉結(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)距離最小。ISAM小結(jié)VSAM(虛擬存儲(chǔ)存取方法)文件此存取方法利用虛擬內(nèi)存系統(tǒng)訪問(wèn)存儲(chǔ)設(shè)備B+樹(shù)(B樹(shù)的變型)動(dòng)態(tài)索引結(jié)構(gòu)大型索引順序文件VSAM文件的組織方式 59 97 15 44 59 72 97 10 15 20 37 44 51 59 63 72 85 91 975710111215sqtroot索引集B+樹(shù)順序集數(shù)據(jù)集控制區(qū)域(面)控制區(qū)間(道)VSAM文件上的操

10、作：查找和插入1.查找方法1：隨機(jī)查找。方法2：順序查找。2.插入 分為三種情況：所插入的控制區(qū)間未滿 將待插記錄插入合適的位置所插入的控制區(qū)間已滿，但其所在的控制區(qū)域有空閑控制區(qū)間 分裂該控制區(qū)間，將近乎一半的記錄移到全空的控制區(qū)間，并修改順序集中的相應(yīng)索引所插入的控制區(qū)域已滿 分裂控制區(qū)域，一般控制區(qū)域較大，此情況很少3.刪除 在一個(gè)控制區(qū)間內(nèi)，被刪記錄之后的記錄前移。若該控制區(qū)間變空，回收為空閑區(qū)間，并刪除順序集中的相應(yīng)索引VSAM文件上的操作：刪除能保持較高的查找效率動(dòng)態(tài)地分配和釋放空間不必隨記錄的變動(dòng)對(duì)文件進(jìn)行再組織VSAM和ISAM文件相比的優(yōu)點(diǎn)直接存取文件（散列文件）散列文件的組

11、織方式類(lèi)似于散列表處理沖突主要采用拉鏈法桶：一個(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)散列文件上的操作查找1)由散列函數(shù)求出基桶地址2)將基桶讀入內(nèi)存順序查找3)若未查到，讀入溢出桶繼續(xù)查找插入1)由散列函數(shù)求出基桶地址2)讀入基桶，若基桶未滿，直接插入3)若基桶已滿，但溢出桶有空，插入溢出桶 否則，指定溢出桶空間，插入刪除在被刪記錄上作刪除標(biāo)記散列文件的優(yōu)缺點(diǎn)優(yōu)點(diǎn)文件記錄不必排序便于插入

12、、刪除記錄存取速度快節(jié)省存儲(chǔ)空間缺點(diǎn)只能按關(guān)鍵字存取，詢(xún)問(wèn)方式限于簡(jiǎn)單詢(xún)問(wèn)多次插入、刪除記錄會(huì)造成文件結(jié)構(gòu)不合理，需重組文件多關(guān)鍵字文件目的 方便對(duì)次關(guān)鍵字的查詢(xún)多關(guān)鍵字文件的概念 包含有多個(gè)次關(guān)鍵字索引的文件兩種主要的組織方式多重表文件倒排文件 多重表文件組織方式 主文件(主關(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 1

13、06 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 105 1多重表文件操作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í)，插入方便刪除記錄處理繁瑣 倒排文件組織方式 主文件 (主關(guān)鍵字有序順

14、序文件，含有一個(gè)或多個(gè)次關(guān)鍵字表) +主關(guān)鍵字非稠密索引+一個(gè)或多個(gè)次關(guān)鍵字倒排表(索引表) 次關(guān)鍵字 物理地址(或主關(guān)鍵字)序列 例物理記錄號(hào) 學(xué)號(hào) 姓名 成績(jī) 性別 成績(jī)倒排表 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，1051.查找 進(jìn)行多關(guān)鍵字查詢(xún)時(shí)，可在倒排表中完成查詢(xún)條件的布爾運(yùn)算，最后對(duì)記錄進(jìn)行存取。2.修改

15、在主文件中插入/刪除/更新記錄，并修改倒排表優(yōu)缺點(diǎn)查詢(xún)快，但維護(hù)困難 倒排文件操作作業(yè)1. 設(shè)有一個(gè) 職工文件，其記錄格式為(職工號(hào)、姓名、性別、職務(wù)、年齡、工資)，其中職工號(hào)為關(guān)鍵字，并設(shè)該文件由如下五個(gè)記錄組成：地址 A 39 張三 男 程序員 25 3270 B 50 王二 女 分析員 31 5685 C 10 李四 男 程序員 28 3575 D 75 丁一 女 操作員 20 1650 E 18 趙五 男 分析員 33 62801)若該文件為順序文件，寫(xiě)出文件的存儲(chǔ)結(jié)構(gòu)；2)若該文件為索引文件，寫(xiě)出索引表；3)若該文件為倒排文件，寫(xiě)出關(guān)于性別和職業(yè)的倒排索引。2. 下圖給出了ISAM文件的局