中國科大數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)構(gòu)造

第十二章 文件本章內(nèi)容12.1有關(guān)文件的根本概念12.2順序文件12.3索引文件12.4ISAM和VSAM文件12.5直接存取文件12.6多關(guān)鍵字文件12-12.1有關(guān)文件的根本概念文件：是大量記錄的集合。習(xí)慣上稱存儲(chǔ)在主存儲(chǔ)器〔內(nèi)存儲(chǔ)器〕中的記錄集合為表，稱存儲(chǔ)在二級(jí)存儲(chǔ)器〔外存儲(chǔ)器〕中的記錄集合為文件。數(shù)據(jù)項(xiàng)：是文件中可運(yùn)用的、不可分的的最小數(shù)據(jù)單位。屬性：記錄中一切非關(guān)鍵字的數(shù)據(jù)項(xiàng)，稱為記錄的屬性。文件類別按記錄的類型不同可分成：操作系統(tǒng)的文件：操作系統(tǒng)中的文件僅是一維的延續(xù)的字符序列，無構(gòu)造、無解釋。數(shù)據(jù)庫文件：數(shù)據(jù)庫中的文件是帶有構(gòu)造的記錄的集合。這類記錄是由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成的集合，它也是文件中可存取的數(shù)據(jù)的根本單位。按記錄中關(guān)鍵字的多少數(shù)據(jù)庫文件可分成：單關(guān)鍵字文件：文件中記錄只需一個(gè)獨(dú)一標(biāo)識(shí)記錄的主關(guān)鍵字。多關(guān)鍵字文件：文件中記錄除了含有一個(gè)主關(guān)鍵字外，還含有假設(shè)干個(gè)次關(guān)鍵字。12-12.1有關(guān)文件的根本概念按記錄含有信息的長度不同可分成：定長記錄文件：文件中每個(gè)記錄含有的信息長度一樣。不定長記錄文件：文件中每個(gè)記錄含有的信息長度不等。記錄的邏輯構(gòu)造和物理構(gòu)造記錄的邏輯構(gòu)造：是指記錄在用戶或運(yùn)用程序員面前呈現(xiàn)的方式，是用戶對數(shù)據(jù)的表示和存取方式。著眼于用戶運(yùn)用方便。記錄的物理構(gòu)造：是數(shù)據(jù)在物理存儲(chǔ)器上存儲(chǔ)的方式，是數(shù)據(jù)的物理表示和組織。著眼于提高存儲(chǔ)空間的利用率和減少存取記錄的時(shí)間。物理記錄和邏輯記錄之間能夠存在以下三種關(guān)系：一個(gè)物理記錄存放一個(gè)邏輯記錄；一個(gè)物理記錄包含多個(gè)邏輯記錄；多個(gè)物理記錄表示一個(gè)邏輯記錄。12-12.1有關(guān)文件的根本概念記錄的邏輯構(gòu)造與物理構(gòu)造的差別例如12-12.1有關(guān)文件的根本概念文件的操作：主要有兩類，即檢索與修正文件的檢索：主要有三種方式：順序存?。捍嫒∠乱粋€(gè)邏輯記錄。直接存?。捍嫒〉趇個(gè)邏輯記錄。按關(guān)鍵字存?。航o定一個(gè)值，查詢一個(gè)或一批關(guān)鍵字與給定值相關(guān)的記錄。對數(shù)據(jù)庫文件可以有如下4種查詢方式：簡單訊問：查詢關(guān)鍵字等于給定值的記錄。區(qū)域訊問：查詢關(guān)鍵字屬某個(gè)區(qū)域內(nèi)的記錄。函數(shù)訊問：給定關(guān)鍵字的某個(gè)函數(shù)。布爾訊問：以上3種訊問用布爾運(yùn)算組合起來的訊問。文件的修正：文件的修正包括：插入一條記錄；刪除一條記錄更新一條記錄。12-12.1有關(guān)文件的根本概念文件的操作有實(shí)時(shí)和批量兩種處置方式實(shí)時(shí)操作要求有較短的應(yīng)對呼應(yīng)時(shí)間，在接受指令后盡能夠快地完成檢索或修正義務(wù)。批量的文件處置那么允許較長反響時(shí)間。用戶可以根據(jù)需求選擇不同的文件處置方式。批量處置方式可減少更新操作的代價(jià)例如，銀行的帳戶系統(tǒng)需實(shí)時(shí)檢索，但可進(jìn)展批量修正，即可以將一天的存款和提款記錄在一個(gè)事務(wù)文件上，在一天的營業(yè)之后再進(jìn)展批量處置。事務(wù)文件有序的排序事務(wù)文件終端主文件新主文件批處置表示圖12-12.1有關(guān)文件的根本概念文件的物理構(gòu)造 文件在存儲(chǔ)介質(zhì)〔磁盤或磁帶〕上的組織方式。文件邏輯組織方式：順序構(gòu)造的定長記錄；順序構(gòu)造的變長記錄；按關(guān)鍵碼存取的記錄。文件物理組織方方式：順序文件散列文件索引文件倒排文件12-12.2順序文件定義：順序文件〔SequentialFile〕：是記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序是一致的。延續(xù)文件：次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置是相鄰的順序文件。串聯(lián)文件：物理記錄之間的次序由指針相鏈表示的順序文件。特點(diǎn)：順序文件是根據(jù)記錄的序號(hào)或記錄的相對位置來進(jìn)展存取的文件組織方式。它的特點(diǎn)是：存取第i個(gè)記錄，必需先搜索在它之前的i－1個(gè)記錄。插入新的記錄時(shí)只能加在文件的末尾。假設(shè)要更新文件中的某個(gè)記錄，那么必需將整個(gè)文件進(jìn)展復(fù)制。12-12.2順序文件順序文件的操作：普通由三種不同的方法：順序存取是從文件的第一個(gè)記錄開場依次順序進(jìn)展存取。這種方法存取效率很高。隨機(jī)存取是希望對指定的記錄直接進(jìn)展存取。但是這種要求對于順序文件來說，是極不方便的，存取效率很低。按關(guān)鍵字存取是按記錄的關(guān)鍵字值進(jìn)展存取。這種方法對于順序文件來講，也需求從文件的第一個(gè)記錄開場進(jìn)展查找，因此，在普通情況下，存取效率不高。12-12.2順序文件批處置算法實(shí)現(xiàn) 批處置的表示算法如教材p310的算法12.1所示。算法中用到的各符號(hào)的含義闡明如下：F：主文件；G：事務(wù)文件；H：新主文件。 它們都按關(guān)鍵字遞增排序。事務(wù)文件的每個(gè)記錄中，增設(shè)一個(gè)代碼以示修正要求，其中：I：表示插入；D：表示刪除；U：表示更改。12-12.2順序文件voidMergeFile(FILE*f,FILE*g,FILE*h){//由按關(guān)鍵字遞增有序的非空順序文件f和g歸并得到新文件h，//三個(gè)文件均已翻開，其中，f和g為只讀文件，文件中各附加//一個(gè)最大關(guān)鍵字記錄，且g文件中對該記錄的操作為插入。//h為只寫文件。fread(*fr,sizeof(RcdType),1,f);fread(*gr,sizeof(RcdType),1,g);while(!feof(f)||!feof(g)){switch{casefr.key<gr.key://復(fù)制“舊〞主文件中記錄fwrite(*fr,sizeof(RcdType),1,h);if(!feof(f))fread(*fr,sizeof(RcdType),1,f);break;casegr.code==‘D’&&fr.key==gr.key://刪除〞舊〞主文件中記錄,不復(fù)制if(!feof(f))fread(*fr,sizeof(RcdType),1,f);if(!feof(g))fread(*gr,sizeof(RcdType),1,g);break;casegr.code==‘I’&&fr.key>gr.key://插入,函數(shù)P把gr加工為h的構(gòu)造fwrite(P(gr),sizeof(RcdType),1,h);if(!feof(g))fread(*gr,sizeof(RcdType),1,g);break;casegr.code==‘U’&&fr.key==gr.key://更改〞舊〞主文件中記錄fwrite(Q(fr,gr),sizeof(RcdType),1,h);//函數(shù)Q將fr和gr歸并成一個(gè)h構(gòu)造的記錄if(!feof(f))fread(*fr,sizeof(RcdType),1,f);if(!feof(g))fread(*gr,sizeof(RcdType),1,g);break;defaultERROR();//其他均為出錯(cuò)情況}//switch}//while}//MergeFile12-12.2順序文件分析批處置算法的時(shí)間 假設(shè)主文件包含n個(gè)記錄，事務(wù)文件包含m個(gè)記錄。普通情況下，事務(wù)文件較小，可以進(jìn)展內(nèi)部排序，那么時(shí)間復(fù)雜度為O(m*logm)。內(nèi)部歸并的時(shí)間復(fù)雜度為O(n＋m)，那么總的內(nèi)部處置時(shí)間為O(m*logm＋n)。 假設(shè)一切的輸入/輸出都是經(jīng)過緩沖區(qū)進(jìn)展的，并假設(shè)緩沖區(qū)大小為s〔個(gè)記錄〕，那么整個(gè)批處置過程中讀/寫外存的次數(shù)為：2m/s+(m+n)/s〕12-12.3索引文件根本術(shù)語索引表：除了文件本身〔稱做數(shù)據(jù)區(qū)〕之外，另建立的一張指示邏輯記錄和物理記錄之間一一對應(yīng)關(guān)系的表。索引項(xiàng)：索引表中的每一項(xiàng)?？偸前搓P(guān)鍵字〔或邏輯記錄號(hào)〕順序陳列。索引文件：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。索引順序文件：數(shù)據(jù)區(qū)中的記錄也按關(guān)鍵字順序陳列的文件。索引非順序文件：數(shù)據(jù)區(qū)中的記錄不按關(guān)鍵字順序陳列的文件。稠密索引：由于數(shù)據(jù)文件中記錄不按關(guān)鍵字順序陳列，那么必需對每個(gè)記錄都建立一個(gè)索引項(xiàng)，如此建立的索引表稱為稠密索引。非稠密索引：數(shù)據(jù)文件中的記錄按關(guān)鍵字順序有序，那么可對一組記錄建立一個(gè)索引項(xiàng)，這種索引表稱為非稠密索引。12-12.3索引文件例如，以下圖為兩個(gè)索引表的例子。邏輯記錄號(hào)存在標(biāo)識(shí)物理記錄號(hào)01111720null3110關(guān)鍵字ki物理記錄號(hào)1011190119117812311601251142物理地址職工號(hào)姓名性別工資1142125張三男35001160123李四女40001178119王五男45001190101黃六男280012-12.3索引文件索引文件的存儲(chǔ)

索引文件在存儲(chǔ)器上分為兩個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放主文件。索引文件的建立

建立索引文件的過程：按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表。其中索引表中關(guān)鍵字是無序的待全部記錄輸入終了后對索引表進(jìn)展排序，排序后的索引表和主文件一同就構(gòu)成了索引文件。12-12.3索引文件檢索操作

檢索分兩步進(jìn)展：將外存上含有索引區(qū)的頁塊送人內(nèi)存，查找所需記錄的物理地址將含有該記錄的頁塊送人內(nèi)存留意：索引表不大時(shí)，索引表可一次讀入內(nèi)存，在索引文件中檢索只需兩次訪問外存：一次讀索引，一次讀記錄。由于索引表有序，對索引表的查找可用順序查找或二分查找12-12.3索引文件索引文件的修正刪除操作：刪除一個(gè)記錄時(shí)，僅需刪去相應(yīng)的索引項(xiàng)；插入操作：插入一個(gè)記錄時(shí)，應(yīng)將記錄置于數(shù)據(jù)區(qū)的末尾，同時(shí)再索引表中插入索引項(xiàng)；更新操作：更新記錄時(shí)，應(yīng)將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時(shí)修正索引表中相應(yīng)的索引項(xiàng)。多級(jí)索引： 查找表：對索引表建立的索引。通常最高可有四級(jí)索引：數(shù)據(jù)文件索引表查找表第二查找表第三查找表多級(jí)索引是靜態(tài)索引，各級(jí)索引均為順序表構(gòu)造。其構(gòu)造簡單，但修正很不方便，每次修正都要重組索引。因此，當(dāng)數(shù)據(jù)文件在運(yùn)用過程中記錄變動(dòng)較多時(shí)，應(yīng)采用動(dòng)態(tài)索引。如二叉排序樹〔或二叉平衡樹〕、B-樹以及鍵樹。12-12.4ISAM和VSAM文件12.4.1ISAM文件ISAM文件定義：索引順序存取方法ISAM(IndexedSequentialAccessMethod)是一種專為磁盤存取設(shè)計(jì)的文件組織方式。磁盤是以盤組、柱面和磁道三級(jí)地址存取的設(shè)備，可對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級(jí)索引。磁道索引項(xiàng)：根本索引項(xiàng)：關(guān)鍵字：表示該磁道中最末一個(gè)記錄的關(guān)鍵字〔在此為最大關(guān)鍵字〕。指針：指示該磁道中第一個(gè)記錄的位置。溢出索引項(xiàng)：關(guān)鍵字：表示該磁道溢出的記錄的最大關(guān)鍵字。指針：指示在溢出區(qū)中的第一個(gè)記錄。12-12.4ISAM和VSAM文件柱面索引項(xiàng)：關(guān)鍵字：表示該柱面中最末一個(gè)記錄的關(guān)鍵字〔最大關(guān)鍵字〕。指針：指示該柱面上的磁道索引位置。ISAM文件的組成 ISAM文件由多級(jí)主索引、柱面索引、磁道索引和主文件組成。文件的記錄在同一盤組上存放時(shí)，應(yīng)先集中放在一個(gè)柱面上，然后再順序存放在相鄰的柱面上。對同一柱面，那么應(yīng)按盤面的次序順序存放。12-12-12.4ISAM和VSAM文件在ISAM文件上檢索記錄時(shí)，先從主索引出發(fā)檢索到相應(yīng)的柱面索引，然后從柱面索引檢索到記錄所在柱面的磁道索引，最后從磁道索引檢索到記錄所在磁道的第一個(gè)記錄的位置，由此出發(fā)在該磁道上進(jìn)展順序查找直至檢索到為止；反之，假設(shè)檢索遍磁道而不存在此記錄，那么闡明文件中無此記錄。ISAM文件中刪除記錄比較簡單，只需作刪除標(biāo)志而不用挪動(dòng)記錄或改動(dòng)指針。當(dāng)然應(yīng)該周期性地把記錄讀入內(nèi)存重排整理ISAM文件，以盡量填滿根本區(qū)而空出溢出區(qū)。12-12.4ISAM和VSAM文件12.4.2VSAM文件 VSAM〔VirtualStorageAccessMethod〕即虛擬存儲(chǔ)存取方法。它運(yùn)用戶只需思索控制區(qū)間等邏輯存儲(chǔ)單位，而無需思索其物理位置以及何時(shí)對外存儲(chǔ)器進(jìn)展讀寫操作，給用戶運(yùn)用文件提供了方便。 VSAM文件的構(gòu)造由索引集、順序集和數(shù)據(jù)集三部分組成。數(shù)據(jù)集存放文件的一切記錄，順序集和索引集構(gòu)成一棵B+樹是文件的索引部分。數(shù)據(jù)集中的一個(gè)結(jié)點(diǎn)稱為控制區(qū)間〔ControlInterval〕。12-12.4ISAM和VSAM文件 順序集中的一個(gè)結(jié)點(diǎn)，存放著假設(shè)干相鄰控制區(qū)間的索引項(xiàng)，每個(gè)索引項(xiàng)由控制區(qū)間中的最大關(guān)鍵字和指向該控制區(qū)間的指針組成。順序集中的一個(gè)結(jié)點(diǎn)連同其下層一切控制區(qū)間構(gòu)成的整體稱作控制區(qū)域〔ControlRange〕。順序集中的結(jié)點(diǎn)之間用指針相鏈接，在它們上層的結(jié)點(diǎn)又以它們?yōu)楦讟?gòu)成索引，并逐級(jí)向上建立索引，構(gòu)成B+樹的非終端結(jié)點(diǎn)。12-12.4ISAM和VSAM文件VSAM文件的構(gòu)造表示圖控制區(qū)間控制區(qū)域索引集順序集數(shù)據(jù)集B+樹12-12.4ISAM和VSAM文件 對VSAM文件中記錄的檢索，既可從最高層的索引逐層往下按關(guān)鍵字進(jìn)展檢索，又可在順序集中沿著指針鏈順序檢索。 VSAM文件沒有專門的溢出區(qū)，但可以利用控制區(qū)間中的空隙或控制區(qū)域中的空控制區(qū)間來插入記錄〔即在B+樹上插入記錄〕。而在VSAM文件中刪除記錄時(shí)，也需挪動(dòng)記錄。 VSAM文件占有較多的存儲(chǔ)空間，然而它具有許多優(yōu)點(diǎn)，如動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，無需像ISAM文件那樣定期重排文件，并能較快地執(zhí)行插入操作和堅(jiān)持較高的檢索效率。 VSAM文件通常作為組織大型索引順序文件的規(guī)范方式。12-12.4ISAM和VSAM文件VASM文件的特點(diǎn)優(yōu)點(diǎn)：動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，不需求對文件進(jìn)展重組，并能較快地對插入的記錄進(jìn)展查找，查找一個(gè)后插入記錄的時(shí)間與查找一個(gè)原有記錄的時(shí)間是一樣的。缺陷：占有較多的存儲(chǔ)空間，普通只能堅(jiān)持約75％的存儲(chǔ)空間利用率。12-12.5直接存取文件(散列文件)定義：直接存取文件指的是利用雜湊〔Hash〕法進(jìn)展組織的文件。它類似于哈希表，既根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種哈希函數(shù)和處置沖突的方法將記錄散列到存儲(chǔ)設(shè)備上，故又稱散列文件。與哈希表不同的是，對于文件來說，磁盤上的文件記錄通常是成組存放的。溢出處置：假設(shè)干個(gè)記錄組成一個(gè)存儲(chǔ)單位，在散列文件中，這個(gè)存儲(chǔ)單位叫做桶〔Bucket〕。 假假設(shè)一個(gè)桶能存放m個(gè)記錄，這就是說，m個(gè)同義詞的記錄可以存放在同一地址的桶中，而當(dāng)?shù)趍＋1個(gè)同義詞出現(xiàn)時(shí)才發(fā)生“溢出〞。對散列文件主要采用鏈地址法處置溢出。 發(fā)生“溢出〞時(shí)，需求將第m＋1個(gè)同義詞存放到另一個(gè)桶中，稱此桶為“溢出桶〞；相對地，稱前m個(gè)同義詞存放的桶為“基桶〞。溢出桶和基桶大小一樣，相互之間用指針相鏈接。當(dāng)在基桶中沒有待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)展查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。12-12.5直接存取文件(散列文件)例如，某一文件有18個(gè)記錄，其關(guān)鍵字分別為278，109，063，930，589，184，505，269，008，083，164，215，330，810，620，110，384，355。桶的容量為m＝3，桶數(shù)b＝7。用除留余數(shù)法作哈希函數(shù)H(key)＝keyMOD7。由此得到的直接存取文件如以下圖所示。桶編號(hào) 基桶 溢出桶00631841589505008 33023269164410962052782158101103556930083384直接存取文件例如12-12.5直接存取文件(散列文件)查找操作 查找過程：首先根據(jù)給定值求得哈希地址〔即基桶號(hào)〕，將基桶的記錄讀入內(nèi)存進(jìn)展順序查找，假設(shè)找到關(guān)鍵字等于給定值的記錄，那么檢索勝利；否那么，假設(shè)基桶內(nèi)沒有填滿記錄或其指針域?yàn)榭眨敲次募?nèi)不含有待查記錄；否那么根據(jù)指針域的值的指示將溢出桶的記錄讀入內(nèi)存繼續(xù)進(jìn)展順序查找，直至檢索勝利或不勝利。因此，總的查找時(shí)間為：T=a(te+ti) 其中：a為存取桶數(shù)的期望值〔相當(dāng)于哈希表中的平均查找長度〕，對鏈地址處置溢出來說，a=1+α/2；te為存取一個(gè)桶所需的時(shí)間；ti為在內(nèi)存中順序查找一個(gè)記錄所需的時(shí)間。 α為裝載因子，在散列文件中：α=n/(bm) n為文件的記錄數(shù)，b為桶數(shù)，m為桶的容量。12-12.5直接存取文件(散列文件)刪除操作 在直接存取文件中刪除記錄時(shí)，僅需對被刪記錄作一標(biāo)志即可。直接存取文件的特點(diǎn)優(yōu)點(diǎn)：文件隨機(jī)存放，記錄不需進(jìn)展排序；插入、刪除方便，存取速度快，不需求索引區(qū)，節(jié)省存儲(chǔ)空間。缺陷：不能進(jìn)展順序存取，只能按關(guān)鍵字隨機(jī)存取，且訊問方式限于簡單訊問，并且在經(jīng)過多次的插入、刪除之后，也能夠呵斥文件構(gòu)造不合理，即溢出桶滿而基桶內(nèi)多數(shù)為被刪除的記錄。此時(shí)亦需重組文件。12-12.6多關(guān)鍵字文件 在對文件進(jìn)展檢索操作是，不僅對主關(guān)鍵字進(jìn)展簡單訊問，