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