數(shù)據(jù)結(jié)構(gòu)-文件及查找_第1頁
數(shù)據(jù)結(jié)構(gòu)-文件及查找_第2頁
數(shù)據(jù)結(jié)構(gòu)-文件及查找_第3頁
數(shù)據(jù)結(jié)構(gòu)-文件及查找_第4頁
數(shù)據(jù)結(jié)構(gòu)-文件及查找_第5頁
已閱讀5頁,還剩46頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領(lǐng)

文檔簡介

1第九章文件及查找提綱9.1文件概述9.2順序文件9.3索引文件9.4B-樹與B+樹9.5雜湊(Hash)文件

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第1頁。29.1文件概述

數(shù)據(jù)庫文件的每個記錄由若干數(shù)據(jù)項構(gòu)成。記錄是文件存取的基本單位,數(shù)據(jù)項是文件使用的最小單位。數(shù)據(jù)項又稱關(guān)鍵字項,關(guān)鍵字項的值稱為關(guān)鍵字(Key)。能惟一標識一個記錄的關(guān)鍵字稱為主關(guān)鍵字,而其他的關(guān)鍵字稱為次關(guān)鍵字。

文件(File)是性質(zhì)相同、邏輯上相關(guān)的記錄的集合。

按文件記錄的類型不同可以將文件分為兩類:操作系統(tǒng)文件和數(shù)據(jù)庫文件。操作系統(tǒng)文件是一維的字符序列,無結(jié)構(gòu),無解釋。數(shù)據(jù)庫文件是帶有結(jié)構(gòu)的記錄集合。

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第2頁。39.1文件概述文件的存儲介質(zhì)磁帶磁盤光盤移動電子盤數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第3頁。4學(xué)號姓名性別年齡200801001張小平立新女20200801003王鵬飛男19200801004王新剛惠女199.1文件概述

下面是一個簡單的學(xué)生文件,每個學(xué)生的情況是一個記錄。每個記錄由學(xué)號、姓名、性別和年齡4個數(shù)據(jù)項組成。其中“學(xué)號”是主關(guān)鍵字,“姓名”、“性別”等是次關(guān)鍵字。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第4頁。59.1文件概述

文件又可分為定長文件和不定長文件。

和其它數(shù)據(jù)結(jié)構(gòu)一樣,文件結(jié)構(gòu)也包括邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及文件上的各種操作這3個方面。文件的操作是定義在邏輯結(jié)構(gòu)上的,但操作的具體實現(xiàn)要在存儲結(jié)構(gòu)上進行

若文件中記錄含有的信息長度相同,則稱這類記錄為定長記錄,由這種定長記錄組成的文件稱為定長文件;若文件中記錄含有的信息長度不等,則稱為不定長文件。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第5頁。69.1文件概述

文件的邏輯結(jié)構(gòu)是指文件的外部組織形式,是用戶對數(shù)據(jù)的表示和存取方式。

文件中各記錄之間存在著邏輯關(guān)系,當一個文件的各記錄按照某種次序排列起來時,各記錄之間自然地形成了一種線性關(guān)系。文件中的各個記錄最多只有一個前驅(qū)記錄和一個后繼記錄,而文件的第一個記錄只有后繼記錄沒有前驅(qū)記錄,文件的最后一個記錄只有前驅(qū)記錄沒有后繼記錄。所以可以把文件看成是線性結(jié)構(gòu)。

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第6頁。79.1文件概述

文件檢索就是在文件中查找滿足條件的記錄,可以按記錄的邏輯號查找,也可以按關(guān)鍵字查找。

文件維護主要是指對文件進行記錄的插入、刪除及修改等更新操作。

文件上的操作主要有兩類:檢索和維護。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第7頁。89.1文件概述

文件的存儲結(jié)構(gòu)是指文件在物理存儲介質(zhì)(磁盤、光盤、U盤)上的組織形式,它決定了文件信息在存儲設(shè)備上的存儲位置。

文件的存取方式與文件的物理結(jié)構(gòu)有關(guān)。采用不同的組織形式就得到不同的存儲結(jié)構(gòu)。基本的組織有順序組織、索引組織和Hash組織。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第8頁。99.2順序文件

順序文件是指記錄按其在文件中的邏輯順序依次存入存儲介質(zhì)而建立的,即順序文件中物理記錄的順序和邏輯記錄的順序是一致的。若順序文件中的記錄按關(guān)鍵字有序,則稱此順序文件為有序順序文件,否則稱為無序順序文件。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第9頁。10

順序文件在存儲介質(zhì)中可以有兩種不同的實現(xiàn)結(jié)構(gòu):連續(xù)結(jié)構(gòu)和鏈結(jié)構(gòu)。

連續(xù)結(jié)構(gòu)是指邏輯上相鄰的記錄其存儲位置是相鄰的,鏈結(jié)構(gòu)是指物理記錄之間的次序由指針鏈來表示。這兩種結(jié)構(gòu)對應(yīng)的順序文件分別稱為連續(xù)順序文件和鏈接順序文件。9.2順序文件數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第10頁。119.2順序文件

上圖為一個具有4個邏輯塊的連續(xù)結(jié)構(gòu)文件,其邏輯塊號0、1、2、3依次存放在物理塊15、16、17、18中。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第11頁。129.2順序文件

排序順序文件一般順序文件數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第12頁。139.2順序文件連續(xù)結(jié)構(gòu)的優(yōu)點是:(2)順序訪問速度快,對于等長記錄的連續(xù)文件可以進行順序存取,也可以進行類似折半查找的隨機存取,但是對于不等長記錄的連續(xù)文件只能進行順序存??;(3)因為數(shù)據(jù)集中存放在連續(xù)的盤塊中,訪問時所需的尋道次數(shù)和尋道時間少。

(1)結(jié)構(gòu)簡單;數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第13頁。149.2順序文件連續(xù)結(jié)構(gòu)存儲的缺點:

(1)由于插入和刪除記錄會引起其它記錄的移動,在外存中執(zhí)行此操作會引起磁頭的頻繁來回移動,因此連續(xù)結(jié)構(gòu)只能在文件的末尾插入記錄,刪除記錄時,只作標記進行邏輯刪除,只有用戶指定物理刪除時才真正刪除相應(yīng)記錄,進行記錄的移動;數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第14頁。159.2順序文件

(2)順序文件需要連續(xù)的盤塊存放數(shù)據(jù),因此,在插入記錄時如果原來分配的盤塊已沒有空閑空間,而與其鄰接的盤塊也不空閑時,需要重新在外存中查找新的較大的空閑空間,并將原有數(shù)據(jù)移動到新空間中,然后才能插入新的數(shù)據(jù),因此,連續(xù)結(jié)構(gòu)不易動態(tài)增長,而且外存容易存在碎片。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第15頁。169.2順序文件

上圖為一個4個邏輯塊的鏈結(jié)構(gòu)文件的物理存儲。使用鏈結(jié)構(gòu)時,只要指明該文件的第一個塊號就可以按鏈指針檢索整個文件。鏈結(jié)構(gòu)的另一個特點是文件長度可以動態(tài)地增長,只要調(diào)整鏈指針就可插入或刪除一個信息塊。

鏈結(jié)構(gòu)文件適用于順序存取,不便于進行直接存取,存取第i個記錄,必須搜索在它之前的i-1個記錄。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第16頁。179.2順序文件(1)提高了磁盤空間利用率,解決了磁盤碎片問題;(2)便于文件的插入和刪除操作;鏈結(jié)構(gòu)主要優(yōu)點是:(3)便于文件的動態(tài)增長。

從本質(zhì)上講,順序文件就是線性表,因而對順序文件的各種操作與線性表類似,但是,外存的訪問速度比主存要慢的多,在考慮算法時要立足于盡量減少外存的訪問次數(shù),尋道次數(shù)和尋道時間。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第17頁。189.3索引文件稠密索引文件索引對基本文件中的每個記錄都保持一個索引項。索引項按記錄關(guān)鍵字值大小排序數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第18頁。199.3索引文件非稠密索引文件將基本文件分成若干塊,每一塊內(nèi)的記錄不必排序,但在塊與快之間有序,即前一塊中的所有記錄的關(guān)鍵字都小于后一塊中所有記錄的關(guān)鍵字。索引表只需對每個塊保存一個索引項,分別給出每一塊的最大關(guān)鍵字及該塊的首地址。這種索引稱為非稠密索引非稠密索引分塊文件數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第19頁。209.3索引文件多級索引文件1.二叉樹排序樹多級索引2.多分樹索引數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第20頁。21B樹是一種平衡的多路查找樹,它在數(shù)據(jù)處理中有著巨大的作用,已經(jīng)成為數(shù)據(jù)處理中主要的文件組織形式。它以占用存儲空間少,查找效率高的優(yōu)勢在數(shù)據(jù)庫系統(tǒng)的索引技術(shù)中占據(jù)了重要的地位。定義:一棵m階的B樹,或者為空樹,或為滿足下列特性的m叉樹。(1)對樹中子樹的要求:每個結(jié)點至多有m棵子樹。若根結(jié)點不是葉子結(jié)點,則至少有兩棵子樹。除根結(jié)點之外的所有非終端結(jié)點至少有m/2

棵子樹。9.4B-樹與B+樹數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第21頁。22(2)對樹中關(guān)鍵字個數(shù)的要求:所有的非終端結(jié)點中包含以下信息(n,A0,K1,A1,K2,…,Kn,An)。其中,n為關(guān)鍵字個數(shù),m/2

1≤n≤m1;Ki(i=1,2,…,n)為關(guān)鍵字,且Ki<Ki+1;Ai為指向子樹根結(jié)點的指針(i=0,1,…,n),且指針Ai-1所指子樹中所有結(jié)點的關(guān)鍵字值均小于Ki(i=1,2,…,n),An所指子樹中所有結(jié)點的關(guān)鍵字值均大于Kn。(3)對葉子結(jié)點的要求:所有的葉子結(jié)點都出現(xiàn)在同一層次上,并且不帶信息(可以看做是外部結(jié)點或查找失敗的結(jié)點,實際上這些結(jié)點不存在,指向這些結(jié)點的指針為空)。9.4B-樹與B+樹數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第22頁。23例一棵5階的B樹

9.4B-樹與B+樹數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第23頁。249.4B-樹與B+樹例一棵7階的B樹在一棵7階的B樹中,樹根結(jié)點的關(guān)鍵字個數(shù)最少為1,最多為m1=6,子樹個數(shù)最少為2,最多為m=7;每個非樹根結(jié)點的關(guān)鍵字個數(shù)最少為「m/2

-1=「7/21=3,最多為m1=6,子樹個數(shù)最少為「m/2=「7/2=4,最多為m=7。

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第24頁。259.4B-樹與B+樹例1在一棵3階B樹上依次插入關(guān)鍵字65、24、50和38

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第25頁。269.4B-樹與B+樹例2有下列關(guān)鍵字序列{20,54,69,84,71,30,78,25,93,41,7,76,51,66,68,53,3,79,35,12,15,65},建立5階B樹

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第26頁。279.4B-樹與B+樹B—樹的刪除數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第27頁。28B+樹是應(yīng)文件系統(tǒng)所需而產(chǎn)生的一種B樹的變形樹。一棵m階的B+樹和m階的B樹的差異在于:(1)在B樹中,每個結(jié)點含n個關(guān)鍵字,n+1棵子樹;在B+樹中,每個結(jié)點含n個關(guān)鍵字,n棵子樹。(2)在B樹中,每個結(jié)點中關(guān)鍵字個數(shù)n的取值范圍m/2

1≤n≤m1(除根)結(jié)點外。在B+樹中,每個結(jié)點中關(guān)鍵字個數(shù)n的取值范圍m/2≤n≤m(除根結(jié)點外),1≤n≤m(根結(jié)點)。(3)B+樹中所有葉子結(jié)點包含了全部關(guān)鍵字及指向?qū)?yīng)記錄的指針,且所有葉子結(jié)點按關(guān)鍵字由小到大順序依次鏈接。(4)B+樹中所有非葉子結(jié)點僅起索引作用,結(jié)點中僅含有其子樹中的最大(或最小)關(guān)鍵字。

9.4B-樹與B+樹數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第28頁。299.4B-樹與B+樹B+樹定義一個m階B+樹滿足下列條件:

(1)每個分支節(jié)點至多m棵子樹

(2)出根結(jié)點外,其它每個分支結(jié)點至少有ceiling(m/2)棵子樹

(3)跟結(jié)點至少有兩顆子樹

(4)有n棵子樹的結(jié)點有n個關(guān)鍵字

(5)葉子結(jié)點中存放了數(shù)據(jù)文件的中記錄的關(guān)鍵字及指向該記錄的指針,或存放數(shù)據(jù)文件分塊后沒塊的最大關(guān)鍵字及指向該塊的指針,也結(jié)點關(guān)鍵字值按大小順序鏈接。

(6)所有分支結(jié)點可以看成是索引的索引,結(jié)點中僅包含它的各個子結(jié)點中最大(或最?。╆P(guān)鍵字及指向子結(jié)點的指針數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第29頁。309.4B-樹與B+樹9.4B-樹與B+樹B+樹操作(1)查找(2)插入(3)刪除數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第30頁。319.5雜湊(Hash)文件查找操作要完成什么任務(wù)?我們學(xué)過哪些查找技術(shù)?這些查找技術(shù)的共性?順序查找、二叉排序樹查找等。以上討論的查找方法,由于記錄的存儲位置與關(guān)鍵字之間不存在確定的關(guān)系,因此查找時需要進行一系列對關(guān)鍵字的查找比較,即“查找算法”是建立在比較的基礎(chǔ)上的,查找效率由比較一次縮小的查找范圍決定。

待查值k確定k在存儲結(jié)構(gòu)中的位置數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第31頁。329.5雜湊(Hash)文件能否不用比較,通過關(guān)鍵碼直接確定存儲位置?理想的情況是,依據(jù)關(guān)鍵字直接得到其對應(yīng)的記錄位置,即要求關(guān)鍵字與記錄位置間存在一一對應(yīng)關(guān)系,通過這個關(guān)系,能很快地由關(guān)鍵字得到對應(yīng)的記錄位置。

數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第32頁。339.5雜湊(Hash)文件散列技術(shù)僅僅是一種查找技術(shù)嗎?散列既是一種查找技術(shù),也是一種存儲技術(shù)。散列是一種完整的存儲結(jié)構(gòu)嗎?散列只是通過記錄的關(guān)鍵碼定位該記錄,沒有完整地表達記錄之間的邏輯關(guān)系,所以,散列主要是面向查找的存儲結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第33頁。349.5雜湊(Hash)文件散列技術(shù)適合于哪種類型的查找?散列技術(shù)一般不適用于允許多個記錄有同樣關(guān)鍵碼的情況。散列方法也不適用于范圍查找,換言之,在散列表中,我們不可能找到最大或最小關(guān)鍵碼的記錄,也不可能找到在某一范圍內(nèi)的記錄。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第34頁。359.5雜湊(Hash)文件散列技術(shù)的關(guān)鍵問題:⑴散列函數(shù)的設(shè)計。如何設(shè)計一個簡單、均勻、存儲利用率高的散列函數(shù)。①所選函數(shù)盡可能簡單,以便提高轉(zhuǎn)換速度。②所選函數(shù)對關(guān)鍵字計算出的地址,應(yīng)在Hash地址集中大致均勻分布,以盡量減少沖突。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第35頁。36散列技術(shù)的關(guān)鍵問題:⑵沖突的處理。如何采取合適的處理沖突方法來解決沖突。①Hash函數(shù)。若Hash函數(shù)選擇得當,就可使Hash地址盡可能均勻地分布在Hash地址空間上,從而減少沖突的發(fā)生;否則,若Hash函數(shù)選擇不當,就可能使Hash地址集中于某些區(qū)域,從而加大沖突的發(fā)生。②處理沖突的方法。選擇適當?shù)腍ash函數(shù)可以減少沖突,但不能避免沖突,因此當沖突發(fā)生時,必須有較好的處理沖突的方法。③Hash表的裝填因子。

9.5雜湊(Hash)文件數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第36頁。379.5雜湊(Hash)文件散列函數(shù)是關(guān)鍵碼的線性函數(shù),即:H(key)=a

key+b(a,b為常數(shù))例:關(guān)鍵碼集合為{10,30,50,70,80,90},選取的散列函數(shù)為H(key)=key/10,則散列表為:0123456789103050708090適用情況?事先知道關(guān)鍵碼,關(guān)鍵碼集合不是很大且連續(xù)性較好。散列函數(shù)——直接定址法數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第37頁。389.5雜湊(Hash)文件散列函數(shù)為:H(key)=keymodp

關(guān)鍵碼如何選取合適的p,產(chǎn)生較少同義詞?例:p

=21=3×7散列函數(shù)——除留余數(shù)法數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第38頁。39根據(jù)關(guān)鍵碼在各個位上的分布情況,選取分布比較均勻的若干位組成散列地址。

例:關(guān)鍵碼為8位十進制數(shù),散列地址為2位十進制數(shù)81346

5

3

281372

2

4281387

4

2281301

3

6781322

8

1781338

9

67①②③④⑤⑥⑦⑧9.5雜湊(Hash)文件散列函數(shù)——數(shù)字分析法數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第39頁。40對關(guān)鍵碼平方后,按散列表大小,取中間的若干位作為散列地址(平方后截取)。事先不知道關(guān)鍵碼的分布且關(guān)鍵碼的位數(shù)不是很大。適用情況:例:散列地址為2位,則關(guān)鍵碼123的散列地址為:(1234)2=15227569.5雜湊(Hash)文件散列函數(shù)——平方取中法數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第40頁。41將關(guān)鍵碼從左到右分割成位數(shù)相等的幾部分,將這幾部分疊加求和,取后幾位作為散列地址。例:設(shè)關(guān)鍵碼為25346358705,散列地址為三位。

253463587

+05───1308

移位疊加

253364587+50───1254

間界疊加適用情況:關(guān)鍵碼位數(shù)很多,事先不知道關(guān)鍵碼的分布。9.5雜湊(Hash)文件散列函數(shù)——折疊法數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第41頁。42由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了沖突,就去尋找下一個空的散列地址,并將記錄存入。

如何尋找下一個空的散列地址?(1)線性探測法(2)二次探測法(3)隨機探測法9.5雜湊(Hash)文件沖突處理方法—開放定址法數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第42頁。439.5雜湊(Hash)文件沖突處理——線性探測法當發(fā)生沖突時,從沖突位置的下一個位置起,依次尋找空的散列地址。

對于鍵值key,設(shè)H(key)=d,閉散列表的長度為m,則發(fā)生沖突時,尋找下一個散列地址的公式為:

Hi=(H(key)+di)%m

(di=1,2,…,m-1)用開放定址法處理沖突得到的散列表叫閉散列表。數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第43頁。44

例:有關(guān)鍵字序列為{36,7,40,11,16,81,22,8,14},Hash表表長為11,Hash(key)=key%11,用線性探測法處理沖突,建立Hash表

9.5雜湊(Hash)文件數(shù)據(jù)結(jié)構(gòu)-文件及查找全文共51頁,當前為第44頁。45

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論