版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)
文檔簡介
1、第十二章 文件 主要內(nèi)容文件的基本概念順序文件索引文件索引順序文件(ISAM文件和VSAM文件)直接存取文件(散列文件)多關(guān)鍵字文件文件的基本概念表 存儲在內(nèi)存中的大量記錄的集合。文件 存儲在外存中的大量記錄的集合。不同的范疇中,文件代表不同的意義操作系統(tǒng)中,文件是命名的無結(jié)構(gòu)的字節(jié)序列,其記錄的格式依需要可以靈活劃定。文件管理系統(tǒng)或數(shù)據(jù)庫系統(tǒng)中,文件是命名的性質(zhì)相同的邏輯記錄的集合,每個記錄由若干個數(shù)據(jù)項構(gòu)成。文件被放置在外存上。數(shù)據(jù)項(字段/屬性) 文件可使用的最小單位主關(guān)鍵字項 其值能唯一標識一個記錄的數(shù)據(jù)項或數(shù)據(jù)項的組合;該值稱為主關(guān)鍵字。次關(guān)鍵字項 其值不能唯一標識一個記錄的數(shù)據(jù)項,
2、稱為次關(guān)鍵字。單關(guān)鍵字文件 文件的記錄只有主關(guān)鍵字多關(guān)鍵字文件 文件的記錄除有主關(guān)鍵字,還含有若干個次關(guān)鍵字定長記錄文件 每個記錄含有信息的長度相同(所有數(shù)據(jù)項定長)不定長記錄文件 文件中每個記錄含有的信息長度不一定相同文件的基本概念 文件的邏輯結(jié)構(gòu)及操作文件中記錄之間的邏輯關(guān)系 一般看作是線性關(guān)系文件上的主要操作 (1)檢索順序檢索:存取下一個邏輯記錄直接檢索:存取第i個邏輯記錄按關(guān)鍵字檢索 簡單詢問:查詢單個關(guān)鍵字等于給定值的記錄 范圍詢問:查詢單個關(guān)鍵字屬于某個范圍的所有記錄 函數(shù)詢問:規(guī)定單個關(guān)鍵字的某個函數(shù),查詢函數(shù)的值 布爾詢問:以上三種詢問用布爾運算(與、或、非)組 (2)修改
3、對記錄的插入、刪除,對記錄某些數(shù)據(jù)項的更新等文件操作的處理方式實時批量文件的存儲結(jié)構(gòu)(物理結(jié)構(gòu))物理記錄(頁塊)和邏輯結(jié)構(gòu)之間可能存在的關(guān)系一個物理記錄存放一個邏輯記錄一個物理記錄存放多個邏輯記錄多個物理記錄存放一個邏輯記錄文件的常用存儲結(jié)構(gòu)順序組織索引組織散列組織鏈組織 文件操作實現(xiàn)的基本方法 內(nèi)外存交換以物理記錄為單位內(nèi)存外存存取塊號順序文件順序文件的組織方式和特點組織方式 記錄在物理結(jié)構(gòu)中的排列順序與邏輯順序一致。連續(xù)文件:次序相繼的兩個物理記錄的存儲位置是相鄰的串聯(lián)文件:物理記錄之間次序由指針相鏈表示特點 根據(jù)記錄的序號或記錄的相對位置進行存取。 順序存取時效率較高。順序文件上的查找查
4、找順序存取存儲器(磁帶)上的順序文件順序查找 為提高效率,適合于批量檢索。直接存取存儲器(磁盤)上的順序文件順序查找折半查找 適合于較小的有序定長記錄文件的檢索。查找很大的文件時(多個柱面),磁頭頻繁移動,降低時效。由于文件的記錄不易于像內(nèi)存空間的數(shù)據(jù)那樣“移動”,通常采用批量處理方式。事務(wù)文件 排序 有序的事務(wù)文件主文件新主文件修改請求原始文件 (有序)在一段時間內(nèi)使用的記錄批量處理方式:增刪改索引文件索引文件的組織方式 主文件 + 索引表(按主關(guān)鍵字有序) 索引項的結(jié)構(gòu): 關(guān)鍵字 物理塊號索引文件只能是磁盤文件索引順序文件:主文件中的記錄按主關(guān)鍵字有序索引非順序文件:主文件中的記錄按主關(guān)鍵
5、字無序稠密索引:主要用于索引非順序文件 主文件中的每個記錄對應(yīng)一個索引項稀疏索引:用于索引順序文件 主文件的每個頁塊對應(yīng)一個索引項索引文件上的操作前提:索引非順序文件,稠密索引查找1)將外存上存放索引表的索引區(qū)頁塊讀入內(nèi)存,可采用順序或折半查找來查找記錄的物理記錄號(塊號)2)再將外存上存放該記錄的數(shù)據(jù)區(qū)頁塊讀入內(nèi)存進行查找修改插入:將插入的記錄置于數(shù)據(jù)區(qū)末尾,并在索引表中插入索引項刪除:刪去相應(yīng)的索引項更新:若主關(guān)鍵字被修改,則需修改對應(yīng)的索引表項多級索引 當(dāng)外存的一個頁塊不能容納下索引表時,通??梢詾樗饕碓俳⒁粋€索引,稱為查找表;在此基礎(chǔ)上還可以建立第二查找表、第三查找表、例 主文件
6、索引表 查找表物理記錄號 學(xué)號 姓名 其它 關(guān)鍵字 物理記錄號 最大 物理 101 07 王得 15 04 103 關(guān)鍵字 塊號 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ù),應(yīng)盡量減少索引表深度各級索引均為順序表,結(jié)構(gòu)簡單;但修改不便,每次更新操作,可能都要重組索引,因此多級索引適合于靜態(tài)索引當(dāng)文件記錄變動較多時,可采用適合于動態(tài)索引的樹表結(jié)構(gòu),插入刪除方便平衡二叉樹:內(nèi)存可容納整個索引表B-樹:索引表很大時索
7、引順序文件 索引順序文件是常用的一種文件組織形式主文件按關(guān)鍵字有序,可以有較高的檢索效率采用稀疏索引,索引占用空間較少ISAM(索引順序存取方法)文件專為磁盤存取文件設(shè)計的文件組織方式靜態(tài)索引結(jié)構(gòu)ISAM文件的組織方式多級主索引+柱面索引+磁道(盤面)索引+主文件 主索引 柱面索引 磁道索引 主文件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)在該磁道上查找 從磁道索引項的溢出索引項中得到溢出鏈表的頭指針查找2.插入1) 利用查找確定記錄應(yīng)插入的柱面和磁道2)該磁道不滿,則插入該磁道的適當(dāng)位置上,結(jié)束3)該磁道已滿,視插入記錄的關(guān)鍵字插入磁道,調(diào)整溢出鏈表和磁道索引直接插入溢出鏈表,調(diào)整磁道索引3.刪除1) 查找待刪除的記錄2)在基本區(qū)時,在其存儲位置上作刪除標記 在溢出區(qū)時,可從鏈表中取消周期性地集中整理ISAM文件,以保證空間利用率和存取效率。ISAM文件上的操作ISAM小結(jié)ISAM文件是一種多叉樹
9、形的索引順序文件葉結(jié)點存放數(shù)據(jù)記錄,組成文件的數(shù)據(jù)區(qū)非葉結(jié)點組成文件的索引區(qū)文件在記錄插入和刪除時,索引結(jié)構(gòu)不變,是靜態(tài)索引結(jié)構(gòu)主索引和柱面索引在每次檢索時都需查找,宜放在文件所占的幾個柱面的居中的柱面上,使磁頭平均移動距離最小。ISAM小結(jié)VSAM(虛擬存儲存取方法)文件此存取方法利用虛擬內(nèi)存系統(tǒng)訪問存儲設(shè)備B+樹(B樹的變型)動態(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ù)據(jù)集控制區(qū)域(面)控制區(qū)間(道)VSAM文件上的操
10、作:查找和插入1.查找方法1:隨機查找。方法2:順序查找。2.插入 分為三種情況:所插入的控制區(qū)間未滿 將待插記錄插入合適的位置所插入的控制區(qū)間已滿,但其所在的控制區(qū)域有空閑控制區(qū)間 分裂該控制區(qū)間,將近乎一半的記錄移到全空的控制區(qū)間,并修改順序集中的相應(yīng)索引所插入的控制區(qū)域已滿 分裂控制區(qū)域,一般控制區(qū)域較大,此情況很少3.刪除 在一個控制區(qū)間內(nèi),被刪記錄之后的記錄前移。若該控制區(qū)間變空,回收為空閑區(qū)間,并刪除順序集中的相應(yīng)索引VSAM文件上的操作:刪除能保持較高的查找效率動態(tài)地分配和釋放空間不必隨記錄的變動對文件進行再組織VSAM和ISAM文件相比的優(yōu)點直接存取文件(散列文件)散列文件的組
11、織方式類似于散列表處理沖突主要采用拉鏈法桶:一個存儲單位(一塊/多塊),可以存放若干個記錄基桶溢出桶裝載因子: =n/(bm) n:記錄數(shù) b:桶數(shù) m:桶容量0 063 184 1 589 008 5052 3 014 4 930 011 384320 007 123 089 基桶溢出桶桶號散列文件上的操作查找1)由散列函數(shù)求出基桶地址2)將基桶讀入內(nèi)存順序查找3)若未查到,讀入溢出桶繼續(xù)查找插入1)由散列函數(shù)求出基桶地址2)讀入基桶,若基桶未滿,直接插入3)若基桶已滿,但溢出桶有空,插入溢出桶 否則,指定溢出桶空間,插入刪除在被刪記錄上作刪除標記散列文件的優(yōu)缺點優(yōu)點文件記錄不必排序便于插入
12、、刪除記錄存取速度快節(jié)省存儲空間缺點只能按關(guān)鍵字存取,詢問方式限于簡單詢問多次插入、刪除記錄會造成文件結(jié)構(gòu)不合理,需重組文件多關(guān)鍵字文件目的 方便對次關(guān)鍵字的查詢多關(guān)鍵字文件的概念 包含有多個次關(guān)鍵字索引的文件兩種主要的組織方式多重表文件倒排文件 多重表文件組織方式 主文件(主關(guān)鍵字有序順序文件,含有一個或多個次關(guān)鍵字鏈表) +主關(guān)鍵字非稠密索引+ 一個或多個次關(guān)鍵字索引表 例 次關(guān)鍵字 頭指針 鏈長 物理記錄號 學(xué)號 姓名 成績 性別 主關(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 成績 性別 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)鍵字表頭指針若多個次關(guān)鍵字的布爾“與”,應(yīng)選較短的鏈表進行查找2.插入插入主文件,調(diào)整其中的次關(guān)鍵字鏈表修改次關(guān)鍵字索引表3.刪除在主文件刪除記錄,調(diào)整其中的次關(guān)鍵字鏈表修改次關(guān)鍵字索引表優(yōu)缺點易于查找;且不要求保持鏈表的某種順序時,插入方便刪除記錄處理繁瑣 倒排文件組織方式 主文件 (主關(guān)鍵字有序順
14、序文件,含有一個或多個次關(guān)鍵字表) +主關(guān)鍵字非稠密索引+一個或多個次關(guān)鍵字倒排表(索引表) 次關(guān)鍵字 物理地址(或主關(guān)鍵字)序列 例物理記錄號 學(xué)號 姓名 成績 性別 成績倒排表 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.查找 進行多關(guān)鍵字查詢時,可在倒排表中完成查詢條件的布爾運算,最后對記錄進行存取。2.修改
15、在主文件中插入/刪除/更新記錄,并修改倒排表優(yōu)缺點查詢快,但維護困難 倒排文件操作作業(yè)1. 設(shè)有一個 職工文件,其記錄格式為(職工號、姓名、性別、職務(wù)、年齡、工資),其中職工號為關(guān)鍵字,并設(shè)該文件由如下五個記錄組成:地址 A 39 張三 男 程序員 25 3270 B 50 王二 女 分析員 31 5685 C 10 李四 男 程序員 28 3575 D 75 丁一 女 操作員 20 1650 E 18 趙五 男 分析員 33 62801)若該文件為順序文件,寫出文件的存儲結(jié)構(gòu);2)若該文件為索引文件,寫出索引表;3)若該文件為倒排文件,寫出關(guān)于性別和職業(yè)的倒排索引。2. 下圖給出了ISAM文件的局
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年增資協(xié)議合同簽訂流程
- 2025年倉儲貨物出借協(xié)議
- 2025年圣誕節(jié)裝飾協(xié)議
- 2025年商業(yè)責(zé)任不足額保險條款設(shè)定
- 二零二五版木屑生物質(zhì)顆粒燃料研發(fā)與推廣合同4篇
- 二零二五年度木工行業(yè)技術(shù)標準制定合作協(xié)議3篇
- 二零二五年度汽車抵押貸款購車二手車過戶合同
- 二零二五年度科技創(chuàng)業(yè)項目股權(quán)眾籌委托投資合同
- 二零二五年度車輛綠色出行補貼購買合同
- 二零二五年度經(jīng)典實習(xí)合同(法律事務(wù)實習(xí))
- 機電安裝工程安全培訓(xùn)
- 洗浴部前臺收銀員崗位職責(zé)
- 2024年輔警考試公基常識300題(附解析)
- GB/T 43650-2024野生動物及其制品DNA物種鑒定技術(shù)規(guī)程
- 暴發(fā)性心肌炎查房
- 工程質(zhì)保金返還審批單
- 【可行性報告】2023年電動自行車項目可行性研究分析報告
- 五月天歌詞全集
- 商品退換貨申請表模板
- 實習(xí)單位鑒定表(模板)
- 數(shù)字媒體應(yīng)用技術(shù)專業(yè)調(diào)研方案
評論
0/150
提交評論