數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)

《數(shù)據(jù)結(jié)構(gòu)(嚴(yán)蔚敏)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

1、索引文件索引文件由索引表和主文件兩部分構(gòu)成。索引表是一張指示邏輯記錄和物理記錄之間對應(yīng)關(guān)糸的表。索引表中的每項稱作索引項。索引項是按鍵（或邏輯記錄號）順序排列。若文件本身也是按關(guān)鍵字順序排列，則稱為索引順序文件。否則，稱為索引非順序文件。（1）索引順序文件(IndexedSequentialFile)主文件按主關(guān)鍵字有序的文件稱索引順序文件。在索引順序文件中，可對一組記錄建立一個索引項。這種索引表稱為稀疏索引。（2）索引非順序文件(IndexedNonSequentailFile)主文件按主關(guān)鍵字無序得文件稱索引非順序文件。在索引非順序文件中，必須為每個記錄建立一個索引項，這樣建立的索

2、引表稱為稠密索引。注意：①通常將索引非順序文件簡稱為索引文件。②索引非順序文件主文件無序，順序存取將會頻繁地引起磁頭移動，適合于隨機(jī)存取，不適合于順序存取。③索引順序文件的主文件是有序的，適合于隨機(jī)存取、順序存取。④索引順序文件的索引是稀疏索引。索引占用空間較少，是最常用的一種文件組織。⑤最常用的索引順序文件：ISAM文件和VSAM文件。文件一、基礎(chǔ)知識題11.1名詞解釋：索引文件,索引順序文件，ISAM文件，VSAM文件，散列文件，倒排文件。【解答】先介紹文件的概念：文件是由大量性質(zhì)相同的記錄組成的集合,按記錄類型不同可分為操作系統(tǒng)文件和數(shù)據(jù)庫文件。文件的基本組織方式有順序組織、索引

3、組織、散列組織和鏈組織。文件的存儲結(jié)構(gòu)可以采用將基本組織結(jié)合的方法,常用的結(jié)構(gòu)有順序結(jié)構(gòu)、索引結(jié)構(gòu)、散列結(jié)構(gòu)。（1）順序結(jié)構(gòu),相應(yīng)文件為順序文件,其記錄按存入文件的先后次序順序存放。順序文件本質(zhì)上就是順序表。若邏輯上相鄰的兩個記錄在存儲位置上相鄰,則為連續(xù)文件；若記錄之間以指針相鏈接,則稱為串聯(lián)文件。順序文件只能順序存取,要更新某個記錄,必須復(fù)制整個文件。順序文件連續(xù)存取的速度快,主要適用于順序存取,批量修改的情況。（2）帶索引的結(jié)構(gòu),相應(yīng)文件為索引文件。索引文件包括索引表和數(shù)據(jù)表,索引表中的索引項包括數(shù)據(jù)表中數(shù)據(jù)的關(guān)鍵字和相應(yīng)地址,索引表有序,其物理順序體現(xiàn)了文件的邏輯次序,實現(xiàn)了文

4、件的線性結(jié)構(gòu)。索引文件只能是磁盤文件,既能順序存取,又能隨機(jī)存取。（3）散列結(jié)構(gòu),也稱計算尋址結(jié)構(gòu),相應(yīng)文件稱為散列文件,其記錄是根據(jù)關(guān)鍵字值經(jīng)散列函數(shù)計算確定其地址,存取速度快,不需索引,節(jié)省存儲空間。不能順序存取,只能隨機(jī)存取。其它文件均由以上文件派生而得。文件采用何種存儲結(jié)構(gòu)應(yīng)綜合考慮各種因素,如：存儲介質(zhì)類型、記錄的類型、大小和關(guān)鍵字的數(shù)目以及對文件作何種操作。索引文件：在主文件外,再建立索引表指示關(guān)鍵字及其物理記錄的地址間一一對應(yīng)關(guān)系。這種由索引表和主文件一起構(gòu)成的文件稱為索引文件。索引表依關(guān)鍵字有序。主文件若按關(guān)鍵字有序稱為索引順序文件,否則稱為索引非順序文件（通常簡稱索引

5、文件）。索引順序文件因主文件有序,一般用稀疏索引,占用空間較少。ISAM文件：ISAM是專為磁盤存取設(shè)計的文件組織方式。即使主文件關(guān)鍵字有序,但因磁盤是以盤組、柱面和磁道（盤面）三級地址存取的設(shè)備,因此通常對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道（盤面）三級索引。在ISAM文件上檢索記錄時,先從主索引（柱面索引的索引）找到相應(yīng)柱面索引。再從柱面索引找到記錄所在柱面的磁道索引,最后從磁道索引找到記錄所在磁道的第一個記錄的位置,由此出發(fā)在該磁道上進(jìn)行順序查找直到查到為止；反之,若找遍該磁道而未找到所查記錄,則文件中無此記錄。VSAM文件：VSAM文件采用B+樹動態(tài)索引結(jié)構(gòu),文件只有控制區(qū)間和

6、控制區(qū)域等邏輯存儲單位,與外存儲器中柱面、磁道等具體存儲單位沒有必然聯(lián)系。VSAM文件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分,記錄存于數(shù)據(jù)集中,順序集和索引集構(gòu)成B+樹,作為文件的索引部分可實現(xiàn)順鏈查找和從根結(jié)點開始的隨機(jī)查找。散列文件：散列文件也稱直接存取文件,根據(jù)關(guān)鍵字的散列函數(shù)值和處理沖突的方法,將記錄散列到外存上。這種文件組織只適用于像磁盤那樣的直接存取設(shè)備,其優(yōu)點是文件隨機(jī)存放,記錄不必排序,插入、刪除方便,存取速度快,無需索引區(qū),節(jié)省存儲空間。缺點是散列文件不能順序存取,且只限于簡單查詢。經(jīng)多次插入、刪除后,文件結(jié)構(gòu)不合理,需重組文件,這很費時。倒排文件：倒排文件是一種多關(guān)鍵

7、字的文件,主數(shù)據(jù)文件按關(guān)鍵字順序構(gòu)成串聯(lián)文件,并建立主關(guān)鍵字索引。對次關(guān)鍵字也建立索引,該索引稱為倒排表。倒排表包括兩項,一項是次關(guān)鍵字,另一項是具有同一次關(guān)鍵字值的記錄的物理記錄號（若數(shù)據(jù)文件非串聯(lián)文件,而是索引順序文件—如ISAM,則倒排表中存放記錄的主關(guān)鍵字而不是物理記錄號）。倒排表作索引的優(yōu)點是索引記錄快,缺點是維護(hù)困難。在同一索引表中,不同的關(guān)鍵字其記錄數(shù)不同,各倒排表的長度不同,同一倒排表中各項長度也不相等。11.2什么是文件的邏輯