數(shù)據(jù)結(jié)構(gòu)-文件教材

第十章文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第1頁。文件的應(yīng)用背景，數(shù)據(jù)結(jié)構(gòu)范疇的文件概念?；跈z索的文件的基本形式與特點(diǎn)。常用的文件方式和關(guān)鍵技術(shù)實(shí)現(xiàn)要點(diǎn)。學(xué)習(xí)要點(diǎn)：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第2頁。10.1.1文件

文件（file）文件是性質(zhì)相同、邏輯上相關(guān)的數(shù)據(jù)記錄集合。按數(shù)據(jù)記錄的長度是否確定而分為定長文件和不定長文件：●定長文件：文件中所有記錄含有的數(shù)據(jù)項(xiàng)個數(shù)相同?！癫欢ㄩL文件：文件中記錄含有的數(shù)據(jù)項(xiàng)個數(shù)不等?！?0.1文件基本概念數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第3頁。按文件實(shí)際用途可以分為操作系統(tǒng)文件和數(shù)據(jù)庫文件：①操作系統(tǒng)文件無嚴(yán)格意義下的數(shù)據(jù)結(jié)構(gòu)，只是作為記錄的集合，主要表現(xiàn)為一維無結(jié)構(gòu)連續(xù)字符序列，記錄之間既沒有結(jié)構(gòu)的解釋也沒有特性的解釋；相應(yīng)文件操作只有“整體”操作即打開或關(guān)閉文件、刪除文件或復(fù)制文件等；以及“字節(jié)”操作即從文件讀取一個字節(jié)或?qū)⒁粋€字節(jié)寫到文件當(dāng)中。②數(shù)據(jù)庫文件各項(xiàng)記錄之間具有嚴(yán)格的邏輯結(jié)構(gòu)（例如基本的線性表結(jié)構(gòu)、關(guān)系文件和面向?qū)ο笪募Y(jié)構(gòu)等），同時每個記錄也有相應(yīng)結(jié)構(gòu)，即數(shù)據(jù)庫記錄由若干數(shù)據(jù)項(xiàng)構(gòu)成。10.1.1文件2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第4頁。數(shù)據(jù)庫文件：例：下圖是一個學(xué)生學(xué)籍文件，每個學(xué)生情況形成一個記錄。每個記錄由學(xué)號、姓名、性別、籍貫、出生年月和住址6個數(shù)據(jù)項(xiàng)組成。定義“學(xué)號”是主關(guān)鍵字，“姓名”、“性別”等是次關(guān)鍵字。10.1.1文件3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第5頁。按只有主關(guān)鍵字還是同時具有主關(guān)鍵字和次關(guān)鍵字而分為單關(guān)鍵字文件或多關(guān)鍵字文件：●單關(guān)鍵字文件：記錄中只有一個惟一標(biāo)識記錄的主關(guān)鍵字?！穸嚓P(guān)鍵字文件：記錄中除了含有一個主關(guān)鍵字外還含有若干個次關(guān)鍵字。10.1.1文件4數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第6頁。1、文件邏輯結(jié)構(gòu)作為存儲在外存中的數(shù)據(jù)，文件是具有相同性質(zhì)的記錄集合，其邏輯結(jié)構(gòu)應(yīng)當(dāng)為集合。但在實(shí)際操作過程中，文件中各個記錄至少都是“順次”進(jìn)入計(jì)算機(jī)的，即其至少具有“工作”順序，在這種意義下，通常將文件看作一種線性表，或者說，文件就是外存中的線性表。注意區(qū)分文件中記錄的“順序”（sequential）概念和文件記錄的“有序”（order）概念。10.1.2文件結(jié)構(gòu)與操作數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第7頁。2、文件存儲結(jié)構(gòu)

存儲結(jié)構(gòu)是文件在物理存儲介質(zhì)（磁盤或磁帶）上的組織方式，它決定了文件信息在存儲設(shè)備上的存儲位置。①順序文件順序文件在邏輯上是將數(shù)據(jù)記錄間的順序作為相應(yīng)線性表中元素的“次序”關(guān)系，在存儲上，這種順序關(guān)系與物理存儲順序一致。②索引文件在存儲的文件之外，建立一個相對于主文件用于描述文件邏輯記錄與物理存儲記錄之間的一一關(guān)系（即文件的第i號記錄對應(yīng)存儲的物理地址）的索引表，此時，主文件和其索引表構(gòu)成的二元組就稱為索引文件。③散列文件散列文件也稱為哈希（hash）文件或者直接存取文件，其特點(diǎn)是使用散列存儲方式組織文件。④鏈?zhǔn)轿募準(zhǔn)轿募械倪B結(jié)點(diǎn)一般都比較大，同時也不定長。在文件存儲方式中，鏈?zhǔn)轿募ǔ６际墙Y(jié)合索引文件一起使用，例如多關(guān)鍵字文件等。10.1.2文件結(jié)構(gòu)與操作2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第8頁。3、文件基本操作（1）文件檢索

文件檢索就是在文件中查找滿足給定條件的數(shù)據(jù)記錄，實(shí)現(xiàn)途徑可以是按照記錄進(jìn)入外存的時間順序（邏輯序號）查找，也可以是按照記錄的關(guān)鍵字大小查找。①順序檢索

通過逐次讀取所有序號小于i的記錄，定位所需要的第i號記錄。②直接檢索不通過逐次讀取所有序號小于i的記錄而直接定位第i號記錄。直接檢索也稱為隨機(jī)檢索。③按關(guān)鍵字檢索定位關(guān)鍵字與給定關(guān)鍵字相同或相關(guān)的數(shù)據(jù)記錄?！窈唵螜z索：詢問單個關(guān)鍵字等于給定值的記錄。●范圍檢索：詢問單個關(guān)鍵字屬于某個范圍內(nèi)的所有記錄。●函數(shù)檢索：規(guī)定單個關(guān)鍵字的某個函數(shù)，詢問該函數(shù)的某個值?！癫紶枡z索：以上三種詢問用布爾運(yùn)算(與、或、非)組合起來的詢問。例如查詢某成績表中，查找表中(數(shù)學(xué)成績>90)and（性別=“女”)的記錄。10.1.2文件結(jié)構(gòu)與操作3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第9頁。3、文件基本操作（1）文件檢索2按操作的處理方式，可分為實(shí)時與批量處理兩種不同的方式:實(shí)時處理：響應(yīng)時間要求嚴(yán)格，要求在接受詢問后幾秒種內(nèi)完成檢索和更新。批量處理：響應(yīng)時間要求寬松一些，不同的文件系統(tǒng)有不同的要求。

例如一個銀行的賬戶系統(tǒng)，需要滿足實(shí)時檢索要求，也可進(jìn)行批量更新，即可以將一天的存款和提款記錄在一個事務(wù)文件上，在一天的營業(yè)之后再進(jìn)行批量處理。10.1.2文件結(jié)構(gòu)與操作3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第10頁。3、文件基本操作2（2）文件更新

數(shù)據(jù)庫文件的維護(hù)操作可以分為文件更新、故障恢復(fù)、安全性保護(hù)和完整性約束等基本情形。文件更新操作類型：

●插入記錄在給定文件中插入給定的數(shù)據(jù)記錄。此時是針對整條數(shù)據(jù)記錄的操作。●刪除記錄在給定文件中刪除其中一條或多條記錄，此時也是針對整條記錄的操作?！裥薷挠涗浽诮o定文件中修改其中一條記錄的某個或多個數(shù)據(jù)項(xiàng)，此時是針對記錄中部分?jǐn)?shù)據(jù)項(xiàng)的操作。10.1.2文件結(jié)構(gòu)與操作3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第11頁。10.2.1順序文件存儲結(jié)構(gòu)順序文件在存儲介質(zhì)中可以有兩種不同的存儲結(jié)構(gòu)：連續(xù)結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。連續(xù)結(jié)構(gòu)是指邏輯上相鄰的記錄其存儲位置是相鄰的;連續(xù)順序文件鏈?zhǔn)浇Y(jié)構(gòu)是指物理記錄之間的次序由指針鏈來表示。鏈接順序文件§10.2順序文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第12頁。10.2.2基于磁帶/磁盤的順序存儲1、基于順序存儲器的順序文件存儲在順序存儲器（如磁帶）上的文件，只能是順序文件，這種文件只能進(jìn)行“順序存取”和“成批處理”。磁帶是一種典型的順序存儲設(shè)備。磁帶適合于存放文件數(shù)據(jù)量大、文件中的記錄平時變化少、只作批量修改的情況。存儲在磁帶上的順序文件只能采用順序查找法，即順序掃描文件，按記錄的主關(guān)鍵字逐個查找。優(yōu)點(diǎn)：連續(xù)存取時速度快，例如，如果文件中的第i個記錄剛被存取過，而下一個要存取的記錄就是第i+1個記錄，則此次存取將會很快完成。批處理效率高，節(jié)省存儲空間。缺點(diǎn)：實(shí)時性差，特別是更新操作要復(fù)制整個文件，所以一般不做隨機(jī)處理，如刪除記錄時只做標(biāo)記處理?！?0.2順序文件2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第13頁。10.2.2基于磁帶/磁盤的順序存儲22、基于直接存儲器的順序文件順序文件也可以存放在直接存取設(shè)備上，磁盤就是一個直接存取的存儲設(shè)備。存放于磁盤上的文件，既可以是順序文件，也可以是索引結(jié)構(gòu)或其它結(jié)構(gòu)類型的文件。對存儲在這類設(shè)備上的順序文件不僅可以進(jìn)行順序存取，還可進(jìn)行分塊查找、二分查找等查找方法。

對磁盤等直接存取設(shè)備，還可以對順序文件進(jìn)行插值查找和跳步查找。§10.2順序文件2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第14頁。10.3.1索引概念及操作索引結(jié)構(gòu)是當(dāng)文件信息存放在若干不連續(xù)物理塊中時，系統(tǒng)為該文件建立一個專用數(shù)據(jù)結(jié)構(gòu)即索引表，需要存儲的文件（主文件）和索引表構(gòu)成的二元組就是索引文件。作為文件信息所在邏輯塊號和與相應(yīng)物理塊號之間的對照表，索引表中每一個記錄稱作索引項(xiàng)。索引項(xiàng)由主關(guān)鍵字（或邏輯記錄號）和該關(guān)鍵字所屬文件記錄的物理塊號組成。索引表的基本特征是其中索引項(xiàng)必須按關(guān)鍵字（或邏輯記錄號）有序排列而無論主文件是否按關(guān)鍵字有序。如果主文件本身按照主關(guān)鍵字有序，就稱相應(yīng)索引文件為索引順序文件；如果主文件不是按照關(guān)鍵字有序，則稱相應(yīng)索引文件為索引非順序文件。§10.3索引文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第15頁。10.3.1索引概念及操作2索引順序文件通常有ISAM（IndexedSequentialAccessMethod）文件和VSAM（VirtualStorageAccessMethod）文件兩種類型。索引非順序文件通常有B-樹和B+樹等方式?！?0.3索引文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第16頁。10.3.1索引概念及操作3索引文件操作主要是查找和修改兩種情形。●索引文件查找一般分為直接存取和按關(guān)鍵字存取，檢索可以分成兩步進(jìn)行：首先在索引表容量合適的情況下，將索引表讀入內(nèi)存；然后根據(jù)關(guān)鍵字或邏輯記錄號通過二分查找方法在索引表中查找記錄是否存在。此時在查找記錄成功情況下至少需要訪問外存兩次?！袼饕募薷牟迦胗涗洉r，記錄插入在主文件的末尾，同時在索引表中合適的位置插入索引項(xiàng)，而刪除記錄時，在索引表中刪除相應(yīng)的索引項(xiàng)。由于索引表具有順序存儲結(jié)構(gòu)，插入和刪除后應(yīng)當(dāng)保持新的索引表的順序結(jié)構(gòu)，因此可能需要移動大量的索引記錄。更新記錄時，將更新后的記錄插入在主文件的末尾，同時修改相應(yīng)的索引項(xiàng)?！?0.3索引文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第17頁。ISAM(IndexedSequentialAccessMethod)即“索引順序存取方法”是一種專為磁盤存取文件設(shè)計(jì)的文件組織方式，采用靜態(tài)索引結(jié)構(gòu)。1、ISAM文件結(jié)構(gòu)ISAM對磁盤上的數(shù)據(jù)文件建立盤組、柱面和磁道三級索引。各級索引結(jié)構(gòu)如下：10.3.2ISAM文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第18頁。ISAM文件結(jié)構(gòu)圖：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第19頁。2、ISAM文件檢索從主索引出發(fā)，找到相應(yīng)的柱面索引；從柱面索引找到記錄所在柱面的磁道索引；從磁道索引找到記錄所在磁道的起始地址，由此出發(fā)在該磁道上進(jìn)行順序查找，直到找到為止。若找遍該磁道均不存在此記錄，則表明該文件中無此記錄；若被查找的記錄在溢出區(qū)，則可以從磁道索引項(xiàng)的溢出索引項(xiàng)中得到溢出鏈表的頭指針，然后對該表進(jìn)行順序查找。10.3.2ISAM文件2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第20頁。3、ISAM文件的插入和刪除插入新紀(jì)錄時，首先找到它應(yīng)插入的磁道，若該磁道不滿，則將新紀(jì)錄插入該磁道的適當(dāng)位置上即可；若該磁道已滿，則新紀(jì)錄或插在該磁道上，或直接插入到該磁道的溢出鏈表上。插入后，可能要修改磁道索引中的基本索引項(xiàng)和溢出索引項(xiàng)。刪除記錄時，只要找到待刪除的記錄，在其存儲位置上作刪除標(biāo)記即可，而不需要移動記錄或改變指針。在經(jīng)過多次的增刪后，文件的結(jié)構(gòu)可能變得很不合理。因此，通常需要周期性地整理ISAM文件，把記錄讀入內(nèi)存重新排列，復(fù)制成一個新的ISAM文件，填滿基本區(qū)而空出溢出區(qū)。10.3.2ISAM文件3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第21頁。VSAM（VirtualStorageAccessMethod）即“虛擬存儲存取方法”也是一種索引順序文件的組織方式，采用B+樹作為動態(tài)索引結(jié)構(gòu)。

1、VSAM文件結(jié)構(gòu)VSAM文件的結(jié)構(gòu)由三部分組成：索引集、順序集和數(shù)據(jù)集10.3.3VSAM文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第22頁。VSAM文件結(jié)構(gòu)示意圖：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第23頁。2、VSAM文件的插入和刪除VSAM文件中沒有溢出區(qū)，解決插入的方法是在初建文件時留出空間：一是每個控制區(qū)間內(nèi)不填滿記錄，在最后一個記錄和控制信息之間留有空隙；二是在每個控制區(qū)域中有一些完全空的控制區(qū)間，并在順序集的索引中指明這些空區(qū)間。當(dāng)插入新紀(jì)錄時，大多數(shù)的新紀(jì)錄能插入到相應(yīng)的控制區(qū)間內(nèi)，但要注意保持區(qū)間記錄的關(guān)鍵字從小至大有序。在VSAM文件中刪除記錄時，需將同一控制區(qū)間中比刪除記錄關(guān)鍵字大的記錄向前移動，把空間留給以后插入的新紀(jì)錄。若整個控制區(qū)間變空，則將其回收用作空閑區(qū)間，且需刪除順序集中相應(yīng)的索引項(xiàng)。10.3.3VSAM文件2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第24頁。3、ISAM和VSAM比較ISAM是一種專為磁盤存取設(shè)計(jì)的文件組織形式，采用靜態(tài)索引結(jié)構(gòu)，對磁盤上的數(shù)據(jù)文件建立盤組、柱面、磁道三級索引。ISAM文件中的記錄按關(guān)鍵字順序存放。經(jīng)過多次插入和刪除記錄后，文件結(jié)構(gòu)變得不合理，需定時整理ISAM文件。和ISAM文件相比，給基于B+樹的VSAM文件有如下優(yōu)點(diǎn)：能保持較高的查找效率，查找一個后插入記錄和查找一個原有記錄具有相同的速度；動態(tài)地分配和釋放存儲空間，可以保持平均75%的存儲利用率；永遠(yuǎn)不必對文件進(jìn)行再組織。因而基于B+樹的VSAM文件，通常作為大型索引順序文件的標(biāo)準(zhǔn)組織。VSAM文件采用B+樹動態(tài)索引結(jié)構(gòu)，文件只有控制區(qū)間和控制區(qū)域等邏輯存儲單位，與外存儲器中的柱面，磁道等具有存儲單位沒有必然聯(lián)系。VSAM文件結(jié)構(gòu)包括索引集、順序集和數(shù)據(jù)集三部分，記錄存放于數(shù)據(jù)集中，順序集和索引集構(gòu)成B+樹，作為文件的索引部分。10.3.3VSAM文件3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第25頁。10.4.1B-樹1、B-樹基本概念一棵m階（m≥3）B-樹或者為空樹，或者是滿足下述條件的m叉樹：①樹中每個結(jié)點(diǎn)至多有m棵子樹；②若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則至少有兩棵子樹；③所有非葉結(jié)點(diǎn)都包含信息：（n，p0，k1，p1，k2，p2，…，kn，pn），其中：ki（1≤i≤n）為關(guān)鍵碼，且ki＜ki+1（1≤i＜n）；pj（0≤j≤n）為指向子樹根結(jié)點(diǎn)的指針，且pj（0≤j<n）所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均小于kj+1，pn所指子樹中所有結(jié)點(diǎn)的關(guān)鍵碼均大于kn；n（m/2-1≤n≤m-1）為關(guān)鍵碼個數(shù)（n+1為子樹個數(shù)）。④根結(jié)點(diǎn)外所有非葉結(jié)點(diǎn)至少有m/2棵子樹，即每個內(nèi)部結(jié)點(diǎn)至少有m/2-1個關(guān)鍵碼；⑤所有葉結(jié)點(diǎn)都位于樹的同一層次。葉結(jié)點(diǎn)本身都不帶有數(shù)據(jù)信息，可以看作外部結(jié)點(diǎn)或查找失敗的結(jié)點(diǎn)。§10.4動態(tài)索引B-樹數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第26頁。1、B-樹基本概念2一棵3階B-樹實(shí)例：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第27頁。1、B-樹基本概念3B-樹存儲結(jié)構(gòu)中結(jié)點(diǎn)類型定義：00#defineMAXM1001typedefintKeyType;03tepedefstructnode04{05intkeynum;06KeyTypekey[MAXM];07structnode*patent;08structnode*ptr[MAXM];09}BTNode;10intm;11intMax;12intMin;數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第28頁。2、B-樹查找在一棵B-樹上進(jìn)行順序查找關(guān)鍵碼k的步驟如下：將k與根結(jié)點(diǎn)中k[i]進(jìn)行比較：●若k=k[i]，查找成功?！袢鬹＜k[i]，沿指針ptr[0]所指子樹繼續(xù)進(jìn)行查找?！袢鬹[i]＜k＜k[i+1]，沿指針ptr[i]所示子樹繼續(xù)查找?！袢鬹＞k[n]，沿指針ptr[n]所指子樹繼續(xù)查找。10.4.1B-樹2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第29頁。2、B-樹查找2算法10-1B-樹查找算法00ResultSearchBTree(BTree*T,KeyTypeK)01{02BTree*p,*q;03intn,i;04 p=T;05q=NULL;06i=0;07 while(p)08 {09n=p->keynum;10i=Search(p,K);/*在p->key[0..keynum-1]中查找i*/11p->key[i]<=K<p->key[i+1]10.4.1B-樹2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第30頁。2、B-樹查找2算法10-1B-樹查找算法12 if(i>0&&p->key[i]==K)13return(p,i,1);/*查找成功*/14 else15{16q=p;/*q指示p的雙親*/17p=p->ptr[i];18}19 }20 return(q,i,0);/*查找不成功*/21}10.4.1B-樹2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第31頁。3、B-樹插入與生成（1）B-樹插入step1.位置查找在B-樹中查找k，若找到則直接返回（假設(shè)不處理相同關(guān)鍵碼插入）；否則查找操作失敗于某葉結(jié)點(diǎn),將k插入到p所指葉結(jié)點(diǎn)第pos個位置上。step2.非滿插入若該葉結(jié)點(diǎn)原來是非滿（結(jié)點(diǎn)中原有關(guān)鍵碼總數(shù)小于m-1），插入k不會破壞B-樹平衡性質(zhì)，插入k后即完成了插入操作。step3.滿則分裂若p所指示葉結(jié)點(diǎn)為滿，插入k后keynum=m，破壞B-樹平衡性質(zhì)，須進(jìn)行調(diào)整以維持B-樹性質(zhì)不變。step4.分裂傳遞將km/2插入父結(jié)點(diǎn)后，父結(jié)點(diǎn)亦可能原本為滿，即添加后父結(jié)點(diǎn)中關(guān)鍵碼個數(shù)也破壞了的平衡性質(zhì)，則需要按照“step3”方法進(jìn)行在分裂，再將新的中間位置關(guān)鍵碼和新結(jié)點(diǎn)向上添加，這個過程可能傳遞到根結(jié)點(diǎn)為止。10.4.1B-樹3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第32頁。3、B-樹插入與生成2（2）B-樹生成設(shè)有關(guān)鍵碼為1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15，創(chuàng)建一棵5階B-樹關(guān)鍵碼插入過程如下：插入1,2,6,7插入11插入4,8,13插入1010.4.1B-樹3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第33頁。設(shè)有關(guān)鍵碼為1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15，創(chuàng)建一棵5階B-樹關(guān)鍵碼插入過程如下：插入5,17,9,16插入20插入3,12,14，18,19B-樹生成例子（續(xù)）：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第34頁。設(shè)有關(guān)鍵碼為1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，18，19，15，創(chuàng)建一棵5階B-樹關(guān)鍵碼插入過程如下：插入15B-樹生成例子（續(xù)）：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第35頁。4、B-樹刪除B-樹中刪除關(guān)鍵碼k的基本步驟如下：Step1.結(jié)點(diǎn)查找Step2.非葉結(jié)點(diǎn)關(guān)鍵碼刪除Step3.葉結(jié)點(diǎn)關(guān)鍵碼刪除

此時可以分為下述三種情形：①k所在葉子上面一層結(jié)點(diǎn)中的關(guān)鍵碼數(shù)目不小于m/2。②k所在葉子上面一層結(jié)點(diǎn)中的關(guān)鍵碼數(shù)目等于m/2-1，而與該結(jié)點(diǎn)相鄰的右兄弟結(jié)點(diǎn)（或左兄弟結(jié)點(diǎn)）中的關(guān)鍵碼數(shù)目大于m/2-1。③k所在葉子上面一層結(jié)點(diǎn)中的關(guān)鍵碼數(shù)和其相鄰的兄弟結(jié)點(diǎn)中的關(guān)鍵碼數(shù)目均等于m/2-1。10.4.1B-樹4數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第36頁。刪除6,16B-樹刪除例子：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第37頁。刪除15B-樹刪除例子（續(xù)）：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第38頁。刪除4B-樹刪除例子（續(xù)）：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第39頁。1、B+樹概念滿足如下條件的樹型結(jié)構(gòu)稱為一棵m階的B+樹：●樹中每個結(jié)點(diǎn)至多具有m棵子樹；●非根結(jié)點(diǎn)的每個分枝至少具有m/2棵子樹；●非葉結(jié)點(diǎn)的根結(jié)點(diǎn)至少具有兩棵子樹；●具有n棵子樹的結(jié)點(diǎn)具有n個關(guān)鍵碼。每個非葉結(jié)點(diǎn)中的關(guān)鍵碼ki

即為其相應(yīng)指針?biāo)缸訕渲嘘P(guān)鍵碼的最大值；●所有葉結(jié)點(diǎn)都位于樹的同一層面，每個葉結(jié)點(diǎn)含有n

個關(guān)鍵碼和n

個指向記錄的指針；每個葉結(jié)點(diǎn)中關(guān)鍵碼個數(shù)n滿足m/2≤n≤m；所有葉子結(jié)點(diǎn)彼此相鏈接構(gòu)成一個有序鏈表，其頭指針指向含最小關(guān)鍵碼的結(jié)點(diǎn)。10.4.2B+樹數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第40頁。一棵4階B+樹實(shí)例：數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第41頁。2、B+樹查找B+樹一般都設(shè)有兩個頭指針，一個指向根結(jié)點(diǎn)，另一個指向關(guān)鍵碼最小的葉結(jié)點(diǎn)，B+樹所有葉結(jié)點(diǎn)構(gòu)成一個線性鏈表。這樣的數(shù)據(jù)結(jié)構(gòu)既可實(shí)現(xiàn)基于最小關(guān)鍵碼的順序查找，也可實(shí)現(xiàn)基于根結(jié)點(diǎn)進(jìn)行縮小范圍的隨機(jī)查找。在縮小范圍的查找時，無論成功與否都須查找到葉結(jié)點(diǎn)方可結(jié)束；若在結(jié)點(diǎn)內(nèi)查找時，給定值k≤ki，則應(yīng)繼續(xù)在ai

所指子樹中進(jìn)行查找。B+樹中每次查找都需要完成一條由根結(jié)點(diǎn)到某個葉結(jié)點(diǎn)的路徑。在實(shí)際應(yīng)用中，B+樹葉結(jié)點(diǎn)通常不是只對應(yīng)一個記錄（稠密索引），而是對應(yīng)一個磁盤塊（稀疏索引）。10.4.2B+樹2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第42頁。3、B+樹插入和刪除B+樹中關(guān)鍵碼插入都在葉結(jié)點(diǎn)層進(jìn)行。當(dāng)結(jié)點(diǎn)中原關(guān)鍵碼個數(shù)等于m時，同樣需要進(jìn)行相應(yīng)分割。同時還需要使得它們的父結(jié)點(diǎn)中包含這兩個結(jié)點(diǎn)的最大關(guān)鍵碼和指向它們的指針。當(dāng)其結(jié)點(diǎn)關(guān)鍵碼個數(shù)因此而大于m時，需要繼續(xù)分裂，依次類推。B+

樹中關(guān)鍵碼刪除都在葉結(jié)點(diǎn)層進(jìn)行。當(dāng)刪除關(guān)鍵碼破壞了平衡條件時，則需與相應(yīng)兄弟結(jié)點(diǎn)進(jìn)行合并。10.4.2B+樹3數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第43頁。散列文件也可稱哈希（hash）文件或者直接存取文件，其特點(diǎn)是使用散列存儲方式組織文件。散列文件根據(jù)文件記錄關(guān)鍵字特征，設(shè)計(jì)相應(yīng)散列函數(shù)和沖突處理的技術(shù)方法，從而完成將記錄散列存儲到外存儲器。散列文件不宜使用磁帶或光盤存儲而比較適宜于磁盤存儲；另外，散列文件這種結(jié)構(gòu)更適合于定長記錄文件和按主鍵隨機(jī)查找的訪問方式。散列文件來說，磁盤上一個文件中所有記錄一般“分組”存放。具體而言，就是文件中若干個記錄組成一個稱為“桶”的存儲單位，由若干個“桶”來存放一個散列文件。散列文件也可采用散列表中處理沖突的各種方法，但散列文件處理沖突的基本方法是鏈地址法。（基桶、溢出桶）§10.5散列文件數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第44頁。例：假定某個文件有20個記錄，其中關(guān)鍵字集合為{12,23,17,26,21,35,28,18,27,22,7，9,46,19,6,16,30,19,10,64}。桶的容量m=3，桶數(shù)b=9，用除留余數(shù)法作散列函數(shù)H（key）=key%9，其對應(yīng)的散列文件如下所示：§10.5散列文件2數(shù)據(jù)結(jié)構(gòu)——文件教材全文共53頁，當(dāng)前為第45頁。查找記錄首先根據(jù)待查記錄的關(guān)鍵字值求得散列地址（即基桶地址），將基桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到某記錄的關(guān)鍵字等于待查記錄的關(guān)鍵字，則查找成功；若基桶內(nèi)無帶查記錄且基桶內(nèi)指針為空，則文件中沒有待查記錄，查找失敗，若基桶內(nèi)無待查記錄且基桶內(nèi)指針不空,則將溢出桶中的記錄的如內(nèi)存進(jìn)行順序查找，若在某個溢