文件與外排序課件

文件與外排序10.1文件10.2外排序

10.1.1

外存信息的存取

10.1.2文件的基本概念

10.1.3順序文件10.1.5索引順序文件10.1.6直接存取文件10.1.7多關鍵字文件10.1文件10.1.4索引文件一、文件與記錄文件即為記錄的集合，和“查找表”的差別在于，“文件”指的是存儲在外存儲器中的記錄的集合。

“記錄”是文件中可以存取的數據的基本單位。10.1.2

文件的基本概念

二、文件可按其中記錄的類型不同而分成兩類：

其一為操作系統(tǒng)的文件。文件中的記錄僅是一個字符組。由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，為了用戶存取和加工的方便，將文件中的信息劃分為若干組，其中每一組信息稱作一個記錄；10.1.2

文件的基本概念

其二為數據庫文件。文件中的記錄帶有結構，是數據項的集合。記錄是文件中可以存取的數據基本單位，數據項是文件中可以使用的數據最小單位10.1.2

文件的基本概念

三、關鍵字

記錄中能識別不同記錄的數據項被稱為關鍵字。

若該數據項能唯一識別一個記錄，則稱為主關鍵字，若能識別多個記錄則稱為次關鍵字。10.1.2

文件的基本概念

四、文件的邏輯結構與物理結構

文件的邏輯結構指的是呈現在用戶面前的文件中記錄之間的邏輯關系；

文件的物理結構指的是文件中的邏輯記錄在存儲器中的組織方式。10.1.2

文件的基本概念

五、文件的操作檢索修改排序10.1.2

文件的基本概念

結構特點：

記錄在文件中的排列順序是由記錄進入存儲介質的次序決定的。

即文件物理結構中記錄的排列順序和文件的邏輯結構中記錄的排列順序一致。10.1.3順序文件

順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由指針相鏈.連續(xù)文件：

次序相繼的兩個物理記錄其存儲位置相鄰;10.1.3順序文件操作特點：1．便于進行順序存?。?．不便于進行直接存取，為取第i個記錄，必須先讀出前i-1個記錄，對于磁盤上的等長記錄的連續(xù)文件可以進行折半查找；10.1.3順序文件3．插入新的記錄只能加在文件的末尾；4．刪除記錄時，只作標記；5．更新記錄必須生成新的文件。10.1.3順序文件

順序文件的插入、刪除和更新操作在多數情況下都采用批處理方式。此時，為處理方便，通常將順序文件作成有序文件，稱作“主文件”，同時將所有的操作做成一個“事務文件”（經過排序也成為有序文件）。所謂“批處理”，就是將這兩個文件“合”為一個新的主文件。具體操作相當于“歸并兩個有序表”。10.1.3順序文件（1）對于事務文件中的每個操作首先要判別其“合法性”；（2）事務文件中可能存在多個操作是對主文件中同一個記錄進行的。但有兩點不同：10.1.3順序文件一、結構特點1．索引文件由“主文件”和多級“索引”組成。2．索引中的每個記錄由“關鍵字”和“指針”組成。3．通常，索引文件中的主文件是無序文件，索引是（按關鍵字有序）的有序文件。4．“索引”是在輸入數據建立文件時自動生成。初建時的“靜態(tài)索引”為無序文件，經過排序后成為有序文件。10.1.4索引文件二、操作的特點１．檢索方式為：直接存取和按關鍵字存取。“按關鍵字檢索”將分兩步進行：先查索引，然后根據索引中指針所指索取記錄。２．插入記錄時，“記錄”插入在主文件的末尾，而相應的“索引項”必須插入在索引的合適位置上。因此，最好在建索引表時留有一定“空位”。10.1.4索引文件３．刪除記錄時，僅需刪除索引表中相應的索引項即可。４．更新記錄時，應將更新后的記錄插入在主文件的末尾，同時修改相應的索引項。10.1.4索引文件１．多級靜態(tài)索引10.1.4索引文件

主文件

索引表

查找表

第二查找表

第三查找表…...…...…...…...此時的索引文件結構：對主文件中每個記錄建立一個索引項：

主關鍵字

記錄在主文件中的存儲位置稱作稠密索引，由這些索引項構成索引表；１．多級靜態(tài)索引

從索引表建立的索引稱查找表，其中每個索引項為：

最大關鍵字

其所在數據塊的存儲位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。１．多級靜態(tài)索引10.1.4索引文件２．動態(tài)索引索引表采用查找樹表或哈希表。

優(yōu)點：

1.不需要建立多級索引;2.初建索引不需要進行排序;3.插入或刪除記錄時，修改索引方便;２．動態(tài)索引

用查找樹表作索引時，查找索引所需訪問外存次數的最大值恰為查找樹的深度。

稠密索引的優(yōu)點是，可以實現“預查找”；缺點是，索引表占用的存儲空間大。

可以作索引的樹表有：二叉排序樹、B-樹和鍵樹。２．動態(tài)索引

主文件按主關鍵字有序，對一組記錄建立一個索引項，即建立非稠密索引。結構特點：10.1.5索引順序文件一、ISAM文件

ISAM(Index

SequentialAccessMethod)

（索引順序存取方法）是一種專為磁盤存取設計的文件組織方法。有兩種典型的索引順序文件:10.1.5索引順序文件１．文件的組織方式：

主文件按柱面集中存放，同時建立

三級索引：磁道索引、柱面索引和主索引。

關鍵字

指針

關鍵字

指針

磁道索引結構基本索引項溢出索引項一、ISAM文件2101024主索引

r(14)r(21)r(38)r(41)r(57)r(63)r(72)r(85)r(99)

溢出區(qū)

磁道索引

r(514)……

溢出區(qū)

磁道索引……r(1024)一個柱面

….柱面索引992101024T0T1T2T3T4T5２．操作的特點：檢索插入刪除一、ISAM文件檢索----

可有兩種方式：按關鍵字存取

—

從主索引開始,到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。順序存取

—

依關鍵字最小至大順序存取。一、ISAM文件插入:

修改本磁道的索引項(包括基本索引項和溢出索引項)。

將該磁道上關鍵字最大的記錄移出到本柱面的溢出區(qū)中;

將記錄插入在某個磁道的合適位置上;一、ISAM文件刪除:

在被刪記錄當前存儲位置上作“刪除標記”。一、ISAM文件３．文件重組

在經過多次的插入和刪除操作之后，大量的記錄進入文件的“溢出區(qū)”,而“基本存儲區(qū)”中出現很多已被刪去的記錄空間，此時的文件結構很不合理。因此，對ISAM

文件，需要周期地進行重整。一、ISAM文件４．柱面索引的位置

ISAM文件占有多個柱面，其柱面索引本身占有一個柱面，為使“磁頭”的平均移動距離最小，柱面索引應設在數據文件所占全部柱面的中間位置上。一、ISAM文件二、VSAM文件

VSAM(Vistual

StorageAccessMethod)

文件是利用操作系統(tǒng)中提供的虛擬存儲器的功能組織的文件；免除了用戶為讀/寫記錄時直接對外存進行的操作。

對用戶而言，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位?！?...........

索引集B+樹順序集控制區(qū)域控制區(qū)間數據集1.文件的結構控制區(qū)間是用戶進行一次存取的邏輯單位，可看成是一個邏輯磁道。但它的實際大小和物理磁道無關。

VSAM

文件初建時，每個控制區(qū)間內的記錄數不足額定數，并且有的控制區(qū)間內的記錄數為零。

控制區(qū)域由若干控制區(qū)間和它們的索引項組成，可看成是一個邏輯柱面.二、VSAM文件３．順序集

本身是一個單鏈表，它包含文件的全部索引項，同時，順序集中的每個結點即為B+樹的葉子結點.

索引集中的結點即為B+樹的非葉結點.二、VSAM文件４．文件的操作檢索：可進行順序存取和按關鍵字存取;插入：按關鍵字大小插入在某個適當的控制區(qū)間中，當控制區(qū)間中的記錄數超過文件規(guī)定的大小時，要“分裂”控制區(qū)間，必要時，還需要“分裂”控制區(qū)域;刪除：必須“真實地”刪除記錄，因此要在控制區(qū)間內“移動”記錄;二、VSAM文件５．VSAM文件通常被作為大型索引順序文件的標準組織方式。其缺點是：占有較多的存儲空間，一般只能保持約75%

的存儲空間利用率。因此，一般情況下，極少產生需要分裂控制區(qū)域的情況。其優(yōu)點是：動態(tài)地分配和釋放空間,不需要重組文件；能較快地實現對“后插入”

的記錄的檢索;二、VSAM文件１．直接存取文件的特點和前幾節(jié)討論的文件組織方法不同，直接存取文件的特點是，由記錄的關鍵字“直接”得到記錄在外存上的映象地址。

類似于哈希表的構造方法，根據文件中關鍵字的特點設計一種“哈希函數”和“處理沖突的方法”將記錄散列到外存儲設備上，又稱“散列文件”。10.1.6直接存取文件２．哈希文件的結構

由于記錄在外存上是成組存放的，因此允許多個記錄映象到同一個地址上。在此，稱外存儲器中存放多個記錄的“數據塊”為“桶”。因此由哈希函數得到的映象地址為“桶地址”。10.1.6直接存取文件例如：有一組關鍵字如下：

{589，063，269，505，764，182，166，330}假設哈希函數為keyMOD7，每個桶可以容納3個記錄（稱桶的容量為3），則哈希文件如下:基桶063182589505764269166330溢出桶

在哈希文件中，“沖突”和“溢出”是不同的概念。一般情況下，假設桶的大小為m，則允許哈希地址產生m-1次的沖突，當發(fā)生第m次沖突時，才需要進行“沖突處理”。對散列文件而言，通常采用鏈地址法出路沖突。為區(qū)別起見，稱直接“散列”的數據塊為“基桶”，而因“溢出”存放的數據塊為“溢出桶”.10.1.6直接存取文件３．文件的操作檢索：只能進行按關鍵字的查找，不能進行順序查找。檢索時，先在基桶內進行查找，若不存在，則再到溢出桶中進行查找。插入：當查找不成功時，將記錄插入在相應的基桶或溢出桶內。刪除：對被刪記錄作特殊標記。10.1.6直接存取文件４．哈希文件分析

優(yōu)點：記錄隨機存放，不需要進行排序；插入、刪除方便，存取速度快；節(jié)省存儲空間，不需要索引區(qū)。

缺點：不能進行順序存??；在經過多次插入和刪除操作之后，需進行“重組文件”

的操作。10.1.6直接存取文件一、多關鍵字文件的特點

除需要對主關鍵字建立“主索引”外，尚需對各個次關鍵字建立“次索引”。次索引項：次關鍵字（指向記錄的）指針10.1.7多關鍵字文件二、次索引的組織方法1．多重鏈表文件

特點：將所有具有相同次關鍵字的記錄鏈接在同一鏈表中，該鏈表的頭指針即為次索引項中“指針域”的值。10.1.7多關鍵字文件2.倒排文件特點：將所有具有相同次關鍵字的記錄構成一個次索引順序表，此時的次索引順序表中僅存放記錄的“主關鍵字”或記錄的“物理記錄號”。次索引項中的“指針”指向相應的次索引順序表。10.1.7多關鍵字文件3．次關鍵字索引表本身的結構可以是順序表，也可以是樹表或哈希表，視具體的次關鍵字的特性而定。

10.1.7多關鍵字文件10.2.1外排序的方法

10.2.2

多路平衡歸并及實現

10.2.3置換－選擇排序

10.2.4最佳歸并樹

10.2外排序外排序指的是大文件的排序。排序前不可能將全部數據讀入內存，在排序過程中還需要進行多次的內、外存之間的交換。這種內外存并用的排序方法稱為外排序。10.2.1外排序的方法

最常用的外排序方法是歸并排序法。這種方法由兩個階段組成：

第1階段是把文件逐段輸入到內存，用有效的內排序方法對文件的各個段進行排序，經排序的文件段稱為順串（或歸并段），當它們生成后立即寫到外存上，這樣在外存上就形成了許多初始順串；10.2.1外排序的方法

第2階段是對這些順串用某種歸并方法（如2-路歸并）進行多趟歸并，使順串的長度逐漸由小至大，直至變成一個順串，即整個文件有序為止。10.2.1外排序的方法

2-路歸并過程示意R1R2R3R4R5R6R1’R2’R3’第1趟R1’’第2趟R1’’’第3趟10.2.2

多路平衡歸并及實現

為了減少歸并的趟數，可采用多路歸并。

3-路歸并過程示意R1R2R3R4R5R6R1’R2’第1趟R1’’第2趟在k路歸并中，為了確定下一個要輸出的記錄，就需要在k個記錄中尋找關鍵字值最小的那個記錄，這要比2-路歸并復雜些。為了減少這個代價，我們可采用選擇樹的方法來實現