數據結構第十二章-文件-文庫吧
2025-07-20 16:56 本頁面
【正文】 其存儲位置相鄰 。 操作特點 ： ? 1． 便于 進行順序存取； ? 2． 不便于 進行直接存取 ， 為取第 i個記錄 ， 必須先讀出前 i1個記錄 ，對于磁盤上的等長記錄的連續(xù)文件可以進行折半查找； ? 3．插入新的記錄 只能 加在文件的末尾； ? 4．刪除記錄時， 只作標記 ； ? 5．更新記錄必須 生成新的文件 。 順序文件的插入、刪除和更新操 作在多數情況下都采用 批處理方式 。 此時，為處理方便，通常將順序文件 作成有序文件，稱作“ 主文件 ”，同時 將所有的操作作成一個“ 事務文件 ” （經過排序也成為有序文件），所謂 “批處理”，就是將這兩個文件 “合”為 一個新的主文件 。具體操作相當于 “歸并兩個有序表”。 （ 1）對于事務文件中的每個 操作 首先要判別其“ 合法性 ” （ 2）事務文件中可能存在 多個操 作 是 對 主文件中 同一個記錄 進行的 但有兩點不同： 假設主文件中含有 n個記錄，事 務文件中含有 m個記錄，則對事務文 件進行排序的時間復雜度為 O(mlogm）， 內部歸并的時間復雜度為 O(m+n）， 則 總的內部處理的時間為 O(mlogm+n） 。 批處理的時間分析 ： 假設對外存進行一次讀 /取為 s個 記錄，則整個批處理過程中 讀 /寫外存 的次數為 2?（ ?m/s?+?(m+n)/s?） （其中 s為對外存進行一次讀 /取的記錄 數）。 一 、 結構特點： ? 1． 索引文件由 “ 主文件 ” 和多級 “ 索引 ” 組成； ? 2． 索引中的每個記錄由 “ 關鍵字 ” 和 “ 指針 ” 組成； ? 3． 通常 ， 索引文件中的主文件是無序文件 ， 索引是 (按關鍵字有序 )的有序文件； ? 4． “ 索引 ” 是在輸入數據建立文件時自動生成 。初建時的 “ 靜態(tài)索引 ” 為無序文件 ， 經過排序后成為有序文件 。 索 引 文 件 二 、 操作的特點： ? １ ． 檢索方式為：直接存取和按關鍵字存取 。 “ 按關鍵字檢索 ” 將分兩步進行：先查索引 ， 然后根據索引中指針所指索取記錄； ? ２ ． 插入記錄時 ， “ 記錄 ” 插入在主文件的末尾 ， 而相應的 “ 索引項 ” 必須插入在索引的合適位置上 。 因此 ，最好在建索引表時留有一定 “ 空位 ” ； ? ３ ． 刪除記錄時 ， 僅需刪除索引表中相應的索引項即可； ? ４ ． 更新記錄時 ， 應將更新后的記錄插入在主文件的末尾 ， 同時修改相應的索引項 。 主 文 件 索 引 表 查 找 表 第 二 查 找表 第三查找表 … ... … ... … ...
黨政相關相關推薦
鄂ICP備17016276號-1