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

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

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

12361,07251,03309,30976

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

hash(x)=x%73+13420

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

在這種散列文件中刪除記錄時，因為可能需要重新鏈接，所以只需做一個邏輯刪除標(biāo)記即可，待系統(tǒng)做周期性重構(gòu)時再做物理刪除。070∧512204246O1597177∧262157∧116613∧285635208O2923076∧0123456O1O2O3O4O5O6O7015337988O3817117390O4

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

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

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

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

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

ID[i-1].max_key<K

ID[i].max_key

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

ASLIndexSeq=ASLIndex

+ASLSubList其中,ASLIndex

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

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

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

ASLIndexSeq=ASLIndex

+ASLSubList

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

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

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

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

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

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

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