01數(shù)據(jù)結(jié)構(gòu)講義09第12章文件組織

1、1 物料管理物料管理File1Algorithms and DataStructures:files1、基本概念、基本概念2、順序文件、順序文件3、索引文件、索引文件4、ISAM文件和文件和VSAM文件文件5、直接存取文件、直接存取文件6、多關(guān)鍵字文件、多關(guān)鍵字文件目錄目錄第第 12 章章 文文 件件2 物料管理物料管理File2Algorithms and DataStructures:files1、基本概念、基本概念1、常用外存：、常用外存： 磁帶：由磁帶介質(zhì)、讀、寫磁頭、驅(qū)動(dòng)器、接收盤和原始盤組成。磁帶：由磁帶介質(zhì)、讀、寫磁頭、驅(qū)動(dòng)器、接收盤和原始盤組成。 便宜、可反復(fù)使用、是一種順序存

2、取設(shè)備。查找費(fèi)時(shí)、速度慢（尤其是查找末便宜、可反復(fù)使用、是一種順序存取設(shè)備。查找費(fèi)時(shí)、速度慢（尤其是查找末 端記錄時(shí)）。端記錄時(shí)）。.讀讀出出頭頭寫寫入入頭頭原原始始盤盤接接收收盤盤IBG（Inter Block Gap）塊間塊間間隙間隙塊塊 1塊塊 3塊塊 2帶文件的讀寫帶文件的讀寫時(shí)間：時(shí)間：T i/o = ta + n tw ta ：延遲時(shí)間：延遲時(shí)間 tw：傳輸時(shí)間：傳輸時(shí)間/ 字符字符 n 字符字符數(shù)。數(shù)。3 物料管理物料管理File3Algorithms and DataStructures:files1、基本概念、基本概念 磁盤：由存取裝置、讀、寫磁頭、活動(dòng)臂、盤片（磁道、扇區(qū)）

3、、旋轉(zhuǎn)主軸構(gòu)成。磁盤：由存取裝置、讀、寫磁頭、活動(dòng)臂、盤片（磁道、扇區(qū)）、旋轉(zhuǎn)主軸構(gòu)成。 速度快、容量大、直接存取設(shè)備。速度快、容量大、直接存取設(shè)備。 種類：固定頭磁盤、活動(dòng)頭磁盤種類：固定頭磁盤、活動(dòng)頭磁盤 固定頭磁盤：每個(gè)磁道都有一個(gè)磁頭（速度快）固定頭磁盤：每個(gè)磁道都有一個(gè)磁頭（速度快） 活動(dòng)頭磁盤：每個(gè)盤面共用一個(gè)磁頭，活動(dòng)頭磁盤：每個(gè)盤面共用一個(gè)磁頭， 增加了找道的時(shí)間，應(yīng)用廣泛。增加了找道的時(shí)間，應(yīng)用廣泛。 柱面：各盤面的直徑相同的磁道的總和。柱面：各盤面的直徑相同的磁道的總和。 物理位置：盤組號(hào)、物理位置：盤組號(hào)、 柱面號(hào)、柱面號(hào)、 磁道號(hào)、磁道號(hào)、 塊（扇區(qū)號(hào)）塊（扇區(qū)號(hào)） 盤

4、文件的讀寫時(shí)間：盤文件的讀寫時(shí)間：T i/o = tseck + tla + ntwm tseck ：找道時(shí)間：找道時(shí)間tla ：等待時(shí)間：等待時(shí)間twm ：傳輸時(shí)間：傳輸時(shí)間/ 字符，字符，n 字符數(shù)。字符數(shù)。4 物料管理物料管理File4Algorithms and DataStructures:files1、基本概念、基本概念 數(shù)據(jù)域（數(shù)據(jù)場(chǎng)）：記錄中的每個(gè)數(shù)據(jù)項(xiàng)，稱之為域或場(chǎng)（數(shù)據(jù)域（數(shù)據(jù)場(chǎng)）：記錄中的每個(gè)數(shù)據(jù)項(xiàng)，稱之為域或場(chǎng)（Field） 關(guān)鍵字：唯一標(biāo)識(shí)記錄的域，稱之為關(guān)鍵字。輔助關(guān)鍵字，稱之為次關(guān)鍵字。關(guān)鍵字：唯一標(biāo)識(shí)記錄的域，稱之為關(guān)鍵字。輔助關(guān)鍵字，稱之為次關(guān)鍵字。 記錄（記

5、錄（Record）：）：若干相關(guān)的若干相關(guān)的數(shù)據(jù)項(xiàng)的集合。如果存之于外存，則叫做記錄。數(shù)據(jù)項(xiàng)的集合。如果存之于外存，則叫做記錄。 文件：記錄的集合。文件：記錄的集合。 記錄的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)：記錄的物理結(jié)構(gòu)和邏輯結(jié)構(gòu)： 邏輯結(jié)構(gòu)：記錄在用戶或程序員面前呈現(xiàn)的形式。邏輯結(jié)構(gòu)：記錄在用戶或程序員面前呈現(xiàn)的形式。 物理結(jié)構(gòu)：記錄在在物理存儲(chǔ)器上的存儲(chǔ)方式，是數(shù)據(jù)的物理表示和組織。物理結(jié)構(gòu)：記錄在在物理存儲(chǔ)器上的存儲(chǔ)方式，是數(shù)據(jù)的物理表示和組織。 物理記錄和邏輯記錄：物理記錄和邏輯記錄： 物理記錄：計(jì)算機(jī)用一條物理記錄：計(jì)算機(jī)用一條 I/O 指令進(jìn)行讀寫外存的基本單位。通常，對(duì)一定指令進(jìn)行讀寫外存的

6、基本單位。通常，對(duì)一定 的設(shè)備和操作系統(tǒng)，大小是固定不變的。的設(shè)備和操作系統(tǒng)，大小是固定不變的。 邏輯記錄：程序員加以定義，用戶要求使用的。邏輯記錄：程序員加以定義，用戶要求使用的。 關(guān)系：關(guān)系： 物理記錄物理記錄 - 邏輯記錄邏輯記錄2、基本術(shù)語：、基本術(shù)語：5 物料管理物料管理File5Algorithms and DataStructures:files1、基本概念、基本概念記錄記錄B記錄記錄C記錄記錄D記錄記錄A記錄記錄A記錄記錄B記錄記錄C6 物料管理物料管理File6Algorithms and DataStructures:files1、基本概念、基本概念 檢索：檢索： 順序存取

7、：存取下一個(gè)邏輯記錄順序存取：存取下一個(gè)邏輯記錄 直接存?。捍嫒〉谥苯哟嫒。捍嫒〉?i 個(gè)邏輯記錄個(gè)邏輯記錄 按關(guān)鍵字值存取相應(yīng)的記錄：按關(guān)鍵字值存取相應(yīng)的記錄：簡(jiǎn)單詢問：查單個(gè)記錄簡(jiǎn)單詢問：查單個(gè)記錄區(qū)域詢問：查多個(gè)記錄區(qū)域詢問：查多個(gè)記錄函數(shù)詢問：滿足某種條件的記錄函數(shù)詢問：滿足某種條件的記錄布爾詢問：滿足布爾運(yùn)算組合的詢問布爾詢問：滿足布爾運(yùn)算組合的詢問 修改：插入、修改、更新修改：插入、修改、更新 更新方式：實(shí)時(shí)、批量?jī)煞N方式更新方式：實(shí)時(shí)、批量?jī)煞N方式3、檢索和修改、檢索和修改7 物料管理物料管理File7Algorithms and DataStructures:files2、順序

8、文件、順序文件n順序文件的特點(diǎn)：順序文件的特點(diǎn)：在順序文件中，所有邏輯記錄在存儲(chǔ)介質(zhì)中的實(shí)際順序與它們?cè)陧樞蛭募校羞壿嬘涗浽诖鎯?chǔ)介質(zhì)中的實(shí)際順序與它們進(jìn)入存儲(chǔ)器的順序一致。進(jìn)入存儲(chǔ)器的順序一致。順序文件的主要優(yōu)點(diǎn)是順序存取速度塊，適宜于順序存取和成順序文件的主要優(yōu)點(diǎn)是順序存取速度塊，適宜于順序存取和成批處理。批處理。順序文件的缺點(diǎn)是不利于修改。順序文件的缺點(diǎn)是不利于修改。順序文件特別適應(yīng)于磁帶存儲(chǔ)器，也適應(yīng)于磁盤存儲(chǔ)。順序文件特別適應(yīng)于磁帶存儲(chǔ)器，也適應(yīng)于磁盤存儲(chǔ)。提示：順序文件是指按記錄寫入文件的先后順序存放、提示：順序文件是指按記錄寫入文件的先后順序存放、其邏輯順序和物理順序一致的文

9、件。順序文件可分為順其邏輯順序和物理順序一致的文件。順序文件可分為順序有序文件和順序無序文件兩種。序有序文件和順序無序文件兩種。8 物料管理物料管理File8Algorithms and DataStructures:files2、順序文件、順序文件 順序存取是指按記錄的邏輯(或物理)順序?qū)崿F(xiàn)逐個(gè)存取，若要查詢第i個(gè)記錄則必須先檢索前 i1 個(gè)記錄；插入新的記錄只能加在文件的末尾；更新某個(gè)記錄必須對(duì)整個(gè)文件進(jìn)行復(fù)制。順序文件的修改操作是按批處理的方式進(jìn)行的。批處理的工作原理如下進(jìn)行：稱待修改的原始文件為主文件，文件中記錄按關(guān)鍵碼有序；所有的修改請(qǐng)求依請(qǐng)求的先后次序生成一個(gè)事務(wù)文件，在進(jìn)行批處理

10、之前首先對(duì)事務(wù)文件進(jìn)行排序，然后和主文件歸并得到一個(gè)新的主文件，如右圖所示。9 物料管理物料管理File9Algorithms and DataStructures:files3、索引文件和多關(guān)鍵字文件、索引文件和多關(guān)鍵字文件n 一、索引文件n索引文件：是索引方法與鏈接方法相結(jié)合的一種組織方式，它包括數(shù)據(jù)文件和索引表n數(shù)據(jù)文件：記錄結(jié)構(gòu)為n索引表：按關(guān)鍵字范圍建立的分段索引，結(jié)點(diǎn)結(jié)構(gòu)為n ，其中關(guān)鍵字是該范圍內(nèi)最大關(guān)鍵字的值，指針是最小關(guān)鍵字的始地址數(shù)據(jù) 指針關(guān)鍵字 指針10 物料管理物料管理File10Algorithms and DataStructures:files3、索引文件和多關(guān)鍵

11、字文件、索引文件和多關(guān)鍵字文件 職職 工號(hào)工號(hào)姓姓 名名職職 務(wù)務(wù)性性 別別工工 資資指指 針針10029王王 平平講講 師師男男50510410105李李 林林教教 授授女女87010610202魏魏 黎黎講講 師師男男49710110338徐徐 萍萍助助 教教女女38110510431李李 新新教教 授授男男119010910543孫孫 玉玉講講 師師男男51310710617郭郭 燕燕講講 師師女女52210810746朱朱 文文助助 教教女女39710823張張 萌萌教教 授授男男93010010935常常 平平講講 師師女女505103以這個(gè)數(shù)據(jù)文件為例以這個(gè)數(shù)據(jù)文件為例11 物料管

12、理物料管理File11Algorithms and DataStructures:files3、索引文件和多關(guān)鍵字文件、索引文件和多關(guān)鍵字文件 索引表是對(duì)該數(shù)據(jù)文件按索引表是對(duì)該數(shù)據(jù)文件按0019，2039，4059建立的分段索建立的分段索引引02關(guān)鍵字指針1939591021081050517 2329313538 4346 12 物料管理物料管理File12Algorithms and DataStructures:files3、索引文件和多關(guān)鍵字文件、索引文件和多關(guān)鍵字文件n在索引鏈接文件中查找關(guān)鍵字為k的記錄方法：n 在索引表中確定待查記錄所在的索引段。n 順著該段的鏈查找待查記錄。n

13、例如查找的主關(guān)鍵字為3102關(guān)鍵字指針1939591021081050517 2329313538 4346 1931 柱面索引柱面索引 磁道索引磁道索引 磁道的第一個(gè)記錄磁道的第一個(gè)記錄 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出記錄出記錄 2、3 磁道的磁道索引項(xiàng)磁道的磁道索引項(xiàng)50 T2 1 R60 R70 R80 R85 R9090 T3 1 插入：插入： R14、R21、R43、R47、R50進(jìn)入進(jìn)入 2 磁道；磁道；R60、R70、R80、R85、R90進(jìn)入進(jìn)入3磁道磁道R14 R21 R43 R47 R5018 道道 注意：基本區(qū)：采用順序

14、結(jié)構(gòu)。注意：基本區(qū)：采用順序結(jié)構(gòu)。 溢出區(qū)：采用鏈接結(jié)構(gòu)。溢出區(qū)：采用鏈接結(jié)構(gòu)。26 物料管理物料管理File26Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一個(gè)記錄磁道的第一個(gè)記錄 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出記錄出記錄 2、3 磁道的磁道索引項(xiàng)磁道的磁道索引項(xiàng)47 T2 1 50 T19 1 R60 R70 R80 R85 R9090 T3 1 插入：插入： R30 進(jìn)入進(jìn)入 2 磁道之后。磁道之后

15、。R14 R21 R30 R43 R47R50 27 物料管理物料管理File27Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一個(gè)記錄磁道的第一個(gè)記錄 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出記錄出記錄 2、3 磁道的磁道索引項(xiàng)磁道的磁道索引項(xiàng)47 T2 1 50 T19 1 R60 R65 R70 R80 R85 85 T3 1 90 T19 2 插入：插入： R65 進(jìn)入進(jìn)入 3 磁道之后。磁道之后。R14 R

16、21 R30 R43 R47R50 R90 28 物料管理物料管理File28Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 查找：主索引查找：主索引 柱面索引柱面索引 磁道索引磁道索引 磁道的第一個(gè)記錄磁道的第一個(gè)記錄 柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出記錄出記錄 2、3 磁道的磁道索引項(xiàng)磁道的磁道索引項(xiàng)47 T2 1 50 T19 3 R60 R65 R70 R80 R85 85 T3 1 90 T19 2 插入：插入： R48 進(jìn)入進(jìn)入 2 磁道之后。因磁道之后。因 48 4

17、7 , 只能進(jìn)入本道溢出區(qū)。若同時(shí)插入多個(gè)記錄進(jìn)入只能進(jìn)入本道溢出區(qū)。若同時(shí)插入多個(gè)記錄進(jìn)入 溢出區(qū)，注意排成遞減序進(jìn)入溢出區(qū)。溢出區(qū)，注意排成遞減序進(jìn)入溢出區(qū)。R14 R21 R30 R43 R47R50 R90 R4829 物料管理物料管理File29Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件柱面柱面 C1磁道索引磁道索引 1 道道2 道道3 道道19和和20道存溢道存溢出記錄出記錄 2、3 磁道的磁道索引項(xiàng)磁道的磁道索引項(xiàng)47 T2 1 50 T19 3 R60 R65 R70 R80 R85 85 T3 1 90 T

18、19 2 刪除：刪除： 給被刪除記錄作一標(biāo)記。優(yōu)點(diǎn)：不必移動(dòng)記錄變更指針。缺點(diǎn)：周期性整理給被刪除記錄作一標(biāo)記。優(yōu)點(diǎn)：不必移動(dòng)記錄變更指針。缺點(diǎn)：周期性整理 ISAM 文文 件。如刪除件。如刪除 R21。R14 R21 R30 R43 R47R50 R90 R4830 物料管理物料管理File30Algorithms and DataStructures:files 定義：定義： m 階階 B+ 樹滿足或空，或：樹滿足或空，或：A、根結(jié)點(diǎn)要么是葉子，要么至少有兩個(gè)兒子根結(jié)點(diǎn)要么是葉子，要么至少有兩個(gè)兒子B、除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)為除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)為

19、: m/2 = s - 控制區(qū)間控制區(qū)間36 物料管理物料管理File36Algorithms and DataStructures:files4、 ISAM文件和文件和VSAM文件文件 為什么稱之為為什么稱之為 VSAM 文件文件：虛擬存儲(chǔ)，同機(jī)器、設(shè)備無關(guān)。：虛擬存儲(chǔ)，同機(jī)器、設(shè)備無關(guān)。分頁格式化磁盤組分頁格式化磁盤組頁面號(hào)頁面號(hào)指針指針外部頁面映射表外部頁面映射表123 分頁：把內(nèi)外存按同樣的大小進(jìn)行分頁。使文件技術(shù)不依賴于具體的外部設(shè)備。更換分頁：把內(nèi)外存按同樣的大小進(jìn)行分頁。使文件技術(shù)不依賴于具體的外部設(shè)備。更換外設(shè)時(shí)，不必改變整個(gè)程序，只需改變外部頁面映射表中的相對(duì)地址到絕對(duì)地址的

20、計(jì)算外設(shè)時(shí)，不必改變整個(gè)程序，只需改變外部頁面映射表中的相對(duì)地址到絕對(duì)地址的計(jì)算程序即可。程序即可。 控制區(qū)間控制區(qū)間 若干頁面。控制面若干頁面。控制面 若干控制區(qū)間。外存是內(nèi)存的延伸，虛擬若干控制區(qū)間。外存是內(nèi)存的延伸，虛擬 存儲(chǔ)器。存儲(chǔ)器。VSAM 可脫離具體的外存組織文件，所以稱之為可脫離具體的外存組織文件，所以稱之為 VSAM 文件。文件。37 物料管理物料管理File37Algorithms and DataStructures:files5、直接存取文件、直接存取文件(散列文件散列文件) 散列文件又稱直接存取文件，其特點(diǎn)是，由記錄的關(guān)鍵碼“直接”得到記錄在外存（磁盤）上的映象地址。

21、類似于構(gòu)造一個(gè)哈希表，根據(jù)文件中關(guān)鍵碼的特點(diǎn)設(shè)計(jì)一種“哈希函數(shù)”和“處理沖突的方法”，然后將記錄散列到外存儲(chǔ)設(shè)備上，故稱“散列文件”。散列文件由若干個(gè)“桶”組成，根據(jù)設(shè)定的哈希函數(shù)將記錄“映象”到某個(gè)桶號(hào)。處理沖突通常采用鏈地址法，即每個(gè)桶可以包括一個(gè)或幾個(gè)頁塊，頁塊之間以指針相鏈。每個(gè)頁塊中的記錄個(gè)數(shù)則由邏輯記錄和物理記錄的大小決定。38 物料管理物料管理File38Algorithms and DataStructures:files5、直接存取文件、直接存取文件(散列文件散列文件)例如：假設(shè)有18個(gè)記錄，它們的關(guān)鍵碼分別為： 278, 109, 063, 930, 589, 182, 505, 269, 008, 083, 164, 215, 330,