第11章文件與外部排序

1、第第11章章 文件與外部排序文件與外部排序 在許多實際應(yīng)用中，特別是數(shù)據(jù)處理時，都需要在許多實際應(yīng)用中，特別是數(shù)據(jù)處理時，都需要長期存儲海量數(shù)據(jù)，這些數(shù)據(jù)通常以長期存儲海量數(shù)據(jù)，這些數(shù)據(jù)通常以文件文件的方式組織的方式組織并存儲在外存。如何有效地管理這些數(shù)據(jù)，從而給使并存儲在外存。如何有效地管理這些數(shù)據(jù)，從而給使用者提供方便而高效的使用數(shù)據(jù)的方法稱為用者提供方便而高效的使用數(shù)據(jù)的方法稱為文件管理文件管理。 在實際存取這些海量數(shù)據(jù)時，為了方便使用，往往在實際存取這些海量數(shù)據(jù)時，為了方便使用，往往以某種順序排序后再存儲在外存上，這種排序稱為以某種順序排序后再存儲在外存上，這種排序稱為外外部排序部排序

2、。在排序時由于一次不能將數(shù)據(jù)文件中的所有。在排序時由于一次不能將數(shù)據(jù)文件中的所有數(shù)據(jù)同時裝入內(nèi)存中進(jìn)行，因此就必須研究如何對外數(shù)據(jù)同時裝入內(nèi)存中進(jìn)行，因此就必須研究如何對外存上的數(shù)據(jù)進(jìn)行排序的技術(shù)。存上的數(shù)據(jù)進(jìn)行排序的技術(shù)。11.1 文件的基本概念文件的基本概念1 文件的基本概念文件的基本概念 數(shù)據(jù)項數(shù)據(jù)項(Item或或field) ：數(shù)據(jù)文件中最小的基本：數(shù)據(jù)文件中最小的基本單位，反映實體某一方面的特征單位，反映實體某一方面的特征屬性的數(shù)據(jù)表示。屬性的數(shù)據(jù)表示。 記錄記錄(Record) ：一個實體的所有數(shù)據(jù)項的集合。：一個實體的所有數(shù)據(jù)項的集合。 用來標(biāo)識一個記錄的數(shù)據(jù)項集合用來標(biāo)識一個記

3、錄的數(shù)據(jù)項集合(一個或多個一個或多個)稱為關(guān)鍵稱為關(guān)鍵字項字項(Key) ，關(guān)鍵字項的值稱為關(guān)鍵字，關(guān)鍵字項的值稱為關(guān)鍵字；能唯一標(biāo)識一能唯一標(biāo)識一個記錄的關(guān)鍵字稱為個記錄的關(guān)鍵字稱為主關(guān)鍵字主關(guān)鍵字(Primary Key)，其它的，其它的關(guān)鍵字稱為關(guān)鍵字稱為次關(guān)鍵字次關(guān)鍵字(Secondary Key) 。 通常的記錄指的是通常的記錄指的是邏輯記錄邏輯記錄，是從用戶角度所看到，是從用戶角度所看到的對數(shù)據(jù)的表示和存取的方式。的對數(shù)據(jù)的表示和存取的方式。 文件存儲在外存上，通常是以塊文件存儲在外存上，通常是以塊(I/O讀寫的基本單讀寫的基本單位，稱為位，稱為物理記錄物理記錄)存取。存取。 物理

4、記錄和邏輯記錄之間的關(guān)系是物理記錄和邏輯記錄之間的關(guān)系是： 一個物理記錄存放一個邏輯記錄；一個物理記錄存放一個邏輯記錄； 一個物理記錄包含多個邏輯記錄；一個物理記錄包含多個邏輯記錄； 多個物理記錄存放一個邏輯記錄多個物理記錄存放一個邏輯記錄。 文件文件(File)：大量性質(zhì)相同的數(shù)據(jù)記錄的集合。文：大量性質(zhì)相同的數(shù)據(jù)記錄的集合。文件的所有記錄是按某種排列順序呈現(xiàn)在用戶面前件的所有記錄是按某種排列順序呈現(xiàn)在用戶面前，這種，這種排列順序可以是按記錄的關(guān)鍵字，也可以是按記錄進(jìn)入排列順序可以是按記錄的關(guān)鍵字，也可以是按記錄進(jìn)入文件的先后等文件的先后等。則記錄之間形成一種線性結(jié)構(gòu)則記錄之間形成一種線性結(jié)

5、構(gòu)(邏輯上邏輯上的的)，稱為文件的，稱為文件的邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)；文件在外存上的組織方式；文件在外存上的組織方式稱為文件的稱為文件的物理結(jié)構(gòu)物理結(jié)構(gòu)?；镜奈锢斫Y(jié)構(gòu)有基本的物理結(jié)構(gòu)有：順序結(jié)構(gòu)：順序結(jié)構(gòu)，鏈接結(jié)構(gòu)，索引結(jié)構(gòu)鏈接結(jié)構(gòu)，索引結(jié)構(gòu) 。 文件的分類文件的分類 按記錄類型，可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件按記錄類型，可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件： 操作系統(tǒng)文件操作系統(tǒng)文件(流式文件流式文件) ： 連續(xù)的字符序列連續(xù)的字符序列(串串)的集合；的集合； 數(shù)據(jù)庫文件數(shù)據(jù)庫文件： 有特定結(jié)構(gòu)有特定結(jié)構(gòu)(所有記錄的結(jié)構(gòu)都相所有記錄的結(jié)構(gòu)都相同同)的數(shù)據(jù)記錄的集合的數(shù)據(jù)記錄的集合。 按記錄長度，可分為

6、定長記錄文件和不定長記錄文件按記錄長度，可分為定長記錄文件和不定長記錄文件： 定長記錄文件定長記錄文件：文件中每個記錄都有固定的數(shù)：文件中每個記錄都有固定的數(shù)據(jù)項組成據(jù)項組成，每個數(shù)據(jù)項的長度都是固定的；，每個數(shù)據(jù)項的長度都是固定的； 不定長記錄文件不定長記錄文件：與：與定長記錄文件相反定長記錄文件相反。2 文件的有關(guān)操作文件的有關(guān)操作 文件是由大量記錄組成的線性表，因此，對文件的操文件是由大量記錄組成的線性表，因此，對文件的操作主要是針對記錄的，通常有：記錄的檢索、插入、刪作主要是針對記錄的，通常有：記錄的檢索、插入、刪除、修改和排序，其中檢索是最基本的操作。除、修改和排序，其中檢索是最基本

7、的操作。 檢索記錄檢索記錄 根據(jù)用戶的要求從文件中查找相應(yīng)的記錄。根據(jù)用戶的要求從文件中查找相應(yīng)的記錄。 查找下一個記錄查找下一個記錄：找當(dāng)前記錄的下一個邏輯記錄：找當(dāng)前記錄的下一個邏輯記錄； 查找第查找第k個記錄個記錄：給出記錄的邏輯序號，根據(jù)該序：給出記錄的邏輯序號，根據(jù)該序號查找相應(yīng)的記錄；號查找相應(yīng)的記錄； 按關(guān)鍵字查找按關(guān)鍵字查找：給出指定的關(guān)鍵字值，查找關(guān)鍵：給出指定的關(guān)鍵字值，查找關(guān)鍵字值相同或滿足條件的記錄。對數(shù)據(jù)庫文件，有以下字值相同或滿足條件的記錄。對數(shù)據(jù)庫文件，有以下四種按關(guān)鍵字查找的方式：四種按關(guān)鍵字查找的方式： 簡單匹配簡單匹配：查找關(guān)鍵字的值與給定的值相等的：查找關(guān)

8、鍵字的值與給定的值相等的記錄記錄； 區(qū)域匹配區(qū)域匹配：查找關(guān)鍵字的值在某個區(qū)域范圍內(nèi)：查找關(guān)鍵字的值在某個區(qū)域范圍內(nèi)的記錄的記錄； 函數(shù)匹配函數(shù)匹配：給出關(guān)鍵字的某個函數(shù)：給出關(guān)鍵字的某個函數(shù)，查找符合查找符合條件的記錄條件的記錄； 組合條件匹配組合條件匹配：給出用布爾表達(dá)式表示的多個：給出用布爾表達(dá)式表示的多個條件組合條件組合，查找符合條件的記錄。查找符合條件的記錄。 插入記錄插入記錄 將給定的記錄插入到文件的指定位置。插入是首先要將給定的記錄插入到文件的指定位置。插入是首先要確定插入點的位置確定插入點的位置(檢索記錄檢索記錄)，然后才能插入，然后才能插入。 刪除記錄刪除記錄 從文件中刪除給

9、定的記錄。記錄的刪除有兩種情況：從文件中刪除給定的記錄。記錄的刪除有兩種情況： 在文件中刪除第在文件中刪除第k個記錄個記錄； 在文件中刪除符合條件的記錄。在文件中刪除符合條件的記錄。 修改記錄修改記錄 對符合條件的記錄對符合條件的記錄，更改某些屬性值，更改某些屬性值。修改時首先要。修改時首先要檢索到所要修改的記錄，然后才能修改檢索到所要修改的記錄，然后才能修改。 記錄排序記錄排序 根據(jù)指定的關(guān)鍵字根據(jù)指定的關(guān)鍵字，對文件中的記錄按關(guān)鍵字值的大，對文件中的記錄按關(guān)鍵字值的大小以非遞減或非遞增的方式重新排列小以非遞減或非遞增的方式重新排列(或存儲或存儲)。11.2 文件的組織方式文件的組織方式 文

10、件的組織方式文件的組織方式指的是文件的物理結(jié)構(gòu)。指的是文件的物理結(jié)構(gòu)。11.2.1 順序文件順序文件 記錄記錄按按其在文件中的其在文件中的邏輯順序邏輯順序依次進(jìn)入存儲介質(zhì)依次進(jìn)入存儲介質(zhì)。在順序文件中在順序文件中，記錄的邏輯順序和存儲順序是一致的，記錄的邏輯順序和存儲順序是一致的。 根據(jù)根據(jù)記錄是否按關(guān)鍵字排序記錄是否按關(guān)鍵字排序：可分為排序順序文件和一般：可分為排序順序文件和一般順序文件順序文件； 根據(jù)根據(jù)邏輯上相鄰邏輯上相鄰的記錄的的記錄的物理位置物理位置關(guān)系：可分為連續(xù)順序關(guān)系：可分為連續(xù)順序文件和鏈接順序文件。文件和鏈接順序文件。 順序文件類似于線性表的順序存儲結(jié)構(gòu)順序文件類似于線性表

11、的順序存儲結(jié)構(gòu)，比較簡單，比較簡單，適合于順序存取的外存介質(zhì)，但不適合隨機處理適合于順序存取的外存介質(zhì)，但不適合隨機處理。11.2.2 索引文件索引文件 索引技術(shù)是組織大型數(shù)據(jù)庫的一種重要技術(shù)，索引技術(shù)是組織大型數(shù)據(jù)庫的一種重要技術(shù)，索索引是記錄和記錄存儲地址之間的對照表引是記錄和記錄存儲地址之間的對照表。索引結(jié)構(gòu)。索引結(jié)構(gòu)(稱稱為索引文件為索引文件)由由索引表索引表和和數(shù)據(jù)表數(shù)據(jù)表兩部分，如圖兩部分，如圖11-1所示。所示。 數(shù)據(jù)表數(shù)據(jù)表：存儲實際的數(shù)據(jù)記錄；：存儲實際的數(shù)據(jù)記錄； 索引表索引表：存儲記錄的：存儲記錄的關(guān)鍵字關(guān)鍵字和和記錄記錄(存儲存儲)地址地址之之間的對照表，每個元素稱為一

12、個間的對照表，每個元素稱為一個索引項索引項。 如果數(shù)據(jù)文件中的每一個記錄都有一個索引項，這種如果數(shù)據(jù)文件中的每一個記錄都有一個索引項，這種索引稱為索引稱為稠密索引稠密索引，否則，稱為，否則，稱為非稠密索引非稠密索引。 對于非稠密索引，通常將文件記錄劃分為若干塊，對于非稠密索引，通常將文件記錄劃分為若干塊，塊塊內(nèi)內(nèi)記錄可以記錄可以無序無序，但，但塊間塊間必須必須有序有序。若塊內(nèi)記錄是有序。若塊內(nèi)記錄是有序的，稱為索引順序文件，否則稱為索引非順序文件。對的，稱為索引順序文件，否則稱為索引非順序文件。對于索引非順序文件，只需對每一塊建立一個索引項。于索引非順序文件，只需對每一塊建立一個索引項。圖圖1

13、1-1 索引結(jié)構(gòu)的基本形式索引結(jié)構(gòu)的基本形式索引表索引表數(shù)據(jù)表數(shù)據(jù)表關(guān)鍵字關(guān)鍵字 指針指針 263 275 386 1046 593 681 386 1046 681 593 263 275關(guān)鍵字關(guān)鍵字 其他域其他域(a) 稠密索引文件稠密索引文件索引表索引表數(shù)據(jù)表數(shù)據(jù)表(b) 非稠密索引文件非稠密索引文件 263 386 681關(guān)鍵字關(guān)鍵字 指針指針 386 681 263 275關(guān)鍵字關(guān)鍵字 其他域其他域 對于對于稠密索引稠密索引，可以根據(jù)索引項直接查找到記錄的，可以根據(jù)索引項直接查找到記錄的位置。若在索引表中位置。若在索引表中采用順序查找采用順序查找，查找，查找時間復(fù)雜度為時間復(fù)雜度為O

14、(n) ；若；若采用折半查找采用折半查找，查找，查找時間復(fù)雜度為時間復(fù)雜度為O(2n) 。 對于稠密索引，索引項數(shù)目與數(shù)據(jù)表中記錄數(shù)相同，對于稠密索引，索引項數(shù)目與數(shù)據(jù)表中記錄數(shù)相同，當(dāng)索引表很大時，檢索記錄需多次訪問外存。當(dāng)索引表很大時，檢索記錄需多次訪問外存。 對于對于非稠密索引非稠密索引，查找的基本思想是：，查找的基本思想是： 首先根據(jù)索引找到記錄所在塊，再將該塊讀入到內(nèi)首先根據(jù)索引找到記錄所在塊，再將該塊讀入到內(nèi)存，然后再在塊內(nèi)順序查找。存，然后再在塊內(nèi)順序查找。 平均查找長度由兩部分組成：塊地址的平均查找長平均查找長度由兩部分組成：塊地址的平均查找長度度Lb，塊內(nèi)記錄的平均查找長度，

15、塊內(nèi)記錄的平均查找長度Lw，即，即ASLbs=Lb+Lw 若將長度為若將長度為n的文件分為的文件分為b塊，每塊內(nèi)有塊，每塊內(nèi)有s個記錄，個記錄，則則b=n/s 。設(shè)每塊的查找概率為。設(shè)每塊的查找概率為1/b，塊內(nèi)每個的記錄，塊內(nèi)每個的記錄查找概率為查找概率為1/b，則采用順序查找方法時有：，則采用順序查找方法時有：ASLbs=Lb+Lw=(b+1)/2+(s+1)/2=(n/s+s)+1顯然，當(dāng)顯然，當(dāng)s=n1/2時，時，ASLbs的值達(dá)到最??；的值達(dá)到最??； 若在索引表中采用折半查找方法時有：若在索引表中采用折半查找方法時有：ASLbs=Lb+Lw= 2(n/s+1)+s/2 如果文件中記錄

16、數(shù)很龐大，對非稠密索引而言，如果文件中記錄數(shù)很龐大，對非稠密索引而言，索引也很大，可以將索引表再分塊，建立索引也很大，可以將索引表再分塊，建立索引的索引索引的索引，形成樹形結(jié)構(gòu)的多級索引，如后面將要介紹的形成樹形結(jié)構(gòu)的多級索引，如后面將要介紹的ISAM文文件和件和VSAM文件。文件。11.2.3 ISAM文件文件 ISAM(Indexed Sequential Access Method，順順序索引存取方法序索引存取方法)，是專為磁盤存取設(shè)計的一種文件組，是專為磁盤存取設(shè)計的一種文件組織方式，采用靜態(tài)索引結(jié)構(gòu)，是一種三級索引結(jié)構(gòu)的順織方式，采用靜態(tài)索引結(jié)構(gòu)，是一種三級索引結(jié)構(gòu)的順序文件。圖序文

17、件。圖11-2是一個磁盤組的結(jié)構(gòu)圖。是一個磁盤組的結(jié)構(gòu)圖。磁道磁道扇區(qū)扇區(qū)柱面柱面圖圖11-2 一個磁盤組結(jié)構(gòu)形式一個磁盤組結(jié)構(gòu)形式盤面盤面 ISAM文件文件由由基本文基本文件件、磁道索引磁道索引、柱面索引柱面索引和和主索引主索引組成。組成。 基本文件基本文件按關(guān)鍵字按關(guān)鍵字的值順序存放的值順序存放，首先集中，首先集中存放在同一柱面上，然后存放在同一柱面上，然后再順序存放在相鄰柱面上；再順序存放在相鄰柱面上；對于同一柱面，則按盤面對于同一柱面，則按盤面的次序順序存放。的次序順序存放。 在每個柱面上，還開辟了一個溢出區(qū)，存放從該在每個柱面上，還開辟了一個溢出區(qū)，存放從該柱面的磁道上溢出的記錄。同

18、一磁道上溢出的記錄通常柱面的磁道上溢出的記錄。同一磁道上溢出的記錄通常由指針相鏈接。由指針相鏈接。 ISAM文件為每個磁道建立一個索引項，相同柱面文件為每個磁道建立一個索引項，相同柱面的磁道索引項組成一個索引表，稱為的磁道索引項組成一個索引表，稱為磁道索引磁道索引，由基本，由基本索引項和溢出索引項組成，其結(jié)構(gòu)是：索引項和溢出索引項組成，其結(jié)構(gòu)是： 基本索引項基本索引項：關(guān)鍵字域存放該磁道上的最大關(guān)鍵：關(guān)鍵字域存放該磁道上的最大關(guān)鍵字；指針域存放該磁道的首地址。字；指針域存放該磁道的首地址。 關(guān)鍵字關(guān)鍵字 指針指針 關(guān)鍵字關(guān)鍵字 指針指針基本索引項基本索引項溢出索引項溢出索引項 溢出索引項溢出索

19、引項：是為插入記錄設(shè)置的。關(guān)鍵字域存放該磁道：是為插入記錄設(shè)置的。關(guān)鍵字域存放該磁道上上溢出溢出的記錄的最大關(guān)鍵字；指針域存放的記錄的最大關(guān)鍵字；指針域存放溢出溢出記錄鏈表的頭指記錄鏈表的頭指針。針。 在磁道索引的基礎(chǔ)上，又為文件所占用的柱面建立在磁道索引的基礎(chǔ)上，又為文件所占用的柱面建立一個一個柱面索引柱面索引，其結(jié)構(gòu)是，其結(jié)構(gòu)是：關(guān)鍵字關(guān)鍵字 指針指針 關(guān)鍵字域存放該柱面上的最大關(guān)鍵字；指針域指關(guān)鍵字域存放該柱面上的最大關(guān)鍵字；指針域指向該柱面的第向該柱面的第1個磁道索引項。個磁道索引項。 當(dāng)柱面索引很大時，柱面索引本身占用很多磁道當(dāng)柱面索引很大時，柱面索引本身占用很多磁道，又可為柱面索引

20、建立一個，又可為柱面索引建立一個主索引主索引。則。則ISAM文件的三文件的三級索引結(jié)構(gòu)如圖級索引結(jié)構(gòu)如圖11-3所示。所示。磁道索引磁道索引柱面索引柱面索引R7 R13 R23 R76 R31基本區(qū)基本區(qū)溢出區(qū)溢出區(qū)柱面柱面C1 R2340 R3760 溢出區(qū)溢出區(qū)柱面柱面Cn23 3076 23403760 761363487683760主索引主索引3487683760圖圖11-3 ISAM文件結(jié)構(gòu)示意圖文件結(jié)構(gòu)示意圖1 ISAM文件的檢索文件的檢索 根據(jù)關(guān)鍵字查找時，首先從主索引中查找記錄所在根據(jù)關(guān)鍵字查找時，首先從主索引中查找記錄所在的柱面索引塊的位置；再從柱面索引塊中查找磁道索引的柱面

21、索引塊的位置；再從柱面索引塊中查找磁道索引塊的位置；然后再從磁道索引塊中查找出該記錄所在的塊的位置；然后再從磁道索引塊中查找出該記錄所在的磁道位置；最后從磁道中順序查找要檢索的記錄。磁道位置；最后從磁道中順序查找要檢索的記錄。2 記錄的插入記錄的插入 首先根據(jù)待插入記錄的關(guān)鍵字查找到相應(yīng)位置首先根據(jù)待插入記錄的關(guān)鍵字查找到相應(yīng)位置；然然后將該磁道中后將該磁道中插入位置及以后的記錄后移插入位置及以后的記錄后移一個位置一個位置(若若溢出，將該磁道中最后一個記錄存入同一柱面的溢出區(qū)，溢出，將該磁道中最后一個記錄存入同一柱面的溢出區(qū)，并修改磁道索引并修改磁道索引) ；最后將記錄插入到相應(yīng)位置。；最后將

22、記錄插入到相應(yīng)位置。3 記錄的刪除記錄的刪除 只需找到要刪除的記錄，對其只需找到要刪除的記錄，對其做刪除標(biāo)記做刪除標(biāo)記，不移動，不移動記錄記錄。當(dāng)經(jīng)過多次插入和刪除操作后。當(dāng)經(jīng)過多次插入和刪除操作后，基本區(qū)有大量被，基本區(qū)有大量被刪除的記錄，而溢出區(qū)也可能有大量記錄，則周期性地刪除的記錄，而溢出區(qū)也可能有大量記錄，則周期性地整理整理ISAM文件，形成一個新的文件，形成一個新的ISAM文件文件。4 ISAM文件的特點文件的特點 優(yōu)點優(yōu)點：節(jié)省存儲空間：節(jié)省存儲空間，查找速度快，查找速度快； 缺點缺點：處理刪除記錄復(fù)雜：處理刪除記錄復(fù)雜，多次刪除后，多次刪除后存儲空間的利用率存儲空間的利用率和存取

23、效率降低和存取效率降低，需定期整理，需定期整理ISAM文件文件。11.2.4 VSAM文件文件 VSAM(Virtual Storage Access Method，虛擬存，虛擬存取方法取方法)，也是一種索引順序文件組織方式，利用，也是一種索引順序文件組織方式，利用OS的的虛擬存儲器功能，采用的是基于虛擬存儲器功能，采用的是基于B+樹的動態(tài)索引結(jié)構(gòu)。樹的動態(tài)索引結(jié)構(gòu)。 文件文件的存取不是以柱面、磁道等物理空間為存取單位，的存取不是以柱面、磁道等物理空間為存取單位，而是以邏輯空間而是以邏輯空間控制區(qū)間控制區(qū)間(Control Interval)和控制和控制區(qū)域區(qū)域(Control Range)為

24、存取單位。為存取單位。 一個一個VSAM文件由文件由索引集索引集、順序集順序集和和數(shù)據(jù)集數(shù)據(jù)集組成，組成，如圖如圖11-4所示。所示。 文件的文件的記錄都存放在數(shù)據(jù)集中記錄都存放在數(shù)據(jù)集中，數(shù)據(jù)集又分成多個控，數(shù)據(jù)集又分成多個控制區(qū)間；制區(qū)間；VSAM進(jìn)行進(jìn)行I/O操作的基本單位是控制區(qū)間操作的基本單位是控制區(qū)間，由一組連續(xù)的存儲單元組成，同一文件的控制區(qū)間大小由一組連續(xù)的存儲單元組成，同一文件的控制區(qū)間大小相同；相同； 每個控制區(qū)間存放一個或多個邏輯記錄，記錄是每個控制區(qū)間存放一個或多個邏輯記錄，記錄是按關(guān)鍵字值順序存放在控制區(qū)間的前端，尾端存放記錄按關(guān)鍵字值順序存放在控制區(qū)間的前端，尾端存

25、放記錄的控制信息和控制區(qū)間的控制信息，如圖的控制信息和控制區(qū)間的控制信息，如圖11-5所示。所示。 控制區(qū)間控制區(qū)間 69 124 246 22 38 69 198 246 12 20 24 31 386812141720 212 228 246203208212213218228233238246控制區(qū)域控制區(qū)域索索引引集集順序集順序集B+樹樹圖圖11-4 VSAM文件結(jié)構(gòu)示意圖文件結(jié)構(gòu)示意圖數(shù)據(jù)集數(shù)據(jù)集 順序集順序集是由是由B+樹索引結(jié)構(gòu)的葉子結(jié)點組成。每個結(jié)樹索引結(jié)構(gòu)的葉子結(jié)點組成。每個結(jié)點存放若干個相鄰控制區(qū)間的索引項，每個索引項存放點存放若干個相鄰控制區(qū)間的索引項，每個索引項存放一個

26、控制區(qū)間中記錄的最大關(guān)鍵字值和指向該控制區(qū)間一個控制區(qū)間中記錄的最大關(guān)鍵字值和指向該控制區(qū)間的指針。順序集中的每個結(jié)點及與它所對應(yīng)的全部控制的指針。順序集中的每個結(jié)點及與它所對應(yīng)的全部控制區(qū)間組成一個區(qū)間組成一個控制區(qū)域控制區(qū)域。 順序集中的結(jié)點之間按順序順序集中的結(jié)點之間按順序鏈接鏈接成一個鏈表，每成一個鏈表，每個結(jié)點又在其上層建立索引，并逐層向上按個結(jié)點又在其上層建立索引，并逐層向上按B+樹的形式樹的形式建立多級索引。則順序集中的每一個結(jié)點就是建立多級索引。則順序集中的每一個結(jié)點就是B+樹的葉樹的葉子結(jié)點；在順序集之上的索引部分稱為子結(jié)點；在順序集之上的索引部分稱為索引集索引集。 在在VS

27、AM文件上既可以按文件上既可以按B+樹的方式實現(xiàn)記錄的查找，樹的方式實現(xiàn)記錄的查找，又可以利用順序集索引實現(xiàn)記錄順序查找。又可以利用順序集索引實現(xiàn)記錄順序查找。未用的未用的自由空間自由空間Rn的的控制信息控制信息R1的的控制信息控制信息控制區(qū)間的控制區(qū)間的控制信息控制信息R1 R2 Rn圖圖11-5 控制區(qū)間的結(jié)構(gòu)控制區(qū)間的結(jié)構(gòu) VSAM文件中沒有溢出區(qū)，解決方法是留出空間：文件中沒有溢出區(qū)，解決方法是留出空間： 每個控制區(qū)間中留出空間；每個控制區(qū)間中留出空間； 每個控制區(qū)域留出空的控制空間，并在順序集的每個控制區(qū)域留出空的控制空間，并在順序集的索引中指出。索引中指出。1 記錄的插入記錄的插入

28、 首先根據(jù)待插入記錄的關(guān)鍵字查找到相應(yīng)的位置：首先根據(jù)待插入記錄的關(guān)鍵字查找到相應(yīng)的位置： 若若該控制區(qū)間有可用空間該控制區(qū)間有可用空間：將關(guān)鍵字：將關(guān)鍵字大于待插入大于待插入記錄的關(guān)鍵字的記錄全部后移記錄的關(guān)鍵字的記錄全部后移一個位置，在空出的一個位置，在空出的位置存放待插入記錄；位置存放待插入記錄； 若若控制區(qū)間沒有可用空間控制區(qū)間沒有可用空間：利用同一控制區(qū)域的：利用同一控制區(qū)域的一個空白控制空間進(jìn)行區(qū)間分裂，將近一半記錄移一個空白控制空間進(jìn)行區(qū)間分裂，將近一半記錄移到新的控制區(qū)間中，并修改順序集中相應(yīng)的索引，到新的控制區(qū)間中，并修改順序集中相應(yīng)的索引，插入新的記錄；插入新的記錄； 若若

29、控制區(qū)域中沒有空白控制空間控制區(qū)域中沒有空白控制空間：則開辟一個新的控制區(qū)：則開辟一個新的控制區(qū)域，進(jìn)行控制區(qū)間域分裂和相應(yīng)的順序集中的結(jié)點分裂域，進(jìn)行控制區(qū)間域分裂和相應(yīng)的順序集中的結(jié)點分裂。也可也可按按B+樹的分裂方法進(jìn)行樹的分裂方法進(jìn)行。2 記錄的刪除記錄的刪除 先找到要刪除的記錄，然后將同一控制區(qū)間中比刪先找到要刪除的記錄，然后將同一控制區(qū)間中比刪除記錄關(guān)鍵字大的所有記錄逐個前移，覆蓋要刪除的記除記錄關(guān)鍵字大的所有記錄逐個前移，覆蓋要刪除的記錄錄。當(dāng)一個控制區(qū)間的記錄全部刪除后。當(dāng)一個控制區(qū)間的記錄全部刪除后，需修改順序集，需修改順序集中相應(yīng)的索引項中相應(yīng)的索引項。3 VSAM文件的特

30、點文件的特點 優(yōu)點優(yōu)點 能動態(tài)地分配和釋放空間；能動態(tài)地分配和釋放空間； 能保持較高的查詢效率，無論是查詢原有的還能保持較高的查詢效率，無論是查詢原有的還是后插入的記錄，都有相同的查詢速度；是后插入的記錄，都有相同的查詢速度； 能保持較高的存儲利用率能保持較高的存儲利用率(平均平均75%) ； 永遠(yuǎn)不需定期整理文件或?qū)ξ募M(jìn)行再組織。永遠(yuǎn)不需定期整理文件或?qū)ξ募M(jìn)行再組織。 缺點缺點 為保證具有較好的索引結(jié)構(gòu)，在插入或刪除時為保證具有較好的索引結(jié)構(gòu)，在插入或刪除時索引結(jié)構(gòu)本身也在變化；索引結(jié)構(gòu)本身也在變化； 控制信息和索引占用空間較多，因此，控制信息和索引占用空間較多，因此，VSAM文件通常比

31、較龐大。文件通常比較龐大。 基于基于B+樹的樹的VSAM文件通常被作為大型索引順序文件通常被作為大型索引順序文件的標(biāo)準(zhǔn)。文件的標(biāo)準(zhǔn)。11.2.5 散列文件散列文件 散列文件散列文件(直接存取文件直接存取文件) ：利用散列存儲方式利用散列存儲方式組織的文件。類似散列表，即根據(jù)文件中記錄關(guān)鍵字的組織的文件。類似散列表，即根據(jù)文件中記錄關(guān)鍵字的特點，設(shè)計一個散列函數(shù)和沖突處理方法，將記錄散列特點，設(shè)計一個散列函數(shù)和沖突處理方法，將記錄散列到存儲介質(zhì)上。到存儲介質(zhì)上。 在散列文件中，磁盤上的記錄是成組存放的，若在散列文件中，磁盤上的記錄是成組存放的，若干個記錄組成一個存儲單位，稱為干個記錄組成一個存儲

32、單位，稱為桶桶(Bucket)，同一個，同一個桶中的記錄都是同義詞桶中的記錄都是同義詞(關(guān)鍵字的角度關(guān)鍵字的角度) 。 設(shè)一個桶中能存放設(shè)一個桶中能存放m個記錄，當(dāng)桶中已有個記錄，當(dāng)桶中已有m個同義個同義詞的記錄時，要存放第詞的記錄時，要存放第m+1個同義詞就個同義詞就“溢出溢出” 。沖突。沖突處理方法一般是處理方法一般是拉鏈法拉鏈法。 檢索記錄時，先根據(jù)給定值求出散列桶地址，將檢索記錄時，先根據(jù)給定值求出散列桶地址，將基基桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到關(guān)鍵字等于給桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到關(guān)鍵字等于給定值的記錄，則查找成功；否則，依次讀入各溢出桶中定值的記錄，則查找成功；否則

33、，依次讀入各溢出桶中的記錄繼續(xù)進(jìn)行查找。的記錄繼續(xù)進(jìn)行查找。 在散列文件中刪除記錄，是對記錄加刪除標(biāo)記在散列文件中刪除記錄，是對記錄加刪除標(biāo)記 。散列文件的特點散列文件的特點 優(yōu)點優(yōu)點 文件隨機存取，記錄不需進(jìn)行排序；文件隨機存取，記錄不需進(jìn)行排序； 插入、刪除方便，存取速度快；插入、刪除方便，存取速度快； 不需要索引區(qū)，節(jié)省存儲空間。不需要索引區(qū)，節(jié)省存儲空間。 缺點缺點 不能進(jìn)行順序存取，只能按關(guān)鍵字隨機存??；不能進(jìn)行順序存取，只能按關(guān)鍵字隨機存??； 檢索方式僅限于簡單查詢。檢索方式僅限于簡單查詢。11.2.6 多關(guān)鍵字文件多關(guān)鍵字文件 數(shù)據(jù)庫文件常常是多關(guān)鍵字文件，多關(guān)鍵字文件數(shù)據(jù)庫文件

34、常常是多關(guān)鍵字文件，多關(guān)鍵字文件的特點是不僅可以對主關(guān)鍵字進(jìn)行各種查詢，而且可以的特點是不僅可以對主關(guān)鍵字進(jìn)行各種查詢，而且可以對次關(guān)鍵字進(jìn)行各種查詢。因此，對多關(guān)鍵字文件除了對次關(guān)鍵字進(jìn)行各種查詢。因此，對多關(guān)鍵字文件除了可按前面的方法組織主關(guān)鍵字索引外，還需要建立各個可按前面的方法組織主關(guān)鍵字索引外，還需要建立各個次關(guān)鍵字的索引。由于建立次關(guān)鍵字的索引的結(jié)構(gòu)不同，次關(guān)鍵字的索引。由于建立次關(guān)鍵字的索引的結(jié)構(gòu)不同，多關(guān)鍵字文件有多重表文件和倒排文件。多關(guān)鍵字文件有多重表文件和倒排文件。1 多重表文件多重表文件 多重表文件多重表文件(Multilist Files)的特點是：記錄按的特點是：記

35、錄按主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件主關(guān)鍵字的順序構(gòu)成一個串聯(lián)文件(物理上的物理上的) ，并建立，并建立主關(guān)鍵字索引主關(guān)鍵字索引(稱為主索引稱為主索引)；對每個次關(guān)鍵字都建立次；對每個次關(guān)鍵字都建立次關(guān)鍵字索引關(guān)鍵字索引(稱為次索引稱為次索引)，所有具有同一次關(guān)鍵字值的，所有具有同一次關(guān)鍵字值的記錄構(gòu)成一個鏈表記錄構(gòu)成一個鏈表(邏輯上的邏輯上的)。 主索引主索引一般是非稠密索引，其索引項一般有兩項：一般是非稠密索引，其索引項一般有兩項：主關(guān)鍵字值、頭指針。主關(guān)鍵字值、頭指針。 次索引次索引一般是稠密索引，其索引項一般有三項：次一般是稠密索引，其索引項一般有三項：次關(guān)鍵字值、頭指針、鏈表長度。關(guān)鍵

36、字值、頭指針、鏈表長度。頭指針頭指針指向數(shù)據(jù)文件中指向數(shù)據(jù)文件中具有該次關(guān)鍵字值的第具有該次關(guān)鍵字值的第1個記錄，在數(shù)據(jù)文件中為各個個記錄，在數(shù)據(jù)文件中為各個次關(guān)鍵字增加一個指針域，指向具有相同次關(guān)鍵字值的次關(guān)鍵字增加一個指針域，指向具有相同次關(guān)鍵字值的下一個記錄的地址。下一個記錄的地址。 對于任何次關(guān)鍵字的查詢，都應(yīng)首先查找對應(yīng)的對于任何次關(guān)鍵字的查詢，都應(yīng)首先查找對應(yīng)的索引，然后順著相應(yīng)指針?biāo)傅姆较虿檎覍儆诒炬湵淼乃饕?，然后順著相?yīng)指針?biāo)傅姆较虿檎覍儆诒炬湵淼挠涗?。記錄。多重表文件的特點多重表文件的特點 優(yōu)點優(yōu)點易于構(gòu)造和修改、查詢方便。易于構(gòu)造和修改、查詢方便。 缺點缺點插入和刪除一

37、個記錄時，需要修改多個次關(guān)鍵字的插入和刪除一個記錄時，需要修改多個次關(guān)鍵字的指針指針(在鏈表中插入或刪除記錄在鏈表中插入或刪除記錄)，同時還要修改各，同時還要修改各索引中的有關(guān)信息。索引中的有關(guān)信息。2 倒排文件倒排文件 倒排文件倒排文件又稱逆轉(zhuǎn)表文件。與多重表文件類似，又稱逆轉(zhuǎn)表文件。與多重表文件類似，可以處理多關(guān)鍵字查詢。其差別是：可以處理多關(guān)鍵字查詢。其差別是： 多重表文件：將具有相同關(guān)鍵字值的記錄鏈接在多重表文件：將具有相同關(guān)鍵字值的記錄鏈接在一起，在數(shù)據(jù)文件中設(shè)有與各個關(guān)鍵字對應(yīng)的指針一起，在數(shù)據(jù)文件中設(shè)有與各個關(guān)鍵字對應(yīng)的指針域；域； 倒排文件：將具有相同關(guān)鍵字值的記錄的地址收倒排

38、文件：將具有相同關(guān)鍵字值的記錄的地址收集在一起，并保存到相應(yīng)的次關(guān)鍵字的索引項中，集在一起，并保存到相應(yīng)的次關(guān)鍵字的索引項中，在數(shù)據(jù)文件中不設(shè)置對應(yīng)的指針域，見在數(shù)據(jù)文件中不設(shè)置對應(yīng)的指針域，見p321。 次索引次索引是次關(guān)鍵字倒排表，倒排表由次關(guān)鍵字值、是次關(guān)鍵字倒排表，倒排表由次關(guān)鍵字值、記錄指針記錄指針(地址地址)，索引中保持次關(guān)鍵字的邏輯順序。，索引中保持次關(guān)鍵字的邏輯順序。倒排表文件的特點倒排表文件的特點 優(yōu)點優(yōu)點檢索速度快，插入和刪除操作比多重表文件簡單。檢索速度快，插入和刪除操作比多重表文件簡單。當(dāng)插入一個記錄時，只要將記錄存入數(shù)據(jù)文件，并當(dāng)插入一個記錄時，只要將記錄存入數(shù)據(jù)文件

39、，并將其存儲地址加入各倒排表中；刪除也很方便。將其存儲地址加入各倒排表中；刪除也很方便。 缺點缺點倒排表維護(hù)比較困難。在同一索引表中，不同關(guān)鍵倒排表維護(hù)比較困難。在同一索引表中，不同關(guān)鍵字值的記錄數(shù)目不同，同一倒排表中的各項長度不字值的記錄數(shù)目不同，同一倒排表中的各項長度不等。等。11. 3 外部排序外部排序 當(dāng)對數(shù)據(jù)記錄量巨大的數(shù)據(jù)文件進(jìn)行排序時，由于受當(dāng)對數(shù)據(jù)記錄量巨大的數(shù)據(jù)文件進(jìn)行排序時，由于受到內(nèi)存容量的限制，無法將所有數(shù)據(jù)記錄一次全部讀入到內(nèi)存容量的限制，無法將所有數(shù)據(jù)記錄一次全部讀入到內(nèi)存進(jìn)行。排序過程中需要多次進(jìn)行內(nèi)、外存之間的到內(nèi)存進(jìn)行。排序過程中需要多次進(jìn)行內(nèi)、外存之間的數(shù)據(jù)

40、交換。數(shù)據(jù)交換。利用外存對數(shù)據(jù)文件進(jìn)行排序利用外存對數(shù)據(jù)文件進(jìn)行排序稱為稱為外部排外部排序序。11.3.1 外部排序方法外部排序方法 外部排序最基本的方法是外部排序最基本的方法是歸并歸并。這種方法是由兩個。這種方法是由兩個相對獨立的階段組成：相對獨立的階段組成： 按內(nèi)存按內(nèi)存(緩沖區(qū)緩沖區(qū))的大小，將的大小，將n個記錄的數(shù)據(jù)文件分個記錄的數(shù)據(jù)文件分成若干個長度為成若干個長度為l的段或子文件，依次讀入內(nèi)存并選的段或子文件，依次讀入內(nèi)存并選擇有效的內(nèi)部排序方法進(jìn)行排序；然后將排好序的擇有效的內(nèi)部排序方法進(jìn)行排序；然后將排好序的有序子文件重新寫入到外存。子文件稱為有序子文件重新寫入到外存。子文件稱為歸并段歸并段或或順串順串。 采用歸并的辦法對采用歸并的辦法對歸并段歸并段進(jìn)行逐趟歸并，使進(jìn)行逐