1、數(shù)據(jù)結(jié)構(gòu)第8章 文件山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第1頁，共19頁。本章內(nèi)容文件概述順序文件直接文件索引文件倒排文件8/5/20222山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第2頁，共19頁。 1 文件概述一、 文件的概念域（Field）是數(shù)據(jù)的基本單位，又稱為字段或數(shù)據(jù)項(xiàng)。域通常用于描述數(shù)據(jù)對(duì)象的屬性，不可分割的域含有一個(gè)簡單的值。記錄（Record）是一組相關(guān)域的集合，它可以看作是應(yīng)用程序的一個(gè)單元。根據(jù)設(shè)計(jì)的不同，記錄可以是固定長或可變長。如果記錄中某些域的長度是可變的，則該記錄就是可變長度的記錄。文件（File）是由大量性質(zhì)相同的記錄組成的集合，它被應(yīng)用程序看作是一個(gè)實(shí)體。文件有一個(gè)惟一的名

2、字，可以被創(chuàng)建或刪除。數(shù)據(jù)庫（Database）是一組相關(guān)的數(shù)據(jù)，它的本質(zhì)特征是數(shù)據(jù)單元間存在明確的關(guān)系，并且設(shè)計(jì)成可供許多不同的應(yīng)用程序使用。數(shù)據(jù)庫自身是由一種或多種不同類型的文件組成。8/5/20223山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第3頁，共19頁。二、文件的邏輯結(jié)構(gòu)文件的邏輯結(jié)構(gòu)是用戶能觀察到的，可加以處理的數(shù)據(jù)集合。 文件的邏輯結(jié)構(gòu)分兩種形式：一種是流式文件，另一種是記錄式文件。 記錄成組與分解處理流式文件指文件內(nèi)的數(shù)據(jù)不再組織成記錄，只是連續(xù)的字符序列。 記錄式文件是指若干邏輯記錄（按信息在邏輯上的獨(dú)立含意劃分的一個(gè)信息單位）的集合。 邏輯記錄1邏輯記錄2邏輯記錄3物理記錄邏輯記錄

3、用戶緩沖區(qū)系統(tǒng)緩沖區(qū)8/5/20224山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第4頁，共19頁。三、 文件的物理結(jié)構(gòu)構(gòu)造文件物理結(jié)構(gòu)的方法：計(jì)算法和指針法。四、文件的操作記錄檢索記錄插入記錄刪除記錄更新文件排序?qū)崿F(xiàn)原理是設(shè)計(jì)映射算法，通過對(duì)記錄關(guān)鍵字的計(jì)算轉(zhuǎn)換成對(duì)應(yīng)的物理塊地址，從而找到所需記錄。 置專門指針，指明相應(yīng)記錄的物理地址或表達(dá)各記錄之間的關(guān)聯(lián)。 8/5/20225山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第5頁，共19頁。 2 順序文件分塊塊插值查找 算法：（1）初始化 low = 1；high=N。（2）反復(fù)執(zhí)行下面操作，直到highlow成立 (a)i = (b)讀取第i個(gè)物理塊，獲得Li和Hi

4、 (c)分下面三種情況執(zhí)行LiKHi時(shí)，查找成功，第i個(gè)物理塊即為所求;KHi時(shí)，執(zhí)行l(wèi)ow = i+1;KLi時(shí)，執(zhí)行high = i-1; (3)查找失敗，算法結(jié)束。low:查找范圍內(nèi)的最小物理塊號(hào)；high: 查找范圍內(nèi)的最大物理塊號(hào)；Li：第i個(gè)物理塊內(nèi)的記錄的最小關(guān)鍵字；Hi：第i個(gè)物理塊內(nèi)的記錄的最大關(guān)鍵字 8/5/20226山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第6頁，共19頁。 3 直接文件（散列文件）直接文件：記錄在介質(zhì)上的位置是通過對(duì)記錄的鍵施加變換而獲得相應(yīng)地址。一、桶散列 （靜態(tài)散列）基本思想： 把文件的記錄通過散列函數(shù)H分別存儲(chǔ)在許多存儲(chǔ)桶中，每個(gè)存儲(chǔ)桶包含一個(gè)或多個(gè)物理塊

5、，一個(gè)存儲(chǔ)桶中的物理塊用指針連接形成鏈表，每個(gè)物理塊存放若干記錄。如果一個(gè)桶溢出，即它容納不下所有屬于它的記錄，那么可以給該存儲(chǔ)桶增加一個(gè)溢出塊鏈表以存放更多的記錄。 操作：以i=H(key) 為依據(jù)完成查找、插入、刪除、更新等操作。8/5/20227山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第7頁，共19頁。 3 直接文件（散列文件）二、 可擴(kuò)展散列（動(dòng)態(tài)散列文件）可散列文件的組織方式：散列函數(shù)H把關(guān)鍵字key轉(zhuǎn)換成一個(gè)定長的二進(jìn)制位串k（偽關(guān)鍵字），取k前i位二進(jìn)制數(shù)（設(shè)為k）作為存儲(chǔ)桶目錄表中的目錄項(xiàng)號(hào)，即表示目錄表中第k個(gè)目錄項(xiàng)，目錄項(xiàng)中的指針指向的物理塊就是具有關(guān)鍵字key的記錄所在的物理塊；

6、存儲(chǔ)桶目錄項(xiàng)的個(gè)數(shù)為2i。 i確定記錄在該物理塊中的成員資格 的二進(jìn)制位串的位數(shù)8/5/20228山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第8頁，共19頁。查找操作 查找關(guān)鍵字為K的記錄，先計(jì)算出H（K），取出這一二進(jìn)制位串的前i位（設(shè)為k），并找到序號(hào)為k的存儲(chǔ)桶目錄項(xiàng)。根據(jù)此目錄項(xiàng)的指針找到物理塊B。插入操作 為了插入關(guān)鍵字為K的記錄，先其所在的物理塊，若該物理塊中有空閑空間，我們就把新記錄存入，插入操作完成。如果B中沒有空閑空間，那么根據(jù)數(shù)字i的不同有兩種可能： 如果j=i，那么我們必須先將i加1，使存儲(chǔ)桶目錄項(xiàng)個(gè)數(shù)增加一倍，即2i+1。在新存儲(chǔ)桶目錄表中，序號(hào)為k0和k1（分別用0和1擴(kuò)展k）

7、的項(xiàng)都指向原k目錄項(xiàng)指向的物理塊。8/5/20229山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第9頁，共19頁。插入操作如果ji（j的值可在每個(gè)物理塊的“小凸塊”中找到），那么不必對(duì)存儲(chǔ)桶目錄表做任何變化。按下面規(guī)則操作：（a）將物理塊B分裂成兩個(gè)存儲(chǔ)塊。（b）根據(jù)記錄關(guān)鍵字的散列值的第j+1位，將B中的記錄分配到這兩個(gè)存儲(chǔ)塊中，該位為0的記錄繼續(xù)保留在B中，而該位為1的記錄放入到新塊中。（c）把j+1存儲(chǔ)到兩個(gè)存儲(chǔ)塊的“小凸塊”中，以標(biāo)明用于確定成員資格的二進(jìn)制位數(shù)。（d）調(diào)整存儲(chǔ)桶目錄項(xiàng)中指針，使原來指向塊B的指針項(xiàng)指向塊B或新塊，這由記錄關(guān)鍵字的散列值的第j+1位決定。注意，分裂B可能解決不了問題

8、，因?yàn)橛锌赡軌KB中所有記錄將分配到由B分裂成的兩個(gè)存儲(chǔ)塊的其中一塊中。如果這樣，我們需要對(duì)仍太滿的塊用下一個(gè)更大的j值重復(fù)上述操作。 8/5/202210山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第10頁，共19頁。插入關(guān)鍵字為0000、0111的記錄 再插入關(guān)鍵字值為1000的記錄 8/5/202211山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第11頁，共19頁。 4 索引文件索引文件的結(jié)構(gòu)二級(jí)索引、多級(jí)索引記錄1關(guān)鍵字地址記錄2記錄N文件名索引表塊塊塊數(shù)據(jù)區(qū)索引區(qū)查找稠密索引：每個(gè)數(shù)據(jù)記錄，在索引表里都有一個(gè)索引項(xiàng) 稀疏索引：每一組數(shù)據(jù)記錄僅有一索引項(xiàng) 8/5/202212山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第1

9、2頁，共19頁。 5 索引順序文件 一、ISAM專為磁盤存取設(shè)計(jì)的文件組織方式，是一種靜態(tài)索引結(jié)構(gòu)。 ISAM采用多級(jí)索引：主索引、柱面索引、磁道索引。 指示查找鍵字為99記錄路徑8/5/202213山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第13頁，共19頁。二、VSAM總體結(jié)構(gòu)記錄存放區(qū)順序集：存放每個(gè)控制區(qū)間的索引項(xiàng)（該控制區(qū)間中的最大關(guān)鍵字和指向控制區(qū)間的指針）。若干相鄰控制區(qū)間的索引項(xiàng)構(gòu)成順序集中的一個(gè)結(jié)點(diǎn)，相當(dāng)于B+樹的一個(gè)葉子結(jié)點(diǎn) 。8/5/202214山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第14頁，共19頁。VSAM中插入操作 （1）調(diào)用B+樹的查找算法，確定該記錄應(yīng)插入的順序集結(jié)點(diǎn)，進(jìn)而確定

10、該記錄應(yīng)插入的控制區(qū)間及相應(yīng)位置。 （2）如果該控制區(qū)間中自由空間足以容納該記錄，則將要插入位置右面的記錄右移騰出空間插入該記錄，并在相應(yīng)位置建立控制信息。 （3）如果自由空間不夠，則檢查該控制區(qū)間所在的控制域中是否還有空閑的控制區(qū)間，若有，則將控制區(qū)間分裂，將其中的近似一半的記錄移動(dòng)到一個(gè)空閑的控制區(qū)間中。如無，則進(jìn)行一次控制域的分裂。 8/5/202215山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第15頁，共19頁。插入ARS、BIT插入BEC8/5/202216山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第16頁，共19頁。 6 倒排文件關(guān)鍵字指針組倒排表具有這種倒排表形式的索引文件稱為倒排文件（Revers

11、e File） 具有相同關(guān)鍵字的記錄 倒排表作索引的好處在于檢索記錄較快。特別是對(duì)某些詢問，不用讀取記錄，就可得到解答。 倒排文件的缺點(diǎn)是維護(hù)困難。 8/5/202217山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第17頁，共19頁。 7 本章小結(jié)1文件概述（1）文件是由大量性質(zhì)相同的記錄組成的集合，它被應(yīng)用程序看作是一個(gè)實(shí)體。（2）文件的邏輯結(jié)構(gòu)是用戶能觀察到的，可加以處理的數(shù)據(jù)集合。文件的邏輯結(jié)構(gòu)分兩種形式：一種是流式文件，另一種是記錄式文件。（3）文件物理結(jié)構(gòu)的構(gòu)造方法：（1）計(jì)算法，通過對(duì)記錄關(guān)鍵字的計(jì)算轉(zhuǎn)換成對(duì)應(yīng)的物理塊地址，從而找到所需記錄。（2）指針法，這類方法設(shè)置專門指針，指明相應(yīng)記錄的物

12、理地址或表達(dá)各記錄之間的關(guān)聯(lián)。索引文件、索引順序文件、倒排文件等均屬此類。（4）對(duì)文件的操作主要有記錄的檢索、插入、刪除、更新和文件排序。2順序文件（1）將一個(gè)文件中邏輯上連續(xù)的信息存放到存儲(chǔ)介質(zhì)的依次相鄰的塊上便形成順序結(jié)構(gòu)，這類文件叫順序文件，又稱連續(xù)文件。（2）掌握順序文件上的物理塊插值查找。8/5/202218山東大學(xué)管理學(xué)院 戚桂杰 姚云鴻第18頁，共19頁。 7 本章小結(jié)3直接文件（散列文件）（1）在直接存取存儲(chǔ)設(shè)備上，記錄的關(guān)鍵字與其地址之間可以通過某種方式建立對(duì)應(yīng)關(guān)系，利用這種關(guān)系實(shí)現(xiàn)存取的文件叫直接文件。（2）桶散列方法的基本思想是把文件的記錄通過散列函數(shù)H分別存儲(chǔ)在許多存儲(chǔ)桶中，每個(gè)存儲(chǔ)桶包含一個(gè)或多個(gè)物理塊，一個(gè)存儲(chǔ)桶中的物理塊用指針連接形成鏈表，每個(gè)物理塊存放若干記錄。4索引文件（1）索引結(jié)構(gòu)是實(shí)現(xiàn)非連續(xù)存儲(chǔ)的另一種方法，適用于數(shù)據(jù)記錄保存在隨機(jī)存取存儲(chǔ)設(shè)備上的文件。索引文件在文件存儲(chǔ)器上分兩個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。（2）索引文件中的索引項(xiàng)可以分為兩類：稠密索引和稀疏索引。5索引順序文件（1）索引順序存取方式ISAM是一種專為磁盤存取設(shè)計(jì)的文件組織方式，是一種靜