第九章文件、外部排序與搜索

主講人：劉曉靜青海大學(xué)計(jì)算機(jī)技術(shù)與應(yīng)用系第九章文件、外部排序與搜索主要內(nèi)容9.1主存儲(chǔ)器和外存儲(chǔ)器9.2文件組織9.3多級(jí)索引結(jié)構(gòu)9.1主存儲(chǔ)器和外存儲(chǔ)器外存儲(chǔ)器與內(nèi)存儲(chǔ)器相比，優(yōu)點(diǎn)是：價(jià)格較低永久的存儲(chǔ)能力缺點(diǎn)：訪問外存儲(chǔ)器上的數(shù)據(jù)比訪問內(nèi)存要慢5～6個(gè)數(shù)量級(jí)要求我們?cè)陂_發(fā)系統(tǒng)時(shí)必須考慮如何使外存訪問次數(shù)達(dá)到最少。磁盤（disc）磁盤存儲(chǔ)器通常稱為直接存取設(shè)備，或隨機(jī)存取設(shè)備，它訪問外存上文件的任一記錄的時(shí)間幾乎相同。磁盤存儲(chǔ)器可以順序存取，也可以隨機(jī)存取。目前使用較多的是活動(dòng)臂硬盤組：若干盤片構(gòu)成磁盤組，它們安裝在主軸上，在驅(qū)動(dòng)裝置的控制下高速旋轉(zhuǎn)。除了最上面一個(gè)盤片和最下面一個(gè)盤片的外側(cè)盤面不用以外，其他每個(gè)盤片上下兩面都可存放數(shù)據(jù)。將這些可存放數(shù)據(jù)的盤面稱為記錄盤面。主軸盤片活動(dòng)臂（回轉(zhuǎn)臂）讀寫磁頭磁道柱面磁盤訪問每個(gè)記錄盤面上有很多磁道，數(shù)據(jù)就存放在這些磁道上。它們?cè)谟涗洷P面上形成一個(gè)個(gè)同心圓。每個(gè)記錄盤面都有一個(gè)讀寫磁頭。所有記錄盤面的讀寫磁頭都安裝在同一個(gè)動(dòng)臂上，隨動(dòng)臂向內(nèi)或向外做徑向移動(dòng)，從一個(gè)磁道移到另一個(gè)磁道。任一時(shí)刻，所有記錄盤面的讀寫磁頭停留在各個(gè)記錄盤面的半徑相同的磁道上。運(yùn)行時(shí)，由于盤面做高速旋轉(zhuǎn)，磁頭所在的磁道上的數(shù)據(jù)相繼在磁頭下，從而可以讀寫數(shù)據(jù)。磁盤訪問各個(gè)記錄盤面上半徑相同的磁道合在一起稱為柱面。動(dòng)臂的移動(dòng)實(shí)際上是將磁頭從一個(gè)柱面移動(dòng)到另一個(gè)柱面上。一個(gè)磁道可以劃分為若干段，稱為扇區(qū)，一個(gè)扇區(qū)就是一次讀寫的最小數(shù)據(jù)量。這樣，對(duì)磁盤存儲(chǔ)器來說，從大到小的存儲(chǔ)單位是：盤片組、柱面、磁道和扇區(qū)。磁盤存取時(shí)間對(duì)磁盤存儲(chǔ)器進(jìn)行一次存取所需時(shí)間：當(dāng)有多個(gè)盤片組時(shí)，要選定某個(gè)盤片組。這是由電子線路實(shí)現(xiàn)的，速度很快。選定盤片組后再選定某個(gè)柱面，并移動(dòng)動(dòng)臂把磁頭移到此柱面上。這是機(jī)械動(dòng)作，速度較慢。這稱為“尋查（seek）”。選定柱面后，要進(jìn)一步確定磁道，即確定由哪個(gè)讀寫磁頭讀寫，由電子線路實(shí)現(xiàn)。‘確定磁道后，還要確定所要讀寫數(shù)據(jù)在磁盤上的位置（如在哪一個(gè)扇區(qū)）。這實(shí)際上就是在等待要讀寫的扇區(qū)轉(zhuǎn)到讀寫磁頭下面。這是機(jī)械動(dòng)作。這段時(shí)間一般稱為旋轉(zhuǎn)延遲（rotationaldelay）時(shí)。真正進(jìn)行讀寫時(shí)間。在磁盤組上一次讀寫的時(shí)間主要為：

tio＝tseek＋tlatency＋trw其中，tseek是平均尋查時(shí)間，是把磁頭定位到要求柱面所需時(shí)間，這個(gè)時(shí)間的長短取決于磁頭移過的柱面數(shù)。tlatency是平均等待時(shí)間，是將磁頭定位到指定塊所需時(shí)間。trw是傳送一個(gè)扇區(qū)數(shù)據(jù)所需的時(shí)間。磁盤一次讀寫操作訪問一個(gè)扇區(qū)，稱為訪問“一頁”（page）或“一塊”（block），又稱為“一次訪外”。磁盤存取時(shí)間9.2文件組織什么是文件文件是存儲(chǔ)在外存上的數(shù)據(jù)結(jié)構(gòu)。文件分操作系統(tǒng)文件和數(shù)據(jù)庫文件操作系統(tǒng)中的文件是流式文件：是沒有結(jié)構(gòu)的字符流數(shù)據(jù)庫文件是具有結(jié)構(gòu)的數(shù)據(jù)集合數(shù)據(jù)結(jié)構(gòu)中討論的是數(shù)據(jù)庫文件。操作系統(tǒng)對(duì)文件是按物理記錄讀寫的，在數(shù)據(jù)庫中文件按頁塊存儲(chǔ)和讀寫。文件的組成文件由記錄組成；記錄由若干數(shù)據(jù)項(xiàng)組成。記錄是文件存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位。從不同的觀點(diǎn)，文件記錄分為邏輯記錄和物理記錄。前者是面向用戶的基本存取單位，后者是面向外設(shè)的基本存取單位。能夠唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)集稱為主關(guān)鍵碼項(xiàng)，其值稱為主關(guān)鍵碼；不唯一標(biāo)識(shí)一個(gè)記錄的數(shù)據(jù)項(xiàng)或數(shù)據(jù)項(xiàng)集稱為次關(guān)鍵碼項(xiàng)，其值稱為次關(guān)鍵碼。文件的組成文件結(jié)構(gòu)包括文件的邏輯結(jié)構(gòu)、文件的存儲(chǔ)結(jié)構(gòu)和文件的操作。文件的邏輯結(jié)構(gòu)是線性結(jié)構(gòu)，各個(gè)記錄以線性方式排列。文件的存儲(chǔ)結(jié)構(gòu)是指文件在外存上的組織方式，它與文件特性有關(guān)。順序組織索引組織直接存取組織（散列組織）文件的操作是定義在邏輯結(jié)構(gòu)上的，但操作的具體實(shí)現(xiàn)要在存儲(chǔ)結(jié)構(gòu)上進(jìn)行。評(píng)價(jià)一個(gè)文件組織的效率執(zhí)行文件操作所花費(fèi)的時(shí)間文件組織所需要的空間。文件的操作檢索維護(hù)簡單查詢范圍查詢函數(shù)查詢布爾查詢插入刪除修改重構(gòu)恢復(fù)三種主要的文件組織方式順序文件(SequentialFile)直接存取文件(DirectAccessFile)索引文件(IndexedFile)順序文件(SequentialFile)順序文件中的記錄按它們進(jìn)入文件的先后順序存放，其邏輯順序與物理順序一致。如果文件的記錄按主關(guān)鍵碼有序，則稱其為順序有序文件，否則稱其為順序無序文件。順序文件通常存放在順序存取設(shè)備（如磁帶）上或直接存取設(shè)備（如磁盤）上。當(dāng)存放在順序存取設(shè)備上時(shí)只能按順序搜索法存?。划?dāng)存放在直接存取設(shè)備上時(shí)，可以使用順序搜索法、折半搜索法等存取。直接存取文件(DirectAccessFile)文件記錄的邏輯順序與物理順序不一定相同。通過記錄的關(guān)鍵碼可直接確定該記錄的地址。利用散列技術(shù)組織文件。處理類似散列法，但它是存儲(chǔ)在外存上的。使用散列函數(shù)把關(guān)鍵碼集合映射到地址集合時(shí)，往往會(huì)產(chǎn)生地址沖突，處理沖突有兩種處理方式：按桶散列可擴(kuò)充散列散列表（HashTable）理想的搜索方法是可以不經(jīng)過比較，一次直接從字典中得到要搜索的元素。如果在元素存儲(chǔ)位置與其關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash()，使得每個(gè)關(guān)鍵碼與結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)： Address＝Hash(key) 在插入時(shí)依此函數(shù)計(jì)算存儲(chǔ)位置并按此位置存放。在搜索時(shí)對(duì)元素的關(guān)鍵碼進(jìn)行同樣的計(jì)算，把求得的函數(shù)值當(dāng)做元素存儲(chǔ)位置，在結(jié)構(gòu)中按此位置搜索。這就是散列方法。實(shí)例090,00054,304查號(hào)臺(tái)%900016278.5001散列表長M=90001散列函數(shù)：H(key)=key%M51,304ZJ-09#4035153.187639,514校長辦公室6277.0211

在散列方法中所用轉(zhuǎn)換函數(shù)叫做散列函數(shù)。按此方法構(gòu)造出來的表叫做散列表。使用散列方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較,搜索速度比較快。散列函數(shù)是一個(gè)壓縮映象函數(shù)。關(guān)鍵碼集合比散列表地址集合大得多。因此有可能經(jīng)過散列函數(shù)的計(jì)算，把不同的關(guān)鍵碼映射到同一個(gè)散列地址上，這就產(chǎn)生了沖突。示例：有一組表項(xiàng)，其關(guān)鍵碼分別是

12361,07251,03309,30976

采用的散列函數(shù)是

hash(x)=x%73+13420

則有hash(12361)=hash(07250)=hash(03309)=hash(30976)=13444。HASH可見，對(duì)于不同的關(guān)鍵碼，通過散列函數(shù)的計(jì)算得到了同一散列地址。稱這些產(chǎn)生沖突的散列地址相同的不同關(guān)鍵碼為同義詞。由于關(guān)鍵碼集合比地址集合大得多,沖突很難避免。所以對(duì)于散列方法,需要討論以下兩個(gè)問題：對(duì)于給定的一個(gè)關(guān)鍵碼集合，選擇一個(gè)計(jì)算簡單且地址分布比較均勻的散列函數(shù)，避免或盡量減少?zèng)_突；擬訂解決沖突的方案。按桶散列文件中的記錄成組存放，若干個(gè)記錄組成一個(gè)存儲(chǔ)單位，稱之為桶。假若一個(gè)桶能存放m個(gè)記錄，則m個(gè)互為同義詞的記錄可以存放在同一地址的桶中。當(dāng)?shù)趍+1個(gè)同義詞出現(xiàn)時(shí)，才發(fā)生“溢出”。(a)溢出鏈當(dāng)發(fā)生“溢出”時(shí)，將第m+1個(gè)同義詞存放到“溢出桶”。并稱存放前m個(gè)同義詞的桶為“基桶”。溢出桶和基桶大小相同。當(dāng)在基桶中檢索不成功，就循指針到溢出桶中檢索。桶大小為3的溢出桶鏈表示例

在這種散列文件中刪除記錄時(shí)，因?yàn)榭赡苄枰匦骆溄?，所以只需做一個(gè)邏輯刪除標(biāo)記即可，待系統(tǒng)做周期性重構(gòu)時(shí)再做物理刪除。070∧512204246O1597177∧262157∧116613∧285635208O2923076∧0123456O1O2O3O4O5O6O7015337988O3817117390O4

575540435∧362∧基桶編號(hào)基桶區(qū)m=3,b=7

溢出桶編號(hào)溢出桶區(qū)(b)分布式溢出空間溢出桶按照一定的間隔分布在基桶之間。如果有一個(gè)基桶溢出了，系統(tǒng)就將記錄存放在下一個(gè)溢出桶中。如果溢出桶自己溢出了，則使用下一個(gè)相繼的溢出桶，這需要第二次溢出處理。01234567891011121314分布式溢出桶基桶基桶基桶溢出桶溢出桶如果系統(tǒng)對(duì)基桶按0,1,2,3,4,5,…進(jìn)行編號(hào)，在按間隔G=5插入溢出桶后，可按下列公式按字節(jié)求出各個(gè)桶的實(shí)際存儲(chǔ)地址：其中，B0是在文件中第0號(hào)桶的起始地址，B是每個(gè)桶的字節(jié)數(shù)。在括號(hào)中的除數(shù)5表示每隔5個(gè)基桶安排一個(gè)溢出桶。(c)

相繼溢出法此方法不設(shè)置溢出桶。當(dāng)記錄應(yīng)存放的桶溢出時(shí)，溢出記錄存放到下一個(gè)相繼的桶中。如果該桶已滿，就把它放到再下一個(gè)桶中，如此處理，直至把記錄存放好。相繼溢出法的優(yōu)點(diǎn)是對(duì)溢出不需要漫長的尋找。緊鄰的桶通常相距不多于一次磁盤旋轉(zhuǎn)。但當(dāng)鄰近的多個(gè)桶被擠滿時(shí)，則為了查找空閑空間就需要檢查許多桶。如果桶的容量很小更是如此。右例桶容量m=4,桶數(shù)b=11362177597157817575070246015542389116204512435337117635613262988285923076208相繼溢出法

012435679810索引文件(IndexedFile)索引文件由索引表和主文件組成。索引表用于指示邏輯記錄與物理記錄間的對(duì)應(yīng)關(guān)系，它是按關(guān)鍵碼有序的表。索引順序文件：主文件也按關(guān)鍵碼有序。此時(shí)可對(duì)主文件分組，一組記錄對(duì)應(yīng)一個(gè)索引項(xiàng)。稱這種索引表為稀疏索引。索引非順序文件：主文件中記錄未按關(guān)鍵碼有序。此時(shí)，每一個(gè)主文件記錄必須對(duì)應(yīng)索引項(xiàng)。稱這種索引表為稠密索引。索引文件(IndexedFile)靜態(tài)索引：采用多級(jí)索引結(jié)構(gòu)，每一級(jí)索引均為有序表。優(yōu)點(diǎn)是結(jié)構(gòu)簡單，缺點(diǎn)是修改很不方便，每次修改都要重組索引。動(dòng)態(tài)索引：采用可動(dòng)態(tài)調(diào)整的平衡搜索樹結(jié)構(gòu)，如二叉搜索樹、B樹與B+樹等。優(yōu)點(diǎn)是插入、刪除和搜索都很方便。在文件中搜索時(shí)，訪問外存所花費(fèi)時(shí)間比在內(nèi)存中搜索所需的時(shí)間大得多，因此，外存上搜索一個(gè)記錄的時(shí)間代價(jià)主要取決于訪問外存的次數(shù)，即索引樹的高度。職工號(hào)姓名性別職務(wù)婚否…83張珊女教師已婚…08李斯男教師已婚…03王璐男教務(wù)員已婚…95劉琪女實(shí)驗(yàn)員未婚…24岳跋男教師已婚…47周斌男教師已婚…17胡江男實(shí)驗(yàn)員未婚…51林青女教師未婚…28

01k2k3k4k5k6k7k索引表數(shù)據(jù)表keyaddr032k081k176k244k475k517k830953k索引非順序文件示例當(dāng)記錄在外存中有序存放時(shí)，可以把所有n個(gè)記錄分為b個(gè)子表(塊)存放，一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)表中一組記錄(子表)。2212133029333642444839406074567980669282889894子表1子表2子表3子表4數(shù)據(jù)區(qū)33488098索引表1234max_min_keyaddr索引順序文件示例對(duì)索引順序文件進(jìn)行搜索，一般分為兩級(jí):先在索引表ID中搜索給定值K,確定滿足

ID[i-1].max_key<K

ID[i].max_key

的i值,即待查記錄可能在的子表的序號(hào)。然后再在第i個(gè)子表中按給定值搜索要求的記錄。索引表是按max_key有序的,且長度也不大,可以折半搜索，也可以順序搜索。各子表內(nèi)各個(gè)記錄如果也按關(guān)鍵碼有序,可以采用折半搜索或順序搜索;如果不是按關(guān)鍵碼有序,只能順序搜索。索引文件的搜索索引順序文件的搜索成功時(shí)的平均搜索長度

ASLIndexSeq=ASLIndex

+ASLSubList其中,ASLIndex

是在索引表中搜索子表位置的平均搜索長度，ASLSubList是在子表內(nèi)搜索記錄位置的搜索成功的平均搜索長度。設(shè)把長度為n的表分成均等的b個(gè)子表，每個(gè)子表s個(gè)記錄，則b=n/s。又設(shè)表中每個(gè)記錄的搜索概率相等，則每個(gè)子表的搜索概率為1/b，子表內(nèi)各記錄的搜索概率為1/s。若對(duì)索引表和子表都用順序搜索，則索引順序搜索的搜索成功時(shí)的平均搜索長度為

ASLIndexSeq=(b+1)/2+(s+1)/2=(b+s)/2+1索引順序文件的搜索索引順序文件的平均搜索長度與表中的記錄個(gè)數(shù)n有關(guān)，與每個(gè)子表中的記錄個(gè)數(shù)s有關(guān)。在給定n的情況下，s應(yīng)選擇多大？用數(shù)學(xué)方法可導(dǎo)出,當(dāng)s=

時(shí),ASLIndexSeq取極小值+1。這個(gè)值比順序搜索強(qiáng)，但比折半搜索差。但如果子表存放在外存時(shí)，還要受到頁塊大小的制約。若采用折半搜索確定記錄所在的子表,則搜索成功時(shí)的平均搜索長度為

ASLIndexSeq=ASLIndex

+ASLSubList

log2(b+1)-1+(s+1)/2

log2(1+n/s)+s/2索引順序文件的搜索9.3多級(jí)索引結(jié)構(gòu)當(dāng)數(shù)據(jù)記錄數(shù)目特別大，索引表本身也很大，在內(nèi)存中放不下，需要分批多次讀取外存才能把索引表搜索一遍。此時(shí),可以建立索引的索引(二級(jí)索引)。二級(jí)索引可以常駐內(nèi)存，二級(jí)索引中一個(gè)索引項(xiàng)對(duì)應(yīng)一個(gè)索引塊，登記該索引塊的最大關(guān)鍵碼及該索引塊的存儲(chǔ)地址。如果二級(jí)索引在內(nèi)存中也放不下，需要分為許多塊多次從外存讀入?？梢越⒍?jí)索引的索引(三級(jí)索引)。這時(shí),訪問外存次數(shù)等于讀入索引次數(shù)再加上1次讀取記錄。必要時(shí),還可以有4級(jí)索引,5級(jí)索引,…。02061115182329323841454952607795(06,)(15,)(23,)(32,)(41,)(49,)(60,)(95,)(23,)(49,)(95,)roothead多級(jí)索引結(jié)構(gòu)多級(jí)索引結(jié)構(gòu)這種多級(jí)索引結(jié)構(gòu)形成m叉樹。樹中每一個(gè)分支結(jié)點(diǎn)表示一個(gè)索引塊,它最多存放m個(gè)索引項(xiàng),每個(gè)索引項(xiàng)分別給出各子樹結(jié)點(diǎn)(低一級(jí)索引塊)的最大關(guān)鍵碼和結(jié)點(diǎn)地址。樹的葉結(jié)點(diǎn)中各索引項(xiàng)給出在數(shù)據(jù)表中存放的記錄的關(guān)鍵碼和存放地址。這種m叉樹用來作為多級(jí)索引，就是m路搜索樹。m路搜索樹可能是靜態(tài)索引結(jié)構(gòu)，即結(jié)構(gòu)在初始創(chuàng)建，數(shù)據(jù)裝入時(shí)就已經(jīng)定型，在整個(gè)運(yùn)行期間，樹的結(jié)構(gòu)不發(fā)生變化。m路搜索樹還可能是動(dòng)態(tài)索引結(jié)構(gòu),即在整個(gè)系統(tǒng)運(yùn)行期間,樹的結(jié)構(gòu)隨數(shù)據(jù)的增刪及時(shí)調(diào)整,以保持最佳的搜索效率。多級(jí)索引結(jié)構(gòu)形成m路搜索樹數(shù)據(jù)區(qū)一級(jí)索引二級(jí)索引三級(jí)索引四級(jí)索引現(xiàn)在我們所討論的m路搜索樹多為可以動(dòng)態(tài)調(diào)整的多路搜索樹，它的遞歸定義為：一棵m路搜索樹,它或者是一棵空樹,或者是滿足如下性質(zhì)的樹：根最多有m棵子樹,并具有如下的結(jié)構(gòu)：

(n,P0,K1,P1,K2,P2,……,Kn,Pn

)

其中,Pi是指向子樹的指針,0≤i≤n<m;Ki是關(guān)鍵碼,1≤i≤n<m。Ki

<Ki+1,1≤i<n。動(dòng)態(tài)的m路搜索樹在子樹

Pi

中所有的關(guān)鍵碼都小于Ki+1,且大于Ki，0<i<n。在子樹Pn

中所有的關(guān)鍵碼都大于Kn；在子樹P0

中的所有關(guān)鍵碼都小于K1。子樹

Pi

也是m路搜索樹，0≤i<n

。一棵3路搜索樹的示例352040abcde253010154550在m路搜索樹上的 搜索過程是一個(gè)在 結(jié)點(diǎn)內(nèi)搜索和自根 結(jié)點(diǎn)向下逐個(gè)結(jié)點(diǎn) 搜索的交替的過程。352040abcde253010154550root搜索35m路搜索樹的搜索算法一棵m階B樹是一棵平衡的m路搜索樹,它或者是空樹,或者是滿足下列性質(zhì)的樹：根結(jié)點(diǎn)至少有2個(gè)子女。除根結(jié)點(diǎn)以外的所有結(jié)點(diǎn)(不包括失敗結(jié)點(diǎn))至少有m/2

個(gè)子女。所有的失敗結(jié)點(diǎn)都位于同一層。在B樹中的“失敗”結(jié)點(diǎn)是當(dāng)x不在樹中時(shí)才能到達(dá)的結(jié)點(diǎn)。這些結(jié)點(diǎn)實(shí)際不存在，指向它們的指針為NULL。它們不計(jì)入樹的高度。B樹m階B樹繼承了m路搜索樹的定義。原來m路搜索樹定義中的規(guī)定在m階B樹中都保留。事實(shí)上，在B樹的每個(gè)結(jié)點(diǎn)中還包含有一組指針recptr[m+1]，指向?qū)嶋H記錄的存放地址。key[i]與recptr[i](1≤i≤n<m)形成一個(gè)索引項(xiàng)(key[i],

recptr[i])，通過key[i]可找到某個(gè)記錄的存儲(chǔ)地址recptr[i]。在討論B樹結(jié)構(gòu)的操作時(shí)先不涉及recpt一棵B樹是平衡的m

路搜索樹，但一棵平衡的m

路搜索樹不一定是B樹。注意非B樹 B樹30352040253010154550root4550354020root101525B樹的搜索算法B樹的搜索算法繼承了m路搜索樹Mtree上的搜索算法。B樹的搜索過程是一個(gè)在結(jié)點(diǎn)內(nèi)搜索和循某一條路徑向下一層搜索交替進(jìn)行的過程。搜索成功，報(bào)告結(jié)點(diǎn)地址及在結(jié)點(diǎn)中的關(guān)鍵碼序號(hào)；搜索不成功，報(bào)告最后停留的葉結(jié)點(diǎn)地址及新關(guān)鍵碼在結(jié)點(diǎn)中可插入的位置。B樹的搜索時(shí)間與B樹的階數(shù)m和B樹的高度h直接有關(guān),必須加以權(quán)衡。

在B樹上進(jìn)行搜索,搜索成功所需的時(shí)間取決于關(guān)鍵碼所在的層次;搜索不成功所需的時(shí)間取決于樹的高度。定義B樹的高度h為葉結(jié)點(diǎn)（失敗結(jié)點(diǎn)的雙