第7章文件與外部排序7.1文件及文件操作7.2文件組織7.3磁盤文件的歸并排序7.4磁帶文件的歸并排序17.1文件及文件操作有結(jié)構(gòu)文件和無結(jié)構(gòu)文件:

在有結(jié)構(gòu)文件中,文件有若干個(gè)相關(guān)記錄組成,

無結(jié)構(gòu)文件中,文件被看作是一個(gè)字符流。2

一、相關(guān)概念

1、定義：文件是用于表示駐留在外存儲(chǔ)器中的數(shù)據(jù)。關(guān)鍵字、主關(guān)鍵字、次關(guān)鍵字7.1文件及文件操作3

2、文件的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)

(1)邏輯結(jié)構(gòu)：

描述記錄間的邏輯關(guān)系,包括文件中記錄順序,記錄中包含多少個(gè)域,域的定義、順序等。

(2)物理結(jié)構(gòu)：

存儲(chǔ)結(jié)構(gòu)，記錄在存儲(chǔ)器中的存儲(chǔ)方式，連續(xù)、鏈?zhǔn)?、索引、散列等?.1文件及文件操作4

3、文件操作

操作

●INSERT●DELETE

●MODIFY●RETRIEVE

查詢方式：

簡單查詢

范圍查詢

函數(shù)查詢

布爾查詢7.1文件及文件操作5檢索方式：實(shí)時(shí)or

成批更新方式：實(shí)時(shí)or

成批7.1文件及文件操作**6

1、順序方式

2、索引方式

3、散列方式

4、鏈接方式7.2

文件組織71、順序方式

文件的各個(gè)記錄按邏輯順序存放在外存的連續(xù)區(qū)內(nèi)。

(1)對(duì)設(shè)備的要求適合磁盤和磁帶。

(2)適合的查詢方法

記錄的順序往往是按主關(guān)鍵字的大小排列。

適合簡單查詢；可用順序查找或折半查找。

7.2

文件組織8

(3)插入或刪除記錄插入或刪除需大量移動(dòng)信息。插入信息時(shí)可將待插入數(shù)據(jù)先放入一個(gè)臨時(shí)的溢出區(qū)(附加文件)中，當(dāng)數(shù)量足夠多或到固定時(shí)間時(shí)統(tǒng)一作插入處理。在刪除時(shí)可暫作刪除標(biāo)記，到一定量時(shí)或固定時(shí)間再統(tǒng)一刪除。**7.2

文件組織9

2、索引方式定義

索引：指的是記錄的關(guān)鍵字值與記錄駐留在外存的地址組成數(shù)對(duì)的集合。每個(gè)數(shù)對(duì)稱為一個(gè)索引項(xiàng)。

索引文件在存儲(chǔ)器上分兩區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。

(1)稠密索引每一個(gè)記錄建立一個(gè)索引項(xiàng)。

(2)稀疏索引對(duì)文件中一組記錄建成一個(gè)索引項(xiàng)。

7.2

文件組織10

(3)查找過程

分兩步進(jìn)行：先在索引區(qū)查找索引項(xiàng)，再根據(jù)索項(xiàng)找到記錄。

(4)查找方式。

索引表一般是有序的，適合順序查找，折半查找。

(5)刪除記錄

只刪除索引。

(6)插入記錄

先存數(shù)據(jù)，然后登記索引并重新排序

(7)建立文件：

按數(shù)據(jù)存入的先后順序建立索引，最后索引排序。7.2

文件組織**11三、散列文件

用散列（HASH）法組織的文件。特點(diǎn)是用一個(gè)散列函數(shù)H(key)，將關(guān)鍵字key映射為記錄的地址，即記錄地址=HASH(key)。

7.2

文件組織**12四、鏈接式文件和多重鏈接表文件把文件中的記錄按主關(guān)鍵字的某種次序用鏈接字鏈接起來。優(yōu)點(diǎn)：方便插入和刪除缺點(diǎn)：不利于查找。只能用順序查找，7.2

文件組織13

1、索引鏈接文件把原來的鏈表按某種原則拆分成多個(gè)鏈表。每一個(gè)鏈表建立一個(gè)索引項(xiàng)，形成一個(gè)索引文件。7.2

文件組織14

2、多重索引鏈接文件除按主關(guān)鍵字建立索引鏈接文件外，對(duì)各次關(guān)健字也建立索引。7.2

文件組織15記錄工號(hào)姓名職務(wù)指針性別指針婚否指針…A29丁一程序員^男E婚E…B05王二維修員E男G婚A…C02趙中程序員G女D婚BD38錢森工程師H女F否HE31劉玉維修員F男^婚FF43李芳維修員^女H婚^G17張紅程序員A男A否DH46王有工程師^女^否^次關(guān)鍵字長度指針程序員3C維修員3B工程師2D次關(guān)鍵字長度指針男4B女4C7.2

文件組織16

3、倒排文件在多重鏈接文件中，具有同一關(guān)鍵字值的所有記錄鏈接在一起，并且原始的記錄中保存有這些鏈指針。鏈指針的信息保存在索引中，只根據(jù)索引就可找到具有同一關(guān)鍵字的所有記錄。7.2

文件組織17記錄工號(hào)姓名職務(wù)性別婚否…A29丁一程序員男婚…B05王二維修員男婚…C02趙中程序員女婚D38錢森工程師女否E31劉玉維修員男婚F43李芳維修員女婚G17張紅程序員男否H46王有工程師女否次關(guān)鍵字指針程序員A,C,G維修員B,E,F工程師D,H次關(guān)鍵字指針男B,G.A.E女C,D,F,H7.2

文件組織***18假設(shè)有一個(gè)磁盤文件,其中有4500個(gè)記錄,依次為A1,A2,…,A4500;

設(shè)系統(tǒng)可提供一個(gè)能容納750個(gè)記錄的內(nèi)存工作空間供外部分類使用。每次磁盤的讀寫單位是250個(gè)記錄的數(shù)據(jù)塊。7.3磁盤文件的歸并分類19每次從文件中輸入三個(gè)數(shù)據(jù)塊共750個(gè)記錄，用內(nèi)部分類法進(jìn)行分類，將結(jié)果寫回磁盤文件中，形成6個(gè)有序的初始?xì)w并段。R11-750R2751-1500…R63751-4500歸并R1與R2,R3與R4,R5與R6一、初始?xì)w并段的生成7.3磁盤文件的歸并分類20將內(nèi)存工作空間三等分。每等分能容納250個(gè)記錄，其中兩塊作為輸入緩沖區(qū)，另一塊作為輸出緩沖區(qū)。以R1與R2的歸并為例:從R1與R2中各讀入250個(gè)記錄；歸并好的記錄寫入輸出緩沖區(qū)；如果輸出緩沖區(qū)滿,則寫入磁盤；如果輸入緩沖區(qū)空則繼續(xù)讀入；直到在磁盤上形成一個(gè)長為1500的有序段。**二、磁盤文件的歸并過程7.3磁盤文件的歸并分類21

8.1.1K路歸并一次歸并K個(gè)有序段一趟歸并后長度增加多少?K倍假如第i趟歸并完成,m=ki.i=logkm假如第i趟歸并完成,初始?xì)w并段個(gè)數(shù)為m7.3磁盤文件的歸并分類22

8.1.1K路歸并的比較次數(shù)從K個(gè)元素中選擇最小值需k-1次比較.若記錄總個(gè)數(shù)為n,則需比較n(k-1)K路歸并的總比較次數(shù)n(k-1)logkmK路歸并的總比較次數(shù)n(k-1)log2m/log2kK路歸并的總比較次數(shù)是(k-1)/log2k的倍數(shù)隨K的增加比較趟數(shù)減少。比較次數(shù)增大。7.3磁盤文件的歸并分類23選擇樹(敗者樹):每個(gè)結(jié)點(diǎn)的關(guān)鍵字都取它的兩個(gè)子結(jié)點(diǎn)的關(guān)鍵字中較小者.1516203820301525155011161001101820109206899017968176867.3磁盤文件的歸并分類24時(shí)間復(fù)雜性分析:

第一次建樹的時(shí)間復(fù)雜性為O(k-1)

以后每次的時(shí)間復(fù)雜性為O(log2k)

處理n個(gè)數(shù)據(jù)的時(shí)間為

(n-1)*log2k+O(k)

k路歸并共需logkm趟歸并

O(n*log2k*logkm)=O(n*log2m)與K路歸并的K值無關(guān)。**7.3磁盤文件的歸并分類25在k路歸并中需要k個(gè)輸入緩沖區(qū),一個(gè)輸出緩沖區(qū);當(dāng)輸出緩沖區(qū)滿時(shí)，這時(shí)需要把輸出緩沖區(qū)的內(nèi)容轉(zhuǎn)移到磁盤上，歸并運(yùn)行要等到輸出完才能開始;同理：在輸入緩沖區(qū)中，如果有一個(gè)排空，需要讀入數(shù)據(jù)后才能繼續(xù)進(jìn)行。7.3磁盤文件的歸并分類26增加一個(gè)輸出緩沖區(qū)，當(dāng)一個(gè)輸出緩沖區(qū)滿時(shí)，通知通道進(jìn)行輸出，同時(shí)歸并程序向第二個(gè)輸出緩沖區(qū)中寫數(shù)據(jù)。同理：增加k個(gè)輸入緩沖區(qū)，當(dāng)一個(gè)輸入緩沖正在運(yùn)行時(shí)，另外一個(gè)可以讀數(shù)據(jù)。7.3磁盤文件的歸并分類27設(shè)4個(gè)輸入緩沖區(qū)為in[i],兩個(gè)輸出緩沖區(qū)為ou[1]和ou[2]

設(shè)有兩組記錄

run1:1,3,5,7,8,9run2:2,4,6,15,20,257.3磁盤文件的歸并分類28--O(1)O(2)--13i(1)i(2)24--i(3)i(4)--歸并到O(1)輸入到i(3)12O(1)O(2)---3i(1)i(2)-457i(3)i(4)--run1:1,3,5,7,8,9run2:2,4,6,15,20,257.3磁盤文件的歸并分類29歸并到O(2)輸入到i(4)--O(1)O(2)34--i(1)i(2)--57i(3)i(4)61512O(1)O(2)---3i(1)i(2)-457i(3)i(4)--輸出O(1)run1:1,3,5,7,8,9run2:2,4,6,15,20,257.3磁盤文件的歸并分類30歸并到O(1)輸入到i(1)56O(1)O(2)--89i(1)i(2)---7i(3)i(4)-15輸出O(2)--O(1)O(2)34--i(1)i(2)--57i(3)i(4)615run1:1,3,5,7,8,9run2:2,4,6,15,20,257.3磁盤文件的歸并分類31歸并到O(2)輸入到i(2)--O(1)O(2)78-9i(1)i(2)2025--i(3)i(4)-15輸出O(1)56O(1)O(2)--89i(1)i(2)---7i(3)i(4)-15run1:1,3,5,7,8,9run2:2,4,6,15,20,257.3磁盤文件的歸并分類32歸并到O(1)輸入到i(3)9-O(1)O(2)----i(1)i(2)2025--i(3)i(4)-15輸出O(2)run1:1,3,5,7,8,9run2:2,4,6,15,20,25--O(1)O(2)78-9i(1)i(2)2025--i(3)i(4)-15**7.3磁盤文件的歸并分類33初始?xì)w并段越長越好。越長歸并的趟數(shù)越少.

如果緩沖區(qū)能容納P個(gè)記錄,如果不采取措施，則初始?xì)w并段的長度是P。

怎樣才能產(chǎn)生大于P的歸并段?

可以采用選擇樹法(置換—選擇樹法)產(chǎn)生大于P的歸并段?7.3磁盤文件的歸并分類34

設(shè)輸入文件的各個(gè)記錄的關(guān)鍵字為15,19,04,83,12,27,11,25,16,34,26,07,10,90,061519048304,1519128315192783111927831125278311162783111634831116268311162607

假設(shè)緩沖區(qū)長度能容納4個(gè)記錄12,15,19,25,27,34,83***具統(tǒng)計(jì)得：用選擇樹方法，可產(chǎn)生2P長的初始?xì)w并段7.3磁盤文件的歸并分類35

與磁盤不同，磁帶是順序存儲(chǔ)設(shè)備，讀取信息塊的時(shí)間與信息塊的位置有關(guān)。研究磁帶分類，需要了解信息塊的分布。7.4磁帶文件的歸并分類367.4.1平衡歸并分類K路平衡歸并分類磁帶機(jī)數(shù)量：2K磁帶機(jī)T1T2…Tk歸并段R1RK+1….Rmk+1R2RK+2….Rmk+2……RkR2k….….7.4磁帶文件的歸并分類37假設(shè)文件中記錄總數(shù)為6000,初始?xì)w并段為1000,采用二路歸并,4臺(tái)磁帶機(jī)為:T1,T2,T3,T4

T1:R1(1000),R3(1000),R5(1000)T2:R2(1000),R4(1000),R6(1000)

T3:空

T4:空7.4磁帶文件的歸并分類38

T1:空

T2:空

T3:R1(2000),R3(2000)T4:R2(2000)7.4磁帶文件的歸并分類39

T1:R1(4000)T2:R2(2000)

T3:空

T4:空7.4磁帶文件的歸并分類40

T1:空

T2:空

T3:R1(6000),T4:空***7.4磁帶文件的歸并分類417.4.2多階段歸并K路平衡歸并分類磁帶機(jī)數(shù)量：K+1以k=2為例,用三臺(tái)磁帶機(jī),t1,t2,t3,假設(shè)初始?xì)w并段長為L,初始?xì)w并段放在t1,t2中,其中放的段數(shù)不等7.4磁帶文件的歸并分類42第八章外部分類t1t2t3開始13(1L)21(1L)空1234567空8(1L)13(2L)8(3L)空5(2L)5(5L)空3(3L)3(8L)空2(5L)2(13L)空1(8L)空1(21L)1(13L)1(34L)空空43第八章外部分類步t1t2t3總段數(shù)n0011n-1n-2n-3n-4n-5n-6n-71102201302353508805130813211321034***44第八章外部分類小結(jié)

1、內(nèi)部分類過程中不需要數(shù)據(jù)的內(nèi)、外存交換，待分類的記錄全部存放在內(nèi)存中；

2、若待非類的文件很大，就無法將整個(gè)文件的所有記錄同時(shí)調(diào)入內(nèi)存進(jìn)行分類；

3、外部分類的實(shí)現(xiàn)，主要是依靠數(shù)據(jù)的內(nèi)、外存交換和內(nèi)部歸并。

4、外部分類基本上包括相對(duì)獨(dú)立的兩個(gè)階段：初始?xì)w并段的形成；多路歸并。45第八章外部分類小結(jié)

5、外部分類主要研究的技術(shù)問題是：

(1)如何進(jìn)行多路歸并以減少文件的歸并遍數(shù)；

(2)如何運(yùn)用內(nèi)存的緩沖區(qū)使I/O和CPU盡可能并行工作；

(3)根據(jù)外存的特點(diǎn)選擇較好的產(chǎn)生初始?xì)w并段的方法。46考試題型一、選擇題（每小題2分，共20分）二、判斷題（每小題1分，共10分）三、填空題（每小題2分，共20分）四、應(yīng)用題6個(gè)（共50分）47第八章外部分類1．磁盤排序過程主要是先生成（），然后對(duì)（）合并，而提高排序速度最重要的是()，我們將采用()方法來提高排序速度。【山東工業(yè)大學(xué)1995一、4（4分）】初始?xì)w并段,初始?xì)w并段,減少外存信息讀寫次數(shù)（即減少歸并趟數(shù)）,增加歸并路數(shù)和減少初始?xì)w并段個(gè)數(shù)。48第八章外部分類2．設(shè)輸入的關(guān)鍵字滿足k1>k2>…>kn，緩沖區(qū)大小為m，用置換-選擇排序方法可產(chǎn)生____個(gè)初始?xì)w并段?！疚錆h大學(xué)2000一、9】

n/m49第八章外部分類3．以歸并算法為例，比較內(nèi)排序和外排序的不同，說明外排序如何提高操作效率?！救A南師范大學(xué)1999四(10分)】1、內(nèi)部排序中的歸并排序是在內(nèi)存中進(jìn)行的歸并排序，時(shí)間復(fù)雜性為nlog2n,輔助空間為O(n)。

2、外部歸并排序是將外存中的多個(gè)有序子文件合并成一個(gè)有序子文件，

3、歸并的趟數(shù)s=logkm,其中，m是歸并段個(gè)數(shù)，k是歸并路數(shù),增加歸并路數(shù)減少內(nèi)外存讀寫次數(shù);

通過敗者樹進(jìn)行多（k）路歸并減少比較次數(shù);

通過置換-選擇法減少初始?xì)w并段個(gè)數(shù);

利用緩存提高I/O與CPU工作和并行性.50第八章外部分類4、給出一組關(guān)鍵字T=(12,2,16,30,8,28,4,10,20,6,18),設(shè)內(nèi)存工作區(qū)可容納4個(gè)記錄，寫出用置換-選擇排序得到的全部初始?xì)w并段。

【上海交通大學(xué)1999十】2，8，12，16，28，304，6，10，18，20***51例題一、選擇題1.散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)樯⒘泻瘮?shù)是一對(duì)一的關(guān)系，則選擇好的（）方法是散列文件的關(guān)鍵。【哈爾濱工業(yè)大學(xué)2001二、5（2分）】散列函數(shù)B.除余法中的質(zhì)數(shù)C.沖突處理D.散列函數(shù)和沖突處理D522.順序文件采用順序結(jié)構(gòu)實(shí)現(xiàn)文件的存儲(chǔ)，對(duì)大型的順序文件的少量修改，要求重新復(fù)制整個(gè)文件，代價(jià)很高，采用（）的方法可降低所需的代價(jià)。【北京郵電大學(xué)2000二、8（20/8分）】附加文件B.按關(guān)鍵字大小排序C.按記錄輸入先后排序D.連續(xù)排序例題A533．下述文件中適合于磁帶存儲(chǔ)的是（）。