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

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