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

8.1文件及文件操作8.2文件組織第8章文件8.1文件及文件操作1、相關(guān)概念文件是用于表示駐留在外存儲(chǔ)器中的數(shù)據(jù)，是同性質(zhì)記錄的有序集合。記錄學(xué)號(hào)姓名性別年齡數(shù)學(xué)語文物理其它A003孫喆B008陳益C009史碩剛D010許藝洪E011張爽F(xiàn)012沈鍵關(guān)鍵字：主關(guān)鍵字次關(guān)鍵字文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu)：呈現(xiàn)給用戶，描述記錄間的邏輯關(guān)系物理結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)，記錄在存儲(chǔ)器中的組織，連續(xù)，鏈?zhǔn)降?、文件操作操作●INSERT●DELETE

●MODIFY●

RETRIEVE檢索方式：實(shí)時(shí)or成批更新方式：實(shí)時(shí)or成批查詢方式：Q1:簡單查詢Q2:范圍查詢

Q3:函數(shù)查詢Q4:布爾查詢Main(){FILE*fp;……}Sourcefile.c輸入數(shù)據(jù)原始數(shù)據(jù)磁盤/帶文件處理結(jié)果輸出數(shù)據(jù)文件指針文件結(jié)構(gòu)體——FILEtypedefstruct{int_fd;//文件號(hào)

int_cleft;//緩沖區(qū)中剩下的字符數(shù)

int_mode;//文件操作方式

char*_next;//文件當(dāng)前讀寫位置

char*_buff;//文件緩沖區(qū)位置}FILE;文件信息用系統(tǒng)定義的名為FILE的結(jié)構(gòu)體描述Stdio.hFILE*變量名；Intfclose(FILE*fp)FILE*fopen(char*name,char*mode)

fread(buffer,size,count,fp);

fwrite(buffer,size,count,fp);標(biāo)準(zhǔn)輸入----鍵盤

stdin標(biāo)準(zhǔn)輸出----顯示器

stdout標(biāo)準(zhǔn)出錯(cuò)輸出----顯示器stderr#include"stdio.h"

main(intargc,char*argv[]){FILE*in,*out;if(argc!=3){printf("Youforgottoenterafilename\n");exit(0);}if((in=fopen(argv[1],"r"))==NULL){printf("Cannotopeninfile!\n");exit(0);}if((out=fopen(argv[2],"w"))==NULL){printf("Cannotopenoutfile!\n");exit(0);}

while(!feof(in))fputc(fgetc(in),out);fclose(in);fclose(out);}？按用途

系統(tǒng)文件、庫文件、用戶文件

按保護(hù)級(jí)別

可執(zhí)行文件、只讀文件、讀寫文件按信息流向

輸入文件、輸出文件、輸入輸出文件按存放時(shí)限

臨時(shí)文件、永久文件、檔案文件按設(shè)備類型

磁盤文件、磁帶文件、卡片文件、打印文件

按文件組織結(jié)構(gòu)邏輯文件(流式文件、記錄式文件)、物理文件（順序文件、鏈接文件、索引文件）文件分類FAT：FileAllocationTableNTFS：NewTechnologyFilesSyatemWinFS：WindowsFutureStorage操作系統(tǒng)FAT12Fat16Fat32NTFSNTFS5.0WinFSDOS3.0以下是支

持

末

來

的

操

作

系

統(tǒng)Dos3.0是DOS4.0是Windows3.X是Windows95是Windows95OSR2是是Windows98是是Windows98SE是WindowsMe是是WindowsNT是是Windows2000是是是是WindowsXP是是是是Windows2003是是是是Unix

是

Linux

是是(軟盤引導(dǎo))

文件大小限制最大支持8M最大支持2G不能大于4G單文件最大64GB單文件最大2TB8.2文件組織

順序方式索引方式

ISAMVSAM

散列方式鏈接方式

UNIX8.2.1順序方式文件的各個(gè)記錄按邏輯順序存放在外存的連續(xù)區(qū)內(nèi)記錄的順序往往是按主關(guān)鍵字的大小排列的適合于Q1型查詢，且檢索與更新是成批進(jìn)行的適合磁帶或磁盤串聯(lián)文件：物理記錄之間的次序由指針相鏈表示的順序文件。（1）定義

順序文件（SequentialFile）：是記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的，即順序文件中物理記錄的順序和邏輯記錄的順序是一致的。

連續(xù)文件：次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置是相鄰的順序文件。（2）特點(diǎn)順序文件是根據(jù)記錄的序號(hào)或記錄的相對位置來進(jìn)行存取的文件組織方式。它的特點(diǎn)是：①存取第i個(gè)記錄，必須先搜索在它之前的i－1個(gè)記錄。②插入新的記錄時(shí)只能加在文件的末尾。③若要更新文件中的某個(gè)記錄，則必須將整個(gè)文件進(jìn)行復(fù)制。（3）磁帶上順序文件的批處理主文件：待修改的原始文件。事務(wù)文件：所有的修改請求集中構(gòu)成的一個(gè)文件。磁帶文件的批處理過程：首先對事務(wù)文件進(jìn)行排序，然后將主文件和事務(wù)文件歸并成一個(gè)新的主文件。

其中，主文件、事務(wù)文件和新的主文件分別存放中一臺(tái)磁帶上。主文件按關(guān)鍵字自小至大（或自大至?。╉樞蛴行颍聞?wù)文件必須和主文件有相同的有序關(guān)系。職工老文件事物文件職工新文件文件修改程序磁帶文件操作實(shí)例

終端事務(wù)文件排序有序的事務(wù)文件主文件新主文件

在歸并的過程中，順序讀出主文件與事務(wù)文件中的記錄，比較它們的關(guān)鍵字并分別進(jìn)行處理。對于關(guān)鍵字不匹配的主文件中的記錄，則直接將其寫入新主文件中?！案摹焙汀皠h除”記錄時(shí)，要求其關(guān)鍵字相匹配?！皠h去”不用寫入，而“更改”則要將更改后的新記錄寫入新主文?！安迦搿睍r(shí)不要求關(guān)鍵字相匹配，可直接將事務(wù)文件上要插入的記錄寫到新主文件的適當(dāng)位置。算法實(shí)現(xiàn)：算法中用到的各符號(hào)的含義說明如下：

f—主文件；g—事務(wù)文件；h—新主文件。它們都按關(guān)鍵字遞增排序。事務(wù)文件的每個(gè)記錄中，增設(shè)一個(gè)代碼以示修改要求，其中：“I”表示插入；“D”表示刪去；“U”表示更改。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的結(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ù)Q將fr和gr歸并成一個(gè)h結(jié)構(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}//MergeFile分析批處理算法的時(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)。(4)磁盤上順序文件的批處理磁盤上順序文件的批處理和磁帶文件類似，只是當(dāng)修改項(xiàng)中沒有插入，且更新時(shí)不增加記錄的長度時(shí)，可以不建立新的主文件，而直接修改原來的主文件即可。顯然，磁盤文件的批處理可以在一個(gè)磁盤上進(jìn)行。

假設(shè)所有的輸入/輸出都是通過緩沖區(qū)進(jìn)行的，并假設(shè)緩沖區(qū)大小為s（個(gè)記錄），則整個(gè)批處理過程中讀/寫外存的次數(shù)為：n：主文件包含的記錄數(shù)，m：事務(wù)文件包含記錄數(shù)8.2.2索引方式“索引”指的是記錄的關(guān)鍵字值與記錄駐留在外存的地址組成數(shù)對的集合。每個(gè)數(shù)對稱為一個(gè)索引項(xiàng)。索引文件在存儲(chǔ)器上分兩區(qū)：索引區(qū)和數(shù)據(jù)區(qū)查找記錄：分兩步進(jìn)行刪除記錄：只刪除索引插入記錄：先存數(shù)據(jù)，然后登記索引并重新排序建立文件：按數(shù)據(jù)存入的先后順序建立索引，最后索引排序示例：序號(hào)姓名記錄內(nèi)容記錄位置柱面號(hào)盤面號(hào)1AnCai…11人事檔案示意文件柱面的最大關(guān)鍵字柱面號(hào)CaiLong1柱面索引盤面的最大關(guān)鍵字盤面號(hào)LiHong1盤面索引

非稠密索引：數(shù)據(jù)文件中的記錄按關(guān)鍵字順序有序，則可對一組記錄建立一個(gè)索引項(xiàng)，這種索引表稱為非稠密索引。（1）基本術(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ù)區(qū)的同時(shí)建立一個(gè)索引表，表中的索引項(xiàng)按記錄輸入的先后次序排列，待全部記錄輸入完畢后再對索引表進(jìn)行排序。（2）索引表的生成索引表是由系統(tǒng)程序自動(dòng)生成的。（3）索引文件的檢索檢索方式：直接存取或按關(guān)鍵字（進(jìn)行簡單詢問）存取。

檢索過程：首先，查找索引表，若索引表上存在該記錄，則根據(jù)索引項(xiàng)的指示讀取外存上該記錄;否則說明外存上不存在該記錄，也就不需要訪問外存。

由于索引項(xiàng)的長度比記錄小得多，則通?？蓪⑺饕硪淮巫x入內(nèi)存，由此再索引文件中進(jìn)行檢索只訪問外存兩次，即一次讀索引，一次讀記錄。并且由于索引表是有序的，則查找索引表時(shí)可用折半查找法。（4）索引文件的修改①刪除操作：刪除一個(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)。（5）多級(jí)索引查找表：對索引表建立的索引。例如，上圖的索引表需占3個(gè)物理塊的外存，每一個(gè)物理塊容納3個(gè)索引，則建立的查找表如圖12.4所示。檢索記錄時(shí)，先查找查找表，再查索引表，然后讀取記錄。最大關(guān)鍵字物理塊號(hào)171382463通常最高可有四級(jí)索引：

上述的多級(jí)索引是一種靜態(tài)索引，各級(jí)索引均為順序表結(jié)構(gòu)。其結(jié)構(gòu)簡單，但修改很不方便，每次修改都要重組索引。因此，當(dāng)數(shù)據(jù)文件在使用過程中記錄變動(dòng)較多時(shí)，應(yīng)采用動(dòng)態(tài)索引。如,二叉排序樹（或二叉平衡樹）、B-樹以及鍵樹。多級(jí)索引結(jié)構(gòu)形成m路搜索樹數(shù)據(jù)區(qū)一級(jí)索引二級(jí)索引三級(jí)索引四級(jí)索引多級(jí)索引結(jié)構(gòu)形成m叉樹。每個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊，最多存放m個(gè)索引項(xiàng)每個(gè)索引項(xiàng)給出各子樹結(jié)點(diǎn)(較低一級(jí)索引塊)的最大關(guān)鍵碼和結(jié)點(diǎn)地址。葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的記錄的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級(jí)索引，就是m路搜索樹ISAM和VSAM文件8.2.3ISAM文件（1）定義索引順序存取方法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è)記錄。②柱面索引項(xiàng)關(guān)鍵字：表示該柱面中最末一個(gè)記錄的關(guān)鍵字（最大關(guān)鍵字）。指針：指示該柱面上的磁道索引位置。主索引柱面索引磁道索引基本數(shù)據(jù)區(qū)ISAM文件結(jié)構(gòu)示意圖圖12.5 ISAM文件結(jié)構(gòu)示例R164

磁道索引50磁道索引柱面C1

柱面索引

主索引R14R21R45R47R50164164164330

溢出區(qū)

溢出區(qū)

溢出區(qū)柱面C2柱面C3R189R215R33011004150415041508103303843215

磁道索引

磁道索引R3843R4150

關(guān)鍵字指針關(guān)鍵字指針基本索引項(xiàng)溢出索引項(xiàng)圖為存放一個(gè)磁盤組上的ISAM文件。每個(gè)柱面建立一個(gè)磁道索引，每個(gè)磁道索引項(xiàng)由基本索引項(xiàng)和溢出索引項(xiàng)兩部分組成。

柱面索引存放在某個(gè)柱面上，若柱面索引較大，占多個(gè)磁道時(shí)，則可建立柱面索引的索引——主索引。（2）ISAM文件的檢索在ISAM文件上檢索記錄的過程：先從主索引出發(fā)找到相應(yīng)的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置，由此出發(fā)在該磁道上進(jìn)行順序查找直至找到為止；反之，若找遍該磁道而不存在此記錄，則表明該文件中無此記錄。（3）溢出區(qū)和插入操作溢出區(qū)是為插入記錄所設(shè)置的。每個(gè)柱面的基本區(qū)是順序存儲(chǔ)結(jié)構(gòu)，而溢出區(qū)是鏈表結(jié)構(gòu)。同一磁道溢出的記錄由指針相鏈。溢出區(qū)的設(shè)置方法：①集中存放：整個(gè)文件設(shè)一個(gè)大的單一的溢出區(qū)。②分散存放：每個(gè)柱面設(shè)一個(gè)溢出區(qū)。③集中與分散相結(jié)合：溢出時(shí)記錄先移至每個(gè)柱面各自的溢出區(qū)，待滿之后再使用公共溢出區(qū)。(a)插入前R50 R60 R70R80 R90R100 R120 R130R136 R145 T2T3T4溢出區(qū)基本區(qū)90T2’1145T3’1基本索引項(xiàng)溢出索引項(xiàng)基本索引項(xiàng)溢出索引項(xiàng)道索引其中：為插入前的某一柱面上的狀態(tài)；為插入R65時(shí)，將第2道中關(guān)鍵字大于65的記錄順次后移，且使R90溢出至溢出區(qū)的情況；為插入R65之后的狀態(tài)，此時(shí)2道的基本索引項(xiàng)的關(guān)鍵字改為80，且溢出索引項(xiàng)的關(guān)鍵字改為90，其指針指向第4道第一個(gè)記錄即R90。是相繼插入R95和R83后的狀態(tài)，R95插入在第3道的第一個(gè)記錄的位置而使R145溢出。而由于80<83<90則R83被直接插入道溢出區(qū)，作為第2道在溢出區(qū)的第一個(gè)記錄，并將它的指針指向R90的位置，同時(shí)修改第2道索引的溢出索引項(xiàng)的指針指向R83。（4）刪除操作

ISAM文件中刪除記錄，只需找到待刪除的記錄，在其存儲(chǔ)位置上做刪除標(biāo)記即可，而不需要移動(dòng)記錄或改變指針。但在經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時(shí)，大量的記錄進(jìn)入溢出區(qū)，而基本區(qū)中又浪費(fèi)很大空間。由此，通常需要周期地整理ISAM文件。把記錄讀入內(nèi)存，重新排列，復(fù)制成一個(gè)新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。（5）柱面索引的位置假設(shè)文件占有n個(gè)柱面，柱面索引在第x柱面上，則磁頭移動(dòng)距離的平均值為： 令，得到。這就是說，柱面索引應(yīng)放在數(shù)據(jù)文件的中間位置的柱面上。8.2.4VSAM文件控制區(qū)域（ControlRange）：順序集中一個(gè)結(jié)點(diǎn)連同對應(yīng)所有控制區(qū)間形成的一個(gè)整體。（1）定義虛擬存儲(chǔ)存取方法VSAM（VirtualStorageAccessMethed）：該方法利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能，給用戶提供方便。對用戶來說，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲(chǔ)單位，與外存儲(chǔ)器中柱面、磁道等具體存儲(chǔ)單位沒有必然的聯(lián)系?？刂茀^(qū)間（ControlInterval）：它是一個(gè)I/O操作的基本單位，由一組連續(xù)的存儲(chǔ)單元組成。同一文件上控制區(qū)間的大小相同。每個(gè)控制區(qū)間可視為一個(gè)邏輯磁道，而每個(gè)控制區(qū)域可視為一個(gè)邏輯柱面。

在VSAM文件中，記錄可以是不定長的，則在控制區(qū)間中除了存放記錄本身以外，還有每個(gè)記錄的控制信息和整個(gè)區(qū)間的控制信息，控制區(qū)間的結(jié)構(gòu)如圖所示。在控制區(qū)間上存取一個(gè)記錄時(shí)需從控制區(qū)間的兩端出發(fā)同時(shí)向中間掃描。記 記 未利用記錄n記錄1控制空錄錄 的的的控制間的控

1n 空閑空間控制信息信息制信息

控制區(qū)間的結(jié)構(gòu)示意圖（2）刪除操作在VSAM文件中刪除記錄是，需將同一控制區(qū)間中較刪除記錄關(guān)鍵字大的記錄向前移動(dòng)，把空間留給以后插入的新記錄。若整個(gè)控制區(qū)間變空，則需修改順序集中相應(yīng)的索引項(xiàng)。

（3）插入操作

VSAM文件中沒有溢出區(qū)，解決插入的辦法是在初建文件時(shí)留有空間。每個(gè)控制區(qū)間內(nèi)不填滿記錄，在最末一個(gè)記錄和控制信息之間留有孔隙；在每個(gè)控制區(qū)域中有一些完全空的控制區(qū)間，并在順序集的索引中指明這些空區(qū)間。當(dāng)插入記錄時(shí)，大多數(shù)的新記錄能插入到相應(yīng)的控制區(qū)間內(nèi)，但要注意為了保持區(qū)間內(nèi)記錄的關(guān)鍵字自小至大有序，則需將區(qū)間內(nèi)關(guān)鍵字大于插入記錄關(guān)鍵字的記錄向控制信息的方向移動(dòng)。若在若干記錄插入之后控制區(qū)間已滿，則在下一個(gè)記錄插入時(shí)要進(jìn)行控制區(qū)間的分裂，既將近乎一半的記錄移到同一控制區(qū)域中全空的控制區(qū)間中，并修改順序集中相應(yīng)索引。若控制區(qū)域中已經(jīng)沒有全空的控制區(qū)間，則要進(jìn)行控制區(qū)域的分裂，此時(shí)順序集中的結(jié)點(diǎn)亦要分裂，由此尚需修改索引集中的結(jié)點(diǎn)信息。8.2.5散列方式用散列（HASH）法組織的文件。特點(diǎn)是用一個(gè)散列函數(shù)H(key)，將關(guān)鍵字key映射為記錄的地址，即:

記錄地址=HASH(key)基本步驟:確定記錄數(shù)存儲(chǔ)單位（桶）記錄數(shù)確定桶數(shù)設(shè)計(jì)HASH(key)函數(shù)（4）VASM文件的特點(diǎn)優(yōu)點(diǎn)：動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，不需要對文件進(jìn)行重組，并能較快地對插入的記錄進(jìn)行查找，查找一個(gè)后插入記錄的時(shí)間與查找一個(gè)原有記錄的時(shí)間是相同的。缺點(diǎn)：占有較多的存儲(chǔ)空間，一般只能保持約75％的存儲(chǔ)空間利用率。（1）定義

直接存取文件指的是利用雜湊（Hash）法進(jìn)行組織的文件。它類似于哈希表，既根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種哈希函數(shù)和處理沖突的方法將記錄散列到存儲(chǔ)設(shè)備上，故又稱散列文件。與哈希表不同的是，對于文件來說，磁盤上的文件記錄通常是成組存放的。（2）溢出處理若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，在散列文件中，這個(gè)存儲(chǔ)單位叫做桶（Bucket）。假若一個(gè)桶能存放m個(gè)記錄，這就是說，m個(gè)同義詞的記錄可以存放在同一地址的桶中，而當(dāng)?shù)趍＋1個(gè)同義詞出現(xiàn)時(shí)才發(fā)生“溢出”。解決溢出：鏈地址法當(dāng)發(fā)生“溢出”時(shí)，需要將第m＋1個(gè)同義詞存放到另一個(gè)桶中，通常稱此桶為“溢出桶”；相對地，稱前m個(gè)同義詞存放的桶為“基桶”。溢出桶和基桶大小相同，相互之間用指針相鏈接。當(dāng)在基桶中沒有待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。（3）圖形表示例如，某一文件有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直接存取文件示例其中：a為存取桶數(shù)的期望值（相當(dāng)于哈希表中的平均查找長度），對鏈地址處理溢出來說，a=1+α/2；te為存取一個(gè)桶所需的時(shí)間；ti為在內(nèi)存中順序查找一個(gè)記錄所需的時(shí)間。（4）查找操作查找過程：首先根據(jù)給定值求得哈希地址（即基桶號(hào)），將基桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則，若基桶內(nèi)沒有填滿記錄或其指針域?yàn)榭?，則文件內(nèi)不含有待查記錄；否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內(nèi)存繼續(xù)進(jìn)行順序查找，直至檢索成功或不成功。因此，總的查找時(shí)間為：T=a(te+ti)α為裝載因子，在散列文件中：其中：n為文件的記錄數(shù)，b為桶數(shù)，m為桶的容量。（5）刪除操作在直接存取文件中刪除記錄時(shí)，僅需對被刪記錄作一標(biāo)記即可。（6）直接存取文件的特點(diǎn)

優(yōu)點(diǎn)：文件隨機(jī)存放，記錄不需進(jìn)行排序；插入、刪除方便，存取速度快，不需要索引區(qū)，節(jié)省存儲(chǔ)空間。

缺點(diǎn)：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問方式限于簡單詢問，并且在經(jīng)過多次的插入、刪除之后，也可能造成文件結(jié)構(gòu)不合理，即溢出桶滿而基桶內(nèi)多數(shù)為被刪除的記錄。此時(shí)亦需重組文件。最大學(xué)號(hào)204060記錄B記錄C記錄A記錄D記錄F記錄E多重索引:在記錄中保存鏈接索引鏈接8.2.6鏈接方式多關(guān)鍵字文件

特點(diǎn)：在對文件進(jìn)行檢索操作是，不僅對主關(guān)鍵字進(jìn)行簡單詢問，還經(jīng)常需要對關(guān)鍵字進(jìn)行其他類型的詢問檢索。1、多重表文件多重表文件（MultilistFile）的特點(diǎn)是：①記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，并建立主關(guān)鍵字的索引（稱為主索引）；②對每一個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。

主索引為非稠密索引，次索引為稠密索引。每個(gè)索引項(xiàng)包括次關(guān)鍵字、頭指針和鏈表長度。01 王雯135002軟件0241203丙02丁0302馬小雁135103軟件0739807甲04丙0303 阮森135204計(jì)算機(jī)05436^乙05丙04丁0504蘇明明1353^應(yīng)用0640208甲06丙0805 田永135406計(jì)算機(jī)^38402乙07丁0906 楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09 王洪135810應(yīng)用1037005甲10丁^10 劉倩1359^應(yīng)用^36409甲^記錄號(hào)姓名學(xué)號(hào)專業(yè)已修學(xué)分選修課程數(shù)據(jù)文件：一個(gè)多重表其中，學(xué)號(hào)為主關(guān)鍵字，記錄按學(xué)號(hào)順序鏈接，為了查找方便，分成3個(gè)子鏈表，其索引如圖(b)所示，索引項(xiàng)中的主關(guān)鍵字為各子表中的最大值。(b)主關(guān)鍵字索引

主關(guān)鍵字頭指針1353 011357 051359 09次關(guān)鍵字頭指針長度350~399 06 6400~449 04 4次關(guān)鍵字頭指針長度甲 02 7乙 03 3丙 01 5丁 01 4(d)“已修學(xué)分”索引(e)“選修課目”索引圖12.10 多重表文件示例(c)“專業(yè)”索引次關(guān)鍵字頭指針長度軟件 014計(jì)算機(jī) 032應(yīng)用044專業(yè)、已修學(xué)分和選修課目為3個(gè)次關(guān)鍵字項(xiàng)，它們的索引如圖(c)～(e)所示，具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中。記錄職工號(hào)姓名職務(wù)指針性別指針婚否指針工資A29丁一程序員^男E婚E898B05王二維修員E男G婚A456C02趙忠程序員G女D婚B1200D38張三工程師H女F否H2400E31王五維修員F男^婚F456F43劉玉維修員^女H婚^456G17李芳程序員A男A否D1200H46張洪工程師^女^否^3000次關(guān)鍵字長度指針程序員3C維修員3B工程師2D次關(guān)鍵字長度指針男4B女4C次關(guān)鍵字長度指針婚5C否3G職務(wù)索引性別索引婚否索引多重鏈表文件結(jié)構(gòu)2、倒排文件——在索引中保存鏈接倒排文件和多重表文件的區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。通常稱倒排文件中的次關(guān)鍵字索引為倒排表，具有相同次關(guān)鍵字的記錄之間不設(shè)指針相鏈，而在倒排表中該次關(guān)鍵字的一項(xiàng)中存放這些記錄的物理記錄號(hào)。01 王雯135002軟件0241203丙02丁0302馬小雁135103軟件0739807甲04丙0303 阮森135204計(jì)算機(jī)05436^乙05丙04丁0504蘇明明1353^應(yīng)用0640208甲06丙0805 田永135406計(jì)算機(jī)^38402乙07丁0906 楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09 王洪135810應(yīng)用1037005甲10丁^10 劉倩1359^應(yīng)用^36409甲^記錄號(hào)姓名