數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)12

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

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