1、1算法導(dǎo)論算法導(dǎo)論B樹樹 B樹的定義 B樹的基本操作 從B樹刪除鍵胡學鋼、吳共慶 2 基于磁盤的數(shù)據(jù)結(jié)構(gòu) 至今為止，搜索樹是僅僅在內(nèi)存里面的數(shù)據(jù)結(jié)構(gòu)。 前提: 內(nèi)存可以容納搜索樹中的數(shù)據(jù)集 (包括樹的負載) 反例: 銀行中的交易數(shù)據(jù) 每天 1 GB 每天增加 1GB 內(nèi)存 ( 電源故障？) 使用二級存儲設(shè)備 (穿孔卡, 硬盤, 磁帶,等等.) 要求: 使搜索樹結(jié)構(gòu)必須能使用二級存儲設(shè)備。3硬盤 I 在 實際的系統(tǒng)中, 我們要處理內(nèi)存中不能裝載的數(shù)據(jù)。 從硬盤讀取數(shù)據(jù)元素:查找磁頭等待該磁頭轉(zhuǎn)過必要的扇區(qū)傳輸 數(shù)據(jù)4硬盤 II 大量數(shù)據(jù)，而且存取緩大量數(shù)據(jù)，而且存取緩慢慢! 定位一頁需要很長時間

2、 (搜索時間 加上旋轉(zhuǎn)延時 5-10ms), 讀取很快比較適合以頁頁讀寫數(shù)據(jù) (或者塊) ，大小為2-16 Kb 。5算法分析 基于磁盤的算法的運行時間主要的測量的指標有 計算時間 (CPU) 磁盤存取數(shù)目 順序讀取 隨機讀取一次處理一個數(shù)據(jù)元素的常規(guī)內(nèi)存算法不能直接“移植”到二級存儲上。6原則 數(shù)據(jù)結(jié)構(gòu)中的指針不再指向內(nèi)存，而是指向文件中的位置。 如果 x 是指向一個對象的指針 如果 x 在內(nèi)存中 keyx 指向它 否則 DiskRead(x) 將對象從磁盤讀入內(nèi)存 (DiskWrite(x) 將其寫回磁盤)7原則 (2) 一個典型的工作模式0102xapointertosomeobject

3、03DiskRead(x)04operationsthataccessand/ormodifyx05DiskWrite(x)/omittedifnothingchanged06otheroperations,onlyaccessnomodify078B樹定義 節(jié)點 x 包括域 nx: 節(jié)點中鍵的數(shù)目 key1x keynxx: 遞增順序的鍵 leafx: 如果是葉子節(jié)點為真, 如果是內(nèi)部節(jié)點為假 如果是內(nèi)部節(jié)點, 那么 c1x, , cnx+1x: 指向孩子 鍵分開了子樹中鍵的范圍。如果 ki 是子樹 cix 中的任意一個鍵，那么 ki keyix ki+19B樹定義 (2) 每個葉子的深度相

4、同 除了根節(jié)點外的所有節(jié)點有 t 到 2t 之間個孩子 (i.e. 從t1 到 2t1之間個鍵). B樹 的度度為 t. 根節(jié)點有 0 到 2t 之間個孩子 (i.e. 從 0 到 2t1 之間個鍵)10B樹:定義 (3) 我們僅僅關(guān)心鍵 B樹是平衡樹 節(jié)點為高扇出 (很多孩子) C G MA BJ K LQ R SN OY ZU VT XPD E F11 高度為 h的B樹 T, 以下對高度的限制成立：B樹的高度1log2tnh111 (1)221hihinttt 1t - 1t - 1t - 1t - 1t - 1ttt - 1t - 1t - 1011222t深度#節(jié)點數(shù)12二叉樹與B樹對

5、比100010001000100010011000100010001001100110011 節(jié)點1000 節(jié)點1001 節(jié)點,1,001,000 節(jié)點1,002,001 節(jié)點,1,002,001,000 鍵 B樹節(jié)點的大小取決于頁的大小。 一頁 一個節(jié)點. 一個高度為2的 B樹包含 1百萬個鍵! 二叉樹的高度和B樹是對數(shù)的B樹:對數(shù)的基, 比如1000 二叉樹: 對數(shù)的基為 213紅黑樹和B樹 比較紅黑樹和B樹 高度均為 O(log n) 紅黑樹對數(shù)的基為2 B樹的基為1000 樹的高度相關(guān)的差異是 lg t 當 t=2時, B樹是 2-3-4樹 (它表示的是紅黑樹)!14B樹操作 B樹的實

6、現(xiàn)應(yīng)該支持以下操作 搜索搜索 (簡單)創(chuàng)建創(chuàng)建 一棵空樹 (很簡單)插入插入 (復(fù)雜)刪除刪除 (復(fù)雜)15搜索n():int n(x) 節(jié)點中x鍵的數(shù)目keyi() keyi(X) x中的第i個鍵 ci() ci(x) the -th x中第i個指針leaf():bool - leaf(x) 如果x 是葉子為真BTreeSearch(x,k)01i102whileinxandkkeyix03ii+104ifinxandk=keyixthen05return(x,i)06ifleafxthen08returnNIL09elseDiskRead(cix)10returnBTtreeSearch(

7、cix,k)16創(chuàng)建一棵空樹 空B樹 = 創(chuàng)建根 & 寫到磁盤!BTreeCreate(T)01xAllocateNode();02leafxTRUE;03nx0;04DiskWrite(x);05rootTx17分裂節(jié)點 節(jié)點被填滿，到達它的最大容量 2t 1 在插入一個新的鍵之前，我們必須”騰出地方”，也就是說 分裂節(jié)點18分裂節(jié)點 (2)P Q R S T V WT1T8. N W .y = cixkeyi-1xkeyixx. N S W .keyi-1xkeyixxkeyi+1xP Q RT V Wy = cixz = ci+1x 結(jié)果: 一個鍵 x 移動到父親節(jié)點，同時增加了兩個t-

8、1個鍵的節(jié)點19分裂節(jié)點 (2)BTreeSplitChild(x,i,y)01zAllocateNode()02leafzleafy03nzt-104forj1tot-105keyjzkeyj+ty06ifnotleafythen07forj1tot08cjzcj+ty09nyt-110forjnx+1downtoi+111cj+1xcjx12ci+1x z13forjnxdowntoi14keyj+1xkeyjx15keyixkeyty16nxnx+117DiskWrite(y)18DiskWrite(z)19DiskWrite(x)x: 父節(jié)點y: x的孩子，要分裂的節(jié)點i: x中的索引

9、z: 新節(jié)點P Q R S T V WT1T8. N W .y = cixkeyi-1xkeyixx20分裂:運行時間 局部操作不會遍歷樹 Q(t) CPU時間, 因為兩個循環(huán)運行 t 次 3 次I/O 21插入鍵 遞歸進行，從根開始遞歸的向葉子遍歷。 在下降到樹的下一層之前，保證節(jié)點的鍵 2t 1 22插入鍵 (2) 特殊情況: 根為空 (BtreeInsert)BTreeInsert(T)01rrootT02ifnr=2t1then03sAllocateNode()05rootTs06leafsFALSE07ns008c1sr09BTreeSplitChild(s,1,r)10BTreeI

10、nsertNonFull(s,k)11elseBTreeInsertNonFull(r,k)23 將根節(jié)點分裂需要創(chuàng)建新的節(jié)點 樹從頂部，而不是底部增長。分裂根A D F H L N PT1T8.rootTrA D FL N PHrootTsr24插入鍵 BtreeNonFull 試圖 將鍵 k 插入到節(jié)點 x, 當這個函數(shù)調(diào)用的時候，要這個假設(shè)假設(shè)節(jié)點不為滿不為滿 BTreeInsert 和 BTreeInsertNonFull中的遞歸保證這一假設(shè)總是成立!25插入鍵: 偽代碼BTreeInsertNonFull(x,k)01inx02ifleafxthen03whilei1andkkeyi

11、x04keyi+1xkeyix05ii-106keyi+1x=k07nxnx+108DiskWrite(x)09elsewhilei1andkkeyixthen16ii+117BTreeInsertNonFull(cix,k)插入葉子內(nèi)部節(jié)點: 遍歷樹26插入: 舉例G M P XA C D EJ KR S T U VN OY ZG M P XA B C D EJ KR S T U VN OY ZG M P T XA B C D EJ KQ R SN OY ZU V初始化樹 (t = 3)插入B插入Q 27插入: 舉例 (2)G MA B C D EJ K LQ R SN OY ZU VT X

12、PC G MA BJ K LQ R SN OY ZU VT XPD E F插入L插入F28插入: 運行時間 磁盤 I/O: O(h),在BTreeInsertNonFull的遞歸調(diào)用期間因為僅進行 O(1) 的磁盤存取 CPU: O(th) = O(t logtn) 任何時間內(nèi)存中有 O(1) 的磁盤頁29刪除鍵 遞歸進行, 從根開始遞歸的向葉子遞歸遍歷。 在下降到樹的下一層之前，保證節(jié)點包含 t 個鍵 (cf. 插入 2t 1 個鍵) BtreeDelete 將刪除分為三個階段/情景情況 1: 在葉子節(jié)點找到鍵 k情況 2: 在內(nèi)部節(jié)點找到鍵 k 情況 3: 懷疑鍵 k 更低層的節(jié)點30 情

13、況 1: 如果鍵k在節(jié)點x中, 并且x是葉子, 從x中刪除k刪除鍵 (2)C G MA BJ K LQ R SN OY ZU VT XPD E F初始化樹C G MA BJ K LQ R SN OY ZU VT XPD EF 被刪除: 情況 1x31刪除鍵 (3)C G LA BJ KQ R SN OY ZU VT XPD EM 被刪除: 情況 2a 情況 2: 如果鍵 k 在節(jié)點x中, 并且x 不是葉子, 從x中刪除 ka) 在節(jié)點x的孩子中如果前于k 的子節(jié)點y 至少有 t 個鍵, 那么找到以y為根的子樹中的k的前繼k 。遞歸的刪除 k, 將中 x的 k 替換為 k.b)對后繼節(jié)點z進行對

14、稱的處理xy32刪除鍵 (4) 如果 y 和 z 都僅有 t 1 個鍵,將k和z的內(nèi)容合并到并到 y, 所以 x 失去了 k 和指向z的指針, 并且現(xiàn)在 y 有了 2t 1 個鍵. 釋放 z 并且遞歸的從y中刪除 k.C LA BD E J KQ R SN OY ZU VT XPG 被刪除: 情況 2cy = y + z - kx - k33刪除鍵 分布 沿著樹下降: 如果在當前節(jié)點x找不到k ,查找必定包含k的子樹cix. 如果cix僅有t 1個鍵，需要采取措施保證我們下降碰到的節(jié)點的大小至少是t. 我們可能碰到兩種情況. 如果 cix 僅有 t-1 個鍵, 但是一個兄弟至少有 t 個鍵,

15、從x移動一個鍵給 cix使它多一個鍵, 從cix的相鄰的左右兄弟移動一個鍵給 x, 并且從兄弟中移動適當?shù)暮⒆咏ocix 分布分布 34刪除鍵 分布(2)C L P T XA BE J KQ R SN OY ZU Vcixx兄弟刪除 BB 被刪除:E L P T XA CJ KQ R SN OY ZU V. k . . k A Bcixx. k . . k AcixB 35刪除鍵 合并 如果 cix 和 cix的兩個兄弟都有 t 1個鍵, 將ci和一個兄弟合并, 包括從x 向下移動一個鍵到新合并的節(jié)點，并且成為這個節(jié)點的中間鍵x. l m .l k m . A Bx. l k m. . l m AB cix36刪除鍵 合并 (2)樹的高度tree shrinks in heightD 被刪除: C L P T XA BE J KQ R SN OY ZU VC LA BD E J KQ R SN OY ZU VT XP刪除 Dcix兄弟37刪除: 運行時間 大多數(shù)鍵在葉子,因此刪除大多發(fā)生在這里! 大多數(shù)情況下刪除從樹上向下走一遍就夠了 磁盤 I/O: O(h), 在遞歸調(diào)用中僅產(chǎn)生 O(1) 的磁盤操作 CPU: