數(shù)據(jù)結(jié)構(gòu)與算法9

第9章文件（2課時(shí)）9.6多關(guān)鍵字文件9.4索引順序文件9.8應(yīng)用實(shí)例9.3索引文件9.7外排序9.1文件的基本概念9.2順序文件9.5散列文件文件是由大量具有相同性質(zhì)的記錄組成的集合。按記錄類型不同，文件可以分為兩類操作系統(tǒng)文件操作系統(tǒng)文件是一維的無(wú)結(jié)構(gòu)連續(xù)字符序列，其中存儲(chǔ)的數(shù)據(jù)按不同含義被劃分為若干個(gè)字符組，每一個(gè)字符組就稱為一條記錄。數(shù)據(jù)庫(kù)文件（數(shù)據(jù)結(jié)構(gòu)主要討論）數(shù)據(jù)庫(kù)文件則是由多條具有相同結(jié)構(gòu)的記錄組成的集合。9.1文件的基本概念9.1文件的基本概念9.1.1文件的組成9.1.5磁盤存儲(chǔ)器9.1.2文件的分類9.1.3文件的操作9.1.4文件的結(jié)構(gòu)文件是大量性質(zhì)相同的數(shù)據(jù)記錄的集合，即一個(gè)文件包含一條或多條記錄。記錄是一個(gè)實(shí)體的所有數(shù)據(jù)項(xiàng)的集合，即一條記錄包含一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)。數(shù)據(jù)項(xiàng)（也稱為字段或?qū)傩裕┦欠从硨?shí)體某一方面屬性的數(shù)據(jù)表示，是文件存取最基本的操作對(duì)象。關(guān)鍵字，次關(guān)鍵字9.1文件的基本概念9.1.1文件的組成按文件中記錄的信息長(zhǎng)度定長(zhǎng)文件：若每個(gè)記錄含有相同長(zhǎng)度的信息，則稱這類記錄為定長(zhǎng)記錄。由定長(zhǎng)記錄組成的文件稱為定長(zhǎng)文件。不定長(zhǎng)文件：若每個(gè)記錄含有不同長(zhǎng)度的信息，則稱這類記錄為不定長(zhǎng)記錄。由不定長(zhǎng)記錄組成的文件則稱為不定長(zhǎng)文件按記錄中關(guān)鍵字的數(shù)目單關(guān)鍵字文件：若文件中的記錄只有一個(gè)用于唯一標(biāo)識(shí)記錄的主關(guān)鍵字，則這類文件稱為單關(guān)鍵字文件。多關(guān)鍵字文件：若文件中的記錄除了含有一個(gè)主關(guān)鍵字之外，還包含若干次關(guān)鍵字，則這類文件稱為多關(guān)鍵字文件。9.1文件的基本概念9.1.2文件的分類文件檢索簡(jiǎn)單查詢區(qū)域查詢函數(shù)查詢布爾查詢文件維護(hù)插入刪除修改9.1文件的基本概念9.1.3文件的操作文件的結(jié)構(gòu)邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)是指文件中各記錄之間的邏輯關(guān)系（線性或非線性）。物理結(jié)構(gòu)：物理結(jié)構(gòu)是指文件在外存中的組織方式。文件基本的物理結(jié)構(gòu)方式順序結(jié)構(gòu)索引結(jié)構(gòu)散列結(jié)構(gòu)鏈?zhǔn)浇Y(jié)構(gòu)。9.1文件的基本概念9.1.4文件的結(jié)構(gòu)前面章節(jié)中的數(shù)據(jù)結(jié)構(gòu)研究的是數(shù)據(jù)在內(nèi)存中的組織方式，而文件研究的是數(shù)據(jù)在外存中的組織方式。由于內(nèi)存和外存在存取速度上有著較大差異，因此，文件與其他數(shù)據(jù)結(jié)構(gòu)研究的側(cè)重點(diǎn)有所不同。硬盤的組成9.1文件的基本概念9.1.5磁盤存儲(chǔ)器硬盤的讀寫步驟1.根據(jù)待讀寫數(shù)據(jù)所處的柱面，用動(dòng)臂將讀寫磁頭移動(dòng)到此柱面上。2.根據(jù)待讀寫數(shù)據(jù)所處的扇區(qū)，用主軸帶動(dòng)盤面將該扇區(qū)轉(zhuǎn)到讀寫磁頭下面。3.用指定盤面上的讀寫磁頭讀寫所需數(shù)據(jù)。硬盤上進(jìn)行一次數(shù)據(jù)讀寫操作所需的時(shí)間其中，tseek為尋查時(shí)間，即將磁頭定位到指定柱面所需的時(shí)間；tla為等待時(shí)間，即將磁頭定位到指定扇區(qū)所需的時(shí)間；twm為傳輸時(shí)間，即傳送一個(gè)扇區(qū)數(shù)據(jù)所需的時(shí)間。9.1文件的基本概念9.1.5磁盤存儲(chǔ)器9.2順序文件順序文件是結(jié)構(gòu)最簡(jiǎn)單的文件，文件中記錄的物理順序與邏輯順序一致，即記錄按其邏輯順序依次存放在文件中。9.2順序文件9.2.1順序文件的分類9.2.2順序文件的操作及實(shí)現(xiàn)按照記錄是否有序有序順序文件無(wú)序順序文件。按照存儲(chǔ)方式的不同連續(xù)順序文件串聯(lián)順序文件9.2順序文件9.2.1順序文件的分類9.2順序文件將待處理的順序文件稱為主文件，主文件按主關(guān)鍵字大小順序排列對(duì)文件的插入、刪除、修改等操作請(qǐng)求全部放在事務(wù)文件中根據(jù)事務(wù)文件中的操作對(duì)主文件進(jìn)行更新生成新的主文件順序文件批量處理步驟對(duì)事務(wù)文件按照主文件中主關(guān)鍵字的順序進(jìn)行排序?qū)τ谛薷闹麝P(guān)鍵字值的操作，轉(zhuǎn)為刪除記錄和插入記錄兩個(gè)操作順序讀出主文件與事務(wù)文件中的記錄，比較它們的主關(guān)鍵字值9.2.2順序文件的操作及實(shí)現(xiàn)9.2順序文件例如，對(duì)表9-1的學(xué)生文件依次進(jìn)行如下操作：插入一條新的記錄（20110006，李延，1201091990XXXXXXXX，612，通信工程）；刪除學(xué)生記錄（20110005，嚴(yán)麗，3000141989XXXXXXXX，635，通信工程）；將學(xué)生記錄（20110007，吳紅，3000311990XXXXXXXX，603，計(jì)算機(jī)應(yīng)用）改為（20110007，吳紅，3000311990XXXXXXXX，603，通信工程）。以字符“I”、“D”和“U”分別表示插入、刪除和修改操作，則生成的事務(wù)文件如表9-2所示9.2順序文件9.2.2順序文件的操作及實(shí)現(xiàn)9.2順序文件9.2.2順序文件的操作及實(shí)現(xiàn)9.2順序文件9.2.2順序文件的操作及實(shí)現(xiàn)9.3索引文件順序文件的檢索、插入、刪除、修改等操作都需要頻繁地進(jìn)行外存的讀/寫操作，主要適用于批量處理的情況。對(duì)于要求高實(shí)時(shí)性的應(yīng)用，則應(yīng)采用非順序文件的組織形式。本節(jié)所要介紹的索引文件是在順序文件的基礎(chǔ)上增加了一個(gè)索引表。9.3索引文件9.3.1順序文件的分類9.3.2順序文件的操作及實(shí)現(xiàn)9.3索引文件索引文件由主文件和索引表兩部分構(gòu)成。主文件中存儲(chǔ)了所有的數(shù)據(jù)記錄索引表是一個(gè)映射關(guān)系表，存儲(chǔ)了邏輯記錄和物理記錄的一一對(duì)應(yīng)關(guān)系索引表中各索引項(xiàng)嚴(yán)格按主關(guān)鍵字有序排列，而主文件中的各記錄可以有序也可以無(wú)序。若主文件中各記錄也是按主關(guān)鍵字有序排列的，則稱該索引文件為索引順序文件；否則，若主文件中各記錄是無(wú)序的，則稱該索引文件為索引非順序文件。（簡(jiǎn)稱為索引文件）9.3.1順序文件的分類9.3索引文件圖9-2為一個(gè)索引非順序文件示例。主文件以學(xué)號(hào)為主關(guān)鍵字，但沒有按主關(guān)鍵字有序排列。索引表按主關(guān)鍵字升序排列。9.3.1順序文件的分類9.3索引文件9.3.2順序文件的操作及實(shí)現(xiàn)檢索操作將索引表讀入內(nèi)存中，并根據(jù)檢索條件在索引表中進(jìn)行查找。若索引表中存在匹配項(xiàng)，則根據(jù)匹配索引項(xiàng)中存儲(chǔ)的物理地址直接讀取外存上的相應(yīng)記錄；若索引表中不存在該記錄，則說(shuō)明外存上也不存在該記錄、不需做外存訪問操作。插入、刪除和修改操作插入：在索引文件中插入一條新的記錄時(shí)，直接將該記錄寫入主文件的末尾，并在索引表中插入索引項(xiàng)；刪除：在刪除一條記錄時(shí)，只需在索引表中刪除對(duì)應(yīng)的索引項(xiàng)即可；修改：在修改記錄時(shí)，需將修改后的記錄寫入主文件的末尾，并同時(shí)對(duì)索引表進(jìn)行修改、將索引項(xiàng)中的物理地址改為修改后記錄的存儲(chǔ)地址。9.3索引文件9.3.2順序文件的操作及實(shí)現(xiàn)

例如，對(duì)于圖9-2所示的索引非順序文件，依次進(jìn)行如下操作：1）插入一條新記錄（0018，陳功，23）；2）將學(xué)號(hào)為0008的記錄刪除；3）將學(xué)號(hào)為0076的記錄的年齡改為24。上述操作之后可以得到圖9-3所示的索引非順序文件。9.3索引文件9.3.2順序文件的操作及實(shí)現(xiàn)9.4散列文件散列文件是利用哈希存儲(chǔ)方式進(jìn)行組織的文件，也稱為直接存取文件。與哈希表的不同之處在于：散列文件中的記錄是以桶為單位成組存放的。若一個(gè)桶能存放m條記錄，則當(dāng)桶中已有m條同義詞記錄時(shí)，再存放第m+1條同義詞記錄就會(huì)發(fā)生“溢出”。在散列文件中，通常采用拉鏈法作為沖突處理方法，即將第m+1條同義詞記錄存放到另一個(gè)稱為“溢出桶”的桶中，相應(yīng)地，將存放前m條同義詞記錄的桶稱為“基桶”，在基桶中設(shè)置一個(gè)指向溢出桶的指針。9.5多關(guān)鍵字文件多關(guān)鍵字文件就是指既包含主關(guān)鍵字索引、又包含多個(gè)次關(guān)鍵字索引的文件。本節(jié)介紹兩種多關(guān)鍵字文件的組織方法多重表文件倒排文件9.5.1多重表文件9.5.2倒排文件9.5多關(guān)鍵字文件9.5多關(guān)鍵字文件9.5.1多重表文件9.5多關(guān)鍵字文件9.5.2倒排文件9.6外排序在做文件排序時(shí)就需進(jìn)行多次內(nèi)/外存之間的數(shù)據(jù)交換，這種基于外存的排序技術(shù)就稱為外排序。如果待排序的記錄數(shù)量很大，以至于不能將它們一次性讀入到內(nèi)存中進(jìn)行處理。在對(duì)文件中的記錄進(jìn)行排序時(shí)，通常是把記錄分成若干部分，每次只將一部分記錄調(diào)入內(nèi)存進(jìn)行處理。9.6.1歸并排序的思想9.6.2歸并排序的實(shí)現(xiàn)9.6外排序歸并排序處理步驟記錄分段處理：將文件中的記錄按照可用內(nèi)存大小劃分為若干段，依次將每段記錄讀入到內(nèi)存中對(duì)其進(jìn)行內(nèi)部排序，并將排序結(jié)果輸出到子文件中。這樣可以生成多個(gè)有序的子文件（即文件內(nèi)的記錄是有序的），通常稱經(jīng)過排序后的段為初始?xì)w并段。文件歸并處理：對(duì)上一步得到的初始?xì)w并段加以歸并，直至將多段中的記錄歸并為一個(gè)有序文件為止。9.6外排序9.6.1歸并排序的思想9.6外排序9.6.1歸并排序的思想9.6外排序9.6.1歸并排序的思想9.6外排序9.6.2歸并排序的實(shí)現(xiàn)為了減少K個(gè)記錄比較所占用的時(shí)間，一般利用敗者樹來(lái)實(shí)現(xiàn)K路歸并敗者樹的結(jié)構(gòu)如下：是一棵有K個(gè)葉子結(jié)點(diǎn)的完全二叉樹；K個(gè)葉子結(jié)點(diǎn)分別存儲(chǔ)從K個(gè)初始?xì)w并段中讀取出來(lái)的K個(gè)待比較的記錄；分支結(jié)點(diǎn)存儲(chǔ)兩個(gè)記錄比較后敗者（即具有較大關(guān)鍵字值的記錄）所在葉子結(jié)點(diǎn)的序號(hào)，勝者參與更高一層的比較；通常在敗者樹的根結(jié)點(diǎn)之上再加一個(gè)結(jié)點(diǎn)來(lái)保存勝者（即當(dāng)前K個(gè)記錄中具有最小關(guān)鍵字值的記錄）所在葉子結(jié)點(diǎn)的序號(hào)。9.6外排序9.6.2歸并排序的實(shí)現(xiàn)9.6外排序失敗樹重構(gòu)舉例9.6.2歸并排序的實(shí)現(xiàn)9.6外排序失敗樹重構(gòu)舉例9.6.2歸并排序的實(shí)現(xiàn)9.6外排序敗者樹的創(chuàng)建9.6.2歸并排序的實(shí)現(xiàn)9.6外排序敗者樹的創(chuàng)建9.6.2歸并排序的實(shí)現(xiàn)9.7應(yīng)用實(shí)例編寫程序，以學(xué)號(hào)作為主關(guān)鍵字對(duì)學(xué)生文件進(jìn)行外排序。