數(shù)據(jù)結(jié)構(gòu)第十二章-文件(存儲(chǔ)版)
【正文】 索 引表 采用查找樹(shù)表或哈希表。 關(guān)鍵字 指針 關(guān)鍵字 指針 磁道索引結(jié)構(gòu) 基本索引項(xiàng) 溢出索引項(xiàng) 210 1024 主 索 引 r(14) r(21) r(38) r(41) r(57) r(63) r(72) r(85) r(99) 溢 出 區(qū) 磁 道 索 引 r(514) … … 溢 出 區(qū) 磁道索引 … … r(1024) 一 個(gè) 柱 面 …. 柱 面 索 引 99 210 1024 T0 T1 T2 T3 T4 T5 ２．操作的特點(diǎn)： 檢 索 插入 刪除 檢索： 可有兩種方式： 按關(guān)鍵字存取 — 從主索引開(kāi)始 ,到 柱面索引，到磁道索引，最后取 得記錄，先后訪問(wèn)四次外存。 ４．柱面索引的位置 ISAM文件占有多個(gè)柱面，其柱 面索引本身占有一個(gè)柱面，為使“磁頭”的平均移動(dòng)距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。 ５． VSAM文件 通常被作為大型索引 順序文件的標(biāo)準(zhǔn)組織方式。一般情況下，假設(shè)桶 的大小為 m，則允許哈希地址產(chǎn)生 m1 次的沖突，當(dāng)發(fā)生第 m次沖突時(shí)，才 需要進(jìn)行“沖突處理”，對(duì)散列文件而 言，通常采用鏈地址法出路沖突。 次索引項(xiàng)中的 “ 指針 ” 指向相應(yīng)的次索引順序表； ? 3． 次關(guān)鍵字索引表本身的結(jié)構(gòu) 可以是 順序表 ， 也可以是 樹(shù)表 或哈希表 ， 視具體的次關(guān)鍵字的特性而定 。 多 關(guān) 鍵 字 文 件 一、多關(guān)鍵字文件的特點(diǎn) 除需要對(duì)主關(guān)鍵字建立“主索引” 外， 尚需對(duì)各個(gè)次關(guān)鍵字建立 “次索引”。 因此 由哈希函 數(shù)得到的映象地址為“桶地址” 。 ３． 順序集 本身是一個(gè)單鏈表，它 包含文件的全部索引項(xiàng)，同時(shí)，順 序集中的每個(gè)結(jié)點(diǎn)即為 B+樹(shù)的葉子 結(jié)點(diǎn)， 索引集 中的結(jié)點(diǎn)即為 B+樹(shù)的 非葉結(jié)點(diǎn)。 ３．文件重組 在經(jīng)過(guò)多次的插入和刪除操作之 后，大量的記錄進(jìn)入文件的“溢出區(qū)”， 而“基本存儲(chǔ)區(qū)”中出現(xiàn)很多已被刪去 的記錄空間，此時(shí)的文件結(jié)構(gòu)很不合 理。 結(jié)構(gòu)特點(diǎn)： 索 引 順 序 文 件 一、 ISAM文件 ISAM(Index Sequential Access Method) (索引順序存取方法 )是一種專為磁 盤(pán)存取設(shè)計(jì)的文件組織方法。 類似地，由查找表建立的索引為 第二 查找表 ；由第二查找表建立的索引為 第 三查找表 。 批處理的時(shí)間分析 ： 假設(shè)對(duì)外存進(jìn)行一次讀 /取為 s個(gè) 記錄，則整個(gè)批處理過(guò)程
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1