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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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