【正文】 的表。 ? 索引文件的檢索方式為直接存取或按關鍵字存取 。 ? 索引文件的修改比較容易實現(xiàn) 。 ? 索引文件只能是磁盤文件 。 ? 主文件有序的索引文件稱為索引順序文件 ， 主文件無序的索引文件稱為索引非順序文件 。 ? 索引表都是有序的 ， 查找索引表時可以用折半查找法。 索引文件的特點和術(shù)語 2. 索引文件的術(shù)語 (1) 主文件、索引表和索引項 索引文件通常是在文件本身 (稱為主文件 )之外，另外建立一個索引表。索引指明邏輯記錄和物理記錄之間的一一對應關系。索引表和主文件一起構(gòu)成的文件稱作索引文件。 索引表中的每一項稱作索引項，索引項都是由主關鍵字和該關鍵字所在記錄的物理地址組成的。索引表必須按主關鍵字有序，而主文件本身可以按主關鍵字有序也可以無序。 (2) 索引順序文件和索引非順序文件 主文件本身按主關鍵字有序的索引文件稱為索引順序文件(Indexed Sequentail File)，主文件無序的索引文件稱為索引非順序文件 (Indexed NonSequentail File)。 索引順序文件的主文件中記錄按關鍵字有序，可對一組記錄建立索引項，這種索引表稱之為“稀疏索引”。索引非順序文件的主文件中記錄是無序的，則必須為每個記錄建立一個索引項，這樣建立的索引表稱為“稠密索引”。 索引文件的存儲 索引文件 在存儲器上分為兩個區(qū)：索引區(qū)和數(shù)據(jù)區(qū)，前者存放索引表，后者存放主文件。在建立文件過程中，按輸入記錄的先后次序建立數(shù)據(jù)區(qū)和索引表，這樣的索引表其關鍵字是無序的，待全部記錄輸入完畢后再對索引表進行排序，排序后的索引表和主文件一起就形成了索引文件。 表 數(shù)據(jù)主文件 物理地址 職工編號 姓 名 其 他 1001 103 張苗 1002 110 王庶 1003 107 張冶 1004 105 李明 1005 106 陳瑩 1006 112 劉冰 1007 114 李儷 1008 109 趙哲 索引文件的存儲 表 按主關鍵字排序后的索引表 索引文件的物理地址 關 鍵 字 主文件的物理地址 201 103 1001 201 105 1004 201 106 1005 202 107 1003 202 109 1008 202 110 1002 203 112 1006 203 114 1007 索引文件的檢索與修改 1. 索引文件的檢索 檢索分兩步進行，首先將存儲在外存上的索引表讀入內(nèi)存，查找所需記錄在主文件中的物理地址，然后再將含有該記錄的塊讀入內(nèi)存。 2. 在索引文件中插入記錄 在索引文件插入記錄時，將插入記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引項。 3. 刪除索引文件中的記錄 在索引文件刪除記錄時，要修改主關鍵字，同時修改索引表。 索引順序文件 ? ISAM文件 ? VSAM文件 ISAM文件 ISAM(Indexed Sequential Access Methed )是索引順序存取方法 。 它是一種專為磁盤存取設計的文件組織方式 ， 采用靜態(tài)索引結(jié)構(gòu) 。 1. ISAM文件的特點 ? ISAM文件的特點如下： ? ISAM是索引順序存取方法 ， 該方法專為磁盤存取設計。 ? ISAM文件是屬于索引順序文件的組織方式 。 ? ISAM文件由多級主索引 、 柱面索引 、 磁道索引和主文 件組成 。 ISAM文件 2. ISAM文件的組織結(jié)構(gòu) 磁盤 是以 盤面 、 柱面 和 磁道 三級地址存取的設備 ， 可對磁盤上的數(shù)據(jù)文件建立盤組 、 柱面和磁道多級索引 。 下面介紹在同一個盤組上建立的 ISAM文件的方法 。 ISAM文件由 多級主索引 、 柱面索引 、 磁道索引 和 主文件 組成 。 文件的記錄在同一盤組上存放時 ， 應先集中放在一個柱面上 ， 然后再順序存放在相鄰的柱面上 。 對同一柱面 ， 則應按盤面的次序順序存放 。 主索引是柱面索引的索引 。 若文件占用的柱面索引很大 ， 一級主索引也可采用多級主索引 。 若柱面索引較小時 ， 主索引可省略 。 主索引和柱面索引放在同一個柱面 (0號柱面 )上 。 ISAM文件 3. ISAM文件的檢索 提示： 在 ISAM文件上檢索記錄的步驟如下： (1) 從主索引出發(fā)，找到相應的柱面索引； (2) 從柱面索引找到記錄所在柱面的磁道索引； (3) 從磁道索引找到記錄所在磁道的起始地址，由此出發(fā)在該磁道上進行順序查找 , 直到找到為止。 ISAM文件 4. 在 ISAM文件中插入記錄 當插入新記錄時 ， 首先找到它應插入的磁道 。 若該磁道不滿 ， 則將新記錄插入該磁道的適當位置上即可；若該磁道已滿 ， 則新記錄直接插入到該磁道的溢出鏈表上 。 插入后 ， 可能要修改磁道索引中的基本索引項和溢出索引項 。 5. 刪除 ISAM文件中的記錄 刪除 ISAM文件中記錄時 ， 先找到待刪除的記錄 ， 在其存儲位置上作刪除標記 ， 不需要移動記錄或改變指針 。 在經(jīng)過多次的增刪后 ，再整理 ISAM文件 。 ISAM文件需要周期性地進行整理 。 把記錄讀入內(nèi)存重新排列 ， 復制成一個新的 ISAM文件 ， 填滿基本區(qū)而空出溢出區(qū) 。 VSAM文件 VSAM(Virtual Storage Access Method)是虛擬存儲存取方法 。 它是一種索引順序文件的組織方式 ， 采用 B+樹作為動態(tài)索引結(jié)構(gòu) 。 1. VSAM文件的特點如下： ? VSAM是虛擬存儲存取方法 ， 該方法為磁盤存取設計。 ? VSAM文件是屬于索引順序文件的組織方式 。 ? VSAM文件采用動態(tài)索引結(jié)構(gòu) 。 VSAM文件 2. 介紹 B+樹 VSAM文件 3. VSAM文件的查找 、 插入與刪除 對 B+樹進行查找有兩種運算 ， 一種是從最小關鍵字起進行順序查找；另一種是從根結(jié)點開始進行隨機查找 。 對 B+樹進行隨機查找 、 插入和刪除的過程與 B— 樹類似 。 只是在查找到非葉結(jié)點上的關鍵字等于給定值 ， 并不終止 ， 而是繼續(xù)向下查找 ，直到葉子結(jié)點 。 在 B+樹中 ， 不管查找成功與否 ， 每次查找都是走了一條從根到葉子結(jié)點的路徑 。 在 B+樹中 ， 每個葉子結(jié)點對應一個記錄 ， 它適宜于稠密索引 。 在 VSAM文件中刪除記錄時 ， 需將同一控制區(qū)間中比刪除記錄關鍵字大的記錄向前移動 ， 把空間留給以后插入的新記錄 。 若整個控制區(qū)間變空 ， 則回收作空閑區(qū)間用 ， 且需刪除順序集中相應的索引項 。 散 列 文 件 ? 散列文件的存儲 ? 散列文件的查找 ? 散列文件的刪除操作 散 列 文 件 散列文件是利用散列存儲方式組織的文件，亦稱直接存取文件。 散列文件的特點如下： ? 散列文件是使用散列技術(shù)組織成的文件。 ? 散列文件中的記錄通常是成組存放的，存放一組的存儲單位稱為桶。 ? 散列文件是隨機存放的，查找、存取和刪除方便。 散列文件的存儲 散列文件 的存儲類似于散列表 ， 根據(jù)文件中關鍵字的特點 ， 設計一個散列函數(shù)和處理沖突的方法 ， 將記錄散列到外存儲設備上 。 在散列文件中 ， 磁盤上的文件記錄成組存放 ， 將若干個記錄組成一個存儲單位 ， 這個存儲單位叫做桶 (Bucket)。 假如一個桶能存放 n個記錄 ， 當桶中已有 n個同義詞的記錄時 ， 存放第 n+1個同義詞會發(fā)生 “溢出 ” 。 處理溢出主要采用拉鏈法 。 當發(fā)生 “ 溢出 ” 時 ， 將第 n+1個同義詞存放到另一個桶中 ， 稱此桶為 “ 溢出桶 ” 。 稱前 n個同義詞存放的桶為 “ 基桶 ” 。 溢出桶和基桶大小相同 。 相互之間用指針相鏈接 。 圖 。 散列文件的存儲 圖 基桶和溢出桶 散列文件的查找 當在基桶中沒有找到待查記錄時 ，就沿著指針到所指溢出桶中進行查找。同一散列地址的溢出桶和基桶，在磁盤上的物理位置不要相距太遠。 對 散列文件進行查找時， 首先根據(jù)給定的關鍵字的值求出散列桶地址，將基桶的記錄讀入內(nèi)存，進行順序查找，若找到關鍵字等于給定值的記錄，則檢索成功；否則，讀入溢出桶的記錄繼續(xù)進行查找。 散列文件的刪除操作 刪除散列文件中的一個記錄 ， 是對被刪記錄作刪除標記 。 階段性地重新組織文件 。 散列文件的優(yōu)點 是文件隨機存放 ， 記錄不需進行排序 ， 插入 、 刪除操作方便 ， 存取速度快 ， 不需要索引 ， 節(jié)省存儲空間 。 其缺點是 不能進行順序存取 ， 只能按關鍵字隨機存取 ， 不能進行復合詢問 ， 在經(jīng)過多次插入 、 刪除后 ， 造成文件結(jié)構(gòu)不合理 ， 需要重新組織文件 。 多關鍵字文件 ? 多重表文件的概念 ? 倒排文件 多關鍵字文件 提示：多關鍵字文件有以下特點 : ① 多關鍵字文件不僅對主關鍵字索引 ， 還對其余的次關鍵字進行索引 。 ② 多重表文件是對數(shù)據(jù)文件中的主關鍵字和次關鍵字分別建立索引 ， 索引是用指針 構(gòu)成鏈表 。 ③ 倒排文件也是對數(shù)據(jù)文件中的主關鍵字和次關鍵字分別建立索引 ， 但索引是用倒 排表 。 同一類關鍵字用一個倒排表 ， 一個倒排表中按關鍵字標出有序的記錄號 。 多重表文件的概念 多重表文件 的主文件是一個順序文件 ， 每個需要查詢的次關鍵字建立一 個索引 ， 并將具有相同次關鍵字的記錄鏈接成一個鏈表 ， 將此鏈表的頭指針 、 鏈表長度及次關鍵字作為索引表的一個索引項 。 表 。 在這個多重表文件中 ， 主關鍵字是職工號 ， 職務和工資級別也是要進行查找的次關鍵字 。 在主文件中為關鍵字 “ 職務 ” 設立了鏈接字段 ， 該字段將相同職務的記錄鏈在一起 。 在主文件中 為關鍵字 “ 工資級別 ” 設立了鏈接字段 ， 該字段將相同的工資級別記錄鏈在一起 。 表 ， 表 。 有了這些索引 ， 便易于處理各種有關次關鍵字的查詢 。 例如 ， 要查詢所有軟件人員， 則只需在職務索引中先找到次關鍵字 “ 軟件人員 ” 的索引項 ， 然后從它的頭指針出發(fā) ， 列出該鏈表上所有的記錄即可。 若要查詢工資級別為 11的所有硬件人員 ， 則既可以從職務索引的 “ 硬件人員 ” 的頭指針出發(fā) ， 也可以從工資級別索引的 “ 11” 的頭指針出發(fā) ， 讀出鏈表上的每個記錄 ， 判定它是否滿足查詢條件 。 多重表文件的概念 表 9 . 4 多重表的主文件 物理地址 職 工 號 姓 名 職 務 工資級別 職 務 鏈 工 資 鏈 101 03 丁麗 硬件人員 12 110 ∧ 102 10 王明 硬件人員 11 1 07 106 103 07 張華 軟件人員 13 108 107 104 05 李征 打字人員 14 105 110 105 06 劉建 打字人員 13 ∧ 103 106 12 趙偉 軟件人員 11 ∧ ∧ 107 14 陳辰 硬件人員 13 ∧ ∧ 108 09 馬越 軟件人員 10 106 ∧ 1 09 01 鄭忠 打字人員 14 104 104 110 11 林業(yè) 硬件人員 14 10 2 ∧ 多重表文件的概念 表 9 . 5 職務索引 次關鍵字 第一人的頭指針 人 數(shù) 硬件人員 101 4 軟件人員 103 3 打字人員 109 3 表 9 . 6 工資級別索引 次關鍵字 第一人的頭指針 人 數(shù) 10 108 1 11 1 02 2 12 101 1 13 105 3 14 109 3 倒排文件 1. 倒排文件的概念 倒排文件中的次關鍵字索引稱作倒排表。相同次關鍵字的不同記錄之間不進行鏈接，而是在倒排表中列出具有該相同次關鍵字記錄的各存儲地址。主文件和倒排表一起就構(gòu)成倒排文件。例如，對表 ，表 ，表 。 2. 倒排表的查找 a在一般的文件組織中 ， 是先找到記錄 ， 然后再找該記錄所含的各個次關鍵字 。 而倒排文件中 ， 是先給定次關鍵字 ， 然后查找含有該次關鍵字的各個記錄 。 對倒排文件的查找次序正好與一般文件的查找次序相反 ， 因此稱之為 “ 倒排 ” 文件 。 倒排文件