數(shù)據(jù)結(jié)構(gòu)第十二章-文件-免費(fèi)閱讀
【正文】 次索引項(xiàng)： 次關(guān)鍵字 （指向記錄的）指針 二、次索引的組織方法 ? 1． 多重鏈表文件 特點(diǎn)：將所有 具有相同次關(guān)鍵字的記錄鏈接在同一鏈表中 ，該鏈表的頭指針即為次索引項(xiàng)中“指針域”的值； ? 2 ． 倒排文件 特點(diǎn)： 將所有 具有相同次關(guān)鍵字的記錄構(gòu)成一個(gè)次索引順序表 ，此時(shí)的次索引順序表中僅存放記錄的 “ 主關(guān)鍵字 ” 或記錄的 “ 物理記錄號(hào) ” 。 例如：有一組關(guān)鍵字如下所列 {589， 063， 269， 505， 764， 182， 166， 330} 假設(shè)哈希函數(shù)為 key MOD 7，每個(gè)桶可以容納 3個(gè)記錄（稱桶的容量為 3），則哈希文件如下 : 基桶 063 182 589 505 764 269 166 330 溢出桶 在哈希文件中， “沖突”和“溢出” 是不同的概念 。 ４ ． 文件的操作 ? 檢索： 可進(jìn)行順序存取和按關(guān)鍵字存??； ? 插入： 按關(guān)鍵字大小插入在某個(gè)適當(dāng)?shù)目刂茀^(qū)間中 ， 當(dāng)控制區(qū)間中的記錄數(shù)超過(guò)文件規(guī)定的大小時(shí) ， 要 “ 分裂 ” 控制區(qū)間 ， 必要時(shí) ， 還需要 “ 分裂 ” 控制區(qū)域； ? 刪除： 必須 “ 真實(shí)地 ” 刪除記錄 ， 因此要在控制區(qū)間內(nèi) “ 移動(dòng) ” 記錄 。因此，對(duì) ISAM文件， 需要周期 地進(jìn)行重整。 有兩種典型的索引順序文件： １．文件的組織方式 ： 主文件按柱面集中存放，同時(shí)建立 三級(jí)索引：磁道索引、柱面索引和 主索引。 按關(guān)鍵字進(jìn)行檢索 時(shí)，從 第三查找表 開始， 至多訪問(wèn)外存五次 。 一 、 結(jié)構(gòu)特點(diǎn)： ? 1． 索引文件由 “ 主文件 ” 和多級(jí) “ 索引 ” 組成； ? 2． 索引中的每個(gè)記錄由 “ 關(guān)鍵字 ” 和 “ 指針 ” 組成； ? 3． 通常 ， 索引文件中的主文件是無(wú)序文件 ， 索引是 (按關(guān)鍵字有序 )的有序文件； ? 4． “ 索引 ” 是在輸入數(shù)據(jù)建立文件時(shí)自動(dòng)生成 。 順 序 文 件 順序文件的具體組織形式有兩種： 串聯(lián)文件 ：物理記錄之間的順序由指 針相鏈。由于操作系 統(tǒng)中的文件僅是 一維的連續(xù)字符 序列 ，為了用戶存取和加工的方 便，將文件中的信息劃分為若干 組，其中每一組信息稱作一個(gè)記 錄； 其二 為 數(shù)據(jù)庫(kù)文件 ，文件中的 記錄帶 有結(jié)構(gòu)，是數(shù)據(jù)項(xiàng)的集合 。記錄 是文件中可以存取的數(shù)據(jù)基本單 位， 數(shù)據(jù)項(xiàng)是文件中可以使用的 數(shù)據(jù)最小單位。 連續(xù)文件 ：次序相繼的兩個(gè)物理記錄 其存儲(chǔ)位置相鄰 。初建時(shí)的 “ 靜態(tài)索引 ” 為無(wú)序文件 ， 經(jīng)過(guò)排序后成為有序文件 。
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1