數(shù)據(jù)結(jié)構(gòu)和算法分析第9講-文件課件

第九章文件數(shù)據(jù)結(jié)構(gòu)和算法分析第9講-文件課件9.1有關(guān)文件的基本概念9.2順序文件9.3索引文件9.4索引順序文件9.1有關(guān)文件的基本概念9.2順序文件99.1有關(guān)文件的基本概念9.1有關(guān)文件的基本概念一、文件即為記錄的集合，和“查找表”的差別在于，“文件”指的是存儲在外存儲器中的記錄的集合。

記錄是文件中可以存取的數(shù)據(jù)的

基本單位。一、文件即為記錄的集合，和“查找二、文件可按其中記錄的類型不同而分成兩類：其一為操作系統(tǒng)的文件，文件中的記錄僅是一個字符組。由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，為了用戶存取和加工的方便，將文件中的信息劃分為若干組，其中每一組信息稱作一個記錄；二、文件可按其中記錄的類型不同而其一為操作系統(tǒng)的文件，文件中其二為數(shù)據(jù)庫文件，文件中的記錄帶有結(jié)構(gòu)，是數(shù)據(jù)項(xiàng)的集合。記錄是文件中可以存取的數(shù)據(jù)基本單位，數(shù)據(jù)項(xiàng)是文件中可以使用的

數(shù)據(jù)最小單位。其二為數(shù)據(jù)庫文件，文件中的記錄帶三、記錄中能識別不同記錄的數(shù)據(jù)項(xiàng)被稱為關(guān)鍵字，若該數(shù)據(jù)項(xiàng)能唯一識別一個記錄，則稱為主關(guān)鍵字，若能識別多個記錄則稱為次關(guān)鍵字。三、記錄中能識別不同記錄的數(shù)據(jù)項(xiàng)四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用戶面前的文件中記錄之間的邏輯關(guān)系；文件的物理結(jié)構(gòu)指的是文件中的邏輯記錄在存儲器中的組織方式。四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用9.2順序文件9.2順序文件結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記錄進(jìn)入存儲介質(zhì)的次序決定的，即文件物理結(jié)構(gòu)中記錄的排列順序和文件的邏輯結(jié)構(gòu)中記錄的排列順序一致。結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由指針相鏈。連續(xù)文件：次序相繼的兩個物理記錄其存儲位置相鄰;順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由操作特點(diǎn)：1．便于進(jìn)行順序存取；2．不便于進(jìn)行直接存取，為取第i個記錄，必須先讀出前i-1個記錄，對于磁盤上的等長記錄的連續(xù)文件可以進(jìn)行折半查找；操作特點(diǎn)：1．便于進(jìn)行順序存取；3．插入新的記錄只能加在文件的末尾；4．刪除記錄時(shí)，只作標(biāo)記；5．更新記錄必須生成新的文件。

3．插入新的記錄只能加在文件的末尾；9.3索引文件9.3索引文件1．索引文件由“主文件”和多級“索引”組成；2．索引中的每個記錄由“關(guān)鍵字”和“指針”組成；3．通常，索引文件中的主文件是無序文件，索引是(按關(guān)鍵字有序的）有序文件；4．“索引”是在輸入數(shù)據(jù)建立文件時(shí)自動生成。1．索引文件由“主文件”和多級“索引”組成；多級靜態(tài)索引多級靜態(tài)索引１．多級靜態(tài)索引１．多級靜態(tài)索引主文件

索引表

查找表

第二查找表

第三查找表…...…...…...…...

此時(shí)的索引文件結(jié)構(gòu)：主文件索引對主文件中每個記錄建立一個索引項(xiàng)：

主關(guān)鍵字

記錄在主文件中的存儲位置稱作稠密索引，由這些索引項(xiàng)構(gòu)成索引表。對主文件中每個記錄建立一個索引項(xiàng)：主關(guān)鍵字記錄從索引表建立的索引稱查找表，其中每個索引項(xiàng)為：

最大關(guān)鍵字

其所在數(shù)據(jù)塊的存儲位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。從索引表建立的索引稱查找表，其中最大關(guān)鍵字其所在數(shù)據(jù)塊按關(guān)鍵字進(jìn)行檢索時(shí)，從第三查找表開始，至多訪問外存五次。按關(guān)鍵字進(jìn)行檢索時(shí)，從第三查找表9.4索引順序文件9.4索引順序文件主文件按主關(guān)鍵字有序，對一組記錄建立一個索引項(xiàng)(建立非稠密索引)。結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)：一、ISAM文件ISAM(IndexSequentialAccessMethod)(索引順序存取方法)是一種專為磁盤存取設(shè)計(jì)的文件組織方法。有兩種典型的索引順序文件：一、ISAM文件有兩種典型的索引順序文件：１．文件的組織方式：

主文件按柱面集中存放，同時(shí)建立三級索引：磁道索引、柱面索引和主索引。關(guān)鍵字

指針

關(guān)鍵字

指針

磁道索引結(jié)構(gòu)基本索引項(xiàng)溢出索引項(xiàng)１．文件的組織方式：主文件按柱面集中存放，同時(shí)建立磁道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)一個柱面

….柱面索引992101024T0T1T2T3T4T52101024主r(14)r(21)r(38)溢２．操作的特點(diǎn)：檢索插入刪除２．操作的特點(diǎn)：檢索插入刪除檢索：

可有兩種方式：

按關(guān)鍵字存取—從主索引開始,到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。順序存取—依關(guān)鍵字最小至大順序存取。檢索：按關(guān)鍵字存取—從主索引開始,到順序存取—依關(guān)鍵字最插入:

修改本磁道的索引項(xiàng)(包括基本索引項(xiàng)和溢出索引項(xiàng))。將該磁道上關(guān)鍵字最大的記錄移出到本柱面的溢出區(qū)中;

將記錄插入在某個磁道的合適位置上;插入:修改本磁道的索引項(xiàng)(包括基本索將該磁道上關(guān)鍵字最大的記刪除:在被刪記錄當(dāng)前存儲位置上作“刪除標(biāo)記”。刪除:在被刪記錄當(dāng)前存儲位置上二、VSAM文件VSAM(VistualStorageAccessMethod)

文件是利用操作系統(tǒng)中提供的虛擬存儲器的功能組織的文件，免除了用戶為讀/寫記錄時(shí)直接對外存進(jìn)行的操作，對用戶而言，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位。二、VSAM文件文件是利用操作系統(tǒng)中提供的虛擬存儲器的功能組…............

索引集B+樹順序集控制區(qū)域控制區(qū)間數(shù)據(jù)集1．文件的結(jié)構(gòu)…............索引集控制區(qū)2.控制區(qū)間是用戶進(jìn)行一次存取的邏輯單位，可看成是一個邏輯磁道。但它的實(shí)際大小和物理磁道無關(guān)。VSAM文件初建時(shí)，每個控制區(qū)間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的控制區(qū)間內(nèi)的記錄數(shù)為零。控制區(qū)域由若干控制區(qū)間和它們的索引項(xiàng)組成，可看成是一個邏輯柱面。VSAM文件初建時(shí)，每個控制區(qū)控３．順序集本身是一個單鏈表，它包含文件的全部索引項(xiàng)，同時(shí)，順序集中的每個結(jié)點(diǎn)即為B+樹的葉子結(jié)點(diǎn)，索引集中的結(jié)點(diǎn)即為B+樹的非葉結(jié)點(diǎn)。３．順序集本身是一個單鏈表，它４．文件的操作檢索：可進(jìn)行順序存取和按關(guān)鍵字存??；插入：按關(guān)鍵字大小插入在某個適當(dāng)?shù)目刂茀^(qū)間中，當(dāng)控制區(qū)間中的記錄數(shù)超過文件規(guī)定的大小時(shí)，要“分裂”控制區(qū)間，必要時(shí)，還需要“分裂”控制區(qū)域；刪除：必須“真實(shí)地”刪除記錄，因此要在控制區(qū)間內(nèi)“移動”記錄。４．文件的操作檢索：可進(jìn)行順序存取和按關(guān)鍵字存??；本章學(xué)習(xí)要求：熟悉各類文件的特點(diǎn)，構(gòu)造方法以及如何實(shí)現(xiàn)檢索，插入和刪除等操作。本章學(xué)習(xí)要求：第九章文件數(shù)據(jù)結(jié)構(gòu)和算法分析第9講-文件課件9.1有關(guān)文件的基本概念9.2順序文件9.3索引文件9.4索引順序文件9.1有關(guān)文件的基本概念9.2順序文件99.1有關(guān)文件的基本概念9.1有關(guān)文件的基本概念一、文件即為記錄的集合，和“查找表”的差別在于，“文件”指的是存儲在外存儲器中的記錄的集合。

記錄是文件中可以存取的數(shù)據(jù)的

基本單位。一、文件即為記錄的集合，和“查找二、文件可按其中記錄的類型不同而分成兩類：其一為操作系統(tǒng)的文件，文件中的記錄僅是一個字符組。由于操作系統(tǒng)中的文件僅是一維的連續(xù)字符序列，為了用戶存取和加工的方便，將文件中的信息劃分為若干組，其中每一組信息稱作一個記錄；二、文件可按其中記錄的類型不同而其一為操作系統(tǒng)的文件，文件中其二為數(shù)據(jù)庫文件，文件中的記錄帶有結(jié)構(gòu)，是數(shù)據(jù)項(xiàng)的集合。記錄是文件中可以存取的數(shù)據(jù)基本單位，數(shù)據(jù)項(xiàng)是文件中可以使用的

數(shù)據(jù)最小單位。其二為數(shù)據(jù)庫文件，文件中的記錄帶三、記錄中能識別不同記錄的數(shù)據(jù)項(xiàng)被稱為關(guān)鍵字，若該數(shù)據(jù)項(xiàng)能唯一識別一個記錄，則稱為主關(guān)鍵字，若能識別多個記錄則稱為次關(guān)鍵字。三、記錄中能識別不同記錄的數(shù)據(jù)項(xiàng)四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用戶面前的文件中記錄之間的邏輯關(guān)系；文件的物理結(jié)構(gòu)指的是文件中的邏輯記錄在存儲器中的組織方式。四、文件的邏輯結(jié)構(gòu)指的是呈現(xiàn)在用9.2順序文件9.2順序文件結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記錄進(jìn)入存儲介質(zhì)的次序決定的，即文件物理結(jié)構(gòu)中記錄的排列順序和文件的邏輯結(jié)構(gòu)中記錄的排列順序一致。結(jié)構(gòu)特點(diǎn)：記錄在文件中的排列順序是由記順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由指針相鏈。連續(xù)文件：次序相繼的兩個物理記錄其存儲位置相鄰;順序文件的具體組織形式有兩種：串聯(lián)文件：物理記錄之間的順序由操作特點(diǎn)：1．便于進(jìn)行順序存??；2．不便于進(jìn)行直接存取，為取第i個記錄，必須先讀出前i-1個記錄，對于磁盤上的等長記錄的連續(xù)文件可以進(jìn)行折半查找；操作特點(diǎn)：1．便于進(jìn)行順序存?。?．插入新的記錄只能加在文件的末尾；4．刪除記錄時(shí)，只作標(biāo)記；5．更新記錄必須生成新的文件。

3．插入新的記錄只能加在文件的末尾；9.3索引文件9.3索引文件1．索引文件由“主文件”和多級“索引”組成；2．索引中的每個記錄由“關(guān)鍵字”和“指針”組成；3．通常，索引文件中的主文件是無序文件，索引是(按關(guān)鍵字有序的）有序文件；4．“索引”是在輸入數(shù)據(jù)建立文件時(shí)自動生成。1．索引文件由“主文件”和多級“索引”組成；多級靜態(tài)索引多級靜態(tài)索引１．多級靜態(tài)索引１．多級靜態(tài)索引主文件

索引表

查找表

第二查找表

第三查找表…...…...…...…...

此時(shí)的索引文件結(jié)構(gòu)：主文件索引對主文件中每個記錄建立一個索引項(xiàng)：

主關(guān)鍵字

記錄在主文件中的存儲位置稱作稠密索引，由這些索引項(xiàng)構(gòu)成索引表。對主文件中每個記錄建立一個索引項(xiàng)：主關(guān)鍵字記錄從索引表建立的索引稱查找表，其中每個索引項(xiàng)為：

最大關(guān)鍵字

其所在數(shù)據(jù)塊的存儲位置稱這類索引為非稠密索引。類似地，由查找表建立的索引為第二查找表；由第二查找表建立的索引為第三查找表。從索引表建立的索引稱查找表，其中最大關(guān)鍵字其所在數(shù)據(jù)塊按關(guān)鍵字進(jìn)行檢索時(shí)，從第三查找表開始，至多訪問外存五次。按關(guān)鍵字進(jìn)行檢索時(shí)，從第三查找表9.4索引順序文件9.4索引順序文件主文件按主關(guān)鍵字有序，對一組記錄建立一個索引項(xiàng)(建立非稠密索引)。結(jié)構(gòu)特點(diǎn)：結(jié)構(gòu)特點(diǎn)：一、ISAM文件ISAM(IndexSequentialAccessMethod)(索引順序存取方法)是一種專為磁盤存取設(shè)計(jì)的文件組織方法。有兩種典型的索引順序文件：一、ISAM文件有兩種典型的索引順序文件：１．文件的組織方式：

主文件按柱面集中存放，同時(shí)建立三級索引：磁道索引、柱面索引和主索引。關(guān)鍵字

指針

關(guān)鍵字

指針

磁道索引結(jié)構(gòu)基本索引項(xiàng)溢出索引項(xiàng)１．文件的組織方式：主文件按柱面集中存放，同時(shí)建立磁道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)一個柱面

….柱面索引992101024T0T1T2T3T4T52101024主r(14)r(21)r(38)溢２．操作的特點(diǎn)：檢索插入刪除２．操作的特點(diǎn)：檢索插入刪除檢索：

可有兩種方式：

按關(guān)鍵字存取—從主索引開始,到柱面索引，到磁道索引，最后取得記錄，先后訪問四次外存。順序存取—依關(guān)鍵字最小至大順序存取。檢索：按關(guān)鍵字存取—從主索引開始,到順序存取—依關(guān)鍵字最插入:

修改本磁道的索引項(xiàng)(包括基本索引項(xiàng)和溢出索引項(xiàng))。將該磁道上關(guān)鍵字最大的記錄移出到本柱面的溢出區(qū)中;

將記錄插入在某個磁道的合適位置上;插入:修改本磁道的索引項(xiàng)(包括基本索將該磁道上關(guān)鍵字最大的記刪除:在被刪記錄當(dāng)前存儲位置上作“刪除標(biāo)記”。刪除:在被刪記錄當(dāng)前存儲位置上二、VSAM文件VSAM(VistualStorage