【文章內容簡介】 sequential access method） 即索引順序存取方法 ， 是一種專為磁盤存取設計的文件組織方式 。 ?由于磁盤是以盤組 、 柱面和磁道三級地址存取的設備 ， 所以可以對磁盤上的數(shù)據(jù)文件建立盤組 、 柱面和磁道三級索引 。 ?文件的記錄在同一盤組上存放時 ， 應先集中放在一個柱面上 ， 然后再順序存放在相鄰柱面上；對同一柱面 ， 則應按盤面的次序順序存放 。 ISAM文件結構舉例 ISAM文件（續(xù)） ?在一個磁盤組上的 ISAM文件 ， 每個柱面建立一個磁道索引 ， 每個磁道索引項由基本索引項和溢出索引項兩部分組成 ， 每一部分都包括關鍵字和指針兩個域 ， 前者表示該磁道中最大關鍵字 ， 后者指示該磁道中第一個記錄的位置 。 ?柱面索引的每一個索引項也由關鍵字和指針兩部分組成 ， 前者表示該柱面中的最大關鍵字 ， 后者指示該柱面上的磁道索引位置 。 ?柱面索引存放在某個柱面上 ， 若柱面索引較大占多個磁道時 ， 則可建立柱面索引的一個主索引 。 ISAM文件（續(xù)） ? 在 ISAM文件上檢索記錄時 ， 先從主索引出發(fā)找到相應的柱面索引 ， 再從柱面索引找到記錄所在柱面的磁道索引 ， 最后從磁道索引找到記錄所在磁道的第一個記錄的位置 ， 由此出發(fā)在該磁道上進行順序查找直至找到為止；反之 ， 若找遍磁道而不存在此記錄 ， 則表明文件中無此記錄 。 ?在前例中為每個柱面開辟了一個溢出區(qū) ， 并在磁道索引項中有溢出索引項 （ 后面兩個域 ） ， 這是為插入記錄所設置的 。 ISAM文件（續(xù)） ?由于 ISAM文件中記錄是按關鍵字順序存放的 ， 在插入一個記錄時需要向后移動記錄 ， 并將同一磁道上的最后一個記錄移至溢出區(qū) ， 同時修改磁道索引項 。除了為每個柱面設置一個溢出區(qū)的方法外 ， 還可只集中設置一個大的公共溢出區(qū)；也可以既為每個柱面設置溢出區(qū) ， 同時也設置了一個公共溢出區(qū) ， 在柱面溢出區(qū)滿后再使用公共溢出區(qū) 。 ?ISAM文件中刪除記錄比較簡單 ， 只需作刪除標記而不用移動記錄或改變指針 。 當然應該周期性地把記錄讀入內存重排整理 ISAM文件 ， 以盡量填滿基本區(qū)而空出溢出區(qū) 。 ? VSAM（ virtual storage access method） 即虛擬存儲存取方法 。 它利用了操作系統(tǒng)的虛擬存儲器的功能 ， 使用戶只需考慮控制區(qū)間等邏輯存儲單位 ， 而無需考慮其物理位置以及何時對外存儲器進行讀寫操作 ，給用戶使用文件提供了方便 。 ? VSAM文件的結構由 索引集 、 順序集 和 數(shù)據(jù)集 三部分組成 。 ?數(shù)據(jù)集存放文件的所有記錄 ， ?順序集和索引集構成一棵 B+樹是文件的索引部分 。 數(shù)據(jù)集中的一個結點稱為控制區(qū)間 （ control interval） ， 它由一組連續(xù)的存儲單元組成 ， 是讀寫操作的基本單位 。 VSAM文件的結構舉例 VSAM文件（續(xù)） ?同一文件上的控制區(qū)間大小相同 ， 含有一個或多個按關鍵字升序排列的記錄 。 ?順序集中的一個結點 ， 存放著若干相鄰控制區(qū)間的索引項 ， 每個索引項由控制區(qū)間中的最大關鍵字和指向該控制區(qū)間的指針組成 。 ?順序集中的一個結點連同其下層所有控制區(qū)間形成的整體稱作控制區(qū)域 （ control range） 。 ?順序集中的結點之間用指針相鏈接；在它們上層的結點又以它們?yōu)榛A形成索引 ， 并逐級向上建立索引 ，形成 B+樹的非終端結點 。 VSAM文件（續(xù)） ? 對 VSAM文件中記錄的檢索 ， 既可以從最高層的索引逐層往下按關鍵字進行查找 ， 又可以在順序集中沿著指針鏈順序查找 。 ?VSAM文件沒有專門的溢出區(qū) ， 但可利用控制區(qū)間中的空隙或控制區(qū)域中空的控制區(qū)間來插入記錄 （ 即在B+樹上插入記錄 ） 。 ?在控制區(qū)間中插入記錄時 ， 為了保證區(qū)間內記錄按關鍵字有序需要移動記錄；而當區(qū)間中記錄已滿時 ，為了插入記錄需要將區(qū)間分裂 。 ?在 VSAM文件中刪除記錄時 ， 也是需要移動記錄的 。 VSAM文件（續(xù)） ? VSAM文件占有較多的存儲空間 ， 存儲空間的利用率一般也只能保持在 75%左右 。 ?然而它具有許多優(yōu)點 ， 如動態(tài)地分配和釋放存儲空間 ， 無需像 ISAM文件那樣定期重排文件 ， 并能較快地執(zhí)行插入操作和保持較高的檢索效率 。 ? VSAM文件通常作為組織大型索引順序文件的標準形式 。 ?散列文件 （ Hash file） 也稱作直接存取文件 ， 它是利用哈希方法組織的數(shù)據(jù)文件；即根據(jù)某個哈希函數(shù)和一定的沖突消解策略而得到的存放在外存儲器上的散列表 。 ? 與哈希表不同的是 ， 磁盤上的文件記錄通常是成組存放的 。 ?若干個記錄組成一個存儲單位 ， 在散列文件中這個存儲單位稱作桶 。 ?一個桶能存放的邏輯記錄的總數(shù)稱作桶的容量 。 假如桶的容量為 m， 即 m個同義詞的記錄可以存放在同一地址的桶中 ， 當?shù)?m+1個同義詞記錄出現(xiàn)時則發(fā)生溢出 。 處理溢出也可采用哈希表中的各種處理沖突的方法 ， 但對散列文件主要是采用鏈地址法消解沖突 。 散列文件（續(xù)） ?當發(fā)生溢出時 ， 需要將第 m+1個同義詞存放到另一個桶中 ， 通常稱作 “ 溢出桶 ” ；相應地把存放前 m個同義詞的桶稱作 “ 基桶 ” 。 ?溢出桶可以有多個 ， 它們和基桶大小相同 ， 相互之間用指針相鏈接 。 當在基桶中沒有檢索到待查記錄時 ， 就順指針所指到溢出桶中去檢索； ?因此 ， 同一散列地址的溢出桶和基桶在磁盤上的物理位置不要相距太遠 ， 最好是在同一柱面上 。 散列文件舉例 ?例如 ， 某文件有 20個記錄 ， 其關鍵字分別為 2 1 19 8 2 1 5 6 1 2 3 8 6 17 3 35。 用除留余數(shù)法選定哈希函數(shù) H(key)= key%7，用鏈地址法消解地址沖突 。 桶的容量 m=3， 基桶個數(shù) b=7，由此得到的散列文件如下圖所示 。 散列文件（續(xù)） ? 在散列文件中檢索時： ?先根據(jù)給定的關鍵字值 k求得哈希地址 ， 即基桶號； ?然后將基桶的記錄讀入內存進行順序檢索 ， 若找到關鍵字值為 k的記錄則檢索成功； ?若基桶中雖無關鍵字值為 k的記錄但指針域非空 ， 需要把溢出桶中的記錄讀入內存繼續(xù)檢索 ， 直到檢索成功或檢索不成功 。 ?檢索不成功的情況為基桶沒有填滿記錄 ， 或雖填滿但指針域為空 （ 無溢出桶 ） ， 或雖有溢出桶但仍未找到關鍵字為 k的記錄 。 散列文件（續(xù)） ?在散列文件中 ， 裝填因子為 ， 其中 n為文件中的記錄數(shù) ，b為桶數(shù) ， m為桶的容量；而存取桶數(shù)的期望值為 。 如上例 ， 。 在散列文件中 ， 刪除記錄時僅需對被刪記錄作一刪除標記即可 。 ?總之 ， 散列文件的 優(yōu)點 是插入和刪除方便 ， 存取速度比索引文件要快；不需要索引區(qū) ， 節(jié)省存儲空間 。 其 缺點 是不能進行順序存取 ， 只能按關鍵字隨機存取 ， 且詢問方式只有簡單詢問；在經過多次的插入和刪除之后 ， 也可能造成溢出桶滿而基桶內多數(shù)為被刪除記錄的不合理文件結構 ， 亦需對文件進行重新整理 。 ?多關鍵字文件 （ multiple key file） 的特點是 ，在對文件進行檢索操作時不僅對主關鍵字進行簡單詢問 ， 還經常需要對次關鍵字進行其它類型的詢問檢索 。 ?因此 ， 對多關鍵字文件還需要建立一系列的次關鍵字索引 。 次關鍵字索引和主關鍵字索引所不同的是 ， 每個索引項應包含次關鍵字和具有同一次關鍵字的多個記錄的主關鍵字或物理記錄號 。 ?多重表文件 和 倒排文件 是常見的兩種多關鍵字文件組織方法 。 多關鍵字文件（續(xù)） ? 多重表文件 （ multilist file） 的 特點 是 ， 記錄按主關鍵字的順序構成一個串聯(lián)文件 ， 并建立主關鍵字索引 （ 稱為主索引 ） ；對每一個次關鍵字項建立次關鍵字索引 （ 稱為次索引 ） ， 所有具有同一次關鍵字的記錄構成一個鏈表 。 ?主索引為非稠密索引 ， 一組記錄建立一個索引項；次索引為稠密索引 ， 每個記錄建立一個索引項 ，每個索引項包括次關鍵字 、 頭指針和鏈表長度 。 多關鍵字文件舉例 ?例如 ， 下圖所示為一個多重表文件 。 其中工號為主關鍵字 ， 記錄按工號順序鏈接 。 多關鍵字文件舉例（續(xù)） ?對工號非稠密索引分成三個子鏈表 ， 其索引如下圖 (b)所示 ，索引項中的主關鍵字為各組中關鍵字的最大值 。 職稱和專業(yè)是兩個次關鍵字項 ， 其索引分別如下圖 (c)和 (d)所示 ， 具有相同次關鍵字值的記錄鏈接在同一鏈表中 。 多關鍵字文件（續(xù)） ?有了這些次關鍵字索引 ， 根據(jù)關鍵字值找到鏈表頭指針 ， 然后從頭指針出發(fā)可列出鏈表中所有記錄 。比如查詢數(shù)學專業(yè)的教授 ， 可以專業(yè)索引表中找到“ 數(shù)學 ” 的頭指針和表長 ， 逐一讀取記錄查看哪些記錄的職稱為教授即可 。 此查詢也可從職稱索引入手進行 。 當然 ， 較好的方法是先讀長度較短的鏈表中的記錄 。 ? 在多重表文件中插入一個記錄是容易的 ， 只要修改指針將記錄插在鏈表的頭指針之后即可 。 然而要刪去一個記錄卻很繁瑣 ， 需要在每個次關鍵字的鏈表中刪去該記錄 。 多關鍵字文件（續(xù)） ? 倒排文件 （ inverted file） 和 多重表文件 的區(qū)別在于次關鍵字索引的結構不同 。 倒排文件的次關鍵字索引稱為 倒排表 ， 在倒排表的索引項中沒有頭指針和鏈長度 ， 而是直接用一個項存放具有同一關鍵字的所有記錄的物理記錄號或主關鍵字值 。 值得注意的是 ， 倒排表中具有同一次關鍵字的記錄號是有序排列的 。 上例的倒排表如下圖所示： 多關鍵字文件（續(xù)） ?倒排表作索引的 好處 在于檢索記錄較快 。 特別是對某些詢問 ， 不用讀取記錄就可得到答案 。 例如上例查詢數(shù)學專業(yè)教授 ， 只要將 “ 數(shù)學 ” 索引中的記錄號和 “ 教授 ” 索引中的記錄號求集合的交集運算就可以了 ， 即 {2， 5， 9}∩{2， 6}={2}就得到記錄號為 2者便是數(shù)學教授 。 ? 在插入和刪除記錄時 ， 倒排表也要進行相應修改；需要移動索引項中記錄號以保持其有序排列 。 若數(shù)據(jù)文件是索引順序文件 （ 如 ISAM文件 ） ， 倒排表中應存放記錄的主關鍵字而不是物理記錄號 。 ? 倒排文件的 缺點 是維護困難 。 同一倒排表中各項長度不同 ，不同倒排表的長度也不同 ， 這些都給倒排文件的維護帶來一定的困難 。 大批量數(shù)據(jù)的組織策略 文件的組織 數(shù)據(jù)庫技術 文件系統(tǒng)的缺陷 ?利用文件組織大批量數(shù)據(jù)是數(shù)據(jù)組織中行之有效的方法 ， 然而 ，文件系統(tǒng)也存在著一些明顯的缺陷 。 如： ?數(shù)據(jù)冗余大 。 因為每個文件都是為特定用途設計的 ， 因此會造成同樣的數(shù)據(jù)在多個文件中的重復存儲 。 ?數(shù)據(jù)的不一致性 ， 這往往是由于數(shù)據(jù)冗余所造成的；在數(shù)據(jù)更新時 ， 稍有不慎就會造成同一數(shù)據(jù)在不同文件中的不一致 。 ?程序和數(shù)據(jù)之間的獨立性差 。 應用程序依賴于文件的存儲結構 ， 使得在對文件的存儲結構進行修改時 ， 必須修改應用程序 。 ?數(shù)據(jù)聯(lián)系弱 。 文件與文件之間是獨立的 ， 文件之間的聯(lián)系必須通過程序來構造 。 因此 ， 文件系統(tǒng)是一個不具有彈性的無結構的數(shù)據(jù)集合 ， 難以反應客觀世界中事物之間的聯(lián)系 。 數(shù)據(jù)庫技術誕生 ?為了克服上述文件系統(tǒng)的不足 ， 20世紀 60年代后期開始誕生了解決大批量數(shù)據(jù)組織和管理的數(shù)據(jù)庫技術 。 數(shù)據(jù)庫技術誕生的標志性事件是： ?1968年研制成功 ， 1969年形成產品的美國 IBM公司的數(shù)據(jù)庫管理系統(tǒng) IMS（ information management system） 的問世 ， 該系統(tǒng)支持的是層次數(shù)據(jù)模型 。 ?美國數(shù)據(jù)系統(tǒng)語言協(xié)會 CODASYL（ conference on data system language） 下屬的數(shù)據(jù)庫任務組 DBTG（ database task group） 對數(shù)據(jù)庫方法進行了系統(tǒng)的研究 ， 在 20世紀 60年代末期和 70年代初期發(fā)表了若干個報告 （ 稱為 DBTG報告 ） ， 該報告建立了數(shù)據(jù)庫的許多概念 、 方法和技術 。 DBTG所提議的方法是基于網狀數(shù)據(jù)模型的 。 ?從 1970年起 ， IBM的研究員 ， 提出了數(shù)據(jù)庫的關系模型 ， 開創(chuàng)了數(shù)據(jù)庫關系方法和關系數(shù)據(jù)理論的研究 ， 為關系數(shù)據(jù)庫的發(fā)展和理論研究奠定了基礎 。 數(shù)據(jù)庫技術 ? 數(shù)據(jù)庫技術發(fā)展到現(xiàn)在 ， 已經是一門非常成熟的技術 ， 作為算法與數(shù)據(jù)結構課程的后續(xù)課程 。 ? 概括地講 ， 數(shù)據(jù)庫具有如下基本特征： ?數(shù)據(jù)庫是相互關聯(lián)的數(shù)據(jù)的集合 。 ?數(shù)據(jù)庫用綜合的方法組織數(shù)據(jù) ， 并保證盡可能高的訪問效率 。 ?數(shù)據(jù)庫具有較小的數(shù)據(jù)冗余 ， 可供多個用戶共享 。