第一章樹的應用(2014)

1、教師：劉城霞*數(shù)據(jù)結構綜合設計*課程安排*課時安排：課時安排：32學時（講課學時（講課 8 上機上機 24）*上機安排：第十二周開始上機安排：第十二周開始*課程要求：先修課程要求：先修 高級程序設計語言，數(shù)高級程序設計語言，數(shù)據(jù)結構據(jù)結構*課件公共郵箱：課件公共郵箱：*密碼密碼:shujujiegou*內容簡介*數(shù)據(jù)結構數(shù)據(jù)結構是為了讓學生學會分析數(shù)據(jù)對象的特性，設計適合的數(shù)據(jù)結構，完成相應的運算，把現(xiàn)實世界中的問題轉化為計算機可識別的表示,用計算機幫助完成各種任務。*數(shù)據(jù)結構綜合設計數(shù)據(jù)結構綜合設計在原來數(shù)據(jù)結構的基礎上增加了一些針對某種或幾種數(shù)據(jù)結構的實踐題目及其講解。*除此之外，原數(shù)據(jù)結

2、構中一些較難的理論也單獨列出講解，彌補因數(shù)據(jù)結構中課時不足等問題造成的部分知識不全面。*內容簡介*本書內容共分4章*第1章 樹的應用*第2章 外排序算法*第3章 內存管理方法*第4章 文件的基本結構*第一章 樹的應用*3.1樹和二叉樹*樹樹*樹是n (n 0)個結點的有限集合。當n = 0時，集合為空集，稱為空樹。在任意一棵非空樹T中：* 有且僅有一個特定的，稱為根(root)的結點。* 當n 1時，除根結點以外的其余結點可分成m (m 0)個互不相交的有限集合T1，T2，Tm。其中每一個集合本身又是一棵樹，并稱其為根的子樹(subtree)。*二叉樹*二叉樹(binary tree)是n (

3、n 0) 個結點的有限集合，*n = 0時為空集，稱為空二叉樹；*n0時，二叉樹由一個根結點及兩棵互不相交、分別稱為左子樹和右子樹的二叉樹組成。*二叉樹和樹在概念上相同的是都有一個且僅有一個根結點，根結點無前驅結點，葉子結點無后繼結點。*不相同的是二叉樹中每個結點的度小于等于2，而且二叉樹的子樹有左右子樹之分。*二叉樹的性質*性質1：二叉樹第i層上的結點數(shù)目至多為2i-1(i1)。*性質2：深度為k的二叉樹至多有2k-1個結點(k1)。*性質3：在任何一棵二叉樹中，如果其終端結點數(shù)為n0，度為2的結點數(shù)為n2，則n0 = n2 + 1*一棵深度為k且有2k - 1個結點的二叉樹稱為滿二叉樹，若

4、在一棵深度為k (k 1) 的二叉樹中，第1層到第k-1層構成一棵深度為k-1的滿二叉樹，第k層的結點不滿2k-1個結點，而這些結點都滿放在該層最左邊，則此二叉樹稱為完全二叉樹。*二叉樹的性質*性質4：具有n個結點的完全二叉樹的深度為log2n+ 1。*性質5：對一棵有n個結點的完全二叉樹的結點按層自左向右編號，則對任一編號為i (1 i n)的結點有下列性質：* 若i = 1，則結點i是二叉樹的根，若i 1，則結點i的雙親結點是 i/2；*若2i n，則結點i有左孩子，左孩子的編號是2i，否則結點i無左孩子，并且是葉子結點；* 若2i + 1 n，則結點i有右孩子，右孩子的編號是2i + 1

5、，否則結點i無右孩子。*二叉樹鏈式存儲結構#define DATATYPE2 chartypedef struct node1 DATATYPE2 data; struct node1 *lchild, *rchild;BTree;*基本操作*構造、插入、刪除、遍歷等* 3.2B樹和B+樹 (1) (1)B-樹的概念：平衡多路查找樹平衡多路查找樹 一棵一棵m m階的階的B-B-樹，或為空樹，或為滿足下列特性的樹，或為空樹，或為滿足下列特性的m m叉樹叉樹1、樹中每個結點最多有、樹中每個結點最多有m棵子樹棵子樹2、若根結點不是葉子結點，則至少有兩棵子樹、若根結點不是葉子結點，則至少有兩棵子樹3、

6、除根之外的所有非終端（葉子）結點至少有、除根之外的所有非終端（葉子）結點至少有 棵子樹棵子樹2/m4、所有非終端結點中包含下列信息數(shù)據(jù)、所有非終端結點中包含下列信息數(shù)據(jù)(n, A0, K1, A1, K2, A2, , Kn, An)5、所有葉子結點都在同一層，不帶信息。、所有葉子結點都在同一層，不帶信息。 (可可以看作是外部結點或查找失敗的結點，實際上以看作是外部結點或查找失敗的結點，實際上這些結點不存在，指向這些結點的指針為空這些結點不存在，指向這些結點的指針為空)a. na. n為關鍵字的個數(shù)，多個關鍵字自小至大有序為關鍵字的個數(shù)，多個關鍵字自小至大有序排列，即：排列，即：K K1 1

7、K K2 2 K key1.keynump-key1.keynum中找中找i,i,使得使得p-keyiKkeyi+1p-keyiKkeyi+1 if(i0 & p-keyi=K) found=TRUE if(i0 & p-keyi=K) found=TRUE;/;/找到找到 else q=p; p=p-ptri; else q=p; p=p-ptri; if(found) return (p,i,1); if(found) return (p,i,1); /成功，返回位置成功，返回位置 else return(q,i,0); else return(q,i,0);/不成功，返回應插入位置不成功

8、，返回應插入位置 B-樹查找性能分析樹查找性能分析 一般情況下，一般情況下，B-樹文件存儲在磁盤上，則樹文件存儲在磁盤上，則 前一查中操作是在磁盤中進行的，即在磁盤上前一查中操作是在磁盤中進行的，即在磁盤上找到指針所指的結點。找到指針所指的結點。 后一查找為內存中進行的，也就是將所查結點后一查找為內存中進行的，也就是將所查結點內容讀入內存，利用順序查找或者折半查找找到內容讀入內存，利用順序查找或者折半查找找到關鍵字。關鍵字。 又因為磁盤查找比內存查找耗時多的多，所又因為磁盤查找比內存查找耗時多的多，所以以在在B-B-樹中進行查找時，其查找時間主要花費在樹中進行查找時，其查找時間主要花費在搜索結

9、點（訪問外存）上，即主要取決于搜索結點（訪問外存）上，即主要取決于B-B-樹的樹的深度。深度。問：問：1 1）含）含 N N 個關鍵字的個關鍵字的 m m 階階 B-B-樹可能達到的樹可能達到的最大深度最大深度 H H 為多少？為多少？B-樹查找性能分析樹查找性能分析2 2）深度為）深度為H+1H+1的的B-B-樹中，至少含有多少個結點？樹中，至少含有多少個結點？第第 2 層層 2 個個先推導每一層所含最少結點數(shù)：先推導每一層所含最少結點數(shù)：第第 1 層層 1 個個第第 H+1 層層 2 ( m/2 ) H-1 個個第第 4 層層 2 ( m/2 )2 個個第第 3 層層 2m/2 個個 B-

10、樹查找性能分析樹查找性能分析假設假設 m m 階階 B-B-樹的深度為樹的深度為 H+1H+1，由于第，由于第 H+1 H+1 層為層為葉子結點，而當前樹中含有葉子結點，而當前樹中含有 N N 個關鍵字，則葉子個關鍵字，則葉子結點必為結點必為 N+1N+1 個，個， N+12( m/2 )H-1 H-1log m/2 (N+1)/2) Hlog m/2 (N+1)/2)+1由此可推得下列結果：由此可推得下列結果：B-樹查找性能分析樹查找性能分析在含在含 n n 個關鍵字的個關鍵字的 B-B-樹上進行一次查找，需訪樹上進行一次查找，需訪問的結點個數(shù)不超過問的結點個數(shù)不超過結論：結論：1)21(l

11、og2/NmB-樹插入結點樹插入結點在查找不成功之后，需進行插入。顯然，在查找不成功之后，需進行插入。顯然，關鍵字關鍵字插入的位置必定在最下層的非葉結點插入的位置必定在最下層的非葉結點，有下列幾，有下列幾種情況：以三階種情況：以三階B B樹為例來說樹為例來說1 1）插入后，該結插入后，該結點的關鍵字個數(shù)點的關鍵字個數(shù)nmnptri+1* if(q-keynumkeys; /將將q-keys+1.m, q-ptrs.m和和q-recptrs+1.m 移入新結點移入新結點*ap* q=q-parent;* if(q) i=Search(q,x);* *If(!finished) /T為空樹或根結點

12、已分裂為空樹或根結點已分裂* newRoot(T,q,x,ap);*Return OK;*B-樹刪除結點樹刪除結點刪除操作和插入結點的考慮相反刪除操作和插入結點的考慮相反1 1）首先必須找到待刪關鍵字所在結點，并且要求刪除）首先必須找到待刪關鍵字所在結點，并且要求刪除之后，結點中關鍵字的個數(shù)不能小于之后，結點中關鍵字的個數(shù)不能小于 m/2m/2 -1-12 2）否則，要從其左）否則，要從其左( (或右或右) )兄弟結點兄弟結點“借調借調”關鍵字關鍵字3 3）若其左和右兄弟結點均無關鍵字可借）若其左和右兄弟結點均無關鍵字可借( (結點中只有最結點中只有最少量的關鍵字少量的關鍵字),),則必須進行

13、結點的則必須進行結點的“合并合并”。B-樹刪除結點樹刪除結點1.被刪除結點上關鍵字個數(shù)不少于被刪除結點上關鍵字個數(shù)不少于 m/2 -1，那么只，那么只需從該結點上刪除該關鍵字需從該結點上刪除該關鍵字Ki和相應的指針和相應的指針Ai。例如下圖例如下圖3-階階B樹中刪除關鍵字樹中刪除關鍵字12時，直接將時，直接將12 刪除刪除即可。即可。53 9024 50 100 3 12 37 45 61 70 3 abcdefghB-樹刪除結點樹刪除結點2.2.如果被刪除結點上關鍵字個數(shù)等于如果被刪除結點上關鍵字個數(shù)等于 m/2m/2 -1 -1，而與其相鄰的右兄弟結點（或左兄弟）結點中關而與其相鄰的右兄弟

14、結點（或左兄弟）結點中關鍵字的個數(shù)大于鍵字的個數(shù)大于 m/2m/2 -1 -1 則需將其兄弟結點中最?。ɑ蜃畲螅┑年P鍵則需將其兄弟結點中最小（或最大）的關鍵字上移至雙親結點中，而將雙親結點中小于（或字上移至雙親結點中，而將雙親結點中小于（或大于）大于）, ,且緊靠該上移關鍵字的關鍵字移至被刪且緊靠該上移關鍵字的關鍵字移至被刪關鍵字所在結點中。關鍵字所在結點中。B-樹刪除結點樹刪除結點下圖為刪除下圖為刪除5050前、后的前、后的3 3階階B-B-樹。圖中樹。圖中6161為上移為上移關鍵字，而關鍵字，而5353為小于為小于6161且緊靠且緊靠6161的下移到被刪關的下移到被刪關鍵字所在結點中。鍵字

15、所在結點中。53 9024 50 100 3 37 45 61 70 abcdefgh 70 61 90 53 B-樹刪除結點樹刪除結點3.3.被刪除關鍵字所在結點和其相鄰的右兄弟結點被刪除關鍵字所在結點和其相鄰的右兄弟結點（或左兄弟）結點中關鍵字的個數(shù)均等于（或左兄弟）結點中關鍵字的個數(shù)均等于 m/2m/2 -1 -1，假設該結點有右兄弟，且其右兄弟結點地址由雙親假設該結點有右兄弟，且其右兄弟結點地址由雙親結點中的指針結點中的指針AiAi所指，所指，則在刪去關鍵字之后，它所在結點中剩余的關鍵字則在刪去關鍵字之后，它所在結點中剩余的關鍵字和指針，加上雙親結點中的關鍵和指針，加上雙親結點中的關鍵

16、KiKi一起，合并到一起，合并到AiAi所指兄弟結點中（若沒有右兄弟，則合并到左兄弟所指兄弟結點中（若沒有右兄弟，則合并到左兄弟結點中）。結點中）。9061 90B-樹刪除結點樹刪除結點24 100 3 37 45abcdefgh 70 53 刪除關鍵字刪除關鍵字53 61 70 90B-樹刪除結點樹刪除結點24 100 3 37 45abcdegh練習：從下面的練習：從下面的B樹中刪除關鍵字樹中刪除關鍵字37 61 70 90B-樹刪除結點樹刪除結點24 100 37 45abcdegh刪除關鍵字刪除關鍵字37 61 70 3 2437沒有右兄弟且其左兄弟也只有一個關鍵字，沒有右兄弟且其左兄

17、弟也只有一個關鍵字，把把37 雙親結點中小于雙親結點中小于37 的關鍵字的關鍵字24 與左兄弟中的與左兄弟中的3合并成一個結點。合并成一個結點。此時，發(fā)現(xiàn)左右子樹高度不同，必須調整成此時，發(fā)現(xiàn)左右子樹高度不同，必須調整成B-樹。樹。 3 45 90 100 ech3 24 61 70 g45 90B-樹刪除結點樹刪除結點 100 ech3 24 61 70 g調整后的調整后的B-樹，如下所示樹，如下所示B-樹刪除算法步驟樹刪除算法步驟E1:E1:查找算法到要刪除關鍵字位置，刪除該關鍵字。查找算法到要刪除關鍵字位置，刪除該關鍵字。E2:E2:判斷刪除后關鍵字個數(shù)，如少于判斷刪除后關鍵字個數(shù)，如少

18、于 m/2m/2 -1 -1則進入則進入3 3，否則刪，否則刪除完成。除完成。E3:E3:找到其雙親結點（找到其雙親結點（parentparent指針），判斷其左兄弟關鍵字個數(shù)，指針），判斷其左兄弟關鍵字個數(shù)，如大于如大于 m/2m/2 -1, -1,則將其最大關鍵字取出（刪除）后插入雙親則將其最大關鍵字取出（刪除）后插入雙親結點，將雙親結點中的關鍵字插入該結點最左邊。否則對其右結點，將雙親結點中的關鍵字插入該結點最左邊。否則對其右兄弟做相同的處理。如均不滿足則進入兄弟做相同的處理。如均不滿足則進入E4E4。E4:E4:其兄弟結點的關鍵字和該結點的關鍵字合并，并且將其雙親其兄弟結點的關鍵字和該

19、結點的關鍵字合并，并且將其雙親中相應關鍵字取出也插入合并結點中，形成一個新的結點。如中相應關鍵字取出也插入合并結點中，形成一個新的結點。如雙親結點刪除一個關鍵字后滿足雙親結點刪除一個關鍵字后滿足E2E2要求，則結束；否則重復要求，則結束；否則重復E3E3。E5:E5:刪除完成后判斷是否平衡，不平衡則調整。（平衡樹的調整刪除完成后判斷是否平衡，不平衡則調整。（平衡樹的調整參照平衡二叉樹調整過程）參照平衡二叉樹調整過程）*B+樹是是B-樹的一種變型。樹的一種變型。1）有有n n棵子樹的結點中含有棵子樹的結點中含有n n個關鍵字個關鍵字2）所有的葉子結點中包含了全部關鍵字的信息，所有的葉子結點中包含

20、了全部關鍵字的信息，及指向含這些關鍵字記錄的指針，并且，所有葉及指向含這些關鍵字記錄的指針，并且，所有葉子結點彼此相鏈接構成一個有序鏈表，其頭指針子結點彼此相鏈接構成一個有序鏈表，其頭指針指向含最小關鍵字的結點；指向含最小關鍵字的結點；3）每個非葉結點中的關鍵字）每個非葉結點中的關鍵字K Ki i 即為其相應指針即為其相應指針A Ai i 所指子樹中關鍵字的最大值；所指子樹中關鍵字的最大值；*一個3階B+樹 50 96 15 5062 78 96 71 7884 89 96 56 6220 43 50 3 8 15sqroot*B+樹索引的總體結構 B B+ +樹索引是一個多級索引；樹索引是一

21、個多級索引； B B+ +樹索引采用平衡樹結構，即每個葉結樹索引采用平衡樹結構，即每個葉結點到根的路徑長度都相同；點到根的路徑長度都相同； 每個非葉結點有每個非葉結點有 m/2m/2 到到m m個子女，個子女，m m對對特定的樹是固定的；特定的樹是固定的； B B+ +樹的所有結點結構都相同，它最多包樹的所有結點結構都相同，它最多包含含m m個關鍵字值個關鍵字值K K1 1、K K2 2、K Km m，以及，以及m+1m+1個指個指針針P P1 1、P P2 2、P Pm m、 P Pm+1m+1, ,每個結點中的關鍵每個結點中的關鍵字值按次序存放，即如果字值按次序存放，即如果ijij，那么，

22、那么K Ki iKKj j。*B+樹索引的葉結點 指針指針P Pi i(i=1,2,n)(i=1,2,n)指向具有關鍵字值指向具有關鍵字值K Ki i的一個文件記錄的一個文件記錄( (或一個指針桶，桶中的每或一個指針桶，桶中的每個指針指向具有關鍵字值個指針指向具有關鍵字值KiKi的一個文件記錄。的一個文件記錄。指針桶只在文件不按關鍵字順序物理存儲時指針桶只在文件不按關鍵字順序物理存儲時才使用才使用) )。指針。指針P Pm+1m+1鏈接下一個葉節(jié)點；鏈接下一個葉節(jié)點；2*B+樹索引的葉結點* 每個葉結點最多可有每個葉結點最多可有m m個關鍵字值，最少也要有個關鍵字值，最少也要有 m/2m/2

23、個關鍵字值。各個葉結點中關鍵字值的范圍個關鍵字值。各個葉結點中關鍵字值的范圍互不相交。互不相交。*B+B+樹索引如果為稠密索引，數(shù)據(jù)文件中的各關鍵字樹索引如果為稠密索引，數(shù)據(jù)文件中的各關鍵字值都必須出現(xiàn)在某個葉結點中且只能出現(xiàn)一次。值都必須出現(xiàn)在某個葉結點中且只能出現(xiàn)一次。2*B+樹索引的葉結點 由于各葉結點按照所含的關鍵字值從小到大排由于各葉結點按照所含的關鍵字值從小到大排列，所以可以利用各個葉結點的指針列，所以可以利用各個葉結點的指針P Pm+1m+1將葉結點鏈將葉結點鏈接在一起。這個順序鏈能夠高效地對文件進行順序檢接在一起。這個順序鏈能夠高效地對文件進行順序檢索，而索，而B B+ +樹索

24、引的其他結構能夠高效地對文件進行隨樹索引的其他結構能夠高效地對文件進行隨機檢索。機檢索。*B+樹索引的非葉結點 B B+ +樹索引的非葉結點形成葉結點上的一樹索引的非葉結點形成葉結點上的一個多級（稀疏）索引；個多級（稀疏）索引；非葉結點的結構和葉結點的結構相同，即非葉結點的結構和葉結點的結構相同，即含有能夠存儲含有能夠存儲m m個關鍵字值和個關鍵字值和m+1m+1個指針的存?zhèn)€指針的存儲單元的數(shù)據(jù)結構。只不過非葉結點中的所儲單元的數(shù)據(jù)結構。只不過非葉結點中的所有指針都指向樹中的結點；有指針都指向樹中的結點；*B+樹索引的非葉結點 如果一個非葉結點有如果一個非葉結點有n n個指針，則個指針，則 m

25、/2m/2 nmnm。若。若nmnm，則非葉結點中指針，則非葉結點中指針P Pn n之后的所有之后的所有空閑空間作為預留空間如圖空閑空間作為預留空間如圖nnn*B+樹索引的非葉結點 在一個含有在一個含有m m個指針的非葉結點中，指針個指針的非葉結點中，指針P Pi i(i=2,m)(i=2,m)指向一棵子樹，該子樹的所有結點指向一棵子樹，該子樹的所有結點的關鍵字值大于的關鍵字值大于K Ki-1i-1而小于等于而小于等于K Ki i。*B+樹索引的根結點 根結點的結構也與葉結點相同；根結點的結構也與葉結點相同； 根結點包含的指針數(shù)可以小于根結點包含的指針數(shù)可以小于 m/2m/2 。但是，除非整棵

26、樹只有一個結點，否則根結但是，除非整棵樹只有一個結點，否則根結點必須至少包含兩個指針。點必須至少包含兩個指針。*B+樹在索引文件中的應用*用用B+B+樹組織索引順序文件時，用主文件的每個頁塊樹組織索引順序文件時，用主文件的每個頁塊作作B+B+樹的一個外部結點，并且這些頁塊之間相互鏈樹的一個外部結點，并且這些頁塊之間相互鏈接。接。B+B+樹的樹葉層是主文件的稀疏索引，整個樹的樹葉層是主文件的稀疏索引，整個B+B+樹樹構成多級索引。索引項就是構成多級索引。索引項就是B+B+樹中一個關鍵字和它樹中一個關鍵字和它對應的指針所構成的二元組。對應的指針所構成的二元組。*在用在用B+B+樹組成的索引順序文件

27、中，當主文件中需要樹組成的索引順序文件中，當主文件中需要增加或減少一個頁塊時，只需在增加或減少一個頁塊時，只需在B+B+樹中為之插入或樹中為之插入或刪除一個索引項，問題歸結為刪除一個索引項，問題歸結為B+B+樹本身的運算。樹本身的運算。*B+樹的操作*B+B+樹的查找可以分為兩類：樹的查找可以分為兩類：*一是順序查找，即從葉結點的順序鏈表中依次查找需一是順序查找，即從葉結點的順序鏈表中依次查找需要的記錄。要的記錄。*二是按索引查找，這種查找方法類似于二是按索引查找，這種查找方法類似于B-B-樹，只是在樹，只是在查找時，若非終端節(jié)點上的關鍵字等于給定值，并不查找時，若非終端節(jié)點上的關鍵字等于給定

28、值，并不終止，而是繼續(xù)向下直到葉子結點。終止，而是繼續(xù)向下直到葉子結點。*E1:E1:初始化，從根開始查找。初始化，從根開始查找。*E2:E2:查找結點內關鍵字查找結點內關鍵字, ,要求要求Key(i-1)K=Key(i)Key(i-1)KKey(m)KKey(m)或或KKey(1)Kkey1.keynump-key1.keynum中找中找I I / /使得使得p-keyip-keyi1Kkeyi1Kkeyi if(i0 & i0 & iptri; p=p-ptri; else else return (p,i,0); return (p,i,0); *If(p If(p 是葉子）是葉子）i=

29、Search(p, K); i=Search(p, K); if(i0 & ikeyi) if(i0 & ikeyi) return return （p,i,1p,i,1）; ; else else return (p,i,0); return (p,i,0);*B+樹的插入*在查找不成功之后，需進行插入。顯然，在查找不成功之后，需進行插入。顯然，關鍵字插入關鍵字插入的位置必定在最下層的葉子結點的位置必定在最下層的葉子結點，有下列幾種情況：，有下列幾種情況：*當結點中的關鍵字個數(shù)小于等于當結點中的關鍵字個數(shù)小于等于m m時直接插入；時直接插入；1.1.當結點中的關鍵字個數(shù)大于當結點中的關鍵字個

30、數(shù)大于m m時要分裂成兩個結點時要分裂成兩個結點, ,并且要在雙親結點中插入新增了的結點的最大關鍵字。并且要在雙親結點中插入新增了的結點的最大關鍵字。操作類似于操作類似于B-B-樹。樹。B+樹插入結點樹插入結點1 1、3 3階階 B+ B+樹插入關鍵字樹插入關鍵字60,9060,9040 80 20 40 8060 80 60 80 9040 902、3階階B樹插入關鍵字樹插入關鍵字7040 9020 40 60 80 90 60 70 80 90 60 70 80 90 40 70 90*插入步驟*E1:E1:從樹根開始查找要插入位置，并記錄從樹根開始查找要插入位置，并記錄查找路徑。查找路徑

31、。*E2:E2:建立新關鍵字及指針信息，插入葉子建立新關鍵字及指針信息，插入葉子結點中。結點中。*E3:E3:判斷結點關鍵字個數(shù)，若判斷結點關鍵字個數(shù)，若=mmm，則分裂結點，將新的最大，則分裂結點，將新的最大關鍵字插入雙親結點，重復關鍵字插入雙親結點，重復E3E3。*E4:E4:若根結點需要分裂，則新建根結點。若根結點需要分裂，則新建根結點。*使用B+樹索引結構插入記錄的算法* p= p=根結點根結點; ;* 棧棧S S清空清空; ; / S/ S存儲結點的父結點存儲結點的父結點* while p while p不是葉結點不是葉結點 * push(p,S);q= push(p,S);q=樹中

32、樹中p p結點子指針數(shù)結點子指針數(shù); ;/父結點入棧父結點入棧* if if （k k p-kp-k1 1）* p=p-p p=p-p1 1* else else * 找找i i 滿足滿足p-kp-ki-1i-1kkp-ki i ;p=p-p ;p=p-pi i ; ; * 若若p-kp-kn n k k 則則 p=p-p p=p-pn n ; ; * i=Search(p, K); i=Search(p, K); * if(i0 & ikeyi) if(i0 & ikeyi) * 記錄已存在記錄已存在;return;return;*elseelse* 建索引項建索引項(k,d),(k,d),

33、數(shù)據(jù)指針數(shù)據(jù)指針d d指向新記錄指向新記錄; ;*if if 葉點葉點* *p p 不滿不滿 * insert(p,k,d) / insert(p,k,d) / 插到插到* *p p的正確位置的正確位置*else else /對滿葉結點對滿葉結點* *p p作分裂處理作分裂處理* 把滿葉結點把滿葉結點* *p p的索引項復制到的索引項復制到tmp;tmp; /準備分裂準備分裂* 把索引項把索引項(k,d)(k,d)按序插入到按序插入到tmptmp的正確位置的正確位置; ;* 建立一個空的新葉結點建立一個空的新葉結點new;new;* 用用tmptmp的前的前ceil(m/2)ceil(m/2)

34、個索引項覆蓋結點個索引項覆蓋結點* *p p的信息的信息; ;* 把把tmptmp的其余索引項及相鄰葉指針存入的其余索引項及相鄰葉指針存入new;new;* p-P p-Pnextnext=new=new的地址的地址 ; k; k* *= =新的最大關鍵字新的最大關鍵字; ;* Finish=false; Finish=false; /準備把準備把(k(k* *,new),new)插入父親插入父親( (內內) )結點結點* *While (!finish)While (!finish)* if if 棧棧S S空空* root=NewRoot(m,k root=NewRoot(m,k* *,n

35、ew); /,new); /建立新空根結點建立新空根結點* finish=true; finish=true; * else else* * *p=pop(S); p=pop(S); /取出父結點取出父結點* if if 內結點內結點* *p p不滿不滿* 把把(k(k* *,new) ,new) 插入到插入到* *p;finish=true;p;finish=true;* else else* 復制滿內結點復制滿內結點* *p p到到tmp; tmp; * 對滿內結點對滿內結點* *p p分裂分裂; ; * *B+樹的刪除*B+B+樹的刪除也僅在葉子結點上進行，當葉子結樹的刪除也僅在葉子結點

36、上進行，當葉子結點中的最大關鍵字被刪除時，在非終端結點中點中的最大關鍵字被刪除時，在非終端結點中修改成當前最大關鍵字值。若因刪除使結點中修改成當前最大關鍵字值。若因刪除使結點中關鍵字的個數(shù)少于關鍵字的個數(shù)少于 m/2m/2 時，需要從兄弟結點中時，需要從兄弟結點中借一個關鍵字，如兄弟結點無法借出，則和其借一個關鍵字，如兄弟結點無法借出，則和其兄弟結點進行合并，過程同兄弟結點進行合并，過程同B-B-樹。樹。80 9961 80 99B樹刪除結點樹刪除結點24 45 88 993 2437 4545 99abcdefgh70 80 53 613階階B+樹刪除樹刪除53 61 61 70 80*B+

37、樹刪除的步驟E1:E1:查找算法到要刪除關鍵字位置，刪除該關鍵字。查找算法到要刪除關鍵字位置，刪除該關鍵字。E2:E2:判斷刪除后關鍵字個數(shù)，如少于判斷刪除后關鍵字個數(shù)，如少于 m/2m/2 則進入則進入E3E3，否則刪除完成。否則刪除完成。E3:E3:找到其雙親結點（找到其雙親結點（parentparent指針），判斷其右兄弟關指針），判斷其右兄弟關鍵字個數(shù)，如大于鍵字個數(shù)，如大于 m/2m/2 , ,則將其最小關鍵字取出則將其最小關鍵字取出（刪除）插入該結點最右邊，修改雙親結點中的最大（刪除）插入該結點最右邊，修改雙親結點中的最大關鍵字值。否則對其左兄弟做相同的處理。如均不滿關鍵字值。否則

38、對其左兄弟做相同的處理。如均不滿足則進入足則進入E4E4。E4:E4:其兄弟結點的關鍵字和該結點關鍵字合并，形成一其兄弟結點的關鍵字和該結點關鍵字合并，形成一新的結點。且將其雙親中相應關鍵字刪除，如雙親結新的結點。且將其雙親中相應關鍵字刪除，如雙親結點刪除一個關鍵字后滿足點刪除一個關鍵字后滿足E2E2要求則結束；否則重復要求則結束；否則重復E3E3。E5:E5:刪除完成后判斷是否平衡，不平衡則調整。刪除完成后判斷是否平衡，不平衡則調整。*B+的特性總結*B+B+的特性：的特性：*所有關鍵字都出現(xiàn)在葉子結點的鏈表中，且鏈表中的所有關鍵字都出現(xiàn)在葉子結點的鏈表中，且鏈表中的關鍵字是有序的；關鍵字是有序的；*查找不可能在非葉子結點命中；查找不可能在非葉子結點命中；*非葉子結點