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

數(shù)據(jù)結(jié)構(gòu)

第十二章 文件本章內(nèi)容12.1有關(guān)文件的基本概念12.2順序文件12.3索引文件12.4ISAM和VSAM文件12.5直接存取文件12.6多關(guān)鍵字文件12-2

12.1有關(guān)文件的基本概念文件：是大量記錄的集合。習(xí)慣上稱存儲(chǔ)在主存儲(chǔ)器（內(nèi)存儲(chǔ)器）中的記錄集合為表，稱存儲(chǔ)在二級(jí)存儲(chǔ)器（外存儲(chǔ)器）中的記錄集合為文件。數(shù)據(jù)項(xiàng)：是文件中可使用的、不可分的的最小數(shù)據(jù)單位。屬性：記錄中所有非關(guān)鍵字的數(shù)據(jù)項(xiàng)，稱為記錄的屬性。文件類別按記錄的類型不同可分成：操作系統(tǒng)的文件：操作系統(tǒng)中的文件僅是一維的連續(xù)的字符序列，無結(jié)構(gòu)、無解釋。數(shù)據(jù)庫文件：數(shù)據(jù)庫中的文件是帶有結(jié)構(gòu)的記錄的集合。這類記錄是由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)組成的集合，它也是文件中可存取的數(shù)據(jù)的基本單位。按記錄中關(guān)鍵字的多少數(shù)據(jù)庫文件可分成：單關(guān)鍵字文件：文件中記錄只有一個(gè)唯一標(biāo)識(shí)記錄的主關(guān)鍵字。多關(guān)鍵字文件：文件中記錄除了含有一個(gè)主關(guān)鍵字外，還含有若干個(gè)次關(guān)鍵字。12-3

12.1有關(guān)文件的基本概念按記錄含有信息的長度不同可分成：定長記錄文件：文件中每個(gè)記錄含有的信息長度相同。不定長記錄文件：文件中每個(gè)記錄含有的信息長度不等。記錄的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)記錄的邏輯結(jié)構(gòu)：是指記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對數(shù)據(jù)的表示和存取方式。著眼于用戶使用方便。記錄的物理結(jié)構(gòu)：是數(shù)據(jù)在物理存儲(chǔ)器上存儲(chǔ)的方式，是數(shù)據(jù)的物理表示和組織。著眼于提高存儲(chǔ)空間的利用率和減少存取記錄的時(shí)間。物理記錄和邏輯記錄之間可能存在下列三種關(guān)系：一個(gè)物理記錄存放一個(gè)邏輯記錄；一個(gè)物理記錄包含多個(gè)邏輯記錄；多個(gè)物理記錄表示一個(gè)邏輯記錄。12-4

12.1有關(guān)文件的基本概念記錄的邏輯結(jié)構(gòu)與物理結(jié)構(gòu)的差別示例12-5

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-6

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-7

12.1有關(guān)文件的基本概念文件的物理結(jié)構(gòu)

文件在存儲(chǔ)介質(zhì)（磁盤或磁帶）上的組織方式。文件邏輯組織形式：順序結(jié)構(gòu)的定長記錄；順序結(jié)構(gòu)的變長記錄；按關(guān)鍵碼存取的記錄。文件物理組織方形式：順序文件散列文件索引文件倒排文件12-8

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í)只能加在文件的末尾。若要更新文件中的某個(gè)記錄，則必須將整個(gè)文件進(jìn)行復(fù)制。12-9

12.2順序文件順序文件的操作：一般由三種不同的方法：順序存取是從文件的第一個(gè)記錄開始依次順序進(jìn)行存取。這種方法存取效率很高。隨機(jī)存取是希望對指定的記錄直接進(jìn)行存取。但是這種要求對于順序文件來說，是極不方便的，存取效率很低。按關(guān)鍵字存取是按記錄的關(guān)鍵字值進(jìn)行存取。這種方法對于順序文件來講，也需要從文件的第一個(gè)記錄開始進(jìn)行查找，因此，在一般情況下，存取效率不高。12-10

12.2順順序序文文件件批處處理理算算法法實(shí)實(shí)現(xiàn)現(xiàn)批處處理理的的示示意意算算法法如如教教材材p310的的算算法法12.1所所示示。。算算法法中中用用到到的的各各符符號(hào)號(hào)的的含含義義說說明明如如下下：：F：：主主文文件件；；G：：事事務(wù)務(wù)文文件件；；H：新主主文件。。它們都按按關(guān)鍵字字遞增排排序。事事務(wù)文件件的每個(gè)個(gè)記錄中中，增設(shè)設(shè)一個(gè)代代碼以示示修改要要求，其其中：I：表示示插入；；D：表示示刪除；；U：表示示更改。。12-1112.2順序序文件voidMergeFile(FILE*f,FILE*g,FILE*h){//由按按關(guān)鍵字字遞增有有序的非非空順序序文件f和g歸歸并得到到新文件件h，//三個(gè)個(gè)文件均均已打開開，其中中，f和和g為只只讀文件件，文件件中各附附加//一個(gè)個(gè)最大關(guān)關(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ù)復(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ù)數(shù)P把gr加工工為h的的結(jié)構(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ù)數(shù)Q將fr和gr歸并并成一個(gè)個(gè)h結(jié)構(gòu)構(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-1212.2順序序文件分析批處處理算法法的時(shí)間間假設(shè)主文文件包含含n個(gè)記記錄，事事務(wù)文件件包含m個(gè)記錄錄。一般般情況下下，事務(wù)務(wù)文件較較小，可可以進(jìn)行行內(nèi)部排排序，則則時(shí)間復(fù)復(fù)雜度為為O(m*logm)。內(nèi)部部歸并的的時(shí)間復(fù)復(fù)雜度為為O(n＋m)，則總總的內(nèi)部部處理時(shí)時(shí)間為O(m*logm＋n)。假設(shè)所有有的輸入入/輸出出都是通通過緩沖沖區(qū)進(jìn)行行的，并并假設(shè)緩緩沖區(qū)大大小為s（個(gè)記記錄），，則整個(gè)個(gè)批處理理過程中中讀/寫寫外存的的次數(shù)為為：2m/s+(m+n)/s）12-1312.3索引引文件基本術(shù)語語索引表：除了文文件本身身（稱做做數(shù)據(jù)區(qū)區(qū)）之外外，另建建立的一一張指示示邏輯記記錄和物物理記錄錄之間一一一對應(yīng)應(yīng)關(guān)系的的表。索引項(xiàng)：索引表表中的每每一項(xiàng)。?？偸前窗搓P(guān)鍵字字（或邏邏輯記錄錄號(hào)）順順序排列列。索引文件件：包括文文件數(shù)據(jù)據(jù)區(qū)和索索引表兩兩大部分分的文件件。索引順序序文件：數(shù)據(jù)區(qū)區(qū)中的記記錄也按按關(guān)鍵字字順序排排列的文文件。索引非順順序文件件：數(shù)據(jù)區(qū)區(qū)中的記記錄不按按關(guān)鍵字字順序排排列的文文件。稠密索引引：由于數(shù)數(shù)據(jù)文件件中記錄錄不按關(guān)關(guān)鍵字順順序排列列，則必必須對每每個(gè)記錄錄都建立立一個(gè)索索引項(xiàng)，，如此建建立的索索引表稱稱為稠密密索引。。非稠密索索引：數(shù)據(jù)文文件中的的記錄按按關(guān)鍵字字順序有有序，則則可對一一組記錄錄建立一一個(gè)索引引項(xiàng)，這這種索引引表稱為為非稠密密索引。。12-1412.3索引引文件例如，下下圖為兩兩個(gè)索引引表的例例子。邏輯記錄號(hào)存在標(biāo)識(shí)物理記錄號(hào)01111720null3110關(guān)鍵字ki物理記錄號(hào)1011190119117812311601251142物理地址職工號(hào)姓名性別工資1142125張三男35001160123李四女40001178119王五男45001190101黃六男280012-1512.3索引引文件索引文件件的存儲(chǔ)儲(chǔ)索索引文文件在存存儲(chǔ)器上上分為兩兩個(gè)區(qū)：：索引區(qū)區(qū)和數(shù)據(jù)據(jù)區(qū)。索索引區(qū)存存放索引引表，數(shù)數(shù)據(jù)區(qū)存存放主文文件。索引文件件的建立立

建立立索引文文件的過過程：按輸入記記錄的先先后次序序建立數(shù)數(shù)據(jù)區(qū)和和索引表表。其中中索引表表中關(guān)鍵鍵字是無無序的待全全部部記記錄錄輸輸入入完完畢畢后后對對索索引引表表進(jìn)進(jìn)行行排排序序，，排排序序后后的的索索引引表表和和主主文文件件一一起起就就形形成成了了索索引引文文件件。。12-1612.3索索引引文文件件檢索索操操作作檢檢索索分分兩兩步步進(jìn)進(jìn)行行：：將外外存存上上含含有有索索引引區(qū)區(qū)的的頁頁塊塊送送人人內(nèi)內(nèi)存存，，查查找找所所需需記記錄錄的的物物理理地地址址將含含有有該該記記錄錄的的頁頁塊塊送送人人內(nèi)內(nèi)存存注意意：：索引引表表不不大大時(shí)時(shí)，，索索引引表表可可一一次次讀讀入入內(nèi)內(nèi)存存，，在在索索引引文文件件中中檢檢索索只只需需兩兩次次訪訪問問外外存存：：一一次次讀讀索索引引，，一一次次讀讀記記錄錄。。由于于索索引引表表有有序序，，對對索索引引表表的的查查找找可可用用順順序序查查找找或或二二分分查查找找12-1712.3索索引引文文件件索引引文文件件的的修修改改刪除除操操作作：：刪刪除除一一個(gè)個(gè)記記錄錄時(shí)時(shí)，，僅僅需需刪刪去去相相應(yīng)應(yīng)的的索索引引項(xiàng)項(xiàng)；；插入入操操作作：：插插入入一一個(gè)個(gè)記記錄錄時(shí)時(shí)，，應(yīng)應(yīng)將將記記錄錄置置于于數(shù)數(shù)據(jù)據(jù)區(qū)區(qū)的的末末尾尾，，同同時(shí)時(shí)再再索索引引表表中中插插入入索索引引項(xiàng)項(xiàng)；；更新新操操作作：：更更新新記記錄錄時(shí)時(shí)，，應(yīng)應(yīng)將將更更新新后后的的記記錄錄置置于于數(shù)數(shù)據(jù)據(jù)區(qū)區(qū)末末尾尾，，同同時(shí)時(shí)修修改改索索引引表表中中相相應(yīng)應(yīng)的的索索引引項(xiàng)項(xiàng)。。多級(jí)級(jí)索索引引：：查找找表表：：對對索索引引表表建建立立的的索索引引。。通常常最最高高可可有有四四級(jí)級(jí)索索引引：：數(shù)據(jù)據(jù)文文件件索引表查找表第二查找表第三查找表多級(jí)級(jí)索索引引是是靜靜態(tài)態(tài)索索引引，，各各級(jí)級(jí)索索引引均均為為順順序序表表結(jié)結(jié)構(gòu)構(gòu)。。其其結(jié)結(jié)構(gòu)構(gòu)簡簡單單，，但但修修改改很很不不方方便便，，每每次次修修改改都都要要重重組組索索引引。。因因此此，，當(dāng)當(dāng)數(shù)數(shù)據(jù)據(jù)文文件件在在使使用用過過程程中中記記錄錄變變動(dòng)動(dòng)較較多多時(shí)時(shí)，，應(yīng)應(yīng)采采用用動(dòng)動(dòng)態(tài)態(tài)索索引引。。如如二二叉叉排排序序樹樹（（或或二二叉叉平平衡衡樹樹））、、B-樹樹以以及及鍵鍵樹樹。。12-1812.4ISAM和和VSAM文文件件文文件ISAM文件定定義：索索引順序序存取方方法ISAM(IndexedSequentialAccessMethod)是一種種專為磁磁盤存取取設(shè)計(jì)的的文件組組織方式式。磁盤盤是以盤盤組、柱柱面和磁磁道三級(jí)級(jí)地址存存取的設(shè)設(shè)備，可可對磁盤盤上的數(shù)數(shù)據(jù)文件件建立盤盤組、柱柱面和磁磁道三級(jí)級(jí)索引。。磁道索引引項(xiàng)：基本索引引項(xiàng)：關(guān)鍵字：：表示該該磁道中中最末一一個(gè)記錄錄的關(guān)鍵鍵字（在在此為最最大關(guān)鍵鍵字）。。指針：指指示該磁磁道中第第一個(gè)記記錄的位位置。溢出索引引項(xiàng)：關(guān)鍵字：：表示該該磁道溢溢出的記記錄的最最大關(guān)鍵鍵字。指針：指指示在溢溢出區(qū)中中的第一一個(gè)記錄錄。12-1912.4ISAM和VSAM文文件柱面索引引項(xiàng)：關(guān)鍵字：：表示該該柱面中中最末一一個(gè)記錄錄的關(guān)鍵鍵字（最最大關(guān)鍵鍵字）。。指針：指指示該柱柱面上的的磁道索索引位置置。ISAM文件的的組成ISAM文件由由多級(jí)主主索引、、柱面索索引、磁磁道索引引和主文文件組成成。文件件的記錄錄在同一一盤組上上存放時(shí)時(shí)，應(yīng)先先集中放放在一個(gè)個(gè)柱面上上，然后后再順序序存放在在相鄰的的柱面上上。對同同一柱面面，則應(yīng)應(yīng)按盤面面的次序序順序存存放。12-2012-2112.4ISAM和VSAM文文件在ISAM文件件上檢索索記錄時(shí)時(shí)，先從從主索引引出發(fā)檢檢索到相相應(yīng)的柱柱面索引引，然后后從柱面面索引檢檢索到記記錄所在在柱面的的磁道索索引，最最后從磁磁道索引引檢索到到記錄所所在磁道道的第一一個(gè)記錄錄的位置置，由此此出發(fā)在在該磁道道上進(jìn)行行順序查查找直至至檢索到到為止；；反之，，若檢索索遍磁道道而不存存在此記記錄，則則表明文文件中無無此記錄錄。ISAM文件中中刪除記記錄比較較簡單，，只需作作刪除標(biāo)標(biāo)記而不不用移動(dòng)動(dòng)記錄或或改變指指針。當(dāng)當(dāng)然應(yīng)該該周期性性地把記記錄讀入入內(nèi)存重重排整理理ISAM文件件，以盡盡量填滿滿基本區(qū)區(qū)而空出出溢出區(qū)區(qū)。12-2212.4ISAM和VSAM文文件文文件VSAM（VirtualStorageAccessMethod）即虛虛擬存儲(chǔ)儲(chǔ)存取方方法。它它使用戶戶只需考考慮控制制區(qū)間等等邏輯存存儲(chǔ)單位位，而無無需考慮慮其物理理位置以以及何時(shí)時(shí)對外存存儲(chǔ)器進(jìn)進(jìn)行讀寫寫操作，，給用戶戶使用文文件提供供了方便便。VSAM文件的的結(jié)構(gòu)由由索引集集、順序序集和數(shù)數(shù)據(jù)集三三部分組組成。數(shù)數(shù)據(jù)集存存放文件件的所有有記錄，，順序集集和索引引集構(gòu)成成一棵B+樹是是文件的的索引部部分。數(shù)數(shù)據(jù)集中中的一個(gè)個(gè)結(jié)點(diǎn)稱稱為控制制區(qū)間（（ControlInterval）。。12-2312.4ISAM和VSAM文文件順序集中中的一個(gè)個(gè)結(jié)點(diǎn)，，存放著著若干相相鄰控制制區(qū)間的的索引項(xiàng)項(xiàng)，每個(gè)個(gè)索引項(xiàng)項(xiàng)由控制制區(qū)間中中的最大大關(guān)鍵字字和指向向該控制制區(qū)間的的指針組組成。順順序集中中的一個(gè)個(gè)結(jié)點(diǎn)連連同其下下層所有有控制區(qū)區(qū)間形成成的整體體稱作控控制區(qū)域域（ControlRange））。順序序集中的的結(jié)點(diǎn)之之間用指指針相鏈鏈接，在在它們上上層的結(jié)結(jié)點(diǎn)又以以它們?yōu)闉榛A(chǔ)形形成索引引，并逐逐級(jí)向上上建立索索引，形形成B+樹的非非終端結(jié)結(jié)點(diǎn)。12-2412.4ISAM和VSAM文文件VSAM文件的的結(jié)構(gòu)示示意圖

控制區(qū)間控制區(qū)域索引集順序集數(shù)據(jù)集B+樹12-2512.4ISAM和VSAM文文件對VSAM文件件中記錄錄的檢索索，既可可從最高高層的索索引逐層層往下按按關(guān)鍵字字進(jìn)行檢檢索，又又可在順順序集中中沿著指指針鏈順順序檢索索。VSAM文文件沒沒有專專門的的溢出出區(qū)，，但可可以利利用控控制區(qū)區(qū)間中中的空空隙或或控制制區(qū)域域中的的空控控制區(qū)區(qū)間來來插入入記錄錄（即即在B+樹樹上插插入記記錄））。而而在VSAM文文件中中刪除除記錄錄時(shí)，，也需需移動(dòng)動(dòng)記錄錄。VSAM文文件占占有較較多的的存儲(chǔ)儲(chǔ)空間間，然然而它它具有有許多多優(yōu)點(diǎn)點(diǎn)，如如動(dòng)態(tài)態(tài)地分分配和和釋放放存儲(chǔ)儲(chǔ)空間間，無無需像像ISAM文件件那樣樣定期期重排排文件件，并并能較較快地地執(zhí)行行插入入操作作和保保持較較高的的檢索索效率率。VSAM文文件通通常作作為組組織大大型索索引順順序文文件的的標(biāo)準(zhǔn)準(zhǔn)形式式。12-2612.4ISAM和和VSAM文件件VASM文文件的的特點(diǎn)點(diǎn)優(yōu)點(diǎn)：：動(dòng)態(tài)態(tài)地分分配和和釋放放存儲(chǔ)儲(chǔ)空間間，不不需要要對文文件進(jìn)進(jìn)行重重組，，并能能較快快地對對插入入的記記錄進(jìn)進(jìn)行查查找，，查找找一個(gè)個(gè)后插插入記記錄的的時(shí)間間與查查找一一個(gè)原原有記記錄的的時(shí)間間是相相同的的。缺點(diǎn)：：占有有較多多的存存儲(chǔ)空空間，，一般般只能能保持持約75％％的存存儲(chǔ)空空間利利用率率。12-2712.5直直接接存取取文件件(散散列文文件)定義：：直接存存取文文件指的是是利用用雜湊湊（Hash））法進(jìn)進(jìn)行組組織的的文件件。它它類似似于哈哈希表表，既既根據(jù)據(jù)文件件中關(guān)關(guān)鍵字字的特特點(diǎn)設(shè)設(shè)計(jì)一一種哈哈希函函數(shù)和和處理理沖突突的方方法將將記錄錄散列列到存存儲(chǔ)設(shè)設(shè)備上上，故故又稱稱散列文文件。與哈哈希表表不同同的是是，對對于文文件來來說，，磁盤盤上的的文件件記錄錄通常常是成成組存存放的的。溢出處處理：：若干干個(gè)記記錄組組成一一個(gè)存存儲(chǔ)單單位，，在散散列文文件中中，這這個(gè)存存儲(chǔ)單單位叫叫做桶（Bucket）。。假若一一個(gè)桶桶能存存放m個(gè)記記錄，，這就就是說說，m個(gè)同同義詞詞的記記錄可可以存存放在在同一一地址址的桶桶中，，而當(dāng)當(dāng)?shù)趍＋1個(gè)同同義詞詞出現(xiàn)現(xiàn)時(shí)才才發(fā)生生“溢溢出””。對對散列列文件件主要要采用用鏈地地址法法處理理溢出出。發(fā)生““溢出出”時(shí)時(shí)，需需要將將第m＋1個(gè)同同義詞詞存放放到另另一個(gè)個(gè)桶中中，稱稱此桶桶為““溢出出桶””；相相對地地，稱稱前m個(gè)同同義詞詞存放放的桶桶為““基桶桶”。。溢出出桶和和基桶桶大小小相同同，相相互之之間用用指針針相鏈鏈接。。當(dāng)在在基桶桶中沒沒有待待查記記錄時(shí)時(shí)，就就順指指針?biāo)傅降揭绯龀鐾爸兄羞M(jìn)行行查找找。因因此，，希望望同一一散列列地址址的溢溢出桶桶和基基桶在在磁盤盤上的的物理理位置置不要要相距距太遠(yuǎn)遠(yuǎn)，最最好在在同一一柱面面上。。12-2812.5直直接接存取取文件件(散散列文文件)例如，，某一一文件件有18個(gè)個(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ù)法作作哈希希函數(shù)數(shù)H(key)＝keyMOD7。由由此得得到的的直接接存取取文件件如下下圖所所示。。桶編號(hào) 基桶 溢出桶00631841589505008 33023269164410962052782158101103556930083384直接存存取文文件示示例12-2912.5直直接接存取取文件件(散散列文文件)查找操操作查找過過程：首先先根據(jù)據(jù)給定定值求求得哈哈希地地址（（即基基桶號(hào)號(hào)），，將基基桶的的記錄錄讀入入內(nèi)存存進(jìn)行行順序序查找找，若若找到到關(guān)鍵鍵字等等于給給定值值的記記錄，，則檢檢索成成功；；否則則，若若基桶桶內(nèi)沒沒有填填滿記記錄或或其指指針域域?yàn)榭湛?，則則文件件內(nèi)不不含有有待查查記錄錄；否否則根根據(jù)指指針域域的值值的指指示將將溢出出桶的的記錄錄讀入入內(nèi)存存繼續(xù)續(xù)進(jìn)行行順序序查找找，直直至檢檢索成成功或或不成成功。。因此此，總總的查查找時(shí)時(shí)間為為：T=a(te+ti)其中：：a為為存取取桶數(shù)數(shù)的期期望值值（相相當(dāng)于于哈希希表中中的平平均查查找長長度）），對對鏈地地址處處理溢溢出來來說，，a=1+αα/2；；te為存存取一一個(gè)桶桶所需需的時(shí)時(shí)間；；ti為在在內(nèi)存存中順順序查查找一一個(gè)記記錄所所需的的時(shí)間間。α為裝載因因子，在散散列文件中中：α=n/(bm)n為文件的的記錄數(shù)，，b為桶數(shù)數(shù)，m為桶桶的容量。。12-3012.5直直接存取取文件(散散列文件)刪除操作在直接存取取文件中刪刪除記錄時(shí)時(shí)，僅需對對被刪記錄錄作一標(biāo)記記即可。直接存取文文件的特點(diǎn)點(diǎn)優(yōu)點(diǎn)：文件件隨機(jī)存放放，記錄不不需進(jìn)行排排序；插入入、刪除方方便，存取取速度快，，不需要索索引區(qū)，節(jié)節(jié)省存儲(chǔ)空空間。缺點(diǎn)：不能能進(jìn)行順序序存取，只只能按關(guān)鍵鍵字隨機(jī)存存取，且詢詢問方式限限于簡單詢詢問，并且且在經(jīng)過多多次的插插入、刪除除之后，也也可能造成成文件結(jié)構(gòu)構(gòu)不合理，，即溢出桶桶滿而基桶桶內(nèi)多數(shù)為為被刪除的的記錄。此此時(shí)亦需重重組文件。。12-3112.6多多關(guān)鍵字字文件在對文件進(jìn)進(jìn)行檢索操操作是，不不僅對主關(guān)關(guān)鍵字進(jìn)行行簡單詢問問，還經(jīng)常常需要對關(guān)關(guān)鍵字進(jìn)行行其他類型型的詢問檢檢索。12.6.1多重重表文件特點(diǎn)：多重重表文