數(shù)據(jù)結(jié)構(gòu)第十二章-文件(文件)
【正文】 包含文件的全部索引項(xiàng)，同時(shí)，順 序集中的每個(gè)結(jié)點(diǎn)即為 B+樹的葉子 結(jié)點(diǎn)， 索引集 中的結(jié)點(diǎn)即為 B+樹的 非葉結(jié)點(diǎn)。 (因此，一般情況下，極少 產(chǎn)生需要分裂控制區(qū)域的情況 ) 其 優(yōu)點(diǎn)是 ：動(dòng)態(tài)地分配和釋放空間 , 不需 要重組文件；能較快地實(shí)現(xiàn)對 “后插入”的記錄的檢索； 直 接 存 取 文 件 １． 和前幾節(jié)討論的文件組織方法 不同， 直接存取文件的特點(diǎn) 是，由 記錄的關(guān)鍵字 “ 直接”得到 記錄在外 存上的 映象地址 。 因此 由哈希函 數(shù)得到的映象地址為“桶地址” 。 ３．文件的操作 ? 檢索 ： 只能進(jìn)行按關(guān)鍵字的查找 ，不能進(jìn)行順序查找。 多 關(guān) 鍵 字 文 件 一、多關(guān)鍵字文件的特點(diǎn) 除需要對主關(guān)鍵字建立“主索引” 外， 尚需對各個(gè)次關(guān)鍵字建立 “次索引”。 。 次索引項(xiàng)中的 “ 指針 ” 指向相應(yīng)的次索引順序表； ? 3． 次關(guān)鍵字索引表本身的結(jié)構(gòu) 可以是 順序表 ， 也可以是 樹表 或哈希表 ， 視具體的次關(guān)鍵字的特性而定 。 ４． 優(yōu)點(diǎn)： 記錄隨機(jī)存放， 不需要 進(jìn)行 排 序；插入、刪除方便，存取速 度快；節(jié)省存儲(chǔ)空間 ，不需要 索引區(qū)。一般情況下，假設(shè)桶 的大小為 m，則允許哈希地址產(chǎn)生 m1 次的沖突，當(dāng)發(fā)生第 m次沖突時(shí)，才 需要進(jìn)行“沖突處理”，對散列文件而 言，通常采用鏈地址法出路沖突。 ２．哈希文件的結(jié)構(gòu) 由于記錄在外存上是成組存放的， 因此允許多個(gè)記錄映象到同一個(gè)地址 上。 ５． VSAM文件 通常被作為大型索引 順序文件的標(biāo)準(zhǔn)組織方式。 VSAM文件初建時(shí)，每個(gè)控制區(qū) 間內(nèi)的記錄數(shù)不足額定數(shù)，并且有的 控制區(qū)間內(nèi)的記錄數(shù)為零。 ４．柱面索引的位置 ISAM文件占有多個(gè)柱面，其柱 面索引本身占有一個(gè)柱面，為使“磁頭”的平均移動(dòng)距離最小，柱面索引應(yīng)設(shè)在數(shù)據(jù)文件所占全部柱面的中間位置上。 將記錄 插入 在某個(gè)磁道的合適位置上 。 關(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è) 柱 面 ….
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號-1