數(shù)據(jù)結(jié)構(gòu)第十二章-文件(完整版)
【正文】 作 “ 刪除標(biāo)記 ” 。 主文件按主關(guān)鍵字有序，對(duì)一組記 錄建立一個(gè)索引項(xiàng) (建立非稠密索引 )。 從索引表建立的索引稱 查找表 ，其中 每個(gè)索引項(xiàng)為： 最大關(guān)鍵字 其 所在數(shù)據(jù)塊的存儲(chǔ)位置 稱這類索引為 非稠密索引 。 （ 1）對(duì)于事務(wù)文件中的每個(gè) 操作 首先要判別其“ 合法性 ” （ 2）事務(wù)文件中可能存在 多個(gè)操 作 是 對(duì) 主文件中 同一個(gè)記錄 進(jìn)行的 但有兩點(diǎn)不同： 假設(shè)主文件中含有 n個(gè)記錄，事 務(wù)文件中含有 m個(gè)記錄，則對(duì)事務(wù)文 件進(jìn)行排序的時(shí)間復(fù)雜度為 O(mlogm）， 內(nèi)部歸并的時(shí)間復(fù)雜度為 O(m+n）， 則 總的內(nèi)部處理的時(shí)間為 O(mlogm+n） 。 從文件中 刪除 一個(gè)或一批記錄； 文件的操作方式可以 實(shí)時(shí)處理 或 批量處理。 記錄是文件中可以存取的 數(shù)據(jù) 的 基本單位 。 四、文件的邏輯結(jié)構(gòu) 指的是呈現(xiàn)在用 戶面前的文件中 記錄之間的邏輯 關(guān)系 ； 文件的物理結(jié)構(gòu) 指的是文 件中的邏輯記錄 在存儲(chǔ)器中的組 織方式 。 順序文件的插入、刪除和更新操 作在多數(shù)情況下都采用 批處理方式 。 “ 按關(guān)鍵字檢索 ” 將分兩步進(jìn)行：先查索引 ， 然后根據(jù)索引中指針?biāo)杆魅∮涗洠? ? ２ ． 插入記錄時(shí) ， “ 記錄 ” 插入在主文件的末尾 ， 而相應(yīng)的 “ 索引項(xiàng) ” 必須插入在索引的合適位置上 。 ２．動(dòng)態(tài)索引 用查找樹(shù)表作索引時(shí)，查找索引所 需訪問(wèn)外存次數(shù)的最大值恰為查找 樹(shù)的深度。 插入 : 修改 本磁道的索引項(xiàng) (包括基本索 引項(xiàng)和溢出索引項(xiàng) )。 … ... ... ... ... 索引集 B+樹(shù) 順序集 控制區(qū)域 控制區(qū)間 數(shù)據(jù)集 1．文件的結(jié)構(gòu) 2. 控制區(qū)間 是用戶進(jìn)行一次存取的 邏輯單位，可看成是一個(gè)邏輯磁道。 (因此，一般情況下，極少 產(chǎn)生需要分裂控制區(qū)域的情況 ) 其 優(yōu)點(diǎn)是 ：動(dòng)態(tài)地分配和釋放空間 , 不需 要重組文件；能較快地實(shí)現(xiàn)對(duì) “后插入”的記錄的檢索； 直 接 存 取 文 件 １． 和前幾節(jié)討論的文件組織方法 不同， 直接存取文件的特點(diǎn) 是，由 記錄的關(guān)鍵字 “ 直接”得到 記錄在外 存上的 映象地址 。 ３．文件的操作 ? 檢索 ： 只能進(jìn)行按關(guān)鍵字的查找 ，不能進(jìn)行順序查找。 。 ４． 優(yōu)點(diǎn)： 記錄隨機(jī)存放， 不需要 進(jìn)行 排 序；插入、刪除方便，存取速
黨政相關(guān)相關(guān)推薦
鄂ICP備17016276號(hào)-1