第十二章學(xué)習(xí)目標(biāo)熟悉各類文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。重點(diǎn)和難點(diǎn)重點(diǎn)：了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。知識(shí)點(diǎn)順序文件、索引文件、索引順序文件、VSAM文件、散列文件、多關(guān)鍵字文件2/5/2023112.1有關(guān)文件的基本概念文件(File)是由大量性質(zhì)相同的記錄組成的集合，一般放在外存上。記錄是數(shù)據(jù)項(xiàng)的集合，是可存取的數(shù)據(jù)的基本單位。數(shù)據(jù)項(xiàng)由一個(gè)或多個(gè)位或字節(jié)組成，是不可分割的數(shù)據(jù)最小單位。定長(zhǎng)記錄文件文件中每個(gè)記錄含有的信息長(zhǎng)度相等。不定長(zhǎng)文件文件中含有信息長(zhǎng)度不等的不定長(zhǎng)記錄。2/5/20232單關(guān)鍵字文件文件中的記錄只有一個(gè)唯一標(biāo)識(shí)記錄的主關(guān)鍵字。多關(guān)鍵字文件文件中的記錄除了含有一個(gè)主關(guān)鍵字外，還含有若干個(gè)次關(guān)鍵字。記錄的屬性記錄中所有非關(guān)鍵字的數(shù)據(jù)項(xiàng)。記錄的邏輯結(jié)構(gòu)記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對(duì)數(shù)據(jù)的表示和存取方式。記錄的物理結(jié)構(gòu)數(shù)據(jù)在物理存儲(chǔ)器上存儲(chǔ)的方式，是數(shù)據(jù)的物理表示和組織。2/5/20233物理記錄計(jì)算機(jī)用一條I/0命令進(jìn)行讀寫的基本數(shù)據(jù)單位（物理塊）。物理記錄和邏輯記錄之間可能存在下列三種關(guān)系：一個(gè)物理記錄存放一個(gè)邏輯記錄；一個(gè)物理記錄包含多個(gè)邏輯記錄；多個(gè)物理記錄表示一個(gè)邏輯記錄。文件的檢索方式順序存取：存取下一個(gè)邏輯記錄。直接存??；存取第i個(gè)邏輯記錄。按關(guān)鍵字存?。汉?jiǎn)單查詢、區(qū)域查詢、函數(shù)查詢、布爾查詢2/5/20234文件的修改記錄的插入、刪除、修改。文件的物理結(jié)構(gòu)文件在外存上的組織方式。順序組織隨機(jī)組織鏈組織2/5/2023512.2順序文件順序文件定義

記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的，即物理記錄和邏輯記錄的順序是一致的。分類連續(xù)（順序）文件次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置是相鄰的。串聯(lián)（順序）文件物理記錄之間的次序由指針相鏈表示。2/5/20236特點(diǎn)存取第i個(gè)記錄，必須先搜索在它之前的i-1個(gè)記錄。新的記錄只能加在文件末尾。更新記錄，必須將整個(gè)文件復(fù)制。優(yōu)點(diǎn)連續(xù)存取的速度快，主要用于只進(jìn)行順序存取、批量修改的情況。存取設(shè)備磁帶適合于文件的數(shù)據(jù)量大、平時(shí)記錄變化少、只作批量修改的情況。磁盤2/5/2023712.3索引文件引入原因?qū)τ诎搓P(guān)鍵字存取得記錄結(jié)構(gòu)，順序查找和折半查找的速度很慢。為了避免大量與外存打交道，可以保存一個(gè)索引表來指示關(guān)鍵字與記錄地址之間的對(duì)應(yīng)關(guān)系。索引文件包括數(shù)據(jù)區(qū)和索引表兩部分。為按建立時(shí)，系統(tǒng)自動(dòng)開辟索引區(qū)。按記錄進(jìn)入的順序登記索引項(xiàng)。索引項(xiàng)指出該記錄的物理地址。最后，索引表按關(guān)鍵字排序。只能存儲(chǔ)在磁盤存儲(chǔ)設(shè)備上。2/5/202382/5/20239索引文件的檢索將索引表讀入內(nèi)存（若一個(gè)物理塊可容納一個(gè)索引表，則僅一次讀入，否則需要多次讀入）；查找索引表，確定記錄的物理地址（索引表有序，可折半查找）；根據(jù)物理地址，一次讀取記錄。索引文件的修改刪除僅刪去相應(yīng)的索引項(xiàng)。插入記錄進(jìn)入數(shù)據(jù)區(qū)末尾，索引項(xiàng)插入索引表中（或重新排序）。更新刪除與插入的結(jié)合。2/5/202310多級(jí)索引記錄數(shù)目很大，導(dǎo)致一個(gè)物理塊容納不了索引表。此時(shí)，查找索引表需要多次訪問內(nèi)存。對(duì)索引表再建立一個(gè)索引。最高可以有四級(jí)索引，此時(shí)檢索需要訪問外存5次。2/5/20231112.4ISAM文件和VSAM文件ISAM文件（索引順序存取法）是一種專為磁盤存取而設(shè)計(jì)的文件組織方式。由于磁盤是以盤組、柱面和磁道三級(jí)地址存取的設(shè)備，則可對(duì)磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級(jí)索引。文件的記錄在同一盤組上存放時(shí)，應(yīng)先集中放在一個(gè)柱面上，然后再順序存放在相鄰的柱面上，對(duì)同一柱面，則應(yīng)按盤面的次序順序存放。用這種方法建立起來的索引文件稱為ISAM文件。包括：索引區(qū)、數(shù)據(jù)基本區(qū)、數(shù)據(jù)溢出區(qū)。2/5/202312數(shù)據(jù)區(qū)索引區(qū)溢出區(qū)2/5/202313ISAM文件的檢索查主索引（駐內(nèi)存），將相應(yīng)柱面索引（在其柱面上）調(diào)用內(nèi)存。查柱面索引，將磁道索引（一般放在第0道上）調(diào)入內(nèi)存；查磁道索引，將本磁道上的所有記錄送入內(nèi)存；順序?qū)@一組記錄查找。ISAM文件的插入定位應(yīng)插入的磁道；按關(guān)鍵字順序插入新紀(jì)錄，將同一磁道上最后一個(gè)記錄移至溢出區(qū)；同時(shí)修改磁道索引項(xiàng)。2/5/202314ISAM文件的刪除找到待刪除的記錄，在其存儲(chǔ)位置上作刪除標(biāo)記即可，而不需要移動(dòng)記錄或改變指針。ISAM文件的整理經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時(shí)，大量得記錄進(jìn)入溢出區(qū)，而基本區(qū)中又浪費(fèi)很多空間。因此，通常需要周期地整理ISAM文件。把記錄讀入內(nèi)存，重新排列，復(fù)制成一個(gè)新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。2/5/20231512.4.2VSAM文件VSAM（虛擬存儲(chǔ)存取方法）利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能，給用戶提供方便。對(duì)用戶來說，存儲(chǔ)記錄時(shí)不需要考慮記錄的具體存儲(chǔ)位置，也不需要考慮何時(shí)執(zhí)行對(duì)外存的讀寫命令。VSAM文件結(jié)構(gòu)三部分組成：索引集、順序集和數(shù)據(jù)集。2/5/202316B+樹59971544597297101521374451596372859197索引集順序集數(shù)據(jù)集控制區(qū)間控制區(qū)域2/5/202317VSAM文件的檢索在控制區(qū)間上存取一個(gè)記錄時(shí)，需從控制區(qū)間兩端出發(fā)，同時(shí)向中間掃描。VSAM文件的插入新記錄插入到相應(yīng)的控制區(qū)間內(nèi)，移動(dòng)其它記錄，保持有序；控制區(qū)已滿時(shí)，要進(jìn)行控制區(qū)的分裂，即將一半的記錄移入另一個(gè)控制區(qū)間，并修改順序集中相應(yīng)索引。VSAM文件的刪除刪除記錄時(shí)，需將同一控制區(qū)間中記錄關(guān)鍵字較大的記錄向前移動(dòng)，把空間留給以后插入的新記錄。控制區(qū)間變空時(shí)，則需修改順序集中相應(yīng)的索引項(xiàng)。2/5/202318VSAM文件缺點(diǎn)占有較多的存儲(chǔ)空間，一般只能保持約76%的存儲(chǔ)空間利用率。VSAM文件優(yōu)點(diǎn)動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，不需要對(duì)文件進(jìn)行重組。能較快地對(duì)插入的記錄進(jìn)行查找，查找一個(gè)后插入的記錄和查找一個(gè)原有記錄的時(shí)間是相同的。2/5/20231912.5直接存取文件（散列文件）散列文件特點(diǎn)由記錄的關(guān)鍵碼“直接”得到記錄在外存（磁盤）上的映象地址。類似哈希表，根據(jù)文件中關(guān)鍵碼的特點(diǎn)設(shè)計(jì)一種“哈希函數(shù)”和“處理沖突的方法”，然后將記錄散列到外存儲(chǔ)設(shè)備上，故稱“散列文件”。桶散列文件的存儲(chǔ)單位，以磁道或塊為單位，由若干個(gè)記錄組成?；耙粋€(gè)桶能存放m個(gè)記錄，表示這m個(gè)有相同哈希函數(shù)值的記錄具有同一個(gè)桶地址，該桶稱為“基桶”。溢出桶當(dāng)發(fā)生“溢出”時(shí)，需要將第m+1個(gè)同義詞存放到另一個(gè)桶中。2/5/202320溢出桶可以有多個(gè)，它們和基桶大小相同，相互之間用指針相鏈接。當(dāng)在基桶中沒有找到待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。2/5/20232112.6多關(guān)鍵字文件主關(guān)鍵字文件的特點(diǎn)在對(duì)文件進(jìn)行檢索操作時(shí)，不僅對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問，還經(jīng)常需要對(duì)次關(guān)鍵字進(jìn)行其他類型的詢問檢索。因此，對(duì)多關(guān)鍵字文件，尚需建立一系列的次關(guān)鍵字索引。次關(guān)鍵字索引與主關(guān)鍵字索引所不同每個(gè)索引項(xiàng)應(yīng)包含次關(guān)鍵字、具有同一次關(guān)鍵字的多個(gè)記錄的主關(guān)鍵字或或物理記錄號(hào)。多重表文件和倒排文件是兩種多關(guān)鍵字文件的組織方法。2/5/20232212.6.1多重表文件多重表文件（Multilistfile）的特點(diǎn)記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，建立主關(guān)鍵字的索引（稱為主索引）；對(duì)每個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。主索引為非稠密索引（一組記錄建立一個(gè)索引項(xiàng)），次索引為稠密索引（每個(gè)記錄建立一個(gè)索引項(xiàng)）。每個(gè)索引包括次關(guān)鍵字、頭指針和鏈表長(zhǎng)度。在多重表中插入一個(gè)新記錄是很容易的，只要修改指針，將記錄插在鏈表的頭指針之后。但是，要?jiǎng)h去一個(gè)記錄卻很繁瑣，需要在每個(gè)次關(guān)鍵字的鏈表中刪去該記錄。2/5/2023232/5/20232412.6.2倒排文件倒排文件（Invertedfile）和多重表文件的區(qū)別次關(guān)鍵字索引的結(jié)構(gòu)不同。倒排表倒排文件中的次關(guān)鍵字索引。在倒排表的索引項(xiàng)中沒有頭指針和鏈表長(zhǎng)度項(xiàng)，而直接用一項(xiàng)存放具有同一關(guān)鍵字的所有記錄的物理記錄號(hào)或主關(guān)鍵字。2/5/2023252/5/202326本章小結(jié)順序文件文件中記錄的物理順序和邏輯順序一致。對(duì)順序存儲(chǔ)器上的順序文件只能進(jìn)行順序存?。粚?duì)直接存儲(chǔ)器上的順序文件還可按記錄號(hào)或關(guān)鍵碼進(jìn)行隨機(jī)存??；如果是定長(zhǎng)記錄的順序有序文件，還可利用折半查找進(jìn)行快速存取。插入記錄可以插入在文件的末尾或先存入附加文件。刪除記錄僅在原地作標(biāo)志。更新記錄需對(duì)整個(gè)文件進(jìn)行復(fù)制。更多情況下對(duì)順序文件的操作是按批處理方式進(jìn)行的。2/5/202327索引文件對(duì)文件中的每個(gè)記錄都建立一個(gè)由記錄的關(guān)鍵碼和存儲(chǔ)地址構(gòu)成的索引項(xiàng)。所有記錄的索引項(xiàng)構(gòu)成一個(gè)按關(guān)鍵碼有序的索引表。索引表可以是順序結(jié)構(gòu)，也可以是查找樹結(jié)構(gòu)，對(duì)索引文件可以進(jìn)行直接存取或按關(guān)鍵碼存取。按關(guān)鍵碼存取時(shí)，首先在索引中進(jìn)行查找，然后按索引項(xiàng)中指示的存儲(chǔ)地址進(jìn)行存取。插入記錄時(shí)，記錄本身可插入在主文件的末尾，同時(shí)將相應(yīng)的索引項(xiàng)插入索引中恰當(dāng)位置。刪除記錄僅需刪除相應(yīng)的索引項(xiàng)。更新記錄時(shí)，可將更新后的記錄插入在主文件的末尾，同時(shí)修改相應(yīng)的索引項(xiàng)。2/5/202328索引順序文件記錄按關(guān)鍵碼有序，只需建立非稠密索引。VSAM文件是目前大型索引順序文件的一種標(biāo)準(zhǔn)組織方式，它由索引集、順序集和數(shù)據(jù)集三部分構(gòu)成，其中數(shù)據(jù)集為主文件，順序集和索引集分別為B+樹的葉子結(jié)點(diǎn)和非葉結(jié)點(diǎn)，構(gòu)成文件的索引。對(duì)VSAM文件可進(jìn)行按關(guān)鍵碼存取，也可以進(jìn)行順序存取，插入或刪除記錄時(shí)則必須保持控制區(qū)間內(nèi)的記錄按關(guān)鍵碼有序，需在控制區(qū)間內(nèi)進(jìn)行記錄的移動(dòng)。優(yōu)點(diǎn)：動(dòng)態(tài)地分配和釋放存儲(chǔ)空