數(shù)據(jù)結(jié)構(gòu) B樹.ppt

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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