數(shù)據(jù)結(jié)構(gòu)課件-版-ds文件與外排序

第7章外部分 Slide.1-文件系統(tǒng)是數(shù)據(jù)庫系統(tǒng)的基礎(chǔ)，從、高效和系統(tǒng)軟件研制角度看，文件系統(tǒng)1、相關(guān)概文件是用于表示駐留在 器中的數(shù)據(jù)，是同性質(zhì)記錄的有序集合①文件的數(shù)據(jù)量通常很大，被放置在外存上②數(shù)據(jù)結(jié)構(gòu)中討論的文件主要是數(shù)據(jù)庫意義上的文件，不是操作系統(tǒng)義上的文件③操作系統(tǒng)中研究的文件是一維的無結(jié)構(gòu)連續(xù)字符序列。數(shù)據(jù)庫究的文件是帶有結(jié)構(gòu)的記錄集合，每個(gè)記錄可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-記錄是文件中存取的基本單位，數(shù)據(jù)項(xiàng)是文件可使用的最小單位。數(shù)項(xiàng)有時(shí)也稱為字段(Field)，或者稱為屬性(Attribute)或)。為討論方便起見，一般不嚴(yán)格區(qū)分關(guān)鍵字項(xiàng)和關(guān)鍵字。即在不時(shí)，將主(或次)關(guān)鍵字項(xiàng)簡稱為主(或次)關(guān)鍵字，并且假定主關(guān)鍵字項(xiàng)只一個(gè)數(shù)據(jù)項(xiàng)張男 女王女陳男 男林女關(guān)鍵 主關(guān)鍵 次關(guān)鍵哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-不定長記錄文文件的邏輯結(jié)構(gòu)和物理結(jié)邏輯結(jié)構(gòu)：呈現(xiàn)給用戶，描述記準(zhǔn)考證政語數(shù)外物理結(jié)構(gòu) 結(jié)構(gòu)，記錄 器中的組織，連續(xù)，鏈?zhǔn)焦枮I工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)2、文件操操

第7章外部分 Slide.1-檢索方式：實(shí) 成更新方式：實(shí) 成(即記錄存入文件時(shí)的順序編號(hào))①簡單查詢：只查詢單個(gè)關(guān)鍵字等于給定值的記 ”的哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-②范圍查詢：只查詢單個(gè)關(guān)鍵字屬于某個(gè)范圍內(nèi)的所有記【例】下表的學(xué)生文件中，查 >18的所有學(xué)生的記錄③函數(shù)查詢：規(guī)定單個(gè)關(guān)鍵字的某個(gè)函數(shù)，查詢該函數(shù)的某個(gè)【例】下表的學(xué)生文件，查詢?nèi)w學(xué)生的平均數(shù)學(xué)成績是多少 查詢：以上三種查詢 運(yùn)算(與、或、非)組合起來的查詢【例】下表的學(xué)生文件中，要找出所有語文成績低于80的男生以及所數(shù)學(xué)低于80 ，查詢條件是 =“男”)and(語文 =“女”)and(數(shù)學(xué)張男張男 女王女陳男 男林女哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-操作主要是①對文件進(jìn)行記錄的插入、刪除及修改等②為提高文件的效率，進(jìn)行再③文件被破壞后的恢復(fù)操作，以及文件中數(shù)據(jù)的安文件上的檢索和更新操作，都可有實(shí)時(shí)和批量兩種不同的處理①實(shí)時(shí)處理：響應(yīng)時(shí)間要求嚴(yán)格，要求在接受詢問后幾秒種內(nèi)完②批量處理：響應(yīng)時(shí)間要求寬松一些，不同的文件系統(tǒng)有不同要求個(gè) 票系其和更新都應(yīng)實(shí)時(shí)處理銀行的賬戶系統(tǒng)需要實(shí)時(shí)檢，但可進(jìn)行批量更新，即可以將一天的存和提款記錄在一個(gè)事務(wù)文件，在一天的營業(yè)之后再行批量處理。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)一.順序方

第7章外部分 Slide.1-順序方索引方散列方方順序一致的文件。磁盤文由柱面和磁道組

文件改程

職工新文磁帶文件磁帶文件操作實(shí)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-順序文件分順序有序文記錄按其主關(guān)鍵字有序的順序文件為順序順序無序文記錄未按其主關(guān)鍵字有序排列的順序文件為順序無序文注意為提高檢索效率，常將順序文件組織成有序文件順序有序文件存取的查找方順序存 器（磁帶）上文件存取的查找方順序查找法即順序掃描文件，按記錄的主關(guān)鍵字逐個(gè)查找。要索第i個(gè)記錄，必須檢索前i-1個(gè)記錄哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-①這種查找法對于少量的檢索是不經(jīng)濟(jì)的，但適合于批量檢索②順序存 器上的文件只能用順序查找法存直接存 （磁盤）上文件存取的查找方順序查找分塊查找具體方法100個(gè)記錄為一塊，各塊的最后一個(gè)記錄的主關(guān)鍵字為Kl00，K200，…，1i…：查找時(shí)，將所要查找的記錄的主關(guān)鍵字K，依次和各塊的最大于K100(i-且小于或等于塊內(nèi)進(jìn)行掃描。注意分塊查找法在查找時(shí)不必掃描整個(gè)3）分查找①二分查找法只適合對較小的文件或一個(gè)文件的索引進(jìn)行查找哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-②當(dāng)文件很大，在磁盤上占有多個(gè)柱面時(shí)，二分查找將引起磁頭來移動(dòng)，增加尋查時(shí)間③對磁盤等直接存取設(shè)備，還可以對順序文件進(jìn)行插值查找和跳步查順序文件的修順序文件的修改操由于文件中的記錄不能像向量空間的數(shù)據(jù)那樣“移動(dòng)”，故只能通 批量處理方式實(shí)現(xiàn)順序文件的更①把所有對順序文件(以下稱主文件)的更新請求，都放入一個(gè)的事務(wù)文件②當(dāng)事務(wù)文件變得足夠大時(shí)，將事務(wù)文件按主關(guān)鍵字排序③再按事務(wù)文件對主文件進(jìn)行一次全面的更新，產(chǎn)生一個(gè)新的件④最后，清空事務(wù)文件，以便積累此后的更新內(nèi)容哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)二.索引方

第7章外部分 Slide.1- 索引順序文件(IndexedSequential索引非順序文件(IndexedNonSequentail哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-索引文件索引文件索引文件 器上分為兩個(gè)區(qū)：索引區(qū)和數(shù)據(jù)區(qū)。索引區(qū)存放引表，數(shù)據(jù)區(qū)存放主文件索引文件的建建立索引文件的無序的一起就形成了索引文件。10.2如表10.3所示，排序后的索引表見表.4，表10.2和表4一起形成了一個(gè)索引文件。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)索引文件的操

第7章外部分 Slide.1-檢索操檢索分兩步進(jìn)行①將外存上含有索引區(qū)的頁塊送人內(nèi)存，查找所需記錄的物②將含有該記錄的頁塊送人內(nèi)注意①索引表不大時(shí)，索引表可一次讀入內(nèi)存，在索引文件中檢索只需外存：一次讀索引，一次讀記②由于索引表有序，對索引表的查找可用順序查找或二分查找等方法更新操（1）插入：將插入記錄置于數(shù)據(jù)區(qū)的末尾，并在索引表中插入索引（2）刪除：刪去相應(yīng)的索注意：修改主關(guān)鍵字時(shí)，要同時(shí)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-利用查找表建立多級查找對索引表建立的索引，稱為查找表。查找表的建立可以為占據(jù)多個(gè)塊的索引表的查閱減少外存次數(shù)。【例】表10.410.5所示。檢索記錄時(shí)，先查找查找表，再查索引表，然后記錄，三次外存即可表哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)動(dòng)態(tài)索

第7章外部分 Slide.1-當(dāng)數(shù)據(jù)文件在使用過程中記錄變動(dòng)較多時(shí)，利用二叉排序樹(或AVL樹)、B_樹(或其變型)等樹表結(jié)構(gòu)建立的索引，為動(dòng)態(tài)索引樹表①插入、刪除方②本③建立索引表的過程即為排序過程樹表結(jié)構(gòu)選①當(dāng)數(shù)據(jù)文件的記錄數(shù)不很多，內(nèi)存容量足以容納用二叉排序樹(或AVL樹)做索引；②當(dāng)文件很大時(shí)，索引表(樹表)外存的階-樹(或其變型)作為索引表為宜m）。外存的索引表的查找性能評由于外存的時(shí)間比內(nèi)存中查找的時(shí)間大得多，所以外存的索引表的查找性能主要著眼于外存的次數(shù)，即索引表的深度。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-三.散列文件 方式組織的文件，亦稱直接存取文件。即根 散列表與散列文件比散列文比較項(xiàng)單若干記錄為桶處理辦開放地址法、拉鏈拉鏈哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)基桶和溢出

第7章外部分 Slide.1-在散列文件的(Bucet)個(gè)記錄，個(gè)同義詞會(huì)發(fā)生溢出。需要將第溢出桶。相對地，稱前m個(gè)同義詞存放的桶為"基桶"注意出桶和基桶大小相同，相互之間用指針相在基桶中沒有找到待查記錄時(shí)，就沿著指針到所指溢出桶中230526，01，18，02，27，1，0，0，0，1，0，1，3，2。桶的容量，桶數(shù)。用除余法作散列函數(shù)(k7。由此得到的散列文件如下圖所示。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)散列文件的查找

第7章外部分 Slide.1-在散列文件中查找的過程根據(jù)給定值求出散列桶地將基桶的記錄讀人內(nèi)存，進(jìn)行順序查散列文件的刪除操在散列文件中刪去一個(gè)記錄，僅需對被刪記錄作刪除標(biāo)記即可哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)散列文件的特

第7章外部分 Slide.1-散列文件的優(yōu)文件隨機(jī)存放，記錄不需進(jìn)行排序插入、刪除方便存取速度快；不需要索引區(qū)，節(jié) 空間散列文件的缺不能進(jìn)行順序存取，只能按關(guān)鍵字隨機(jī)查詢方式限于簡單查 在經(jīng)過多次插文件哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)四、多關(guān)鍵字文

第7章外部分 Slide.1-多關(guān)鍵字文包含有多個(gè)次關(guān)鍵字索引的文件稱為多關(guān)鍵字文注意：次關(guān)鍵字索引本身可以是順序表或多關(guān)鍵字文件和其他文件的區(qū)多關(guān)鍵字文其它文包含的關(guān)建立的建立主關(guān)鍵字索引多個(gè)次關(guān)鍵字的只有有主關(guān)鍵索查對主關(guān)鍵字索引和關(guān)鍵字索只能順序存取記錄進(jìn)行比較，效低文件組織四種方式均四種方式均哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-多重鏈表文件的組織方多重鏈表文件是將索引方法 方法相結(jié)合的一種組織方式具體組織方式對主關(guān)鍵字索對每個(gè)需要查詢的次關(guān)鍵字建立一個(gè)索引，同時(shí)將具有相同次關(guān)的記 成一個(gè)鏈表并將此鏈表的頭指針、鏈表長度及次關(guān)鍵字，作為索引表的一項(xiàng)通常多重鏈表文件的主文件是一個(gè)順序文哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-【例】上表是一個(gè)多重表文件的示例。主關(guān)鍵字是職工號(hào)，次關(guān)鍵字是職務(wù)和工資級別。它設(shè)有兩個(gè)字段，分別將具有相同職務(wù)和相同工資級哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-多重表文件的查詢操單關(guān)鍵字簡單查詢基本思據(jù)給定值，在對應(yīng)次關(guān)鍵字索引表中找到對應(yīng)索引項(xiàng)，從頭指針發(fā)，列出該鏈表上所有記錄【例】針對上面的多重表查詢所有軟件人員，則只需在職務(wù)索引表中先找到次關(guān)鍵字軟件人員該鏈表上所有的記錄即可。多關(guān)鍵字組合查詢基本思【例】若要查詢工資級別為引的硬件人員哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-注意（多個(gè)多重表的更新操插入新記相同次關(guān)鍵字鏈表不按主關(guān)鍵字大 時(shí)，在主文件中插入新錄后，將記錄在各個(gè)次關(guān)鍵字鏈表中插在鏈表的頭指針之后即刪除記在刪去一個(gè)記錄的同時(shí)，需在每個(gè)次關(guān)鍵字的鏈表中刪去哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)六、倒排文

第7章外部分 Slide.1-倒排文件的組織倒排文件和多重表文件的區(qū)別在于次關(guān)鍵字索引結(jié)構(gòu)不在次關(guān)鍵字索引中，具有相同次關(guān)鍵字的記錄之間不進(jìn) ，而列出具有該次關(guān)鍵字記錄的物理倒排文件中的次關(guān)鍵字索引稱做倒排表。倒排表和主文件一起就構(gòu)了倒排文件哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-【例】將上表所示的多重表文件去掉兩 字段后作為主文件所建立職務(wù)倒排表和工資級別倒排表，如下圖所示哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-倒排文件的查從而提高查找速度。哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-【例】要找出所有工資級別小于的次關(guān)鍵字為的物理地址集合先做交運(yùn)算：{108}∪{102，106}即符合條件的記錄，其物理地址是101和102倒排文件的更在插入和刪除記錄時(shí)，還要修改倒列出主關(guān)鍵字的倒排列出主關(guān)鍵字的倒排表的特點(diǎn)取速度較②主關(guān)鍵字可看成是記錄的符號(hào)地址，對 具有相對獨(dú)立性【例】下面的表就是按上述方法對多重表文件所組織的職務(wù)倒哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-倒排文件與一般文件組織的區(qū)倒排。注意多重表文件實(shí)際上也是倒排文件，只不過索引的方哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)

第7章外部分 Slide.1-理。這樣，在排序過程中必須不斷地在內(nèi)存與外存之間傳送數(shù)據(jù)。這種基于外部外排序的基本當(dāng)對象以文件形式存放于磁盤上的時(shí)候，通常是按物理 的物理塊也叫做頁塊，是磁盤存取的基本單位每個(gè)頁塊可以存放幾個(gè)對象。操作系統(tǒng)按頁塊對磁盤上的信息寫哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-分兩個(gè)階段進(jìn)第一階段：首先，將文件中的數(shù)據(jù)分段輸入到內(nèi)存，在內(nèi)存中采用內(nèi)分類方法對其進(jìn)行分類（分類完的文件段，稱為歸并段)，然后將有序段寫回整個(gè)文件經(jīng)過在內(nèi)存逐段分又逐段寫回外存，這樣在外存中形個(gè)初始的歸并段第二階段：對這些初始?xì)w并段采用某種歸并分類方法，進(jìn)行多遍歸并最后形成整個(gè)文件的單一歸并段哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-如何進(jìn)行多路歸并以減少文件的歸并遍如何巧妙地運(yùn)用內(nèi)存的緩沖區(qū)使I/O和盡可能并行工作根據(jù)外存的特點(diǎn)選擇較好的產(chǎn)生初始?xì)w并段的方哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-設(shè)有一個(gè)入現(xiàn)用一臺(tái)內(nèi)存至多可容納750個(gè)記錄的計(jì)算機(jī)對該文件進(jìn)行分類。輸入文件放在磁盤上,每個(gè)頁塊可容250個(gè)記,這樣全部記錄可 在4500/個(gè)頁塊。輸出文件也放在磁盤上,用以存放歸并結(jié)果。由于內(nèi)存中可用于分類 區(qū)域能容納750個(gè)記錄,因此內(nèi)存中好能存3個(gè)頁塊的記錄在外分類一開始,把18塊記錄,每3塊一組,讀入內(nèi)存。利用某種內(nèi)分類方法進(jìn)行內(nèi)分類形成初始?xì)w并段再寫回外存?？偣部傻玫?個(gè)初始?xì)w歸并

哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-若把內(nèi)存區(qū)域等份地分為3個(gè)緩沖區(qū)。其中的兩個(gè)為輸入緩沖區(qū)一個(gè)為輸出緩沖區(qū)可以在內(nèi)存中利2路歸并函數(shù)merge()路歸并首先,從參加歸并排序的兩個(gè)輸入歸并段R1和R2中分別讀入一塊250個(gè)記錄放在輸入緩沖區(qū)1和輸入緩沖區(qū)2中。然后在內(nèi)存中進(jìn)行2路哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-當(dāng)輸出緩沖區(qū)裝滿250個(gè)記錄時(shí)，就輸出到、、R1 R2 R3 R4歸并第一歸并結(jié)第二歸并結(jié)第三歸并結(jié)哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-

…討論問

m個(gè)歸并段的歸并多路歸并——減少歸并遍并行操作的緩沖區(qū)處理——使輸入、輸出和CPU處理盡可初始?xì)w并段的生哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-多路歸并——減少歸并遍m個(gè)初始段進(jìn)行2路歸并，需要遍歸并一般地，m個(gè)初始段，采用K路歸并，需要遍歸并顯然，K越大，歸并遍數(shù)越少，可提高歸并的效率在K路歸并時(shí)，從K個(gè)關(guān)鍵字中選擇最小記錄時(shí)，要比K-1次。若記錄總數(shù)為n，每遍要比較的次數(shù)為n*(K-1)*[logkm]=n*(K-1)可以看出，隨著k增大，(K-1)/log2K也增大，當(dāng)歸并路數(shù)多時(shí)，處理的時(shí)間也隨之增多。當(dāng)PU處理時(shí)間大于因K為此要選擇好的分類方法，以減少分哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)K選擇樹選最小對象

第7章外部分 Slide.1-69689選擇69689分析第一次建立選擇樹的比較所花時(shí)間為O(k-1)=O(而后每次重新建造選擇樹所需時(shí)間O(log2k間加上n-1次重新選擇樹的時(shí)間：O((n-1)·log2k)+O(k)=O(n·log2kO(n·log2k·logkm)=O(n·log2m)(k路歸并CPU時(shí)間與k無關(guān))哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分 Slide.1-——使輸入、輸出和CPU對k個(gè)歸并段進(jìn)行k路歸并至少需要k個(gè)輸入和1哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)第7章外部分