數(shù)據(jù)結(jié)構(gòu)-文件及查找

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