數(shù)據(jù)結(jié)構(gòu)導(dǎo)論“文件”

1、第第7 7章章 文文 件件以上各章的討論都是針對存放在內(nèi)存中的以上各章的討論都是針對存放在內(nèi)存中的數(shù)據(jù)的。但是，如果數(shù)據(jù)的數(shù)據(jù)的。但是，如果數(shù)據(jù)的“規(guī)模規(guī)?！昂艽蠛艽螅ò臄?shù)據(jù)元素很多）、或者需要長期保（包含的數(shù)據(jù)元素很多）、或者需要長期保存，則必須存放在外部儲(chǔ)器中。通常將存放存，則必須存放在外部儲(chǔ)器中。通常將存放在外存中的數(shù)據(jù)稱為文件。由于外存設(shè)備與在外存中的數(shù)據(jù)稱為文件。由于外存設(shè)備與內(nèi)存儲(chǔ)器的物理特性不同，前面介紹的各種內(nèi)存儲(chǔ)器的物理特性不同，前面介紹的各種數(shù)據(jù)組織方法和操作方法不能簡單地照搬過數(shù)據(jù)組織方法和操作方法不能簡單地照搬過來，需要根據(jù)文件的特點(diǎn)專門加以考慮。來，需要根據(jù)文件的

2、特點(diǎn)專門加以考慮。文件是由特性相同的記錄所構(gòu)成的文件是由特性相同的記錄所構(gòu)成的集合集合，其，其中每個(gè)記錄由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，這就是文件中每個(gè)記錄由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成，這就是文件的的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)。記錄是文件的基本存取單位。記錄是文件的基本存取單位。 7.1 基本概念基本概念7.1.1 文件結(jié)構(gòu)文件結(jié)構(gòu) 職工號(hào)職工號(hào)姓名姓名性別性別年齡年齡住址住址00010001王王 平平男男3030長江路長江路4141號(hào)號(hào)00020002李李 明明男男2525紅星路紅星路100100號(hào)號(hào)00050005張張 紅紅女女2727中山路中山路1818號(hào)號(hào)00060006胡衛(wèi)東胡衛(wèi)東男男2424壽春路壽春路4040號(hào)

3、號(hào)圖圖7-1 文件示例文件示例文件由若干條記錄組成。單位有多少人，文件就文件由若干條記錄組成。單位有多少人，文件就有多少條記錄。每個(gè)職工的信息集中在一條記錄中。有多少條記錄。每個(gè)職工的信息集中在一條記錄中。職工號(hào)為主關(guān)鍵字，姓名等項(xiàng)為次關(guān)鍵字。職工號(hào)為主關(guān)鍵字，姓名等項(xiàng)為次關(guān)鍵字。從用戶的觀點(diǎn)看，記錄應(yīng)是存取操作從用戶的觀點(diǎn)看，記錄應(yīng)是存取操作的基本單位。但從外存儲(chǔ)設(shè)備的觀點(diǎn)看，的基本單位。但從外存儲(chǔ)設(shè)備的觀點(diǎn)看，應(yīng)按其他標(biāo)準(zhǔn)確定基本存取單位。為了應(yīng)按其他標(biāo)準(zhǔn)確定基本存取單位。為了區(qū)分這兩種標(biāo)準(zhǔn)。通常將區(qū)分這兩種標(biāo)準(zhǔn)。通常將按用戶觀點(diǎn)的按用戶觀點(diǎn)的基本存取單（即記錄）稱為邏輯記錄，基本存取單（

4、即記錄）稱為邏輯記錄，將按外存設(shè)備觀點(diǎn)的基本存取單位稱為將按外存設(shè)備觀點(diǎn)的基本存取單位稱為物理記錄物理記錄。文件的基本運(yùn)算有兩種：檢索和修改。文件的基本運(yùn)算有兩種：檢索和修改。其中文件的其中文件的檢索檢索又有三種方式：又有三種方式：（）順序存?。阂来未嫒∫粋€(gè)邏輯記錄。（）順序存?。阂来未嫒∫粋€(gè)邏輯記錄。（）直接存?。捍嫒〉冢ǎ┲苯哟嫒。捍嫒〉趇個(gè)邏輯記錄。個(gè)邏輯記錄。（）按關(guān)鍵字存取：存取鍵值等于給定（）按關(guān)鍵字存?。捍嫒℃I值等于給定值的記錄。值的記錄。 文件的文件的修改修改包括插入一個(gè)記錄、刪除一個(gè)包括插入一個(gè)記錄、刪除一個(gè)記錄和更新一個(gè)記錄三種運(yùn)算。記錄和更新一個(gè)記錄三種運(yùn)算。下面分別舉例

5、說明這三種運(yùn)算（略）。下面分別舉例說明這三種運(yùn)算（略）。文件在存儲(chǔ)介質(zhì)（如磁盤和磁帶）上的實(shí)際文件在存儲(chǔ)介質(zhì)（如磁盤和磁帶）上的實(shí)際組織方式稱為文件的組織方式稱為文件的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)或或物理結(jié)構(gòu)物理結(jié)構(gòu)，常，常見的有四種：順序組織、索引組織、散列組織、見的有四種：順序組織、索引組織、散列組織、和鏈組織。為了討論文件的組織方式，先簡單和鏈組織。為了討論文件的組織方式，先簡單介紹磁帶存儲(chǔ)器和磁盤存儲(chǔ)器的有關(guān)知識(shí)。介紹磁帶存儲(chǔ)器和磁盤存儲(chǔ)器的有關(guān)知識(shí)。 磁帶存儲(chǔ)器把信息存儲(chǔ)在磁帶上，磁帶機(jī)可磁帶存儲(chǔ)器把信息存儲(chǔ)在磁帶上，磁帶機(jī)可以控制磁帶前進(jìn)，后退，磁帶機(jī)上讀寫磁頭可以控制磁帶前進(jìn)，后退，磁帶機(jī)上

6、讀寫磁頭可以讀寫磁帶上的信息。磁帶的運(yùn)行情況類似以以讀寫磁帶上的信息。磁帶的運(yùn)行情況類似以錄音機(jī)上錄音帶的運(yùn)行。錄音機(jī)上錄音帶的運(yùn)行。 7.1.2 外存儲(chǔ)器件簡介外存儲(chǔ)器件簡介 磁盤存儲(chǔ)器是目前使用得最廣泛的外存設(shè)磁盤存儲(chǔ)器是目前使用得最廣泛的外存設(shè)備。微機(jī)上使用上的磁盤分為兩種：硬盤和備。微機(jī)上使用上的磁盤分為兩種：硬盤和軟盤。磁盤有點(diǎn)像唱片，但是磁盤的磁道不軟盤。磁盤有點(diǎn)像唱片，但是磁盤的磁道不是螺旋線，而是同心圓。若干個(gè)盤片可以通是螺旋線，而是同心圓。若干個(gè)盤片可以通過一個(gè)主軸串在一起，構(gòu)成一個(gè)盤組。各個(gè)過一個(gè)主軸串在一起，構(gòu)成一個(gè)盤組。各個(gè)盤面半徑相同的磁盤在一起稱作一個(gè)柱面。盤面半徑

7、相同的磁盤在一起稱作一個(gè)柱面。盤組有多少個(gè)盤面，則說每個(gè)柱面有多少個(gè)盤組有多少個(gè)盤面，則說每個(gè)柱面有多少個(gè)磁道。一個(gè)磁道可分為若干段，每段是一個(gè)磁道。一個(gè)磁道可分為若干段，每段是一個(gè)物理記錄。一個(gè)盤組上從大到小的存儲(chǔ)單位物理記錄。一個(gè)盤組上從大到小的存儲(chǔ)單位為：柱面、磁道、物理記錄。為：柱面、磁道、物理記錄。 主機(jī)對外存儲(chǔ)器的數(shù)據(jù)不能直接地進(jìn)行存取。主機(jī)對外存儲(chǔ)器的數(shù)據(jù)不能直接地進(jìn)行存取。要讀外存上的數(shù)據(jù)，首先要通道把數(shù)據(jù)讀到內(nèi)要讀外存上的數(shù)據(jù)，首先要通道把數(shù)據(jù)讀到內(nèi)存緩沖區(qū)，然后從外存區(qū)讀取數(shù)據(jù)。寫數(shù)據(jù)時(shí)，存緩沖區(qū)，然后從外存區(qū)讀取數(shù)據(jù)。寫數(shù)據(jù)時(shí)，將數(shù)據(jù)送到緩沖區(qū)，再通過通道將緩沖區(qū)內(nèi)容將數(shù)

8、據(jù)送到緩沖區(qū)，再通過通道將緩沖區(qū)內(nèi)容寫到外存儲(chǔ)器。一次從內(nèi)存讀數(shù)據(jù)或往外存寫寫到外存儲(chǔ)器。一次從內(nèi)存讀數(shù)據(jù)或往外存寫數(shù)據(jù)的過程稱作一次訪外。一次訪外可傳送若數(shù)據(jù)的過程稱作一次訪外。一次訪外可傳送若干個(gè)字節(jié)，訪外時(shí)間包括定位和傳送時(shí)間。節(jié)干個(gè)字節(jié)，訪外時(shí)間包括定位和傳送時(shí)間。節(jié)省存取時(shí)間的一個(gè)有效辦法是，使每次訪外，省存取時(shí)間的一個(gè)有效辦法是，使每次訪外，在內(nèi)存和外內(nèi)之間傳送一批較大的數(shù)據(jù)，從而在內(nèi)存和外內(nèi)之間傳送一批較大的數(shù)據(jù)，從而減少訪外次數(shù)。減少訪外次數(shù)。分頁塊的存儲(chǔ)方法是一種有利于減少訪問外分頁塊的存儲(chǔ)方法是一種有利于減少訪問外存次數(shù)又便于管理方法，一個(gè)塊頁是磁帶或磁存次數(shù)又便于管理方法

9、，一個(gè)塊頁是磁帶或磁盤上的一個(gè)物理記錄，它包括多個(gè)邏輯記錄，盤上的一個(gè)物理記錄，它包括多個(gè)邏輯記錄，內(nèi)存中設(shè)置的緩沖區(qū)應(yīng)該和頁塊的大小相等。內(nèi)存中設(shè)置的緩沖區(qū)應(yīng)該和頁塊的大小相等。每次訪外，是把一個(gè)頁塊讀入一個(gè)緩沖區(qū)或者每次訪外，是把一個(gè)頁塊讀入一個(gè)緩沖區(qū)或者把一個(gè)緩沖區(qū)寫到一個(gè)頁塊。把一個(gè)緩沖區(qū)寫到一個(gè)頁塊。 若一次訪外所傳送的頁塊上有多少在近期進(jìn)若一次訪外所傳送的頁塊上有多少在近期進(jìn)行處理的邏輯記錄，則分頁塊的存儲(chǔ)方式可以行處理的邏輯記錄，則分頁塊的存儲(chǔ)方式可以使訪問次數(shù)大大減少。使訪問次數(shù)大大減少。我們可以用訪外次數(shù)作為衡量檢索效率的一個(gè)重要我們可以用訪外次數(shù)作為衡量檢索效率的一個(gè)重要參

10、數(shù)。檢索一次，訪外次數(shù)越少，效率越高，相反，參數(shù)。檢索一次，訪外次數(shù)越少，效率越高，相反，則效率就越低。另一個(gè)衡量檢索效率的參數(shù)是磁頭定則效率就越低。另一個(gè)衡量檢索效率的參數(shù)是磁頭定位，檢索某一記錄，磁頭定位時(shí)間越少，效率越高，位，檢索某一記錄，磁頭定位時(shí)間越少，效率越高，否則，效率就越低。否則，效率就越低。 文件在外存儲(chǔ)器上組織結(jié)構(gòu)主要有三種：文件在外存儲(chǔ)器上組織結(jié)構(gòu)主要有三種：順序文件、順序文件、散列文件、索引文件散列文件、索引文件。這三種組織方式分別適于不同。這三種組織方式分別適于不同的外存儲(chǔ)器，它們的檢索效率是不同的，下面分別討的外存儲(chǔ)器，它們的檢索效率是不同的，下面分別討論這幾種文件

11、在外存儲(chǔ)上是如何組織的，有關(guān)的運(yùn)算論這幾種文件在外存儲(chǔ)上是如何組織的，有關(guān)的運(yùn)算是如何實(shí)現(xiàn)的。是如何實(shí)現(xiàn)的。7.2 順序文件順序文件 順序文件是文件的一種常見組織形式，在順順序文件是文件的一種常見組織形式，在順序文件中，所有邏輯記錄在存儲(chǔ)介質(zhì)中的實(shí)際序文件中，所有邏輯記錄在存儲(chǔ)介質(zhì)中的實(shí)際順序與它們進(jìn)入存儲(chǔ)器的順序一致。順序與它們進(jìn)入存儲(chǔ)器的順序一致。順序文件適宜于順序存取和成批處理，順序順序文件適宜于順序存取和成批處理，順序文件特別適用于磁帶存儲(chǔ)器，也適用于磁盤存文件特別適用于磁帶存儲(chǔ)器，也適用于磁盤存儲(chǔ)器。儲(chǔ)器。 順序文件的檢索操作方法如下：順序文件的檢索操作方法如下： () 順序文件的順

12、序存?。簭奈募牡谝粋€(gè)記錄順序文件的順序存取：從文件的第一個(gè)記錄開始一個(gè)一個(gè)依次讀入各個(gè)記錄進(jìn)行處理和使用。開始一個(gè)一個(gè)依次讀入各個(gè)記錄進(jìn)行處理和使用。順序文件對這種存取方法效率很高，因?yàn)槭∪ズ芏囗樞蛭募@種存取方法效率很高，因?yàn)槭∪ズ芏啻蓬^定位時(shí)間。磁頭定位時(shí)間。 () 順序文件的隨機(jī)存取：對順序文件的這種檢順序文件的隨機(jī)存?。簩樞蛭募倪@種檢索方式，由于沒有建立邏輯記錄和物理記錄之間的索方式，由于沒有建立邏輯記錄和物理記錄之間的直接對應(yīng)關(guān)系每次檢索都要從文件的第一記錄開始直接對應(yīng)關(guān)系每次檢索都要從文件的第一記錄開始找到所要處理的記錄。這樣要花費(fèi)許多定位時(shí)間，找到所要處理的記錄。這樣要花

13、費(fèi)許多定位時(shí)間，因此順序文件的隨機(jī)存取效率很低。因此順序文件的隨機(jī)存取效率很低。 () 順序文件按關(guān)鍵字存?。喉樞蛭募校樞蛭募搓P(guān)鍵字存?。喉樞蛭募校檎乙粋€(gè)指定鍵值記錄的最簡單辦法是從文查找一個(gè)指定鍵值記錄的最簡單辦法是從文件頭到文件尾掃描每個(gè)記錄。若找則停止，件頭到文件尾掃描每個(gè)記錄。若找則停止，否則繼續(xù)查找，直到文件尾，這點(diǎn)同線性表否則繼續(xù)查找，直到文件尾，這點(diǎn)同線性表的順序查找類似。若檢索各記錄的概率相同，的順序查找類似。若檢索各記錄的概率相同，則一次檢索平均要掃描文件的一半記錄。設(shè)則一次檢索平均要掃描文件的一半記錄。設(shè)文件占有的頁塊數(shù)為，則平均訪外次數(shù)為文件占有的頁塊數(shù)為，則平

14、均訪外次數(shù)為，速度很慢。，速度很慢。7.3 索引文件索引文件 索引文件由索引表和主文件兩部分構(gòu)成。索索引文件由索引表和主文件兩部分構(gòu)成。索引表是一張指示邏輯記錄和物理記錄之間對應(yīng)引表是一張指示邏輯記錄和物理記錄之間對應(yīng)關(guān)糸的表。索引表中的每項(xiàng)稱作索引項(xiàng)。索引關(guān)糸的表。索引表中的每項(xiàng)稱作索引項(xiàng)。索引項(xiàng)是按鍵（或邏輯記錄號(hào)）順序排列。若文件項(xiàng)是按鍵（或邏輯記錄號(hào)）順序排列。若文件本身也是按關(guān)鍵字順序排列，則稱為索引順序本身也是按關(guān)鍵字順序排列，則稱為索引順序文件；否則，稱為索引非順序文件。文件；否則，稱為索引非順序文件。索引文件的檢索方式為直接存取或按關(guān)鍵索引文件的檢索方式為直接存取或按關(guān)鍵字存取

15、。整個(gè)過程分兩部分進(jìn)行，首先查找字存取。整個(gè)過程分兩部分進(jìn)行，首先查找索引表，若該記錄在表上存在，則根據(jù)索引索引表，若該記錄在表上存在，則根據(jù)索引項(xiàng)指示的物理位置到外上讀??；否則該記錄項(xiàng)指示的物理位置到外上讀??；否則該記錄不在外存上。通常索引表可預(yù)訂先讀到內(nèi)存不在外存上。通常索引表可預(yù)訂先讀到內(nèi)存中，查找索引表在內(nèi)存中進(jìn)行，因此檢索索中，查找索引表在內(nèi)存中進(jìn)行，因此檢索索引文件只進(jìn)行兩次訪問，一次讀索引，一次引文件只進(jìn)行兩次訪問，一次讀索引，一次讀記錄，由于索引表是有序的，則查找索引讀記錄，由于索引表是有序的，則查找索引表時(shí)可用折半查找法進(jìn)行。表時(shí)可用折半查找法進(jìn)行。索引文件的修改比較容易實(shí)現(xiàn)

16、。刪除一個(gè)索引文件的修改比較容易實(shí)現(xiàn)。刪除一個(gè)記錄僅需要?jiǎng)h去相應(yīng)的索引項(xiàng)；插入一個(gè)記記錄僅需要?jiǎng)h去相應(yīng)的索引項(xiàng)；插入一個(gè)記錄時(shí)，應(yīng)將記錄置于數(shù)據(jù)區(qū)的末尾，同時(shí)在錄時(shí)，應(yīng)將記錄置于數(shù)據(jù)區(qū)的末尾，同時(shí)在索引表中插入索引項(xiàng)。更新記錄時(shí)應(yīng)將更新索引表中插入索引項(xiàng)。更新記錄時(shí)應(yīng)將更新后的記錄置于數(shù)據(jù)區(qū)的末尾，同時(shí)修改索引后的記錄置于數(shù)據(jù)區(qū)的末尾，同時(shí)修改索引表中相應(yīng)的索引項(xiàng)。表中相應(yīng)的索引項(xiàng)。索引文件只能是磁盤文件，因?yàn)樗饕募饕募荒苁谴疟P文件，因?yàn)樗饕募慕M織方式是為隨機(jī)存取而設(shè)計(jì)的；磁帶的的組織方式是為隨機(jī)存取而設(shè)計(jì)的；磁帶的隨機(jī)存取效率很低。隨機(jī)存取效率很低。 在索引非順序文件中，記錄按關(guān)

17、鍵字順在索引非順序文件中，記錄按關(guān)鍵字順序排列，因此對每個(gè)記錄要建立一個(gè)索引序排列，因此對每個(gè)記錄要建立一個(gè)索引項(xiàng)，這樣的索引表稱為稠密索引。在稠密項(xiàng)，這樣的索引表稱為稠密索引。在稠密索引中可以預(yù)查找，由此可知某個(gè)記錄是索引中可以預(yù)查找，由此可知某個(gè)記錄是否存在以及在何處。對于索引順序文件，否存在以及在何處。對于索引順序文件，可以對一組記錄建立一個(gè)索引項(xiàng)，這種索可以對一組記錄建立一個(gè)索引項(xiàng)，這種索引表稱為非稠密索引，它不能進(jìn)行引表稱為非稠密索引，它不能進(jìn)行“預(yù)查預(yù)查找找“，但索引表占用空間少，管理要求低。，但索引表占用空間少，管理要求低。索引順序存取方法索引順序存取方法ISAM（Indexed

18、 Sequential Indexed Sequential Access MethodAccess Method的縮寫）是一種專為磁盤存取設(shè)計(jì)的縮寫）是一種專為磁盤存取設(shè)計(jì)的索引順序文件組織方式。的索引順序文件組織方式。 ISAM文件由多級(jí)主索文件由多級(jí)主索引、柱面索引、磁道索引和主文件組成。文件的記引、柱面索引、磁道索引和主文件組成。文件的記錄在同一盤組上存放時(shí)，應(yīng)盡量先放在一個(gè)柱面上，錄在同一盤組上存放時(shí)，應(yīng)盡量先放在一個(gè)柱面上，然后再順序存放在相鄰的柱面上；對同一柱面，則然后再順序存放在相鄰的柱面上；對同一柱面，則應(yīng)按盤面的次序順序存放。圖應(yīng)按盤面的次序順序存放。圖- -所示為存放在一

19、所示為存放在一個(gè)磁盤組上的個(gè)磁盤組上的ISAM文件。文件。 7.4 ISAM文件文件圖圖7-9 ISAM文件結(jié)構(gòu)示例文件結(jié)構(gòu)示例R150 磁道索引磁道索引50磁道索引磁道索引 柱面柱面C1 柱面索引柱面索引 主索引主索引R11 R20 R45 R47 R50500150150320 溢出區(qū)溢出區(qū) 溢出區(qū)溢出區(qū) 溢出區(qū)溢出區(qū)柱面柱面C2柱面柱面C3R180R210R32011004500450045008003203800210 磁道索引磁道索引 磁道索引磁道索引R3800R4500基本索引項(xiàng)基本索引項(xiàng) 溢出索引項(xiàng)溢出索引項(xiàng)圖圖7-10磁道索引項(xiàng)結(jié)構(gòu)磁道索引項(xiàng)結(jié)構(gòu)關(guān)鍵字關(guān)鍵字指針指針關(guān)鍵字關(guān)鍵字

20、指針指針各級(jí)索引中的索引項(xiàng)結(jié)構(gòu)如圖各級(jí)索引中的索引項(xiàng)結(jié)構(gòu)如圖7-10所示，其所示，其中每個(gè)磁道索引項(xiàng)由兩部分組成：基本索引項(xiàng)中每個(gè)磁道索引項(xiàng)由兩部分組成：基本索引項(xiàng)和溢出索引項(xiàng)。和溢出索引項(xiàng)。關(guān)鍵字指的是該磁道中最末一個(gè)記錄的關(guān)鍵關(guān)鍵字指的是該磁道中最末一個(gè)記錄的關(guān)鍵字，指針指向該磁道第一個(gè)記錄的位置。如：字，指針指向該磁道第一個(gè)記錄的位置。如：50為該磁道上的最后一個(gè)關(guān)鍵字。為該磁道上的最后一個(gè)關(guān)鍵字。柱面索引的每一個(gè)索引項(xiàng)也由關(guān)鍵字和指針柱面索引的每一個(gè)索引項(xiàng)也由關(guān)鍵字和指針兩部分組成，關(guān)鍵字指的是該柱面中最末一個(gè)兩部分組成，關(guān)鍵字指的是該柱面中最末一個(gè)記錄的關(guān)鍵字，指針指示柱面上的磁道索

21、引位記錄的關(guān)鍵字，指針指示柱面上的磁道索引位置，如：置，如：150為該柱面最末一個(gè)記錄的關(guān)鍵字。為該柱面最末一個(gè)記錄的關(guān)鍵字。ISAM文件檢索方法如下。先從主索引出項(xiàng)，找文件檢索方法如下。先從主索引出項(xiàng)，找到相應(yīng)的柱面索引，再從柱面索引找到記錄所在柱到相應(yīng)的柱面索引，再從柱面索引找到記錄所在柱面的磁道索引，最后從磁道索引找到記錄所在的第面的磁道索引，最后從磁道索引找到記錄所在的第一個(gè)記錄位置，由此出發(fā)在該磁道上進(jìn)行順序查找一個(gè)記錄位置，由此出發(fā)在該磁道上進(jìn)行順序查找直至找到為止，反之，若找遍該磁道而不存在此記直至找到為止，反之，若找遍該磁道而不存在此記錄錄,則表明該文件中無此記錄。則表明該文件

22、中無此記錄。在插入該記錄時(shí)，要發(fā)生溢出，每個(gè)柱面上還開在插入該記錄時(shí)，要發(fā)生溢出，每個(gè)柱面上還開辟有一個(gè)溢出區(qū)，磁道索引項(xiàng)中有溢出索引項(xiàng)。由辟有一個(gè)溢出區(qū)，磁道索引項(xiàng)中有溢出索引項(xiàng)。由于于ISAM文件中記錄是按關(guān)鍵字順序存放的，則在文件中記錄是按關(guān)鍵字順序存放的，則在插入記錄時(shí)，需移動(dòng)記錄并將同一磁道上最末一個(gè)插入記錄時(shí)，需移動(dòng)記錄并將同一磁道上最末一個(gè)記錄移至溢出區(qū)，同時(shí)修改磁道索引。記錄移至溢出區(qū)，同時(shí)修改磁道索引。在刪除記錄時(shí)，只需找到待刪記錄，在其在刪除記錄時(shí)，只需找到待刪記錄，在其存儲(chǔ)位置上作刪除標(biāo)志即可，而不需移動(dòng)記存儲(chǔ)位置上作刪除標(biāo)志即可，而不需移動(dòng)記錄或改變指針。在經(jīng)過多次增刪

23、后，文件結(jié)錄或改變指針。在經(jīng)過多次增刪后，文件結(jié)構(gòu)可能變得很不合理。此時(shí)可能溢出區(qū)中存構(gòu)可能變得很不合理。此時(shí)可能溢出區(qū)中存有大量記錄，而基本區(qū)中，又浪費(fèi)很多空間，有大量記錄，而基本區(qū)中，又浪費(fèi)很多空間，因此需要周期地整理文件，將溢出因此需要周期地整理文件，將溢出區(qū)中記錄移到基本區(qū)中，空出溢出區(qū)。區(qū)中記錄移到基本區(qū)中，空出溢出區(qū)。7.5 VSAM文件文件VSAM是是Virtual Storage Access Method(虛擬存儲(chǔ)存取方法虛擬存儲(chǔ)存取方法)的縮寫，它的縮寫，它是一種索引順序文件的組織方式，采用是一種索引順序文件的組織方式，采用B+樹作為動(dòng)態(tài)索引結(jié)構(gòu)。樹作為動(dòng)態(tài)索引結(jié)構(gòu)。7.6

24、 散列文件散列文件散列文件（亦稱直接存取文件）是利用散列技術(shù)散列文件（亦稱直接存取文件）是利用散列技術(shù)組織的文件，其組織方法類似于散列表，但存儲(chǔ)介組織的文件，其組織方法類似于散列表，但存儲(chǔ)介質(zhì)是外存儲(chǔ)器。質(zhì)是外存儲(chǔ)器。散列文件中的記錄通常是成組存放的。若干個(gè)記散列文件中的記錄通常是成組存放的。若干個(gè)記錄組成一個(gè)存儲(chǔ)單位。在散列文件中，這個(gè)存儲(chǔ)單錄組成一個(gè)存儲(chǔ)單位。在散列文件中，這個(gè)存儲(chǔ)單位叫做桶（位叫做桶（Bucket）。假如一個(gè)桶能存放）。假如一個(gè)桶能存放m個(gè)記錄，個(gè)記錄，則則m個(gè)互為同義詞的記錄可以存放在同一地址的桶中，個(gè)互為同義詞的記錄可以存放在同一地址的桶中，稱為基桶。當(dāng)?shù)诜Q為基桶。當(dāng)

25、第m+1個(gè)同義詞出現(xiàn)時(shí)，才發(fā)生個(gè)同義詞出現(xiàn)時(shí)，才發(fā)生“溢溢出出”。通常采用拉鏈法解決溢出。通常采用拉鏈法解決溢出。當(dāng)發(fā)生當(dāng)發(fā)生“溢出溢出”時(shí)，需要將第時(shí)，需要將第m+1個(gè)同義詞存放個(gè)同義詞存放到另一個(gè)桶中，通常稱此桶為到另一個(gè)桶中，通常稱此桶為“溢出桶溢出桶”。溢出桶。溢出桶和基桶大小相同，相互之間用指針相連接。當(dāng)在基和基桶大小相同，相互之間用指針相連接。當(dāng)在基桶中沒有找到待查記錄時(shí)，就按指針?biāo)傅揭绯鐾巴爸袥]有找到待查記錄時(shí)，就按指針?biāo)傅揭绯鐾爸羞M(jìn)行查找。中進(jìn)行查找。例如，某一文件有例如，某一文件有18個(gè)記錄，其關(guān)鍵字分別為個(gè)記錄，其關(guān)鍵字分別為285，116，070，923，597，17

26、7，512，262，015，076，157，208，337，817，613，117，390，362。桶的。桶的容量容量m=3，桶數(shù)，桶數(shù)b=7。用除留余數(shù)法構(gòu)造哈希函數(shù)。用除留余數(shù)法構(gòu)造哈希函數(shù)H(key)=key MOD 7。由此得到如圖。由此得到如圖7-13所示的直接所示的直接存取文件。存取文件。0123456070512015337597177262157116613285208817923076117390362圖圖7-13 直接存取文件直接存取文件桶編號(hào)桶編號(hào) 基桶基桶 溢出桶溢出桶 在直接存取文件中進(jìn)行查找時(shí)，首先根據(jù)給定值求出在直接存取文件中進(jìn)行查找時(shí)，首先根據(jù)給定值求出散列地址

27、（即基桶號(hào)），將基桶的記錄讀入內(nèi)存進(jìn)行順散列地址（即基桶號(hào)），將基桶的記錄讀入內(nèi)存進(jìn)行順序查找。若找到關(guān)鍵字等于給定值的記錄，則檢索成功；序查找。若找到關(guān)鍵字等于給定值的記錄，則檢索成功；否則根據(jù)指針域的值找到溢出桶，讀入溢出桶的記錄后否則根據(jù)指針域的值找到溢出桶，讀入溢出桶的記錄后繼續(xù)進(jìn)行查找。繼續(xù)進(jìn)行查找。散列文件刪除記錄時(shí)，僅需對被刪記錄作一標(biāo)記即可。散列文件刪除記錄時(shí)，僅需對被刪記錄作一標(biāo)記即可?？傊?，直接存取文件的優(yōu)點(diǎn)是：隨機(jī)存放、記錄無須總之，直接存取文件的優(yōu)點(diǎn)是：隨機(jī)存放、記錄無須排序、插入刪除方便、保存速度快、不需要索引區(qū)和節(jié)排序、插入刪除方便、保存速度快、不需要索引區(qū)和節(jié)省存

28、取空間。其缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)省存取空間。其缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取。在經(jīng)過多次插入、刪除后，也可能造成鍵字隨機(jī)存取。在經(jīng)過多次插入、刪除后，也可能造成溢出桶滿而基桶內(nèi)多數(shù)記錄已被刪除的情況，此時(shí)需要溢出桶滿而基桶內(nèi)多數(shù)記錄已被刪除的情況，此時(shí)需要重組文件。重組文件。 7.7 多關(guān)鍵字文件多關(guān)鍵字文件 在對文件進(jìn)行檢索操作時(shí)，不僅對主在對文件進(jìn)行檢索操作時(shí)，不僅對主關(guān)鍵字進(jìn)行詢問，還要對次關(guān)鍵字進(jìn)行關(guān)鍵字進(jìn)行詢問，還要對次關(guān)鍵字進(jìn)行某些查詢。某些查詢。因此，在文件組織中，不僅對主關(guān)鍵因此，在文件組織中，不僅對主關(guān)鍵字建立索引，對被查詢的次關(guān)鍵字也建字建立索引

29、，對被查詢的次關(guān)鍵字也建立相應(yīng)的索引，這樣建立的文件稱為立相應(yīng)的索引，這樣建立的文件稱為多多關(guān)鍵字文件關(guān)鍵字文件 。 多重表文件的特點(diǎn)是：記錄按主多重表文件的特點(diǎn)是：記錄按主關(guān)鍵字關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，并建立的順序構(gòu)成一個(gè)串聯(lián)文件，并建立主主關(guān)鍵字關(guān)鍵字的索引（稱為主索引）；對每一個(gè)需要查詢的索引（稱為主索引）；對每一個(gè)需要查詢的次關(guān)鍵字建立次關(guān)鍵字索引（稱為次索的次關(guān)鍵字建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記引），所有具有同一次關(guān)鍵字的記 錄構(gòu)成一錄構(gòu)成一個(gè)鏈表。主索引為非稠密索引，次索引為稠個(gè)鏈表。主索引為非稠密索引，次索引為稠密索引。每個(gè)索引項(xiàng)包括次關(guān)鍵字、頭指針密索引。每個(gè)索引項(xiàng)包括次關(guān)鍵字、頭指針和鏈表長度。通