數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)12

1、Data StructureData StructurePage 12022-5-21q 學(xué)習(xí)目標(biāo)學(xué)習(xí)目標(biāo)v熟悉各類熟悉各類文件的特點(diǎn)文件的特點(diǎn)，構(gòu)造方法構(gòu)造方法以及如何以及如何實(shí)現(xiàn)檢索，插入和刪除實(shí)現(xiàn)檢索，插入和刪除等操作。等操作。q 重點(diǎn)和難點(diǎn)重點(diǎn)和難點(diǎn)v重點(diǎn)：重點(diǎn)：了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合了解各種文件的結(jié)構(gòu)特點(diǎn)及其適用場(chǎng)合。q 知識(shí)點(diǎn)知識(shí)點(diǎn)v順序文件、索引文件、索引順序文件、順序文件、索引文件、索引順序文件、VSAMVSAM文件、散列文件、多文件、散列文件、多關(guān)鍵字文件關(guān)鍵字文件 Data StructureData StructurePage 22022-5-2112.1 1

2、2.1 有關(guān)文件的基本概念有關(guān)文件的基本概念q 文件文件(File)(File)v是由大量性質(zhì)相同的記錄組成的集合，一般放在外存上。是由大量性質(zhì)相同的記錄組成的集合，一般放在外存上。q 記錄記錄v是數(shù)據(jù)項(xiàng)的集合，是可存取的數(shù)據(jù)的基本單位。是數(shù)據(jù)項(xiàng)的集合，是可存取的數(shù)據(jù)的基本單位。q 數(shù)據(jù)項(xiàng)數(shù)據(jù)項(xiàng)v由一個(gè)或多個(gè)位或字節(jié)組成，是不可分割的數(shù)據(jù)最小單位。由一個(gè)或多個(gè)位或字節(jié)組成，是不可分割的數(shù)據(jù)最小單位。q 定長(zhǎng)記錄文件定長(zhǎng)記錄文件v文件中每個(gè)記錄含有的信息長(zhǎng)度相等。文件中每個(gè)記錄含有的信息長(zhǎng)度相等。q 不定長(zhǎng)文件不定長(zhǎng)文件v文件中含有信息長(zhǎng)度不等的不定長(zhǎng)記錄。文件中含有信息長(zhǎng)度不等的不定長(zhǎng)記錄。D

3、ata StructureData StructurePage 32022-5-21q 單關(guān)鍵字文件單關(guān)鍵字文件v文件中的記錄只有一個(gè)唯一標(biāo)識(shí)記錄的主關(guān)鍵字。文件中的記錄只有一個(gè)唯一標(biāo)識(shí)記錄的主關(guān)鍵字。q 多關(guān)鍵字文件多關(guān)鍵字文件v文件中的記錄除了含有一個(gè)主關(guān)鍵字外，還含有若干個(gè)次關(guān)鍵字。文件中的記錄除了含有一個(gè)主關(guān)鍵字外，還含有若干個(gè)次關(guān)鍵字。q 記錄的屬性記錄的屬性v記錄中所有非關(guān)鍵字的數(shù)據(jù)項(xiàng)。記錄中所有非關(guān)鍵字的數(shù)據(jù)項(xiàng)。q 記錄的邏輯結(jié)構(gòu)記錄的邏輯結(jié)構(gòu)v記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對(duì)數(shù)據(jù)的表示和記錄在用戶或應(yīng)用程序員面前呈現(xiàn)的方式，是用戶對(duì)數(shù)據(jù)的表示和存取方式。存取方式。

4、q 記錄的物理結(jié)構(gòu)記錄的物理結(jié)構(gòu)v數(shù)據(jù)在物理存儲(chǔ)器上存儲(chǔ)的方式，是數(shù)據(jù)的物理表示和組織。數(shù)據(jù)在物理存儲(chǔ)器上存儲(chǔ)的方式，是數(shù)據(jù)的物理表示和組織。Data StructureData StructurePage 42022-5-21q 物理記錄物理記錄v計(jì)算機(jī)用一條計(jì)算機(jī)用一條I/0I/0命令進(jìn)行讀寫(xiě)的基本數(shù)據(jù)單位（物理塊）。命令進(jìn)行讀寫(xiě)的基本數(shù)據(jù)單位（物理塊）。v物理記錄和邏輯記錄之間可能存在下列三種關(guān)系：物理記錄和邏輯記錄之間可能存在下列三種關(guān)系：一個(gè)物理記錄存放一個(gè)邏輯記錄；一個(gè)物理記錄存放一個(gè)邏輯記錄；一個(gè)物理記錄包含多個(gè)邏輯記錄；一個(gè)物理記錄包含多個(gè)邏輯記錄；多個(gè)物理記錄表示一個(gè)邏輯記錄

5、。多個(gè)物理記錄表示一個(gè)邏輯記錄。q 文件的檢索方式文件的檢索方式v順序存取：存取下一個(gè)邏輯記錄。順序存取：存取下一個(gè)邏輯記錄。v直接存取；存取第直接存??；存取第i i個(gè)邏輯記錄。個(gè)邏輯記錄。v按關(guān)鍵字存?。喊搓P(guān)鍵字存取： 簡(jiǎn)單查詢、區(qū)域查詢、函數(shù)查詢、布爾查詢簡(jiǎn)單查詢、區(qū)域查詢、函數(shù)查詢、布爾查詢Data StructureData StructurePage 52022-5-21q 文件的修改文件的修改v記錄的插入、刪除、修改。記錄的插入、刪除、修改。q 文件的物理結(jié)構(gòu)文件的物理結(jié)構(gòu)v文件在外存上的組織方式。文件在外存上的組織方式。順序組織順序組織隨機(jī)組織隨機(jī)組織鏈組織鏈組織Data Str

6、uctureData StructurePage 62022-5-21q 順序文件順序文件v定義定義 記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的記錄按其在文件中的邏輯順序依次進(jìn)入存儲(chǔ)介質(zhì)而建立的，即，即物理記錄和邏輯記錄的順序是一致的。物理記錄和邏輯記錄的順序是一致的。v分類分類連續(xù)（順序）文件連續(xù)（順序）文件 次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置是相鄰的。次序相繼的兩個(gè)物理記錄在存儲(chǔ)介質(zhì)上的存儲(chǔ)位置是相鄰的。串聯(lián)（順序）文件串聯(lián)（順序）文件 物理記錄之間的次序由指針相鏈表示。物理記錄之間的次序由指針相鏈表示。Data StructureData StructurePage 7

7、2022-5-21v特點(diǎn)特點(diǎn)存取第存取第i i個(gè)記錄，必須先搜索在它之前的個(gè)記錄，必須先搜索在它之前的i-1i-1個(gè)記錄。個(gè)記錄。新的記錄只能加在文件末尾。新的記錄只能加在文件末尾。更新記錄，必須將整個(gè)文件復(fù)制。更新記錄，必須將整個(gè)文件復(fù)制。v優(yōu)點(diǎn)優(yōu)點(diǎn) 連續(xù)存取的速度快，主要用于只進(jìn)行順序存取、批量修改的情況。連續(xù)存取的速度快，主要用于只進(jìn)行順序存取、批量修改的情況。v存取設(shè)備存取設(shè)備磁帶磁帶 適合于文件的數(shù)據(jù)量大、平時(shí)記錄變化少、只作批量修改的情況。適合于文件的數(shù)據(jù)量大、平時(shí)記錄變化少、只作批量修改的情況。磁盤磁盤Data StructureData StructurePage 82022-

8、5-21q 引入原因引入原因v對(duì)于按關(guān)鍵字存取得記錄結(jié)構(gòu)，順序查找和折半查找的速度很慢。對(duì)于按關(guān)鍵字存取得記錄結(jié)構(gòu)，順序查找和折半查找的速度很慢。為了避免大量與外存打交道，可以保存一個(gè)索引表來(lái)指示關(guān)鍵字為了避免大量與外存打交道，可以保存一個(gè)索引表來(lái)指示關(guān)鍵字與記錄地址之間的對(duì)應(yīng)關(guān)系。與記錄地址之間的對(duì)應(yīng)關(guān)系。q 索引文件索引文件v包括數(shù)據(jù)區(qū)和索引表兩部分。包括數(shù)據(jù)區(qū)和索引表兩部分。v為按建立時(shí)，系統(tǒng)自動(dòng)開(kāi)辟索引區(qū)。按記錄進(jìn)入的順序登記索引為按建立時(shí)，系統(tǒng)自動(dòng)開(kāi)辟索引區(qū)。按記錄進(jìn)入的順序登記索引項(xiàng)。索引項(xiàng)指出該記錄的物理地址。最后，索引表按關(guān)鍵字排序。項(xiàng)。索引項(xiàng)指出該記錄的物理地址。最后，索引表

9、按關(guān)鍵字排序。v只能存儲(chǔ)在磁盤存儲(chǔ)設(shè)備上。只能存儲(chǔ)在磁盤存儲(chǔ)設(shè)備上。Data StructureData StructurePage 92022-5-21Data StructureData StructurePage 102022-5-21q 索引文件的檢索索引文件的檢索v將索引表讀入內(nèi)存（若一個(gè)物理塊可容納一個(gè)索引表，則僅一次將索引表讀入內(nèi)存（若一個(gè)物理塊可容納一個(gè)索引表，則僅一次讀入，否則需要多次讀入）；查找索引表，確定記錄的物理地址讀入，否則需要多次讀入）；查找索引表，確定記錄的物理地址（索引表有序，可折半查找）；（索引表有序，可折半查找）；v根據(jù)物理地址，一次讀取記錄。根據(jù)物理地址，

10、一次讀取記錄。q 索引文件的修改索引文件的修改v刪除刪除 僅刪去相應(yīng)的索引項(xiàng)。僅刪去相應(yīng)的索引項(xiàng)。v插入插入 記錄進(jìn)入數(shù)據(jù)區(qū)末尾，索引項(xiàng)插入索引表中（或重新排序）。記錄進(jìn)入數(shù)據(jù)區(qū)末尾，索引項(xiàng)插入索引表中（或重新排序）。v更新更新 刪除與插入的結(jié)合。刪除與插入的結(jié)合。Data StructureData StructurePage 112022-5-21q 多級(jí)索引多級(jí)索引v記錄數(shù)目很大，導(dǎo)致一個(gè)物理塊容納不了索引表。此時(shí)，查找索記錄數(shù)目很大，導(dǎo)致一個(gè)物理塊容納不了索引表。此時(shí)，查找索引表需要多次訪問(wèn)內(nèi)存。引表需要多次訪問(wèn)內(nèi)存。v對(duì)索引表再建立一個(gè)索引。對(duì)索引表再建立一個(gè)索引。v最高可以有四級(jí)索

11、引，此時(shí)檢索需要訪問(wèn)外存最高可以有四級(jí)索引，此時(shí)檢索需要訪問(wèn)外存5 5次。次。Data StructureData StructurePage 122022-5-21q ISAMISAM文件（文件（索引順序存取法）索引順序存取法）v是一種是一種專為磁盤存取而設(shè)計(jì)的文件組織方式專為磁盤存取而設(shè)計(jì)的文件組織方式。v由于磁盤是以盤組、柱面和磁道三級(jí)地址存取的設(shè)備，則可對(duì)磁由于磁盤是以盤組、柱面和磁道三級(jí)地址存取的設(shè)備，則可對(duì)磁盤上的數(shù)據(jù)文件盤上的數(shù)據(jù)文件建立建立盤組、柱面和磁道三級(jí)索引盤組、柱面和磁道三級(jí)索引。v文件的記錄在同一盤組上存放時(shí)，應(yīng)先集中放在一個(gè)柱面上，然文件的記錄在同一盤組上存放時(shí)，應(yīng)

12、先集中放在一個(gè)柱面上，然后再順序存放在相鄰的柱面上，對(duì)同一柱面，則應(yīng)按盤面的次序后再順序存放在相鄰的柱面上，對(duì)同一柱面，則應(yīng)按盤面的次序順序存放。用這種方法建立起來(lái)的索引文件稱為順序存放。用這種方法建立起來(lái)的索引文件稱為ISAMISAM文件。文件。v包括：索引區(qū)、數(shù)據(jù)基本區(qū)、數(shù)據(jù)溢出區(qū)。包括：索引區(qū)、數(shù)據(jù)基本區(qū)、數(shù)據(jù)溢出區(qū)。Data StructureData StructurePage 132022-5-21數(shù)據(jù)區(qū)數(shù)據(jù)區(qū)索引區(qū)索引區(qū)溢出區(qū)溢出區(qū)Data StructureData StructurePage 142022-5-21q ISAMISAM文件的檢索文件的檢索v查主索引（駐內(nèi)存），

13、將相應(yīng)柱面索引（在其柱面上）調(diào)用內(nèi)存。查主索引（駐內(nèi)存），將相應(yīng)柱面索引（在其柱面上）調(diào)用內(nèi)存。v查柱面索引，將磁道索引（一般放在第查柱面索引，將磁道索引（一般放在第0 0道上）調(diào)入內(nèi)存；道上）調(diào)入內(nèi)存；v查磁道索引，將本磁道上的所有記錄送入內(nèi)存；查磁道索引，將本磁道上的所有記錄送入內(nèi)存；v順序?qū)@一組記錄查找。順序?qū)@一組記錄查找。q ISAMISAM文件的插入文件的插入v定位應(yīng)插入的磁道；定位應(yīng)插入的磁道；v按關(guān)鍵字順序插入新紀(jì)錄，將同一磁道上最后一個(gè)記錄移至溢出按關(guān)鍵字順序插入新紀(jì)錄，將同一磁道上最后一個(gè)記錄移至溢出區(qū)；區(qū)；v同時(shí)修改磁道索引項(xiàng)。同時(shí)修改磁道索引項(xiàng)。Data Struct

14、ureData StructurePage 152022-5-21q ISAMISAM文件的刪除文件的刪除v找到待刪除的記錄，在其存儲(chǔ)位置上作刪除標(biāo)記即可，而不需要找到待刪除的記錄，在其存儲(chǔ)位置上作刪除標(biāo)記即可，而不需要移動(dòng)記錄或改變指針。移動(dòng)記錄或改變指針。q ISAMISAM文件的整理文件的整理v經(jīng)過(guò)多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時(shí)，大量經(jīng)過(guò)多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時(shí)，大量得記錄進(jìn)入溢出區(qū)，而基本區(qū)中又浪費(fèi)很多空間。因此，通常需得記錄進(jìn)入溢出區(qū)，而基本區(qū)中又浪費(fèi)很多空間。因此，通常需要周期地整理要周期地整理ISAMISAM文件。文件。v把記錄讀入內(nèi)存，重新

15、排列，復(fù)制成一個(gè)新的把記錄讀入內(nèi)存，重新排列，復(fù)制成一個(gè)新的ISAMISAM文件，填滿基文件，填滿基本區(qū)而空出溢出區(qū)。本區(qū)而空出溢出區(qū)。Data StructureData StructurePage 162022-5-21q VSAMVSAM（虛擬存儲(chǔ)存取方法）（虛擬存儲(chǔ)存取方法）v利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能，給用戶提供方便。利用了操作系統(tǒng)的虛擬存儲(chǔ)器的功能，給用戶提供方便。v對(duì)用戶來(lái)說(shuō)，存儲(chǔ)記錄時(shí)不需要考慮記錄的具體存儲(chǔ)位置，也不對(duì)用戶來(lái)說(shuō)，存儲(chǔ)記錄時(shí)不需要考慮記錄的具體存儲(chǔ)位置，也不需要考慮何時(shí)執(zhí)行對(duì)外存的讀寫(xiě)命令。需要考慮何時(shí)執(zhí)行對(duì)外存的讀寫(xiě)命令。q VSAMVSAM文件結(jié)構(gòu)文件

16、結(jié)構(gòu)v三部分組成：索引集、順序集和數(shù)據(jù)集。三部分組成：索引集、順序集和數(shù)據(jù)集。Data StructureData StructurePage 172022-5-2159 9759 9715 44 5915 44 5972 9772 9710 1510 1521 37 4421 37 4451 5951 5963 7263 7285 91 9785 91 97索引集索引集順順序序集集數(shù)數(shù)據(jù)據(jù)集集控制區(qū)間控制區(qū)間控制區(qū)域控制區(qū)域Data StructureData StructurePage 182022-5-21q VSAMVSAM文件的檢索文件的檢索v在控制區(qū)間上存取一個(gè)記錄時(shí)，需從控制區(qū)間

17、兩端出發(fā)，同時(shí)向在控制區(qū)間上存取一個(gè)記錄時(shí)，需從控制區(qū)間兩端出發(fā)，同時(shí)向中間掃描。中間掃描。q VSAMVSAM文件的插入文件的插入v新記錄插入到相應(yīng)的控制區(qū)間內(nèi)，移動(dòng)其它記錄，保持有序；新記錄插入到相應(yīng)的控制區(qū)間內(nèi)，移動(dòng)其它記錄，保持有序；v控制區(qū)已滿時(shí)，要進(jìn)行控制區(qū)的分裂，即將一半的記錄移入另一控制區(qū)已滿時(shí)，要進(jìn)行控制區(qū)的分裂，即將一半的記錄移入另一個(gè)控制區(qū)間，并修改順序集中相應(yīng)索引。個(gè)控制區(qū)間，并修改順序集中相應(yīng)索引。q VSAMVSAM文件的刪除文件的刪除v刪除記錄時(shí)，需將同一控制區(qū)間中記錄關(guān)鍵字較大的記錄向前移刪除記錄時(shí)，需將同一控制區(qū)間中記錄關(guān)鍵字較大的記錄向前移動(dòng)，把空間留給以后

18、插入的新記錄。動(dòng)，把空間留給以后插入的新記錄。v控制區(qū)間變空時(shí)，則需修改順序集中相應(yīng)的索引項(xiàng)?？刂茀^(qū)間變空時(shí)，則需修改順序集中相應(yīng)的索引項(xiàng)。Data StructureData StructurePage 192022-5-21q VSAMVSAM文件缺點(diǎn)文件缺點(diǎn)v占有較多的存儲(chǔ)空間，一般只能保持約占有較多的存儲(chǔ)空間，一般只能保持約76%76%的存儲(chǔ)空間利用率。的存儲(chǔ)空間利用率。q VSAMVSAM文件優(yōu)點(diǎn)文件優(yōu)點(diǎn)v動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，不需要對(duì)文件進(jìn)行重組。動(dòng)態(tài)地分配和釋放存儲(chǔ)空間，不需要對(duì)文件進(jìn)行重組。v能較快地對(duì)插入的記錄進(jìn)行查找，查找一個(gè)后插入的記錄和查找能較快地對(duì)插入的記錄進(jìn)行查

19、找，查找一個(gè)后插入的記錄和查找一個(gè)原有記錄的時(shí)間是相同的。一個(gè)原有記錄的時(shí)間是相同的。Data StructureData StructurePage 202022-5-21q 散列文件特點(diǎn)散列文件特點(diǎn)v由記錄的關(guān)鍵碼由記錄的關(guān)鍵碼“直接直接”得到記錄在外存（磁盤）上的映象地址。得到記錄在外存（磁盤）上的映象地址。v類似哈希表，根據(jù)文件中關(guān)鍵碼的特點(diǎn)設(shè)計(jì)一種類似哈希表，根據(jù)文件中關(guān)鍵碼的特點(diǎn)設(shè)計(jì)一種“哈希函數(shù)哈希函數(shù)”和和“處理沖突的方法處理沖突的方法”，然后將記錄散列到外存儲(chǔ)設(shè)備上，故稱，然后將記錄散列到外存儲(chǔ)設(shè)備上，故稱“散散列文件列文件”。q 桶桶v散列文件的存儲(chǔ)單位，以磁道或塊為單位，

20、由若干個(gè)記錄組成。散列文件的存儲(chǔ)單位，以磁道或塊為單位，由若干個(gè)記錄組成。q 基桶基桶v一個(gè)桶能存放一個(gè)桶能存放m m個(gè)記錄，表示這個(gè)記錄，表示這m m個(gè)有相同哈希函數(shù)值的記錄具有同個(gè)有相同哈希函數(shù)值的記錄具有同一個(gè)桶地址，該桶稱為一個(gè)桶地址，該桶稱為“基桶基桶” ” 。q 溢出桶溢出桶v當(dāng)發(fā)生當(dāng)發(fā)生“溢出溢出”時(shí)，需要將第時(shí)，需要將第m+1m+1個(gè)同義詞存放到另一個(gè)桶中。個(gè)同義詞存放到另一個(gè)桶中。Data StructureData StructurePage 212022-5-21v溢出桶可以有多個(gè)，它們和基桶大小相同，相互之間用指針相鏈接。溢出桶可以有多個(gè)，它們和基桶大小相同，相互之間用

21、指針相鏈接。v當(dāng)在基桶中沒(méi)有找到待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)行查當(dāng)在基桶中沒(méi)有找到待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置找。因此，希望同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。不要相距太遠(yuǎn)，最好在同一柱面上。 桶編號(hào) 基桶 溢出桶 28 14 21 35 8 93 9 16 81 11 19 89 33 13 55 69 62 34 圖 10-6 散列文件示例 Data StructureData StructurePage 222022-5-21q 主關(guān)鍵字文件的主關(guān)鍵字文件的特點(diǎn)特點(diǎn)v在對(duì)

22、文件進(jìn)行檢索操作時(shí)，不僅對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問(wèn)，還經(jīng)在對(duì)文件進(jìn)行檢索操作時(shí)，不僅對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問(wèn)，還經(jīng)常需要對(duì)次關(guān)鍵字進(jìn)行其他類型的詢問(wèn)檢索。因此，對(duì)多關(guān)鍵字常需要對(duì)次關(guān)鍵字進(jìn)行其他類型的詢問(wèn)檢索。因此，對(duì)多關(guān)鍵字文件，尚需建立一系列的次關(guān)鍵字索引。文件，尚需建立一系列的次關(guān)鍵字索引。q 次關(guān)鍵字索引與主關(guān)鍵字索引所不同次關(guān)鍵字索引與主關(guān)鍵字索引所不同v每個(gè)索引項(xiàng)應(yīng)包含次關(guān)鍵字、具有同一次關(guān)鍵字的多個(gè)記錄的主每個(gè)索引項(xiàng)應(yīng)包含次關(guān)鍵字、具有同一次關(guān)鍵字的多個(gè)記錄的主關(guān)鍵字或或物理記錄號(hào)。關(guān)鍵字或或物理記錄號(hào)。q 多重表文件和倒排文件是兩種多關(guān)鍵字文件的組織方法。多重表文件和倒排文件是兩種多

23、關(guān)鍵字文件的組織方法。Data StructureData StructurePage 232022-5-21q 多重表文件（多重表文件（MultilistMultilist file file）的特點(diǎn)）的特點(diǎn)v記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，建立主關(guān)鍵字的索引記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，建立主關(guān)鍵字的索引（稱為主索引）；（稱為主索引）；v對(duì)每個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱為次索引），所有具有對(duì)每個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。v主索引為非稠密索引（一組記錄建立一個(gè)索引項(xiàng)），次索引為稠主索引為

24、非稠密索引（一組記錄建立一個(gè)索引項(xiàng)），次索引為稠密索引（每個(gè)記錄建立一個(gè)索引項(xiàng)）。每個(gè)索引包括次關(guān)鍵字、密索引（每個(gè)記錄建立一個(gè)索引項(xiàng)）。每個(gè)索引包括次關(guān)鍵字、頭指針和鏈表長(zhǎng)度。頭指針和鏈表長(zhǎng)度。v在多重表中插入一個(gè)新記錄是很容易的，只要修改指針，將記錄在多重表中插入一個(gè)新記錄是很容易的，只要修改指針，將記錄插在鏈表的頭指針之后。但是，要?jiǎng)h去一個(gè)記錄卻很繁瑣，需要插在鏈表的頭指針之后。但是，要?jiǎng)h去一個(gè)記錄卻很繁瑣，需要在每個(gè)次關(guān)鍵字的鏈表中刪去該記錄。在每個(gè)次關(guān)鍵字的鏈表中刪去該記錄。Data StructureData StructurePage 242022-5-21Data Struct

25、ureData StructurePage 252022-5-21q 倒排文件（倒排文件（Inverted fileInverted file）和多重表文件的）和多重表文件的區(qū)別區(qū)別v次關(guān)鍵字索引的結(jié)構(gòu)不同。次關(guān)鍵字索引的結(jié)構(gòu)不同。 q 倒排表倒排表v倒排文件中的次關(guān)鍵字索引倒排文件中的次關(guān)鍵字索引。 v在倒排表的索引項(xiàng)中沒(méi)有頭指針和鏈表長(zhǎng)度項(xiàng)，而直接用一項(xiàng)存在倒排表的索引項(xiàng)中沒(méi)有頭指針和鏈表長(zhǎng)度項(xiàng)，而直接用一項(xiàng)存放具有同一關(guān)鍵字的所有記錄的物理記錄號(hào)或主關(guān)鍵字。放具有同一關(guān)鍵字的所有記錄的物理記錄號(hào)或主關(guān)鍵字。 Data StructureData StructurePage 262022-

26、5-21Data StructureData StructurePage 272022-5-21q 順序文件順序文件v文件中記錄的物理順序和邏輯順序一致。文件中記錄的物理順序和邏輯順序一致。v對(duì)順序存儲(chǔ)器上的順序文件只能進(jìn)行順序存??；對(duì)直接存儲(chǔ)器上對(duì)順序存儲(chǔ)器上的順序文件只能進(jìn)行順序存取；對(duì)直接存儲(chǔ)器上的順序文件還可按記錄號(hào)或關(guān)鍵碼進(jìn)行隨機(jī)存取；如果是定長(zhǎng)記的順序文件還可按記錄號(hào)或關(guān)鍵碼進(jìn)行隨機(jī)存取；如果是定長(zhǎng)記錄的順序有序文件，還可利用折半查找進(jìn)行快速存取。錄的順序有序文件，還可利用折半查找進(jìn)行快速存取。v插入記錄可以插入在文件的末尾或先存入附加文件。插入記錄可以插入在文件的末尾或先存入附加

27、文件。v刪除記錄僅在原地作標(biāo)志。刪除記錄僅在原地作標(biāo)志。v更新記錄需對(duì)整個(gè)文件進(jìn)行復(fù)制。更新記錄需對(duì)整個(gè)文件進(jìn)行復(fù)制。v更多情況下對(duì)順序文件的操作是按批處理方式進(jìn)行的。更多情況下對(duì)順序文件的操作是按批處理方式進(jìn)行的。Data StructureData StructurePage 282022-5-21q 索引文件索引文件v對(duì)文件中的每個(gè)記錄都建立一個(gè)由記錄的關(guān)鍵碼和存儲(chǔ)地址構(gòu)成對(duì)文件中的每個(gè)記錄都建立一個(gè)由記錄的關(guān)鍵碼和存儲(chǔ)地址構(gòu)成的索引項(xiàng)。所有記錄的索引項(xiàng)構(gòu)成一個(gè)按關(guān)鍵碼有序的索引表。的索引項(xiàng)。所有記錄的索引項(xiàng)構(gòu)成一個(gè)按關(guān)鍵碼有序的索引表。v索引表可以是順序結(jié)構(gòu)，也可以是查找樹(shù)結(jié)構(gòu)，對(duì)索引文件可以索引表可以是順序結(jié)構(gòu)，也可以是查找樹(shù)結(jié)構(gòu)，對(duì)索引文件可以進(jìn)行直接存取或按關(guān)鍵碼存取。進(jìn)行直接存取或按關(guān)鍵碼存取。v按關(guān)鍵碼存取時(shí)，首先在索引中進(jìn)行查找，然后按索引項(xiàng)中指示按關(guān)鍵碼存取時(shí)，首先在索引中進(jìn)行查找，然后按索引項(xiàng)中指示的存儲(chǔ)地址進(jìn)行存取。的存儲(chǔ)地址進(jìn)行存取。v插入記錄時(shí)，記錄本身可插入在主文件的末尾，同時(shí)將相應(yīng)的索插入記錄時(shí)，記錄本身可插入在主文件的末尾，同時(shí)將相應(yīng)的索引項(xiàng)插入索引中恰當(dāng)位置。引項(xiàng)插入索引中恰當(dāng)位置。v刪除記錄僅需刪除相應(yīng)的索引項(xiàng)。刪除記錄僅需刪除相應(yīng)的索引項(xiàng)。v更新記錄時(shí)，可將更新后的記錄插入在主文件的末尾，同時(shí)修改更新記錄時(shí)，可