中國科大數(shù)據(jù)結(jié)構(gòu)(編輯修改稿)
2025-03-17 14:41 本頁面
【文章內(nèi)容簡介】 間復(fù)雜度為 O(m*logm)。內(nèi)部歸并的時間復(fù)雜度為 O(n＋ m)，則總的內(nèi)部處理時間為 O(m*logm＋ n)。 假設(shè)所有的輸入 /輸出都是通過緩沖區(qū)進行的，并假設(shè)緩沖區(qū)大小為 s（個記錄），則整個批處理過程中讀 /寫外存的次數(shù)為 ： 2??m/s?+?(m+n)/s?） 1213 中國科大《數(shù)據(jù)結(jié)構(gòu)》 索引文件 ? 基本術(shù)語 ? 索引表 ：除了文件本身（稱做數(shù)據(jù)區(qū)）之外，另建立的一張指示邏輯記錄和物理記錄之間一一對應(yīng)關(guān)系的表。 ? 索引項 ：索引表中的每一項?？偸前搓P(guān)鍵字（或邏輯記錄號）順序排列。 ? 索引文件 ：包括文件數(shù)據(jù)區(qū)和索引表兩大部分的文件。 ? 索引順序文件 ：數(shù)據(jù)區(qū)中的記錄也按關(guān)鍵字順序排列的文件。 ? 索引非順序文件 ：數(shù)據(jù)區(qū)中的記錄不按關(guān)鍵字順序排列的文件。 ? 稠密索引 ：由于數(shù)據(jù)文件中記錄不按關(guān)鍵字順序排列，則必須對每個記錄都建立一個索引項，如此建立的索引表稱為稠密索引。 ? 非稠密索引 ：數(shù)據(jù)文件中的記錄按關(guān)鍵字順序有序，則可對一組記錄建立一個索引項，這種索引表稱為非稠密索引。 1214 中國科大《數(shù)據(jù)結(jié)構(gòu)》 索引文件 ? 例如，下圖為兩個索引表的例子。 邏輯記錄號 存在標識 物理記錄號 0 1 1 1 1 7 2 0 null 3 1 10 關(guān)鍵字 ki 物理記錄號 101 1190 119 1178 123 1160 125 1142 物理地址 職工號 姓名 性別 工資 1142 125 張三 男 3500 1160 123 李四 女 4000 1178 119 王五 男 4500 1190 101 黃六 男 2800 1215 中國科大《數(shù)據(jù)結(jié)構(gòu)》 索引文件 ? 索引文件的存儲 索引文件在存儲器上分為兩個區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放索引表，數(shù)據(jù)區(qū)存放主文件。 ? 索引文件的建立 建立索引文件的過程： 1. 按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表。其中索引表中關(guān)鍵字是無序的 2. 待全部記錄輸入完畢后對索引表進行排序，排序后的索引表和主文件一起就形成了索引文件。 1216 中國科大《數(shù)據(jù)結(jié)構(gòu)》 索引文件 ? 檢索操作 檢索分兩步進行： 1. 將外存上含有索引區(qū)的頁塊送人內(nèi)存，查找所需記錄的物理地址 2. 將含有該記錄的頁塊送人內(nèi)存 ? 注意： ? 索引表不大時，索引表可一次讀入內(nèi)存，在索引文件中檢索只需兩次訪問外存：一次讀索引，一次讀記錄。 ? 由于索引表有序，對索引表的查找可用順序查找或二分查找 1217 中國科大《數(shù)據(jù)結(jié)構(gòu)》 索引文件 ? 索引文件的修改 ? 刪除操作：刪除一個記錄時，僅需刪去相應(yīng)的索引項； ? 插入操作：插入一個記錄時，應(yīng)將記錄置于數(shù)據(jù)區(qū)的末尾，同時再索引表中插入索引項； ? 更新操作：更新記錄時，應(yīng)將更新后的記錄置于數(shù)據(jù)區(qū)末尾，同時修改索引表中相應(yīng)的索引項。 ? 多級索引： 查找表：對索引表建立的索引。 通常最高可有四級索引： 數(shù)據(jù)文件 索引表 查找表 第二查找表 第三查找表 多級索引是靜態(tài)索引，各級索引均為順序表結(jié)構(gòu)。其結(jié)構(gòu)簡單，但修改很不方便，每次修改都要重組索引。因此，當數(shù)據(jù)文件在使用過程中記錄變動較多時，應(yīng)采用動態(tài)索引。如二叉排序樹（或二叉平衡樹）、 B樹以及鍵樹。 1218 中國科大《數(shù)據(jù)結(jié)構(gòu)》 ISAM和 VSAM文件 ISAM文件 ? ISAM文件定義：索引順序存取方法 ISAM(Indexed Sequential Access Method)是一種專為磁盤存取設(shè)計的文件組織方式。磁盤是以盤組、柱面和磁道三級地址存取的設(shè)備，可對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。 ? 磁道索引項： ?基本索引項： ?關(guān)鍵字：表示該磁道中最末一個記錄的關(guān)鍵字（在此為最大關(guān)鍵字）。 ?指針：指示該磁道中第一個記錄的位置。 ?溢出索引項： ?關(guān)鍵字：表示該磁道溢出的記錄的最大關(guān)鍵字。 ?指針：指示在溢出區(qū)中的第一個記錄。 1219 中國科大《數(shù)據(jù)結(jié)構(gòu)》 ISAM和 VSAM文件 ? 柱面索引項： ?關(guān)鍵字：表示該柱面中最末一個記錄的關(guān)鍵字（最大關(guān)鍵字）。 ?指針：指示該柱面上的磁道索引位置。 ? ISAM文件的組成 ISAM文件由多級主索引、柱面索引、磁道索引和主文件組成
范文總結(jié)相關(guān)推薦
鄂ICP備17016276號-1