山大《數(shù)據(jù)結(jié)構(gòu)》講義08文件

1、第八章 文件內(nèi)容概述在實際的應(yīng)用中，特別是涉及事務(wù)管理類型的問題，比如企業(yè)的管理信息系統(tǒng)、大型的信息檢索系統(tǒng)、數(shù)字圖書館等問題中將涉及大量數(shù)據(jù)，由于內(nèi)存不適合存儲這類數(shù)據(jù)量大且需長期保存的數(shù)據(jù)，因此這類數(shù)據(jù)需要存儲在外存儲器上。習(xí)慣上稱存儲在內(nèi)存中的數(shù)據(jù)集合為表，稱存儲在外存儲器（二級存儲器）中的數(shù)據(jù)集合為文件。本章討論文件的相關(guān)概念、表示方法及各種運算的實現(xiàn)方法。重點與難點重點為順序文件的操作和索引順序文件的結(jié)構(gòu)。難點是散列文件的設(shè)計模型桶散列。思考與習(xí)題1順序文件的優(yōu)缺點2直接文件的優(yōu)點3VSAM的總體結(jié)構(gòu)4假設(shè)在一個按桶散列的文件組織中，若有B個桶，現(xiàn)在要對文件進行重組成2B個桶，試用算

2、法描述這種重組。5倒排文件的結(jié)構(gòu)特點與優(yōu)點第一節(jié)文件概述本節(jié)主要介紹文件的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)以及文件操作。1、與文件有關(guān)的四個術(shù)語（域、紀錄、文件、數(shù)據(jù)庫）（1）域（Field）是數(shù)據(jù)的基本單位，又稱為字段或數(shù)據(jù)項。域通常用于描述數(shù)據(jù)對象的屬性，不可分割的域含有一個簡單的值，如姓名、日期等。域的特征可由長度和數(shù)據(jù)類型表示。域的長度可以是固定的，也可以是可變的。可變長度的域包含兩個或三個子域：要保存的實際值和域名，在某些情況下還需要域的長度。（2）記錄（Record）是一組相關(guān)域的集合，它可以看作是應(yīng)用程序的一個單元。例如，一個職員記錄可以包括姓名、社會保險號、工作類型、參加工作時間等。根據(jù)設(shè)計

3、的不同，記錄可以是固定長或可變長。如果記錄中某些域的長度是可變的，則該記錄就是可變長度的記錄。（3）文件（File）是由大量性質(zhì)相同的記錄組成的集合，它被應(yīng)用程序看作是一個實體。文件有一個惟一的名字，可以被創(chuàng)建或刪除。（4）數(shù)據(jù)庫（Database）是一組相關(guān)的數(shù)據(jù)，它的本質(zhì)特征是數(shù)據(jù)單元間存在明確的關(guān)系，并且設(shè)計成可供許多不同的應(yīng)用程序使用。數(shù)據(jù)庫自身是由一種或多種不同類型的文件組成。2、構(gòu)建文件物理結(jié)構(gòu)的方法文件的物理結(jié)構(gòu)和組織是指邏輯文件在物理存儲空間中存放方法和組織關(guān)系。有兩類方法可用來構(gòu)造文件的物理結(jié)構(gòu)。第一類稱為計算法，其實現(xiàn)原理是設(shè)計映射算法，例如線性計算法、雜湊法等，通過對記錄

4、關(guān)鍵字的計算轉(zhuǎn)換成對應(yīng)的物理塊地址，從而找到所需記錄。直接尋址文件、計算尋址文件，順序文件均屬此類。計算法的存取效率較高，又不必增加存儲空間存放附加控制信息，能把分布范圍較廣的關(guān)鍵字均勻地映射到一個存儲區(qū)域中。第二類稱為指針法，這類方法設(shè)置專門指針，指明相應(yīng)記錄的物理地址或表達各記錄之間的關(guān)聯(lián)。索引文件、索引順序文件、倒排文件等均屬此類。使用指針的優(yōu)點是可將文件信息的邏輯次序與在存儲介質(zhì)上的物理排列次序完全分開，便于隨機存取，便于更新，能加快存取速度。但使用指針要耗用較多存儲空間，大型文件的索引查找要耗費較多處理器時間，所以，究竟采用哪種文件存儲結(jié)構(gòu)，必須根據(jù)應(yīng)用目標、響應(yīng)時間和存儲空間等多種

5、因素進行權(quán)衡。3、文件的相關(guān)操作對文件的操作主要有記錄的檢索、插入、刪除、更新和文件排序。1記錄的檢索檢索文件的某條記錄或若干條記錄。記錄的檢索方式有三種：（1）檢索下一條記錄：檢索當(dāng)前記錄的下一條記錄。（2）檢索第i條記錄：按照所給文件記錄的邏輯順序號檢索記錄。（3）按關(guān)鍵字檢索：給定一個值，查詢一個或一批關(guān)鍵字與給定值相關(guān)的記錄。對于數(shù)據(jù)庫文件可以有如下四種查詢方式：（a）簡單檢索：查詢關(guān)鍵字等于給定值的記錄。例如檢索學(xué)號為200507001的學(xué)生記錄。（b）區(qū)域檢索：查詢關(guān)鍵字值在某個區(qū)域內(nèi)的記錄。例如檢索某個年級數(shù)據(jù)結(jié)構(gòu)考試成績在8090分的學(xué)生記錄。（c）函數(shù)檢索：給定關(guān)鍵字的某個函

6、數(shù)，檢索符合條件得記錄。例如查詢總分在全體學(xué)生的平均分以上的記錄。（d）布爾檢索：以上三種檢索式用布爾運算符組合起來的檢索。例如，查詢總分在600分以上且數(shù)學(xué)在100分以上，或者總分在平均分以下的外語在98分以上的全部記錄。2記錄的插入在文件的指定位置插入一個新記錄。文件位置的指定由記錄的檢索功能完成，記錄的插入實際是在記錄檢索功能的基礎(chǔ)上增加插入一條新記錄的功能。3記錄的刪除把指定位置上的記錄刪除。這通常有以下兩種情況：（1）刪除文件的第i條記錄。這實際是在記錄檢索功能的基礎(chǔ)上增加刪除一條記錄的功能。（2）刪除文件中符合給定條件的記錄。這實際上是在按關(guān)鍵字檢索功能的基礎(chǔ)上增加刪除對應(yīng)記錄的功

7、能。4記錄的更新修改指定位置上的記錄。通常有如下兩種情況：（1）更新文件中第i條記錄的某些數(shù)據(jù)項值。即在檢索第i個記錄功能的基礎(chǔ)上增加更新該記錄的某些數(shù)據(jù)項的功能。（2）更新文件中符合給定條件的記錄的某些數(shù)據(jù)項。這實際上是在按關(guān)鍵字檢索功能的基礎(chǔ)上增加更新對應(yīng)記錄某些數(shù)據(jù)項的功能。5文件排序根據(jù)給定的關(guān)鍵字，對文件中的記錄按關(guān)鍵字值升序或降序重新進行組織。第二節(jié)順序文件順序文件是在批處理文件、系統(tǒng)文件中用得最多的文件組織方式。本節(jié)介紹順序文件的特點和操作。1、順序文件的優(yōu)缺點順序文件是根據(jù)記錄的序號或記錄的相對位置來進行存取的文件組織方式。其特點是：（1）若存取文件中第i個記錄，必須先搜索在它

8、之前的i-1個記錄。（2）插入新的記錄時只能追加在文件的末尾。（3）若要更新文件中的某個記錄，則必須將整個文件進行復(fù)制。順序文件的基本優(yōu)點是：順序存取記錄時速度較快。所以，批處理文件、系統(tǒng)文件用得最多。采用磁帶存放順序文件時，總可以保持快速存取的優(yōu)點。若以磁盤作存儲介質(zhì)時，順序文件的記錄也按物理鄰接次序排列，因而順序的磁盤文件能像磁帶文件一樣進行嚴格的順序處理。然而，由于多程序訪問，在同一時間另外的用戶作業(yè)可能驅(qū)動磁頭移向其它文件，因而可能要花費較多的處理器時間降低了這一優(yōu)越性。順序文件的主要缺點是：建立文件前需要能預(yù)先確定文件長度，以便分配存儲空間；修改、插入和增生文件記錄有困難；對直接存儲

9、器作連續(xù)分配，會造成少量空閑塊的浪費。2、分塊插值查找的算法假設(shè)文件由記錄R1，R2，Rn組成，并已知記錄按關(guān)鍵字升序排列：K1K2KN，h、l分別表示當(dāng)前查找范圍的上界和下界?，F(xiàn)在我們要查找關(guān)鍵字值為K的記錄。我們回顧一下折半查找的具體做法，首先選取查找范圍內(nèi)的中間點i=，然后將Ki與K進行比較。插值法查找并不是選取查找范圍的中間點作為比較點，而是按關(guān)鍵字的比例選取l和h之間的某一點ii=這表示i的選取與查找范圍的下界關(guān)鍵字、上界關(guān)鍵字和要查找的關(guān)鍵字有關(guān)。然后將Ki與K比較，若K=Ki，則Ri就是要找的記錄；若KKi，則下一步查找范圍的上界為i-1，下界為l；若KKi，則下一步查找范圍的上

10、界為h，下界為i+1。由于文件記錄存放在外存的物理塊上，因此文件的查找采用分塊插值查找，此時，h、l、i表示物理塊號。假設(shè)整個文件的最小關(guān)鍵字為K0，最大關(guān)鍵字為Km，要查找的關(guān)鍵字為K，整個文件分為N個物理塊，并設(shè)：low:查找范圍內(nèi)的最小物理塊號；high:查找范圍內(nèi)的最大物理塊號；Li：第i個物理塊內(nèi)的記錄的最小關(guān)鍵字；Hi：第i個物理塊內(nèi)的記錄的最大關(guān)鍵字分塊插值查找的算法描述如下：（1）初始化low=1；high=N。（2）反復(fù)執(zhí)行下面操作，直到highlow成立(b)讀取第i個物理塊，獲得Li和Hi(c)分下面三種情況執(zhí)行l(wèi)LiKHi時，查找成功，第i個物理塊即為所求;lKHi時，

11、執(zhí)行l(wèi)ow=i+1;lKLi時，執(zhí)行high=i-1;(3)查找失敗，算法結(jié)束。按塊插值查找是一種比較高速的查找方法。第三節(jié)直接文件(散列文件)在直接存取存儲設(shè)備上，記錄的關(guān)鍵字與其地址之間可以通過某種方式建立對應(yīng)關(guān)系，利用這種關(guān)系實現(xiàn)存取的文件叫直接文件（散列文件）。本節(jié)介紹典型的直接文件的設(shè)計模型桶（Bucket）散列法。1、桶散列方法的基本思想桶散列方法的基本思想是把文件的記錄通過散列函數(shù)H分別存儲在許多存儲桶中，每個存儲桶包含一個或多個物理塊，一個存儲桶中的物理塊用指針連接形成鏈表，每個物理塊存放若干記錄。散列函數(shù)H把關(guān)鍵字key值轉(zhuǎn)換成存儲桶號，即H(key)表示具有關(guān)鍵字key的記

12、錄所在的存儲桶號。如果一個桶溢出，即它容納不下所有屬于它的記錄，那么可以給該存儲桶增加一個溢出塊鏈表以存放更多的記錄。2、桶散列結(jié)構(gòu)上是操作（查找、插入、刪除）的實現(xiàn)思想【例8-1】圖8-2表示一個具有B個桶的散列文件。為了使圖例易于處理，假設(shè)每個物理塊只存放一個邏輯記錄，且B=4，即散列函數(shù)的返回值介于03之間。假設(shè)記錄的關(guān)鍵字為字母af，并且假定h(d)=0，h(c)=h(e)=1，h(b)=2，h(f)=h(a)=3。因此，這六個記錄的分布如圖8-2所示。在散列文件上可以進行查找、插入、刪除、修改等操作，下面討論這些操作的主要思路。1.查找假設(shè)要查找一個關(guān)鍵字值等于一個給定值key的記錄

13、。我們首先計算H（key），得到存儲桶號i，然后查看存儲桶目錄表以找到第i號存儲桶的第一個物理塊地址，把該物理塊調(diào)入內(nèi)存，然后順序搜索其中的每一個記錄，檢查有無關(guān)鍵字值等于key的記錄，若找到就結(jié)束查找，否則根據(jù)該物理塊上的鏈表指針找出下一個物理塊并調(diào)入內(nèi)存，以同樣方式查找。以此類推直到找到關(guān)鍵字值等于key的記錄或斷定不存在關(guān)鍵字值等于key的記錄（即桶中所有物理塊全部查找完畢）為止。2插入插入前先根據(jù)上述查找過程查找桶號為H（key）的存儲桶中是否存在關(guān)鍵字值等于key的記錄。如果存在，則表示出錯，因為插入一個與文件中已有記錄具有相同關(guān)鍵字值的記錄是沒有意義的。若不存在相應(yīng)的記錄，則將該記

14、錄存放到該存儲桶的空閑物理塊中。如果存儲桶中所有的物理塊都沒有空間，我們就增加一個新的溢出塊到該存儲桶的鏈表上，并將新記錄存入其中。3刪除首先根據(jù)查找過程在桶號為H（key）的存儲桶中尋找是否存在關(guān)鍵字值等于key的記錄，若不存在，則表示出錯。若找到，則將該記錄的刪除標志置為1，表示該記錄已被刪除。如果我們可以將記錄在物理塊中移動，那么刪除記錄后，我們可選擇合并同一鏈表上的物理塊，但合并一條鏈上的物理塊隨時都要冒風(fēng)險，因為當(dāng)我們往一個存儲桶里交替地插入或刪除記錄時，可能每一步都會導(dǎo)致物理塊的創(chuàng)建或刪除。4修改假定我們要修改關(guān)鍵字值為key的記錄的一個或多個域，若需要修改的域中涉及到關(guān)鍵字，則這

15、樣的修改相當(dāng)于刪除加插入。因為散列文件中，關(guān)鍵字值的變化可能改變記錄的存儲位置，修改后的記錄可能與原記錄位于不同的存儲桶中，因而需要先刪除原記錄，再插入新修改的記錄。如果修改的域沒有涉及到關(guān)鍵字，則首先查找到這個記錄，找到后調(diào)入內(nèi)存進行修改，修改后再寫回存儲桶（外存）中，若找不到，則出錯。3、可擴展散列文件的組織方式可擴展散列文件的組織方式是：散列函數(shù)H把關(guān)鍵字key轉(zhuǎn)換成一個定長的二進制位串k（偽關(guān)鍵字）,取k前i位二進制數(shù)（設(shè)為k）作為存儲桶目錄表中的目錄項號，即表示目錄表中第k個目錄項，目錄項中的指針指向的物理塊就是具有關(guān)鍵字key的記錄所在的物理塊；存儲桶目錄項的個數(shù)為2i。所選擇散列

16、函數(shù)盡可能具有如下性質(zhì)：它所產(chǎn)生的偽關(guān)鍵字中約有一半是第一個二進制位為0，約1/4是前兩位為01，約1/8是前三位為010，等等，即盡可能使所產(chǎn)生的偽關(guān)鍵字分布均勻。圖8-3是使用兩位散列函數(shù)值的散列文件。在圖中，每個物理塊存放兩個邏輯記錄，每個物理塊上的“小凸塊”中的數(shù)字表明由散列函數(shù)得到的二進制位串中有多少位用于確定記錄在該物理塊中的成員資格?？蓴U展散列文件上插入操作開始時類似于靜態(tài)散列文件,即先進行查找操作。為了插入關(guān)鍵字為K的記錄，我們計算出H（K），取出這一二進制位串的前i位（設(shè)為k），并找到序號為k的存儲桶目錄項。根據(jù)此目錄項的指針找到物理塊B。如果該物理塊中有空閑空間，我們就把新

17、記錄存入，插入操作完成。如果B中沒有空閑空間，那么根據(jù)數(shù)字i的不同有兩種可能：1）如果ji（j的值可在每個物理塊的“小凸塊”中找到），那么不必對存儲桶目錄表做任何變化。按下面規(guī)則操作：（a）將物理塊B分裂成兩個存儲塊。（b）根據(jù)記錄關(guān)鍵字的散列值的第j+1位，將B中的記錄分配到這兩個存儲塊中，該位為0的記錄繼續(xù)保留在B中，而該位為1的記錄放入到新塊中。（c）把j+1存儲到兩個存儲塊的“小凸塊”中，以標明用于確定成員資格的二進制位數(shù)。（d）調(diào)整存儲桶目錄項中指針，使原來指向塊B的指針項指向塊B或新塊，這由記錄關(guān)鍵字的散列值的第j+1位決定。注意，分裂B可能解決不了問題，因為有可能塊B中所有記錄將

18、分配到由B分裂成的兩個存儲塊的其中一塊中。如果這樣，我們需要對仍太滿的塊用下一個更大的j值重復(fù)上述操作。2）如果j=i，那么我們必須先將i加1，使存儲桶目錄項個數(shù)增加一倍，即2i+1。在新存儲桶目錄表中，序號為k0和k1（分別用0和1擴展k）的項都指向原k目錄項指向的物理塊。也就是說，這兩個新目錄項共享同一個物理塊，而物理塊本身沒有變化。4、在可擴展散列文件上實現(xiàn)插入操作的方法【例8-2】在圖8-3所示的可擴展散列文件中，首先插入關(guān)鍵字值為0000、0111的記錄，然后再插入關(guān)鍵字值為1000的記錄。當(dāng)插入關(guān)鍵字為0000、0111的記錄時，由于這兩個記錄都屬于第一個物理塊，于是該存儲塊溢出。

19、因為該存儲塊只用一位（即j=1）來確定成員資格，而i=2，所以我們不必調(diào)整存儲桶目錄表，只需分裂該存儲塊，讓0000和0001留在該存儲塊，而將0111存放到新塊中，存儲桶01目錄項指向該新塊。插入后結(jié)果見圖8-4（a）。插入關(guān)鍵字值為1000的記錄，目錄項10所指向的存儲塊溢出。由于它已經(jīng)使用兩位數(shù)來確定其成員資格，這時需要再次分裂存儲桶目錄表，并將i設(shè)為3。第四節(jié)索引文件索引結(jié)構(gòu)是實現(xiàn)非連續(xù)存儲的另一種方法，適用于數(shù)據(jù)記錄保存在隨機存取存儲設(shè)備上的文件。本節(jié)主要介紹索引文件的結(jié)構(gòu)組成。1、索引文件的結(jié)構(gòu)索引結(jié)構(gòu)是鏈式結(jié)構(gòu)的一種擴展，除了具備鏈式結(jié)構(gòu)的優(yōu)點外，還克服了它只能作順序存取的缺點，

20、具有直接讀寫任意一個記錄的能力，便于文件記錄的插入、刪除、修改。在索引文件上插入一個記錄時，將記錄置于數(shù)據(jù)區(qū)的末尾，同時在索引表中插入相應(yīng)的索引項即可；刪除一個記錄時，僅刪除該記錄在索引表中的索引項即可；更新記錄時，應(yīng)將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時修改索引表中相應(yīng)的索引項。索引文件的缺點是：增加了索引表的空間開銷和查找時間，索引表的信息量甚至可能遠遠超過文件記錄本身的信息量。2、稀疏索引和稠密索引索引文件中的索引項可以分為兩類：一類稱稠密索引，即對每個數(shù)據(jù)記錄，在索引表里都有一個索引項，因而索引本身很大，但可以不要求數(shù)據(jù)記錄排序，通過對索引的依次查找就可確定記錄的位置或記錄是否存在；另一種

21、稱稀疏索引，它對每一組數(shù)據(jù)記錄有一索引項，因而索引表本身較小，但數(shù)據(jù)記錄必須按某種次序排列。注意，雖然稀疏索引本身較小，但是，在查找時又要花出一定代價。因為找到索引之后，只判定了記錄所在的組，而該記錄是否存在？是組內(nèi)哪一個記錄？還要進一步查找。第五節(jié)索引順序文件索引順序文件是順序文件的擴展，其中各記錄本身在介質(zhì)上也是順序排列的，它包含了直接處理和修改記錄的能力。根據(jù)在系統(tǒng)運行時索引結(jié)構(gòu)是否變化，又分為靜態(tài)索引結(jié)構(gòu)和動態(tài)索引結(jié)構(gòu)，這正是本節(jié)所要介紹的內(nèi)容。1、ISAM多級索引結(jié)構(gòu)ISAM采用多級索引：主索引、柱面索引、磁道索引。文件的記錄在同一盤組上存放時，應(yīng)先集中放在一個柱面上，然后再順序存放

22、在相鄰的柱面上，對同一柱面，則應(yīng)按盤面的次序順序存放。例如圖8-6為存放在一個磁盤組上的ISAM文件，每個柱面建立一個磁道索引。每個磁道索引項由兩部分組成：基本索引項和溢出索引項，如圖8-7所示，每一部分都包括關(guān)鍵字和指針兩項，前者表示該磁道中最末一個記錄的關(guān)鍵字（在此為最大關(guān)鍵字），后者指示該磁道中第一個記錄的位置。柱面索引的每一個索引項也由關(guān)鍵字和指針兩部分組成，前者表示該柱面中最末一個記錄的關(guān)鍵字（最大關(guān)鍵字），后者指示該柱面上的磁道索引位置。柱面索引存放在某個柱面上，若柱面索引較大，占多個磁道時，則可建立柱面索引的索引主索引。2、VSAM的總體結(jié)構(gòu)虛擬存儲方法VSAM（VirtualS

23、equentialAccessMethod）是B+樹應(yīng)用的一個典型例子，是一種索引順序文件的組織方式。這種存取方法利用了操作系統(tǒng)中的虛擬存儲器的功能，給用戶提供方便。這種存取方法與存儲設(shè)備無關(guān)，與柱面、磁道等物理存儲單位沒有必然聯(lián)系，因為對用戶而言，文件只有控制域和控制區(qū)間等邏輯存儲單位。VSAM的總體結(jié)構(gòu)如圖8-9所示。它由三部分組成：索引集、順序集和數(shù)據(jù)集。文件的記錄均存放在數(shù)據(jù)集中，順序集也是文件索引的一部分，順序集和索引集一起形成一棵B+樹結(jié)構(gòu)的文件索引?？梢岳盟饕龑SAM進行隨機存取，利用順序集對文件進行順序存取。3、在VSAM上插入與刪除操作的實現(xiàn)方法在VSAM文件插入記錄時，首先調(diào)用B+樹的查找算法，確定該記錄應(yīng)插入的順序集結(jié)點，進而確定該記錄應(yīng)插入的控制區(qū)間及相應(yīng)位置。如果該控制區(qū)間中自由空間足以容納該記錄，則將要插入位置右面的記錄右移騰出空間插入該記錄，并在相應(yīng)位置建立控制信息。例如，在圖8-12的VSAM文件中插入ARS、BIT，結(jié)果如圖8-13（a）所示。如果自由空間不夠，則檢查該控制區(qū)間所在的控制域中是否還有空閑的控制區(qū)間，若有，則將