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

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

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

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

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

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

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

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

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

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

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

此時(shí)可以分為下述三種情形：①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-樹(shù)4刪除6,16B-樹(shù)刪除例子：刪除15B-樹(shù)刪除例子（續(xù)）：刪除4B-樹(shù)刪除例子（續(xù)）：1、B+樹(shù)概念滿足如下條件的樹(shù)型結(jié)構(gòu)稱為一棵m階的B+樹(shù)：●樹(shù)中每個(gè)結(jié)點(diǎn)至多具有m棵子樹(shù)；●非根結(jié)點(diǎn)的每個(gè)分枝至少具有m/2棵子樹(shù)；●非葉結(jié)點(diǎn)的根結(jié)點(diǎn)至少具有兩棵子樹(shù)；●具有n棵子樹(shù)的結(jié)點(diǎn)具有n個(gè)關(guān)鍵碼。每個(gè)非葉結(jié)點(diǎn)中的關(guān)鍵碼ki

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

個(gè)關(guān)鍵碼和n

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

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

樹(shù)中關(guān)鍵碼刪除都在葉結(jié)點(diǎn)層進(jìn)行。當(dāng)刪除關(guān)鍵碼破壞了平衡條件時(shí)，則需與相應(yīng)兄弟結(jié)點(diǎn)進(jìn)行合并。10.4.2B+樹(shù)3散列文件也可稱哈希（hash）文件或者直接存取文件，其特點(diǎn)是使用散列存儲(chǔ)方式組織文件。散列文件根據(jù)文件記錄關(guān)鍵字特征，設(shè)計(jì)相應(yīng)散列函數(shù)和沖突處理的技術(shù)方法，從而完成將記錄散列存儲(chǔ)到外存儲(chǔ)器。散列文件不宜使用磁帶或光盤存儲(chǔ)而比較適宜于磁盤存儲(chǔ)；另外，散列文件這種結(jié)構(gòu)更適合于定長(zhǎng)記錄文件和按主鍵隨機(jī)查找的訪問(wèn)方式。散列文件來(lái)說(shuō)，磁盤上一個(gè)文件中所有記錄一般“分組”存放。具體而言，就是文件中若干個(gè)記錄組成一個(gè)稱為“桶”的存儲(chǔ)單位，由若干個(gè)“桶”來(lái)存放一個(gè)散列文件。散列文件也可采用散列表中處理沖突的各種方法，但散列文件處理沖突的基本方法是鏈地址法。（基桶、溢出桶）§10.5散列文件例：假定某個(gè)文件有20個(gè)記錄，其中關(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，其對(duì)應(yīng)的散列文件如下所示：§10.5散列文件2查找記錄首先根據(jù)待查記錄的關(guān)鍵字值求得散列地址（即基桶地址），將基桶的記錄讀入內(nèi)存進(jìn)行順序查找，若找到某記錄的關(guān)鍵字等于待查記錄的關(guān)鍵