1、第11章 文件本章學習內容 11.1 文件的基本概念11.2 順序文件11.3 索引文件11.4 ISAM文件和VSAM文件11.5 散列文件11.6 多關鍵字文件10/12/20221第11章 文件本章學習內容 11.1 文件的基本概念1111.1 文件的基本概念文件是由大量性質相同的記錄所構成的集合。文件有不同的分類方式：按記錄類型分：操作系統(tǒng)文件和數(shù)據庫文件。按記錄是否定長分：定長記錄文件和不定長記錄文件。按查找關鍵字多少分：單關鍵文件和多關鍵文件。記錄有邏輯結構和存儲結構之分。記錄的邏輯結構，是指記錄在用戶或應用程序員面前呈現(xiàn)的方式，是用戶對數(shù)據的表示和存取方式。記錄的存儲結構是指數(shù)據

2、在物理存儲器中的存儲形式，是數(shù)據的物理表示和組織。10/12/2022211.1 文件的基本概念文件是由大量性質相同的記錄所構成的文件和數(shù)據元素一樣，也有邏輯結構和存儲結構。文件的邏輯結構可以表現(xiàn)為記錄的邏輯結構。文件的存儲結構是指文件在物理存儲器（磁盤或磁帶）中的組織方式。文件可以有各種各樣的組織方式，其基本方式有三種：順序組織、隨機組織和鏈組織。對文件所施加的運算（操作）有兩類：查找（檢索）和更新（修改）。文件的查找（檢索）有三種方式：順序查找、按記錄號直接隨機查找、按關鍵字直接隨機查找。文件的更新有三種方式：插入、刪除、更新一條記錄。10/12/20223文件和數(shù)據元素一樣，也有邏輯結構

3、和存儲結構。文件的邏輯結構可11.2 順序文件 順序文件是指記錄按其在文件中的邏輯順序依次存放到外部介質上的文件。也就是說，順序文件的物理記錄順序和邏輯記錄順序一致。若次序相繼的兩個物理記錄在存儲器中位置是相鄰的，則稱為連續(xù)文件；若物理記錄之間的次序由指針相鏈表示，則稱為串鏈文件。順序文件是根據記錄的序號或記錄的相對位置進行存取的文件組織方式。它的特點是：(1) 存取第K個記錄必須先搜索在它之前的K-1個記錄。(2) 插入新的記錄時只能在文件末尾插入。(3) 若要更新文件中的某個記錄，則必須將該文件復制。由于順序文件的優(yōu)點是連續(xù)存取速度快，因此主要用于順序存取、批量修改的情況。磁帶是一種典型的

4、順序存取設備，存儲在磁帶上的文件就是順序文件。但磁帶目前很少使用，使用的順序文件多為磁盤順序文件。對順序文件可以向順序表一樣，進行順序查找、分塊查找或折半查找（文件有序）。10/12/2022411.2 順序文件 順序文件是指記錄按其在文件中的邏輯順序依11.3 索引文件除了文件（主文件）本身外，另外建立一張指示邏輯記錄與物理記錄之間一一對應關系的表（索引表）。這種包含主文件數(shù)據和索引表兩大部分的文件稱為索引文件。索引表中的每一項稱為索引項，索引項由記錄的關鍵字與記錄的存放地址構成。索引文件是按關鍵字有序排列的，若主文件也按關鍵字有序排列，這樣的索引文件稱為索引順序文件；若主文件是無序的，這樣

5、的索引文件為索引非順序文件。索引表是由系統(tǒng)程序自動生成的。在輸入記錄的同時建立一個索引表，表中的索引項按記錄輸入的先后次序排列，待全部記錄輸入完畢再對索引表進行排序。索引文件的查找方式為直接查找或按關鍵字查找，和前面介紹的分塊查找類似，但必須分兩步走：首先在索引表中查找，若找到則再到主文件中查找；否則主文件中不存在該記錄，也就不要訪問外存了。10/12/2022511.3 索引文件除了文件（主文件）本身外，另外建立一張指示索引表是有序表，可以用快速的折半查找來實現(xiàn)，而主文件為索引順序文件時，也可以用折半查找實現(xiàn)，主文件為索引非順序文件時，只能用順序查找來實現(xiàn)。 當一個文件很大時，索引表也很大，

6、這時可以對索引表再建立一個索引，稱為二級索引。更大的索引表可以建立多級索引。在圖11-1中，（a）為主表，(b)為一級索引表，(c)為二級索引表。但圖11-1中的多級索引是一種靜態(tài)索引，為順序表結構。雖然結構簡單，但修改很不方便，所以當主文件在使用過程中變化比較大時，應采用樹表結構的動態(tài)索引，如二叉排序樹、B樹、鍵樹等，以便于插入、刪除。10/12/20226索引表是有序表，可以用快速的折半查找來實現(xiàn)，而主文件為索引順 (a)主表 (b)索引表 (c)二級索引表 圖11-1 索引表文件示例 10/12/20227 (a)主表 11.4 ISAM文件和VSAM文件11.4.1 ISAM文件ISA

7、M（Indexed Sequential Access Method）索引順序存取方法的縮寫，它是一種專為磁盤存取設計的文件組織方式。由于磁盤是以盤組、柱面和磁道三級地址存取的設備，則可對磁盤上的數(shù)據文件建立盤組、柱面、磁道三級索引。文件的記錄在同一盤組上存放時，應先集中放在一個柱面上，然后再順序存放在相鄰的柱面上，對同一柱面，則應按盤面的次序順序存放。例如圖11-2為存放在一個磁盤組上的ISAM文件，每個柱面建立一個磁道索引，每個磁道索引項由兩部分組成：基本索引項和溢出索引項。每一部分都包含關鍵字和指針兩項，前者表示該磁道中最末一個記錄的關鍵字（最大關鍵字），后者指示該磁道中第一個記錄的位置

8、，柱面索引的每一個索引項也由關鍵字和指針兩項組成，前者表示該柱面中最末一個記錄的關鍵字（最大關鍵字），后者指示該柱面上的磁道索引位置。10/12/2022811.4 ISAM文件和VSAM文件11.4.1 ISAM在ISAM文件上檢索記錄時，先從主索引出發(fā)找到相應的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在磁道的第一個記錄的位置，由此出發(fā)在該磁道上進行順序查找直到找到為止；反之，若找遍該磁道而不存在此記錄，則表明該文件中無此記錄。例如，在圖11-2中，查找關鍵字21時，先找到主索引中620，再找到柱面索引164，最后找到磁道索引50，最后順序查找到R21，查找

9、成功。若查找關鍵字48，先找到主索引中620，再找到柱面索引164，最后找到磁道索引50，最后順序查找到R50，無R48，查找不成功。10/12/20229在ISAM文件上檢索記錄時，先從主索引出發(fā)找到相應的柱面索引圖11-2 ISAM文件結構10/12/202210圖11-2 ISAM文件結構10/10/202210從圖11-2可以看到，每個柱面上還開辟有一個溢出區(qū)，這是為插入記錄所設置的。由于ISAM文件中記錄是按關鍵字順序存放的，則在插入記錄時需移動記錄并將同一磁道上最末一個記錄移到溢出區(qū)，同時修改磁道索引項。通常在文件中可集中設置一個溢出區(qū)，或在每個柱面分別設置一個溢出區(qū)，或在柱面溢出

10、區(qū)滿后再使用公共溢出區(qū)。ISAM文件中刪除記錄比插入記錄簡單，只要找到待刪除的記錄，在存儲位置上作刪除標記而無需移動記錄或改變指針。則在經過多次的增刪后，文件的結構可能變得很不合理，這時應將記錄讀入內存重排，進行ISAM文件的整理。10/12/202211從圖11-2可以看到，每個柱面上還開辟有一個溢出區(qū)，這是為插11.4.2 VSAM文件VSAM（Virtual Storage Access Method）虛擬存儲存取方法的縮寫。這種存取方法利用了操作系統(tǒng)的虛擬存儲器的功能，用戶無需了解文件的具體單位，給用戶使用文件提供方便。VSAM文件由三部分組成：索引集、順序集和數(shù)據集。數(shù)據集存放文件的

11、所有記錄，順序集和索引集一起構成一棵B+樹，為文件的索引部分。數(shù)據集中的一個結點稱為控制區(qū)間，它由一組連續(xù)的存儲單元組成，是一個I/O操作的基本單位。一個文件上的每個控制區(qū)的大小相同，含有一個或多個按關鍵字遞增有序排列的記錄并帶有一定的控制信息（如記錄長度、區(qū)間中的記錄數(shù)等）。順序集中的一個結點用于存放若干相鄰控制區(qū)間的索引項（含有控制區(qū)間中的最大關鍵字和指向控制區(qū)間的指針組成），該結點連同其對應的下層所控制區(qū)間形成一個整體，稱為控制區(qū)域。順序集中的結點相互之間用指針相鏈，在他們上一層的結點又以他們?yōu)榛A形成索引，并逐級向上建立索引，形成B+樹的非終端結點。10/12/20221211.4.2

12、 VSAM文件VSAM（Virtual Stor對VSAM文件中記錄的檢索，既可以從最高層的索引逐層往下按關鍵字進行查找，又可以在順序集中沿著指針鏈順序查找。VSAM文件沒有專門的溢出區(qū)，但可以利用控制區(qū)間中的空隙或控制區(qū)域中的空控制區(qū)域來插入記錄（B+樹上插入）。在控制區(qū)間中插入記錄時，為保證區(qū)間內記錄關鍵字的有序，需移動記錄。而當區(qū)間中記錄已滿、再要插入記錄時，區(qū)間將分裂。而在VSAM文件中刪除記錄時，也需要移動記錄。VSAM文件占有較多的存儲空間，存儲空間的利用率也只能保持75%左右。但它的優(yōu)點是：動態(tài)分配和釋放存儲空間，無需象ISAM文件那樣定期重組文件，并能較快地對插入的記錄進行查找

13、和插入。10/12/202213對VSAM文件中記錄的檢索，既可以從最高層的索引逐層往下按關11.5 散列文件散列文件是指利用哈希(Hash)函數(shù)進行組織的文件。它實際上是一個根據某個哈希函數(shù)和一定的處理沖突方法而得到的、存放在外存上的散列表。與哈希表不同的是，對于文件而言，磁盤上的文件記錄通常是成組存放的。若干個記錄組成一個存儲單位，在散列文件中這個存儲單位叫作桶。一個桶能存放的邏輯記錄的總數(shù)稱為桶的容量。假設一個桶能存放m個記錄，即m個同義詞的記錄可以保存到同一地址的桶中，第m+1個同義詞出現(xiàn)時則發(fā)生“溢出”。處理溢出也采用哈希表中處理沖突的各種方法；但對散列文件，主要采用鏈地址法。當發(fā)生

14、“溢出”時，需要將第m+1個同義詞存放到另一個桶中，通常稱此桶為“溢出桶”；相對地，稱前m個同義詞存放的桶為“基桶”。溢出桶可以有多個，它們和基桶大小相同，相互之間用指針鏈接。10/12/20221411.5 散列文件散列文件是指利用哈希(Hash)函數(shù)進行組若要在散列文件中進行查找，先根據散列函數(shù)的地址找到對應的基桶，在基桶中查找；若找到，則查找成功；若找不到，則進入溢出桶中進行查找，若找到，查找成功，否則查找失敗。若要在散列文件中插入記錄，先根據散列函數(shù)的地址找到對應的基桶，有空間則直接插入，否則在它所對應的溢出桶中插入。例如，給定記錄關鍵字為19，13，23，1，68，20，84，28，

15、55，14，10，89，93，69，16，11，33，35。用除留余數(shù)法給定哈希函數(shù)H(key)=key%7。桶的容量m=3，基本桶數(shù)=7，由此得到的散列文件見圖11-3。10/12/202215若要在散列文件中進行查找，先根據散列函數(shù)的地址找到對應的基桶圖11-3 散列文件示例散列文件的優(yōu)點：插入、刪除記錄方便，存取速度比索引文件快，不需要索引區(qū)，節(jié)省存儲空間。散列文件的缺點：不能進行順序存取，只能按關鍵字隨機存取，且詢問方式只有簡單詢問；并且在經過多次插入、刪除之后，也可能造成文件結構不合理，即溢出桶滿而基桶內多數(shù)為被刪除的記錄。此時亦需重組文件。10/12/202216圖11-3 散列文

16、件示例散列文件的優(yōu)點：插入、刪除記錄方便，11.6 多關鍵字文件多關鍵字文件的特點是，在對文件進行檢索操作時，不僅要對主關鍵字進行簡單詢問，還要對次關鍵字進行其它類型的詢問檢索。因此，對多關鍵字文件，還要建立一系列的次關鍵索引。次關鍵字索引和主關鍵索引所不同的是，每個索引項應包含次關鍵字、具有同一次關鍵字的多個記錄的主關鍵字或物理記錄號。下面將討論多關鍵字文件的兩種組織方法。11.6.1 多重表文件多重表文件的特點是：記錄按主關鍵字的順序構成一個串聯(lián)文件，并建立主關鍵字的索引（主索引）；對每一個次關鍵字建立次關鍵字索引（次索引），所有具有同一次關鍵字的記錄構成一個鏈表。主索引為非稠密索引（一組

17、記錄建立一個索引項），次索引為稠密索引（一個記錄建立一個索引項）。每個索引項包含次關鍵字、頭指針和鏈表長度。例如，圖11-4所示就是一個多重表文件。其中，編號為主關鍵字，記錄按編號順序鏈接。對編號分稠密索引，分成3個鏈表，其索引如圖11-4(b)所示，索引項中的主關鍵字為各組中的最大值。部門、職稱為兩個次關鍵字，它們的索引如圖11-4(c)、11-4(d)所示。具有相同次關鍵字的記錄鏈接在同一鏈表中。10/12/20221711.6 多關鍵字文件多關鍵字文件的特點是，在對文件進行檢索(a)數(shù)據文件 (b)主關鍵字索引 (c)部門索引 (d)職稱索引圖11-4 多重表文件示例10/12/2022

18、18(a)數(shù)據文件 (b)主關鍵字索引 在多重表中進行查找很方便，根據關鍵字值找到鏈表的頭指針，然后從頭指針出發(fā)可以找出鏈表中所有記錄。例如，要查找計算機系的教授，可以從部門索引表找到計算機系的頭指針和鏈表長度，分別為1和4，從第1個記錄開始，按鏈表找到第3個記錄，再找到第6個即可。若找遍整個鏈表都沒有符合要求的記錄，則查找失敗。在多重表文件中插入一條記錄很容易，只要修改指針，將記錄插在鏈表的頭指針之后。但是，要刪除一條記錄卻很繁瑣，需在每個次關鍵字的鏈表中刪去該記錄。10/12/202219在多重表中進行查找很方便，根據關鍵字值找到鏈表的頭指針，然后11.6.2 倒排文件 倒排文件和多重表文件的區(qū)別在于次關鍵字索引的結構不同。通常稱倒排文件中的次關鍵字索引為倒排表，具有相同次關鍵字的記錄之間不設指針相鏈，而在倒排表中該次關鍵字的一項中存放這些記錄的物理記錄號。例如，11-4(a)數(shù)據文件的倒排表如圖11-5所示。（a）部門倒排表 (b)職稱倒排表 圖11-5 倒排表文件示例10/12/20222011.6.2 倒排文件 倒排文件和多重表文件的區(qū)別在于次關鍵在倒排表文件中，檢索記錄速度快。特別是處理多個次關鍵字檢索。在處理各種次關鍵字的詢問時，只要在次關鍵字索引中找出有關指針的集合，再對這些指針進行交、并、差等集合運算，