華科數(shù)據(jù)結(jié)構(gòu)課件

華中科技大學(xué)計算機學(xué)院(16)數(shù)據(jù)結(jié)構(gòu)第12章文件內(nèi)存不能永久性保存數(shù)據(jù)，以及容量有限，所以需要數(shù)據(jù)以文件形式存放到外部存儲器中。12.1文件的基本概念文件：由大量性質(zhì)相同的記錄組成的集合。記錄：文件中可存取的基本數(shù)據(jù)單位，它有若干個數(shù)據(jù)項組成。數(shù)據(jù)項：最基本的不可再分的數(shù)據(jù)單位。數(shù)據(jù)項的名稱稱為記錄的域。關(guān)鍵字：能夠區(qū)分文件中各記錄的域。

主關(guān)鍵字-----可以唯一地標識一個記錄的關(guān)鍵字；

次關(guān)鍵字-----不能唯一地標識一個記錄的關(guān)鍵字。文件分類：按記錄類型劃分：（1）流式文件：由一維的連續(xù)的字符（字節(jié)）序列組成，無結(jié)構(gòu)，無解釋。如C源程序。此時的記錄為單個字符（字節(jié)）。（2）記錄文件：記錄是由一個或多個數(shù)據(jù)項組成的集合。如.db.dbf文件。按記錄長度劃分：（1）定長記錄文件：文件中每個記錄含有的信息長度相同。（2）不定長記錄文件：文件有含有長度不等的記錄組成。記錄的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)：邏輯結(jié)構(gòu)：呈現(xiàn)在用戶和應(yīng)用程序員面前的數(shù)據(jù)組織形式，是用戶對數(shù)據(jù)的表示和存取方式。著眼于用戶使用方便。物理結(jié)構(gòu)：數(shù)據(jù)在物理存儲器上存儲的方式，是數(shù)據(jù)的物理表示和組織。應(yīng)考慮提高存儲空間的利用率和減少存取記錄的時間。物理記錄：是計算機用一條I/O命令進行讀寫的基本數(shù)據(jù)單位。對固定的設(shè)備和操作系統(tǒng)，它的大小基本上是固定不變的。邏輯記錄和物理記錄的三種關(guān)系：（1）一個物理記錄存放一個邏輯記錄；（2）一個物理記錄存放多個邏輯記錄；（3）多個物理記錄存放一個邏輯記錄；用戶讀寫記錄是對邏輯記錄，而操作系統(tǒng)對物理記錄。文件的操作：（1）檢索；（2）修改。文件的檢索一般有三種：（1）順序存?。簭漠?dāng)前位置開始，存取下一個邏輯記錄；（2）直接存?。捍嫒〉趇個邏輯記錄；以上兩種存取方式都是根據(jù)記錄的序號（即記錄存入文件時的序號）或記錄的相對位置進行存取。（3）按關(guān)鍵字存?。航o定一個值，查詢一個或一批關(guān)鍵字與給定值相關(guān)的記錄。對數(shù)據(jù)庫文件的查詢有四種：（a）簡單查詢：查詢關(guān)鍵字等于給定值的記錄；（b）區(qū)域查詢：查詢關(guān)鍵字屬于某個區(qū)域的記錄；（c）函數(shù)查詢：給定關(guān)鍵字的某個函數(shù)；例如查詢平均分以上的記錄。（d）布爾查詢：以上三種查詢用布爾運算組合起來的查詢。例如查詢總分600以上并且數(shù)學(xué)在100分以上，或總分在平均分以下并且外語在98分以上的所有記錄。文件的修改包括：(1)插入一個記錄；(2)刪除一個記錄；(3)更新一個記錄。文件的操作有兩種方式：（1）實時：應(yīng)答時間要求嚴格，要求在給定時間內(nèi)完成。（2）批量。文件組織的三種基本形式：（1）順序組織；（2）隨機組織；（3）鏈組織。12.2順序文件

順序文件（SequentialFile)是記錄按其在文件中的邏輯順序依次進入存儲介質(zhì)而建立的，即順序文件中物理記錄和邏輯記錄的順序是一致的。如果次序相繼的兩個物理記錄在存儲介質(zhì)上的存儲位置是相鄰的，則又成連續(xù)文件。如果兩個物理記錄之間的次序有指針鏈表示，則稱串聯(lián)文件。順序文件是根據(jù)記錄序號或記錄的相對位置來進行存取的文件組織方式，特點：（1）存取第i個記錄，必須搜索在它之前的i-1個記錄；（2）插入新的記錄只能在文件尾；（3）若要更新文件中的某個記錄，必須將整個文件復(fù)制。順序文件的優(yōu)點是連續(xù)存取速度快，在查找和修改都是成批處理的情況下，以順序文件為佳。順序文件的分類：（1）按關(guān)鍵字排列；（2）未按關(guān)鍵字排列，僅按先后次序。順序文件的操作：（1）順序存?。簭奈募牡?個記錄依次順序存取，存取效率很高。（2）隨機存取：對指定的記錄進行存取，但這種要求對順序文件來說，極不方便，存取效率很低。（3）按關(guān)鍵字存?。盒鑿奈募牡?個記錄開始查找，一般情況下，存取效率不高。12.3索引文件除文件自身（稱作數(shù)據(jù)區(qū)）之外，另建立一張指示邏輯記錄和物理記錄之間一一對應(yīng)關(guān)系的表：索引表。這類包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件稱為索引文件。索引表的每一項稱為索引項。不論主文件是否按關(guān)鍵字有序，索引表中的索引項總是按關(guān)鍵字順序排列。若數(shù)據(jù)區(qū)中的記錄也按關(guān)鍵字順序排列，則稱索引順序文件，反之，稱索引非順序文件。物理記錄號職工號姓名職務(wù)其它10129張三教授。10205李四講師。10302王紅助教。10438。。。10531。。。10643。。。10717。。。10850。。。10949。。。11047。。。11156。。。(a)文件數(shù)據(jù)區(qū)關(guān)鍵字物理記錄號0210305102171072910131105381044310647110491095010856111(b)索引表12.4索引順序文件索引順序文件是指記錄按關(guān)鍵字順序存放的索引文件。其存儲結(jié)構(gòu)分三個區(qū)：索引區(qū)、基本記錄區(qū)和溢出區(qū)?；居涗泤^(qū)是按記錄的關(guān)鍵字排序的。因此不必為每一個記錄保存一個索引項，而只要把記錄區(qū)分塊，通常是一個磁道作為一塊，每塊記錄設(shè)一個索引項。保存該塊的最大關(guān)鍵字值。溢出記錄區(qū)是為了解決插入問題而設(shè)置的，在這種文件中，由于記錄按關(guān)鍵字值順序存放，因此，如果新增記錄要插入到兩個原有記錄之間時，需要調(diào)整記錄區(qū)，如果當(dāng)前塊已滿，則最后一記錄被調(diào)整出當(dāng)前塊，放入溢出記錄區(qū)。溢出區(qū)采用鏈表結(jié)構(gòu)?；舅饕椧绯鏊饕楆P(guān)鍵字值指針關(guān)鍵字值指針基本數(shù)據(jù)區(qū)每一塊設(shè)一個索引項，登記該塊內(nèi)的最后一個記錄的關(guān)鍵字值和該塊記錄的首地址。溢出數(shù)據(jù)區(qū)的記錄用指針鏈接，從基本數(shù)據(jù)區(qū)同一塊中溢出的記錄形成一個鏈表，基本數(shù)據(jù)區(qū)有多少個塊，溢出區(qū)就可能有多少個鏈表。溢出區(qū)索引項登記該塊的第一個溢出記錄的關(guān)鍵字值（作為本塊的關(guān)鍵字值的上界）和該塊最近溢出的記錄在溢出區(qū)的地址?；舅饕椧绯鏊饕椈舅饕椧绯鏊饕?0T2，1/145T3，1/1記錄2記錄3記錄4記錄5記錄R50R60R70R80R90T2R100R130R135R140R145T3T4索引基本區(qū)溢出區(qū)索引順序文件存儲示意圖基本索引項溢出索引項基本索引項溢出索引項80T2，190T4，1145T3，1/1記錄2記錄3記錄4記錄5記錄R50R60R65R70R80T2R100R130R135R140R145T3R90/T4索引基本區(qū)溢出區(qū)插入R65后，基本數(shù)據(jù)區(qū)的R70到

R90后移，R90到溢出區(qū)基本索引項溢出索引項基本索引項溢出索引項80T2，190T4，1140T3，1145T4，21記錄2記錄3記錄4記錄5記錄R50R60R65R70R80T2R95R100R130R135R140T3R90/R145/T4索引基本區(qū)溢出區(qū)插入R95后，基本數(shù)據(jù)區(qū)的R100到

R145后移，R145到溢出區(qū)基本索引項溢出索引項基本索引項溢出索引項80T2，190T4，3140T3，1145T4，21記錄2記錄3記錄4記錄5記錄R50R60R65R70R80T2R95R100R130R135R140T3R90/R145/R83T4，1T4索引基本區(qū)溢出區(qū)插入R83時，因80<83<90,所以直接加入到溢出區(qū)12.5多關(guān)鍵字文件

多關(guān)鍵字文件的特點：對文件進行檢索操作時，不僅對主關(guān)鍵字進行簡單詢問，還經(jīng)常對次關(guān)鍵字進行其它類型的詢問檢索。如下頁表格中，學(xué)號為主關(guān)鍵字，專業(yè)、已修學(xué)分、選修課目等為次關(guān)鍵字。允許的查詢：

根據(jù)學(xué)號查詢某學(xué)生的信息；查詢已修學(xué)分400分以上的學(xué)生；查詢已修學(xué)分400分以上計算機專業(yè)的學(xué)生人數(shù)；其他查詢?yōu)榇耍瑢Χ嚓P(guān)鍵字文件，可建立一系列的次關(guān)鍵字索引。姓名學(xué)號專業(yè)已修學(xué)分選修課目王文1350軟件412丙丁馬小燕1351軟件398甲丙阮森1352計算機436乙丙丁蘇明明1353應(yīng)用402甲丙田水1354計算機384乙丁楊青1355應(yīng)用356甲薛平平1356軟件398甲乙崔子健1357軟件408甲丙王洪1358應(yīng)用370甲丁劉倩1359應(yīng)用364甲學(xué)生信息表12.5.1多重表文件

多重表文件的特點：記錄按主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件。并建立主關(guān)鍵字的索引（成為主索引），主索引為非稠密索引。如下頁圖所示為一個多重鏈表文件，記錄按學(xué)號鏈接，為查找方便，分成三個鏈表。對每一個次關(guān)鍵字建立一個稠密索引。相同次關(guān)鍵字的記錄形成一個鏈表。12.5.1多重表文件

多重表文件的特點：記錄按主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件。并建立主關(guān)鍵字的索引（成為主索引），主索引為非稠密索引。如下頁圖所示為一個多重鏈表文件，記錄按學(xué)號鏈接，為查找方便，分成三個鏈表。對每一個次關(guān)鍵字建立一個稠密索引。相同次關(guān)鍵字的記錄形成一個鏈表。記錄號姓名學(xué)號專業(yè)已修學(xué)分01王文135002軟件0241203丙02丁0302馬小燕135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^…應(yīng)用0640208甲06丙0805田水135406計算機^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^主關(guān)鍵字頭指針135301135705135909記錄號姓名學(xué)號專業(yè)已修學(xué)分01王文135002軟件0241203丙02丁0302馬小燕135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^…應(yīng)用0640208甲06丙0805田水135406計算機^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^次關(guān)鍵字頭指針長度軟件014計算機032應(yīng)用044記錄號姓名學(xué)號專業(yè)已修學(xué)分01王文135002軟件0241203丙02丁0302馬小燕135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^…應(yīng)用0640208甲06丙0805田水135406計算機^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^次關(guān)鍵字頭指針長度350～399066400～499044記錄號姓名學(xué)號專業(yè)已修學(xué)分01王文135002軟件0241203丙02丁0302馬小燕135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^…應(yīng)用0640208甲06丙0805田水135406計算機^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^次關(guān)鍵字頭指針長度甲027乙033丙015丁01412.5.2倒排表文件倒排文件和多重文件的區(qū)別在次關(guān)鍵字索引的結(jié)構(gòu)不同，通常，稱倒排文件中的次關(guān)鍵字索引為倒排表，具有相同次關(guān)鍵字的記錄之間不設(shè)指針相鏈。而在倒排表中該次關(guān)鍵字的一項中存放這些記錄的物理記錄號。記錄號姓名學(xué)號專業(yè)已修學(xué)分01王文135002軟件0241203丙02丁0302馬小燕135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^…應(yīng)用0640208甲06丙0805田水135406計算機^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09丙^09王洪135810應(yīng)用1037005甲10丁^10劉倩1359^應(yīng)用^36409甲^次關(guān)鍵字記錄物理地址軟件01，02，07，08計算機03，05應(yīng)用04，06，09，10記錄號姓名學(xué)號專業(yè)已修學(xué)分01王文135002軟件0241203丙02丁0302馬小燕135103軟件0739807甲04丙0303阮森135204計算機05436^乙05丙04丁0504蘇明明1353^…應(yīng)用0640208甲06丙0805田水135406計算機^38402乙07丁0906楊青135507應(yīng)用0935610甲0707薛平平135608軟件08398^甲08乙^08崔子健1357^軟件^40801甲09