1、文件,在現(xiàn)代計(jì)算機(jī)的應(yīng)用領(lǐng)域中，數(shù)據(jù)處理是一個(gè)重要方面。數(shù)據(jù)處理是對(duì)各種類(lèi)型的大批量的數(shù)據(jù)進(jìn)行收集、存儲(chǔ)、排序、檢索、計(jì)算、修改、輸出等分析和加工處理的過(guò)程。例如，用計(jì)算機(jī)進(jìn)行企業(yè)管理、財(cái)務(wù)工資管理、倉(cāng)庫(kù)物資管理、情報(bào)檢索、統(tǒng)計(jì)報(bào)表等都涉及到數(shù)據(jù)存放到外存儲(chǔ)器上。有時(shí)，為了長(zhǎng)期保存原始數(shù)據(jù)和加工處理過(guò)的數(shù)據(jù)，也需要將這些數(shù)據(jù)以文件的形式存放在外存上。學(xué)完本章讀者應(yīng)能掌握文件的概念、邏輯特性、物理結(jié)構(gòu)和基本操作。,文件的基本概念,與文件有關(guān)的基本術(shù)語(yǔ)有以下幾個(gè)： 數(shù)據(jù)項(xiàng)：數(shù)據(jù)項(xiàng)是文件中可使用的不可分的最小數(shù)據(jù)單位。一個(gè)數(shù)據(jù)項(xiàng)由若干個(gè)字符或數(shù)字組成，它代表某一事物的一種屬性。數(shù)據(jù)項(xiàng)又稱(chēng)為數(shù)據(jù)域。例

2、如，個(gè)人書(shū)庫(kù)中的登錄號(hào)、書(shū)號(hào)、書(shū)名、作者、出版社和價(jià)格等等都是數(shù)據(jù)項(xiàng)。 記錄：記錄是由一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)根據(jù)一定的目的而組成的數(shù)據(jù)項(xiàng)集合。例如，由登錄號(hào)、書(shū)號(hào)、書(shū)名、作者、出版社和價(jià)格等數(shù)據(jù)項(xiàng)組成的集合是一個(gè)職工記錄。 文件：文件是大量性質(zhì)相同的記錄組成的集合。,關(guān)鍵字：是能夠區(qū)別文件中各記錄的域。通常，把能唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱(chēng)為主關(guān)鍵字；而那些不能唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字稱(chēng)為次關(guān)鍵字；由兩個(gè)以上關(guān)鍵字組成的關(guān)鍵字稱(chēng)為復(fù)合關(guān)鍵字。 在表10-1所給出的個(gè)人書(shū)庫(kù)文件中，各個(gè)記錄的結(jié)構(gòu)相同，信息長(zhǎng)度相同，因而我們將這樣的記錄稱(chēng)為定長(zhǎng)記錄。由定長(zhǎng)記錄組成的文件稱(chēng)為定長(zhǎng)記錄文件。除了定長(zhǎng)記錄文件之

3、外，還有不定長(zhǎng)記錄文件。例如，在學(xué)生學(xué)籍管理文件中，不同的年級(jí)，或者不同專(zhuān)業(yè)的學(xué)生，所修的課程數(shù)和課程名稱(chēng)都不一樣。這樣，反映各個(gè)學(xué)生的學(xué)科成績(jī)的記錄長(zhǎng)度和結(jié)構(gòu)就不相同，這類(lèi)記錄稱(chēng)為不定長(zhǎng)記錄。由不定長(zhǎng)記錄組成的文件叫做不定長(zhǎng)記錄文件。 文件的主要操作有以下幾種： 插入：將一個(gè)記錄插入某個(gè)文件中。 刪除：從某個(gè)文件中刪除一個(gè)或多個(gè)記錄。 修改：用指定值去修改滿足修改條件的某個(gè)（或多個(gè)）記錄中的某個(gè)（或多個(gè)）數(shù)據(jù)項(xiàng)的內(nèi)容。 檢索：對(duì)文件的檢索是通過(guò)對(duì)文件的各種查詢來(lái)實(shí)現(xiàn)的。對(duì)表10-1所示的個(gè)人書(shū)庫(kù)文件，有以下4種類(lèi)型的查詢： 查詢1（Q1）：這是簡(jiǎn)單查詢，它規(guī)定只查詢一個(gè)關(guān)鍵字的值。例如查詢“

4、書(shū)名為數(shù)據(jù)結(jié)構(gòu)”的書(shū)有哪些？又如查詢“書(shū)號(hào)=TP1787”的書(shū)是哪一個(gè)記錄？過(guò)些都是簡(jiǎn)單查詢。 查詢2（Q2）：這是范圍性查詢，它規(guī)定在單個(gè)關(guān)鍵字值的某個(gè)范圍內(nèi)進(jìn)行查詢。例如查詢“價(jià)格22.00”的書(shū)是哪些記錄？ 查詢3（Q3）：這是函數(shù)性查詢，它要求先規(guī)定單個(gè)關(guān)鍵字值的某個(gè)因數(shù)，然后對(duì)該函數(shù)的值進(jìn)行查詢。例如規(guī)定某個(gè)關(guān)鍵字的平均值，可查詢“關(guān)鍵字值大于這個(gè)平均值”的有哪些記錄？對(duì)于個(gè)人書(shū)庫(kù)文件，可查詢“價(jià)格所有圖書(shū)的平均價(jià)格”是哪些圖書(shū)？ 查詢4（Q4）：這是布爾查詢，即對(duì)上述查詢Q1Q3用邏輯運(yùn)算符and（與）、or（或）、not（非）組合起來(lái)進(jìn)行布爾查詢。例如查詢“（書(shū)名為數(shù)據(jù)結(jié)構(gòu)）or

5、（書(shū)號(hào)=TP1787）”的圖書(shū)是哪些記錄？ 在以上的文件操作中，檢索是最基本的操作，其它操作都在檢索的基礎(chǔ)之上進(jìn)行。 文件的操作又可以分成實(shí)時(shí)處理和批量處理兩種方式。采用實(shí)時(shí)處理方式時(shí)，對(duì)任何一類(lèi)查詢或更新，系統(tǒng)應(yīng)立即進(jìn)行響應(yīng)和處理，一般應(yīng)在幾秒鐘之內(nèi)作出反應(yīng)。例如，對(duì)于一個(gè)飛機(jī)訂票系統(tǒng)，必須在幾秒鐘之內(nèi)能給客戶的查詢請(qǐng)求輸出飛機(jī)班次和座位的狀況等信息，即應(yīng)是一個(gè)實(shí)時(shí)檢索系統(tǒng)。同理，飛機(jī)訂票系統(tǒng)應(yīng)采用實(shí)時(shí)更新方式，即當(dāng)某個(gè)航班一個(gè)座位被預(yù)訂出后，應(yīng)立即更新該航班的座位文件，以免發(fā)生差錯(cuò)。采用批量處理方式，系統(tǒng)不必立即進(jìn)行響應(yīng)和處理，因?yàn)檫@時(shí)的響應(yīng)時(shí)間不是一個(gè)重要因素。例如，對(duì)于學(xué)生學(xué)籍管理系統(tǒng)

6、來(lái)說(shuō)，可在期末考試全部結(jié)束后只進(jìn)行次批量處理。 文件的物理結(jié)構(gòu)是指文件在外存上的組織形式。按照文件的檢索方式和物理結(jié)構(gòu)，文件分為順序文件、索引文件、索引順序文件、直接存取文件、鏈接文件和多重鏈表文件、倒排文件。按所存放的外存設(shè)備，文件又可以分為磁帶文件和磁盤(pán)文件等幾類(lèi)。下面分別加以討論。,順序文件,順序文件是物理結(jié)構(gòu)最簡(jiǎn)單的文件，也是數(shù)據(jù)處理歷史上最早使用的文件結(jié)構(gòu)。順序文件的各個(gè)記錄按輸入的先后次序存放在外存中的連續(xù)存儲(chǔ)區(qū)。為了便于檢索和修改文件，文件中的記錄通常按關(guān)鍵字的大小次序排列，成為按關(guān)鍵字排序的順序文件。表10-1所示的個(gè)人書(shū)庫(kù)文件是按關(guān)鍵字登錄號(hào)排序的文件，它存放到外存的連續(xù)存儲(chǔ)

7、區(qū)后便得到一個(gè)按關(guān)鍵字排序的順序文件。 順序文件的基本優(yōu)點(diǎn)是在連續(xù)存取時(shí)速度較快。例如，如果文件中的第i個(gè)記錄剛被存取過(guò)，而下一個(gè)要存取的記錄就是第i+1個(gè)記錄，則此次存取將會(huì)很快完成。磁帶是比較適用于這種應(yīng)用的外存設(shè)備。存放于磁帶上的文件也只能是順序文件，這是由磁帶的物理特性決定的。存放于磁盤(pán)上的文件，既可以是順序文件，也可以是索引結(jié)構(gòu)或其它結(jié)構(gòu)類(lèi)型的文件。 當(dāng)需要對(duì)磁帶順序文件進(jìn)行檢索時(shí)，一般是采用順序掃描的方式來(lái)檢索滿足查詢條件的記錄。例如，若要檢索第i個(gè)記錄，則必須先檢索前面的i-1個(gè)記錄。為了提高平均檢索效率，可采用批量處理技術(shù)。如果將對(duì)文件的多個(gè)檢索請(qǐng)求加以積累和排序，則形成一個(gè)稱(chēng)

8、為待辦文件（或事務(wù)文件）的文件。如果將被查詢的文件稱(chēng)為主文件，則批量檢索就是按照待辦文件的要求成批地檢索主文件。批量檢索對(duì)于實(shí)時(shí)應(yīng)用來(lái)說(shuō)是不適宜的，因?yàn)閷?shí)時(shí)查詢要求響應(yīng)時(shí)間快，而在很短的時(shí)間間隔內(nèi)，積累的批處理文件規(guī)模太小，不能表現(xiàn)出它的優(yōu)越性。 在磁帶順序文件中插入記錄，只能加在文件的末尾，不能插在兩個(gè)原有記錄之間。修改記錄，即使在新舊記錄等長(zhǎng)的情況下，將新記錄寫(xiě)在舊記錄的位置上，一般不但不可能完全重合，甚至還會(huì)破壞鄰近記錄的信息。因此，修改一個(gè)磁帶文件，需要用另一條磁帶將原文件復(fù)制過(guò)來(lái)，在復(fù)制過(guò)程中進(jìn)行插入、刪除、修改記錄的操作。為了提高效率，修改一個(gè)順序文件，也采用成批處理技術(shù)。這種批量

9、修改方式很適用于銀行帳戶結(jié)算管理系統(tǒng)。例如，可把一天的零星支取和存入分別作為記錄收集在一起，構(gòu)成為一個(gè)待辦文件，在當(dāng)天下班時(shí)再按照待辦文件進(jìn)行批量修改主文件（頭天下班修改過(guò)的主文件）的工作，便得到一個(gè)新主文件。,索引文件,順序文件的查詢速度很慢。采用索引文件可以提高檢索效率。實(shí)際上，在前面的章節(jié)中我們已經(jīng)運(yùn)用了索引技術(shù)。 索引用來(lái)表示關(guān)鍵字與相應(yīng)記錄的存儲(chǔ)地址之間的對(duì)應(yīng)關(guān)系。換言之，索引指出了記錄在存儲(chǔ)器中的存儲(chǔ)地址。設(shè)記錄Ri的關(guān)鍵字為Ki，Ri在外存中的存儲(chǔ)地址為Ai，則（Ki，Ai）稱(chēng)為記錄Ri的索引項(xiàng)。索引表（簡(jiǎn)稱(chēng)索引）是索引項(xiàng)的集合。如果文件中的每個(gè)記錄都有一個(gè)索引項(xiàng)，則這樣的索引稱(chēng)

10、為稠密索引。如果多個(gè)記錄只有一個(gè)索引項(xiàng)，則這樣的索引稱(chēng)為非稠密索引。帶有索引的文件稱(chēng)為索引文件。索引也稱(chēng)為目錄。 索引文件在外存（磁盤(pán)、磁鼓等）中可分為兩個(gè)存儲(chǔ)區(qū)：索引區(qū)和記錄區(qū)（數(shù)據(jù)區(qū)）。索引表中的索引項(xiàng)順序存放在索引區(qū)中，但為了便于檢索，索引項(xiàng)一般按關(guān)鍵字的大小次序排列。文件中的記錄按輸入的先后次序存放到記錄區(qū)；記錄區(qū)按關(guān)鍵字大小次序排列的索引文件稱(chēng)為索引順序文件。對(duì)于索引順序文件，可以不必使用稠密索引，只為一個(gè)記錄塊（含多個(gè)有序記錄）建立一個(gè)索引項(xiàng)。記錄區(qū)不按關(guān)鍵字大小次序排列的索引文件稱(chēng)為索引非順序文件，這時(shí)應(yīng)使用稠密索引。圖10-2所示的個(gè)人書(shū)庫(kù)（價(jià)格）索引文件，是一個(gè)索引非順序文件

11、。 通常，索引項(xiàng)所含的數(shù)據(jù)信息比記錄少得多，因而索引所需的存儲(chǔ)空間比文件本身（記錄區(qū)）所需要的存儲(chǔ)空間少得多。在文件的記錄數(shù)較少的情況下，可以為每個(gè)記錄建立一個(gè)索引項(xiàng)。文件建立時(shí)，開(kāi)辟一個(gè)索引區(qū)，一般固定在某個(gè)磁盤(pán)面的一個(gè)或多個(gè)磁道上。寫(xiě)入一個(gè)記錄到記錄區(qū)時(shí)，在索引區(qū)相應(yīng)登入一個(gè)索引項(xiàng)，即把該記錄的關(guān)鍵字（主關(guān)鍵字）和記錄的存儲(chǔ)地址順序?qū)懭胨饕齾^(qū)。文件建立后，將索引區(qū)中的索引讀入內(nèi)存的緩沖區(qū)，按關(guān)鍵字進(jìn)行內(nèi)部排序。最后將排序好的索引項(xiàng)順序?qū)懟氐酱疟P(pán)上的索引區(qū)。 根據(jù)關(guān)鍵字查找索引文件的記錄分兩步進(jìn)行。第1步，訪問(wèn)外存的索引區(qū)，將索引讀入內(nèi)存緩沖區(qū)，使用順序查找或折半查找法找出所查記錄在外存數(shù)據(jù)

12、區(qū)中的地址，這一過(guò)程稱(chēng)為預(yù)查找。第2步，如果在預(yù)查中已找到了所查記錄的地址，則第2次訪問(wèn)外存，根據(jù)已查到的地址，讀取所查的記錄。 刪除一個(gè)記錄時(shí)，只需刪去相應(yīng)的索引項(xiàng)，而不必移動(dòng)數(shù)據(jù)區(qū)中的記錄。插入一個(gè)新記錄時(shí)，將記錄放到記錄區(qū)的末尾，在索引區(qū)登記相應(yīng)的索引項(xiàng)，并對(duì)索引區(qū)中的索引項(xiàng)重新排序。,索引順序文件,在實(shí)際應(yīng)用中，索引順序文件是被經(jīng)常采用的一種文件結(jié)構(gòu)。它是在順序文件的基礎(chǔ)上，用增加索引的辦法而形成的。文件中的記錄按關(guān)鍵字大小順序存放在磁盤(pán)的連續(xù)或相鄰的存儲(chǔ)區(qū)中。由于記錄按關(guān)鍵字排序，因此不必為每一個(gè)記錄設(shè)立一個(gè)索引項(xiàng)，而把文件劃分為若干個(gè)記錄塊，只為每塊中關(guān)鍵字最大（或最?。┑挠涗浽O(shè)置

13、一個(gè)索引項(xiàng)。這種組織文件的方法稱(chēng)為索引順序存取法ISAM（Indexed Sequential Access Method），用這種方法建立起來(lái)的索引文件稱(chēng)為ISAM文件，它是一種專(zhuān)為磁盤(pán)存取設(shè)計(jì)的文件組織方式。,由于磁盤(pán)是以盤(pán)組、柱面和磁道三級(jí)地址存取的設(shè)備，則可對(duì)磁盤(pán)上的數(shù)據(jù)文件建立盤(pán)組、柱面和磁道三級(jí)索引。文件的記錄在同一盤(pán)組上存放時(shí)，應(yīng)先集中放在一個(gè)柱面上，然后再順序存放在相鄰的柱面上，對(duì)同一柱面，則應(yīng)按盤(pán)面的次序順序存放。例如圖10-3為存放在一個(gè)磁盤(pán)組上的ISAM文件。每個(gè)柱面建立一個(gè)磁道索引，每個(gè)磁道索引項(xiàng)由兩部分組成：基本索引項(xiàng)和溢出索引項(xiàng)，如圖10-4所示，每一部分都包括關(guān)鍵

14、字和指針兩項(xiàng)，前者表示該磁道中最大關(guān)鍵字，后者指示該磁道中第一個(gè)記錄的位置，柱面索引的每一個(gè)索引項(xiàng)也由關(guān)鍵字和指針兩部分組成，前者表示該柱面中最末一個(gè)記錄的關(guān)鍵字（最大關(guān)鍵字），后者指示該柱面上的磁道索引位置。柱面索引存放在某個(gè)柱面上，若柱面索引較大，占多個(gè)磁道時(shí)，則可建立柱面索引的索引主索引。,在ISAM文件上檢索記錄時(shí)，先從主索引出發(fā)找到相應(yīng)的柱面索引，再?gòu)闹嫠饕业接涗浰谥娴拇诺浪饕?，最后從磁道索引找到記錄所在磁道的第一個(gè)記錄的位置，由此出發(fā)在該磁道上進(jìn)行順序查找直到找到為止；反之，若找遍該磁道而不存在此記錄，則表明該文件中無(wú)此記錄。 從圖10-3中還可以看到，每個(gè)柱面上還開(kāi)辟有一

15、個(gè)溢出區(qū)；并且，磁道索引項(xiàng)中有溢出索引項(xiàng)，這是為插入記錄所設(shè)置的。由于ISAM文件中記錄是按關(guān)鍵字順序存放的，則在插入記錄時(shí)需移動(dòng)記錄并將同一磁道上最后一個(gè)記錄移至溢出區(qū)，同時(shí)修改磁道索引項(xiàng)。通常溢出區(qū)可有三種設(shè)置方法：（1）集中存放整個(gè)文件設(shè)一個(gè)大的單一的溢出區(qū)；（2）分散存放每個(gè)柱面設(shè)一個(gè)溢出區(qū)；（3）集中與分散相結(jié)合溢出時(shí)記錄先移至每個(gè)柱面各自的溢出區(qū)，待滿之后再使用公共溢出區(qū)。 每個(gè)柱面的基本區(qū)是順序存儲(chǔ)結(jié)構(gòu)，而溢出區(qū)是鏈表結(jié)構(gòu)。同一磁道溢出的記錄由指針相鏈，該磁道索引的溢出索引項(xiàng)中的關(guān)鍵字指示該磁道溢出的記錄的最大關(guān)鍵字；而指針則指示在溢出區(qū)中的第一個(gè)記錄。圖10-5所示為插入記錄和

16、溢出處理的具體例子。 其中（a）為插入前的某一柱面上的狀態(tài)；（b）為插入R65時(shí)，將第二道中關(guān)鍵字大于65的記錄順次后移，且使R90溢出至溢出區(qū)的情況；（c）為插入R65之后的狀態(tài)，此時(shí)2道的基本索引項(xiàng)的關(guān)鍵字改為80，且溢出索引項(xiàng)的關(guān)鍵字改為90，其指針指向第4道第一個(gè)記錄即R90；（d）是相繼插入R95和R83后的狀態(tài)。在R95插入在第3道的第一個(gè)記錄的位置而使R145溢出。而由于808390，則R83被直接插入到溢出區(qū)，作為第2道在溢出區(qū)的第一個(gè)記錄，并將它的指針指向R90的位置，同時(shí)修改第2道索引的溢出索引項(xiàng)的指針指向R83。 ISAM文件中刪除記錄的操作比插入簡(jiǎn)單得多，只需找到待刪除

17、的記錄，在其存儲(chǔ)位置上作刪除標(biāo)記即可，而不需要移動(dòng)記錄或改變指針。則在經(jīng)過(guò)多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。此時(shí)，大量得記錄進(jìn)入溢出區(qū)，而基本區(qū)中又浪費(fèi)很多空間。因此，通常需要周期地整理ISAM文件。把記錄讀入內(nèi)存，重新排列，復(fù)制成一個(gè)新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。,直接存取文件,直接存取文件指的是利用雜湊（Hash）法進(jìn)行組織的文件。它類(lèi)似于哈希表，即根據(jù)文件中關(guān)鍵字的特點(diǎn)設(shè)計(jì)一種哈希函數(shù)和處理沖突的方法將記錄散列到存儲(chǔ)設(shè)備上，故又稱(chēng)散列文件。 與哈希表不同的是，對(duì)于文件來(lái)說(shuō)，磁盤(pán)上的文件記錄通常是成組存放的。若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，在散列文件中這個(gè)存儲(chǔ)單位叫作桶。一

18、個(gè)桶能存放的邏輯記錄的總數(shù)稱(chēng)為桶的容量。假如一個(gè)桶能存放m個(gè)記錄，即m個(gè)同義詞的記錄可以存放在同一地址的桶中，當(dāng)?shù)趍+1個(gè)同義詞出現(xiàn)時(shí)則發(fā)生“溢出”。處理溢出也可采用哈希表中處理沖突的各種方法；但對(duì)散列文件，主要采用鏈地址法。 當(dāng)發(fā)生“溢出”時(shí)，需要將第m+1個(gè)同義詞存放到另一個(gè)桶中，通常稱(chēng)此桶為“溢出桶”；相對(duì)地，稱(chēng)前m個(gè)同義詞存放的桶為“基桶”。溢出桶可以有多個(gè)，它們和基桶大小相同，相互之間用指針相鏈接。當(dāng)在基桶中沒(méi)有找到待查記錄時(shí)，就順指針?biāo)傅揭绯鐾爸羞M(jìn)行查找。因此，希望同一散列地址的溢出桶和基桶在磁盤(pán)上的物理位置不要相距太遠(yuǎn)，最好在同一柱面上。,例如，某i文件有18個(gè)記錄，其關(guān)鍵字分

19、別為28，19，13，93，89，14，55，69，8，9，16，21，33，81，62，11，34，35。用除留余數(shù)法作哈希函數(shù)H（key）=key MOD 7。桶的容量m=3，基本桶數(shù)=7，由此得到的散列文件如圖10-6所示。,在散列文件中進(jìn)行查找時(shí)，首先根據(jù)給定值k求得哈希地址（即基桶號(hào)），將基桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到關(guān)鍵字等于k的記錄，則檢索成功；若基桶內(nèi)沒(méi)有填滿記錄或其指針域?yàn)榭眨礋o(wú)溢出桶）則文件內(nèi)不含有待查的記錄；否則根據(jù)指針域的值的指示將溢出桶的記錄讀入內(nèi)存繼續(xù)進(jìn)行順序查找，直至檢索成功或不成功。在散列文件中，裝填因子=n/bm。 其中：n為文件的記錄數(shù)，b為桶數(shù)，

20、m為桶的容量。而存取桶數(shù)的期望值=1+/2。在散列文件中刪除記錄僅需要對(duì)被刪除記錄作一標(biāo)記即可。 總之，散列文件的優(yōu)點(diǎn)是：插入、刪除方便，存取速度比索引文件要快；不需要索引區(qū)，節(jié)省存儲(chǔ)空間。其缺點(diǎn)是：不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)存取，且詢問(wèn)方式只有簡(jiǎn)單詢問(wèn)；并且在經(jīng)過(guò)多次的插入、刪除之后，也可能造成文件結(jié)構(gòu)不合理，即溢出桶滿而基桶內(nèi)多數(shù)為被刪除的記錄。此時(shí)亦需重組文件。,多關(guān)鍵字文件,主關(guān)鍵字（With more than one key）文件的特點(diǎn)是，在對(duì)文件進(jìn)行檢索操作時(shí)，不僅對(duì)主關(guān)鍵字進(jìn)行簡(jiǎn)單詢問(wèn)，還經(jīng)常需要對(duì)次關(guān)鍵字進(jìn)行其他類(lèi)型的詢問(wèn)檢索。因此，對(duì)多關(guān)鍵字文件，尚需建立一系列的次

21、關(guān)鍵字索引。次關(guān)鍵字索引的主關(guān)鍵字索引所不同的是，每個(gè)索引項(xiàng)應(yīng)包含次關(guān)鍵字、具有同一次關(guān)鍵字的多個(gè)記錄的主關(guān)鍵字或或物理記錄號(hào)。多重表文件和倒排文件是兩種多關(guān)鍵字文件的組織方法。,多重表文件,多重表文件（Multilist file）的特點(diǎn)是：記錄按主關(guān)鍵字的順序構(gòu)成一個(gè)串聯(lián)文件，并建立主關(guān)鍵字的索引（稱(chēng)為主索引）；對(duì)每個(gè)次關(guān)鍵字項(xiàng)建立次關(guān)鍵字索引（稱(chēng)為次索引），所有具有同一次關(guān)鍵字的記錄構(gòu)成一個(gè)鏈表。主索引為非稠密索引（一組記錄建立一個(gè)索引項(xiàng)），次索引為稠密索引（每個(gè)記錄建立一個(gè)索引項(xiàng)）。每個(gè)索引包括次關(guān)鍵字、頭指針和鏈表長(zhǎng)度。 例如，圖10-7所示為一個(gè)多重表文件。其中，工號(hào)為主關(guān)鍵字，記

22、錄按工號(hào)順序鏈接。對(duì)工號(hào)非稠密索引，分成3個(gè)子鏈表。其索引如圖10-8（b）所示，索引項(xiàng)中的主關(guān)鍵字為各組中的最大值。職稱(chēng)、專(zhuān)業(yè)為兩個(gè)次關(guān)鍵字項(xiàng)，它們的索引如圖10-8（c）、（d）所示。具有同次關(guān)鍵字的記錄鏈接在同一鏈表中。有了這些次關(guān)鍵字索引，根據(jù)關(guān)鍵字值找到鏈表的頭指針，然后從頭指針出發(fā)可列出鏈表中所有記錄。例如，要查詢數(shù)學(xué)專(zhuān)業(yè)的教授，可以從“專(zhuān)業(yè)”索引表中查找到“數(shù)學(xué)”的頭指針和表長(zhǎng)，從而可讀取到相應(yīng)的記錄，再查看其中哪些記錄的“職稱(chēng)”為“教授”即可。此查詢也可從“職稱(chēng)”索引表入手。顯然，較好的方法是先讀長(zhǎng)度較短的鏈表中的記錄。 在多重表中插入一個(gè)新記錄是很容易的，只要修改指針，將記錄插在鏈表的頭指針之后。但是，要?jiǎng)h去一個(gè)記錄卻很繁瑣，需要在每個(gè)次關(guān)鍵字的鏈表中刪去該記錄。,倒排文件,倒排文件（Inverted file）和多重表文件的區(qū)別在于次關(guān)鍵字索引的結(jié)構(gòu)不同。倒排文件的次關(guān)鍵字索引稱(chēng)為倒排表。在倒排表的索引項(xiàng)中沒(méi)有頭指針和鏈表長(zhǎng)度項(xiàng)，而直接用一項(xiàng)存放具有同一關(guān)鍵字