數(shù)據(jù)結構 B樹.ppt

1、B樹,B樹,動態(tài)查找結構,現(xiàn)在我們所討論的m路查找樹多為可以動態(tài)調(diào)整的多路查找樹，它的一般定義為： 一棵m路查找樹, 它或者是一棵空樹, 或者是滿足如下性質(zhì)的樹： 根最多有 m 棵子樹, 并具有如下的結構： n, A0, ( K1, A1 ), ( K2, A2 ), , ( Kn, An ) 其中，Ai 是指向子樹的指針，0 i n m；Ki 是關鍵碼，1 i n m。 Ki Ki+1, 1 i n。,動態(tài)的m路查找樹,在子樹 Ai 中所有的關鍵碼都小于 Ki+1，且大于 Ki，0 i n。 在子樹 An 中所有的關鍵碼都大于Kn； 在子樹 A0 中的所有關鍵碼都小于 K1。 子樹 Ai 也

2、是 m 路查找樹，0 i n。,一棵3路查找樹的示例,AVL樹是2路查找樹。如果已知m路查找樹的度 m和它的高度 h, 則樹中的最大結點數(shù)為,(等比級數(shù)前 h 項求和),每個結點中最多有 m-1 個關鍵碼，在一棵高度為 h 的 m 路查找樹中關鍵碼的最大個數(shù)為 mh+1-1。 對于高度 h=2 的二叉樹，關鍵碼最大個數(shù)為7； 對于高度 h=3 的3路查找樹，關鍵碼最大個數(shù)為 34-1 = 80。,提高查找樹的路數(shù) m，可以改善樹的查找性能。對于給定的關鍵碼數(shù) n，如果查找樹是平衡的，可以使 m 路查找樹的性能接近最佳。下面我們將討論一種稱之為B-樹的平衡的 m 路查找樹。在B-樹中我們引入“失

3、敗”結點。一個失敗結點是當查找值x不在樹中時才能到達的結點。,B-樹,一棵 m 階B-樹是一棵 m 路查找樹，它或者是空樹，或者是滿足下列性質(zhì)的樹： 樹中每個結點至多有m棵子樹； 根結點至少有 2 棵子樹； 除根結點以外的所有非終端結點至少有 m/2 棵子樹； 所有非終端結點中包含下列信息數(shù)據(jù) ( n, A0 , K1 , A1 , K2 , A2 , , Kn , An )，其中： Ki (i=1,n)為關鍵字，且Ki Ki+1 , Ai (i=0,n)為指向子樹根結點的指針, n為關鍵字的個數(shù) 所有的葉子結點（失敗結點）都位于同一層。 事實上，每個結點中還應包含指向每個關鍵字的記錄的指針。

4、,非B-樹 B-樹,B-樹的查找算法,B-樹的查找過程是一個順指針查找結點和在結點的關鍵字進行查找交叉進行的過程。因此，B-樹的查找時間與B-樹的階數(shù)m和B-樹的高度h直接有關，必須加以權衡。 在B-樹上進行查找，查找成功所需的時間取決于關鍵碼所在的層次，查找不成功所需的時間取決于樹的高度。如果我們定義B-樹的高度h 為失敗結點所在的層次，需要了解樹的高度h 與樹中的關鍵碼個數(shù) N 之間的關系。,設在 m 階B-樹中，失敗結點位于第 h +1層。在這棵B-樹中關鍵碼個數(shù) N 最小能達到多少？ 從B-樹的定義知, 1層 1 個結點 2層 至少 2 個結點 3層 至少 2 m / 2 個結點 4層

5、 至少 2 m / 2 2 個結點 如此類推， h 層 至少有2 m / 2 h-2個結點。所有這些結點都不是失敗結點。,高度h與關鍵碼個數(shù) N 之間的關系,若樹中關鍵碼有 N 個, 則失敗結點數(shù)為 N +1。這是因為失敗一般發(fā)生在 Ki x Ki+1, 0 i N，設K0 = -，KN+1 = +。因此，有 N +1 = 失敗結點數(shù) = = 位于第 h+1 層的結點數(shù) 2 m / 2 h-1 N 2 m / 2 h-1-1 反之，如果在一棵 m 階B-樹中有 N 個關鍵碼，則所有的非失敗結點所在層次都小于 h，則 h-1 log m / 2 ( (N +1) / 2 ) 示例：若B-樹的階數(shù)

6、 m = 199，關鍵碼總數(shù) N = 1999999，則B-樹的高度 h 不超過 log100 1000000 +1= 4,若B-樹的階數(shù) m = 3，高度 h = 4，則關鍵碼總數(shù)至少為 N = 2 3 / 2 4-1-1 = 15。 m值的選擇 如果提高B-樹的階數(shù) m，可以減少樹的高度，從而減少讀入結點的次數(shù)，因而可減少讀磁盤的次數(shù)。 事實上，m 受到內(nèi)存可使用空間的限制。當 m很大超出內(nèi)存工作區(qū)容量時，結點不能一次讀入到內(nèi)存，增加了讀盤次數(shù)，也增加了結點內(nèi)查找的難度。,m值的選擇：應使得在B-樹中找到關鍵碼 x 的時間總量達到最小。 這個時間由兩部分組成： 從磁盤中讀入結點所用時間 在

7、結點中查找 x 所用時間 根據(jù)定義，B-樹的每個結點的大小都是固定的，結點內(nèi)有 m-1 個索引項 (Ki, Di, Ai), 1 i m。其中，Ki 所占字節(jié)數(shù)為，Di 和 Ai 所占字節(jié)數(shù)為，則結點大小近似為 m(+2) 個字節(jié)。讀入一個結點所用時間為： tseek + tlatency + m( + 2) ttran = a + bm,B-樹的插入,B-樹是從空樹起，逐個插入關鍵碼而生成的。 在B-樹，每個非失敗結點的關鍵碼個數(shù)都在 m/2 -1, m-1 之間。 插入在某個葉結點開始。如果在關鍵碼插入后結點中的關鍵碼個數(shù)超出了上界 m-1，則結點需要“分裂”，否則可以直接插入。 實現(xiàn)結點

8、“分裂”的原則是： 設結點 A 中已經(jīng)有 m-1 個關鍵碼，當再插入一個關鍵碼后結點中的狀態(tài)為,( m, A0, K1, A1, K2, A2, , Km, Am) 其中 Ki Ki+1, 1 i m 這時必須把結點 p 分裂成兩個結點 p 和 q，它們包含的信息分別為： 結點 p： ( m/2 -1, A0, K1, A1, , Km/2 -1, Am/2 -1) 結點 q： (m - m/2, Am/2, Km/2+1, Am/2+1, , Km, Am) 位于中間的關鍵碼 Km/2 與指向新結點 q 的指針形成一個二元組 ( Km/2, q )，插入到這兩個結點的雙親結點中去。,結點“分

9、裂”的示例,示例：從空樹開始逐個加入關鍵碼建立3階B-樹,在插入新關鍵碼時，需要自底向上分裂結點，最壞情況下從被插關鍵碼所在葉結點到根的路徑上的所有結點都要分裂。,若設B-樹的 高度為h, 那么在自頂向下查找到葉結點的過程中需要進行 h 次讀盤。,B-樹的插入算法,當分裂一個非根的結點時需要向磁盤寫出 2 個結點, 當分裂根結點時需要寫出 3 個結點。 如果我們所用的內(nèi)存工作區(qū)足夠大，使得在向下查找時讀入的結點在插入后向上分裂時不必再從磁盤讀入，那么，在完成一次插入操作時 需要讀寫磁盤的次數(shù) = = 找插入結點向下讀盤次數(shù) + + 分裂非根結點時寫盤次數(shù) + + 分裂根結點時寫盤次數(shù) = =

10、h+2(h-1)+3 = = 3h+1。,可以證明，在向一棵初始為空的B-樹中插入 N 個關鍵碼, 并且非失敗結點個數(shù)為 p 時, 分裂的結點總數(shù)最多為 p-2。由于根結點至少有一個關鍵碼，其它各非失敗結點至少有 m/2 -1 個關鍵碼，則一棵擁有 p 個結點的 m 階B-樹至少有 1+(m/2 -1)(p-1) 個關鍵碼。 其平均分裂結點數(shù)Savg 為： Savg = 分裂結點總次數(shù)/N (p-2)/(1+(m/2 -1)(p-1) ) 1/(m/2 -1),B-樹的刪除,在B-樹上刪除一個關鍵碼時，首先需要找到這個關鍵碼所在的結點，從中刪去這個關鍵碼。若該結點不是葉結點，且被刪關鍵碼為 K

11、i，1 i n，則在刪去該關鍵碼之后，應以該結點 Ai 所指示子樹中的最小關鍵碼 x 來代替被刪關鍵碼 Ki 所在的位置，然后在 x 所在的葉結點中刪除 x。 在葉結點上的刪除有 4 種情況。 被刪關鍵碼所在葉結點同時又是根結點且刪除前該結點中關鍵碼個數(shù) n 2，則直接刪去該關鍵碼并將修改后的結點寫回磁盤。,刪除55,簡單刪除,被刪關鍵碼所在葉結點不是根結點且刪除前該結點中關鍵碼個數(shù) n m/2，則直接刪去該關鍵碼并將修改后的結點寫回磁盤，刪除結束。 被刪關鍵碼所在葉結點刪除前關鍵碼個數(shù) n = m/2 -1，若這時與該結點相鄰的右兄弟 (或左兄弟) 結點的關鍵碼個數(shù) n m/2，則可按以下步

12、驟調(diào)整該結點、右兄弟 (或左兄弟) 結點以及其雙親結點，以達到新的平衡。 將雙親結點中剛剛大于 (或小于) 該被刪關鍵碼的關鍵碼 Ki (1 i n) 下移； 將右兄弟 (或左兄弟) 結點中的最小 (或最大)關鍵碼上移到雙親結點的 Ki 位置；,將右兄弟 (或左兄弟) 結點中的最左 (或最右) 子樹指針平移到被刪關鍵碼所在結點中最后 (或最前) 子樹指針位置； 在右兄弟 (或左兄弟) 結點中，將被移走的關鍵碼和指針位置用剩余的關鍵碼和指針填補、調(diào)整。再將結點中的關鍵碼個數(shù)減1。 被刪關鍵碼所在葉結點刪除前關鍵碼個數(shù) n = m/2 -1，若這時與該結點相鄰的右兄弟 (或左兄弟) 結點的關鍵碼個

13、數(shù) n = m/2 -1，則必須按以下步驟合并這兩個結點。,刪除65,結點聯(lián)合調(diào)整,刪除70,將雙親結點 p 中相應關鍵碼下移到選定保留的結點中。若要合并 p 中的子樹指針 Ai 與 Ai+1 所指的結點，且保留 Ai 所指結點，則把 p 中的關鍵碼 Ki+1下移到 Ai 所指的結點中。 把 p 中子樹指針 Ai+1 所指結點中的全部指針和關鍵碼都照搬到 Ai 所指結點的后面。刪去 Ai+1 所指的結點。 在結點 p 中用后面剩余的關鍵碼和指針填補關鍵碼 Ki+1 和指針 Ai+1。 修改結點 p 和選定保留結點的關鍵碼個數(shù)。 在合并結點的過程中，雙親結點中的關鍵碼個數(shù)減少了。,若雙親結點是根

14、結點且結點關鍵碼個數(shù)減到 0，則該雙親結點應從樹上刪去，合并后保留的結點成為新的根結點；否則將雙親結點與合并后保留的結點都寫回磁盤，刪除處理結束。 若雙親結點不是根結點，且關鍵碼個數(shù)減到m/2 -2，又要與它自己的兄弟結點合并，重復上面的合并步驟。最壞情況下這種結點合并處理要自下向上直到根結點。,刪除55,結點合并,刪除80,結點合并,非葉結點刪除,刪除50,刪除55,結點合并與調(diào)整,刪除70,刪除75,B-樹的關鍵碼刪除算法,B+樹,B+樹可以看作是B-樹的一種變形，在實現(xiàn)文件索引結構方面比B-樹使用得更普遍。 一棵m階B+樹可以定義如下： 樹中每個非葉結點最多有 m 棵子樹； 根結點 (非

15、葉結點) 至少有 2 棵子樹。除根結點外，其它的非葉結點至少有 m/2 棵子樹；有 n 棵子樹的非葉結點有 n-1 個關鍵碼。 所有的葉結點都處于同一層次上，包含了全部關鍵碼及指向相應數(shù)據(jù)對象存放地址的指針，且葉結點本身按關鍵碼從小到大順序鏈接；,每個葉結點中的子樹棵數(shù) n 可以多于 m，可以少于 m，視關鍵碼字節(jié)數(shù)及對象地址指針字節(jié)數(shù)而定。 若設結點可容納最大關鍵碼數(shù)為 m1，則指向?qū)ο蟮牡刂分羔樢灿?m1 個。 結點中的子樹棵數(shù) n 應滿足 n m1/2, m1。 若根結點同時又是葉結點，則結點格式同葉結點。 所有的非葉結點可以看成是索引部分，結點中關鍵碼 Ki 與指向子樹的指針 Ai 構

16、成對子樹 (即下一層索引塊) 的索引項 ( Ki, Ai )，Ki 是子樹中最小的關鍵碼。特別地，子樹指針 A0 所指子樹上所有關鍵碼均小于 K1。結點格式同B-樹。,葉結點中存放的是對實際數(shù)據(jù)對象的索引。 在B+樹中有兩個頭指針：一個指向B+樹的根結點，一個指向關鍵碼最小的葉結點。可對B+樹進行兩種查找運算：一種是循葉結點鏈順序查找，另一種是從根結點開始，進行自頂向下，直至葉結點的隨機查找。,在B+樹上進行隨機查找、插入和刪除的過程基本上與B-樹類似。只是在查找過程中，如果非葉結點上的關鍵碼等于給定值，查找并不停止，而是繼續(xù)沿右指針向下，一直查到葉結點上的這個關鍵碼。B+樹的查找分析類似于B

17、-樹。 B+樹的插入僅在葉結點上進行。每插入一個關鍵碼-指針索引項后都要判斷結點中的子樹棵數(shù)是否超出范圍。當插入后結點中的子樹棵數(shù) n m1 時，需要將葉結點分裂為兩個結點，它們的關鍵碼分別為 (m1+1)/2 和 (m1+1)/2。并且它們的雙親結點中應同時包含這兩個結點的最小關鍵碼和結點地址。此后，問題歸于在非葉結點中的插入了。,在非葉結點中關鍵碼的插入與葉結點的插入類似，但非葉結點中的子樹棵數(shù)的上限為 m，超出這個范圍就需要進行結點分裂。,在做根結點分裂時，因為沒有雙親結點，就必須創(chuàng)建新的雙親結點，作為樹的新根。這樣樹的高度就增加一層了。,B+樹的刪除僅在葉結點上進行。當在葉結點上刪除一個關鍵碼-指針索引項后，結點中的子樹棵數(shù)仍然不少于 m1/2，這屬于簡單刪除，其上層索引可以不改變。 如果刪除的關鍵碼是該結點的最小關鍵碼，但因在其上層的副本只是起了一個引導查找的“分界關鍵碼”的作用，所以上層的副本仍然可以保留。 如果在葉結點中刪除