B樹的結(jié)構(gòu)詳細(xì)講解.ppt

,7、B_ 樹和 B+ 樹 1、為什么采用B_ 樹和 B+ 樹： 大量數(shù)據(jù)存放在外存中，通常存放在硬盤中。由于是海量數(shù)據(jù)，不可能一次調(diào)入內(nèi)存。因此，要多次 訪問外存。但硬盤的驅(qū)動(dòng)受機(jī)械運(yùn)動(dòng)的制約，速度慢。所以，主要矛盾變?yōu)闇p少訪外次數(shù)。 在 1970 年由 R bayer 和 E macreight 提出用B_ 樹作為索引組織文件。提高訪問速度、減少時(shí)間。,內(nèi)存,E.G: 用二叉樹組織文件，當(dāng)文件的記錄個(gè)數(shù)為 100，000時(shí)，要找到給定關(guān)鍵字的記錄，需訪問外存17次（log100,000）,太長了！,50,25,10,75,15,35,60,90,20,30,40,55,70,80,95,索引文件,數(shù)據(jù)文件,文件頭，可常駐內(nèi)存,文件訪問示意圖：索引文件、數(shù)據(jù)文件存在盤上,7、B_ 樹和 B+ 樹 2、B_ 樹是一種多分支數(shù)，首先介紹 m 階 B_ 樹： 定義： m 階 B_ 樹滿足或空，或： A、根結(jié)點(diǎn)要么是葉子，要么至少有兩個(gè)兒子 B、除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù)為: m/2 K1 且 Kn 的結(jié)點(diǎn)的地址（指在該 B_ 樹中） 注意：K1 =K2 = . = Kn D、所有的葉子結(jié)點(diǎn)都出現(xiàn)在同一層上，不帶信息（可認(rèn)為外部結(jié)點(diǎn)或失敗結(jié)點(diǎn)）。,7、B_ 樹和 B+ 樹 例如：m = 4 階 B_ 樹。除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)之外，每個(gè)結(jié)點(diǎn)的兒子個(gè)數(shù) 至少為 m/2 = 2 個(gè)；結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為 1 。該 B_ 樹的深度為 4。 葉子結(jié)點(diǎn)都在第 4 層上。,1，99,3，47，58，64,1，39,1，27,1，11,2，43，78,1，18,1，35,第 1 層,第 2 層,第 3 層(L層),第 4 層(L1層),7、B_ 樹和 B+ 樹 3、B_ 樹的查找代價(jià)分析： 查找過程，類似于二叉樹的查找。如查找關(guān)鍵字為 KEY 的記錄。 從根開始查找，如果 Ki = KEY 則查找成功，Ri 為關(guān)鍵字為 KEY 的記錄的地址。 若 Ki Kn; 查找 An指向的結(jié)點(diǎn) 若 找到葉子，則查找失敗。 注意：每次查找將去掉 （s-1）/s 個(gè)分支，比二分查找快得多。 設(shè)關(guān)鍵字的總數(shù)為 N ，求 m階 B_ 樹的最大層次 L。 層次 結(jié)點(diǎn)數(shù) 關(guān)鍵字的個(gè)數(shù)（最少） 1 1 1 2 2 2（ m/2 -1） 3 2（ m/2 ） 2（ m/2 ） （ m/2 -1） 4 2（ m/2 ） 2 2（ m/2 ）2 （ m/2 -1） L 2（ m/2 ）L-2 2（ m/2 ）L-2 （ m/2 -1） L+1 2（ m/2 ）L-1 所以，N=1 2（ m/2 -1） +.+ 2（ m/2 ）L-2 （ m/2 -1） = 2 m/2 L-1 -1 故：Llog （N+1）/2）+ 1,7、B_ 樹和 B+ 樹 3、B_ 樹的查找代價(jià)分析： 設(shè)關(guān)鍵字的總數(shù)為 N ，求 m階 B_ 樹的最大層次 L。 故：Llog m/2 （N+1）/2）+ 1 設(shè) N 1000，000 且 m256 ，則 L = 3；最多 3 次訪問外存可找到所有的記錄。,4、B_ 樹的插入操作 1、確定插入位置，將結(jié)點(diǎn)插入到第 L 層（注意：第 L+1 層為葉子結(jié)點(diǎn)） 2、找到插入位置，將關(guān)鍵字和其它信息按序插入。 3、若被插入結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù) m-1, 則該結(jié)點(diǎn)滿。必須分裂成兩個(gè)結(jié)點(diǎn)。否則不滿結(jié)束。 如結(jié)點(diǎn)原為： （m-1, A0, (K1, A1), (K2, A2), (Km-1, Am-1)） 插入一個(gè)關(guān)鍵字之后變?yōu)椋?（m, A0, (K1, A1), (K2, A2), (Km, Am)） 該結(jié)點(diǎn)將進(jìn)行分裂： . (K m/2 , p ) . （m/2-1, A0, (K1, A1), (K m/2 , A m/2 )） （m- m/2 , A m/2 , (Km, Am)） 生成新結(jié)點(diǎn) p, 將原結(jié)點(diǎn)的后半部分復(fù)制過去。若分裂一直進(jìn)行到根結(jié)點(diǎn)，樹可能長高一層。,P,P,(K m/2 , p ) 數(shù)據(jù)項(xiàng)插入上層結(jié)點(diǎn)之中,7、B_ 樹和 B+ 樹,例如：3 階 B_ 樹的插入操作。m=3, m/2 - 1 = 1; 至少 1 個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。,3，12,7 24 30,24，30,45，70,53,90,26,100,39,50,61,85,3,45，70,53,90,26,100,39,50,61,85,12,30,3,24 45 70,53,90,26,100,39,50,61,85,12,7,30,3,24,53,90,26,100,39,50,61,85,12,7,45,70,7插入,7、B_ 樹和 B+ 樹,5、B_ 樹的刪除操作 1、查找具有給定鍵值的關(guān)鍵字 Ki 2、如果 在第 L 層，可直接刪除（注意：第 L+1 層為葉子結(jié)點(diǎn)），轉(zhuǎn) 4 。 3、否則，則首先生成 “替身”。用 的右子樹中的最左面的結(jié)點(diǎn)的關(guān)鍵字值，即 處于第 L 層上的最小 關(guān)鍵字值取代 。然后，刪除第 L 層上的該關(guān)鍵字。 4、從第 L 層開始進(jìn)行刪除。 A、不動(dòng)：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)仍處于 m/2 -1和 m-1之間。則結(jié)束。 B、借：若刪除關(guān)鍵字值的那個(gè)結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)原為 m/2 -1 。而它們的左或右鄰居結(jié) 點(diǎn)的關(guān)鍵字的個(gè)數(shù) m/2 -1 ; 則借一個(gè)關(guān)鍵字過來。處理結(jié)束。 C、并：若該結(jié)點(diǎn)的左或右鄰居結(jié)點(diǎn)的關(guān)鍵字的個(gè)數(shù)為 m/2 -1 ; 則執(zhí)行合并結(jié)點(diǎn)的操作。 如結(jié)點(diǎn)原為： （ . (Ki, Ai), (Ki+1, Ai+1), . ） （ A0, (K1, A1 ) ） （ A0, (K1, A1 ) ） K1L ,第 L 層：找到了被刪結(jié)點(diǎn)的替身。,7、B_ 樹和 B+ 樹,例如：3 階 B_ 樹的刪除操作。m=3, m/2 - 1 = 1; 至少 1 個(gè)關(guān)鍵字，二個(gè)兒子結(jié)點(diǎn)。,3,24,45,53 90,37,100,50,61，70,被刪關(guān)鍵字,3,24,45,61 90,37,100,53,70,借：向被刪結(jié)點(diǎn)方向旋轉(zhuǎn),假定再刪除該關(guān)鍵字,3,24,45,90,37,100,61，70,假定再刪除該關(guān)鍵字,3，24,45,90,100,61，70,3，24,45 90,100,61，70,并,并,并,并：和父結(jié)點(diǎn)的一個(gè)關(guān)鍵字、及鄰居合并。有可能進(jìn)行到根，使B_ 樹的深度降低一層！,B+樹,B+樹可以看作是B_樹的一種變形，在實(shí)現(xiàn)文件索引結(jié)構(gòu)方面比B_樹使用得更普遍。 一棵 m 階B+樹可以定義如下： 樹中每個(gè)非葉結(jié)點(diǎn)最多有 m 棵子樹； 根結(jié)點(diǎn) (非葉結(jié)點(diǎn)) 至少有 2 棵子樹。除根結(jié)點(diǎn)外, 其它的非葉結(jié)點(diǎn)至少有 m/2 棵子樹；有 n 棵子樹的非葉結(jié)點(diǎn)有 n-1 個(gè)關(guān)鍵碼。 所有葉結(jié)點(diǎn)都處于同一層次上，包含了全部關(guān)鍵碼及指向相應(yīng)數(shù)據(jù)對象存放地址的指針，且葉結(jié)點(diǎn)本身按關(guān)鍵碼從小到大順序鏈接；,每個(gè)葉結(jié)點(diǎn)中的子樹棵數(shù) n 可以多于 m，可以少于 m，視關(guān)鍵碼字節(jié)數(shù)及對象地址指針字節(jié)數(shù)而定。 若設(shè)結(jié)點(diǎn)可容納最大關(guān)鍵碼數(shù)為 m1，則指向?qū)ο蟮牡刂分羔樢灿?m1 個(gè)。 結(jié)點(diǎn)中的子樹棵數(shù) n 應(yīng)滿足 n m1/2, m1。 若根結(jié)點(diǎn)同時(shí)又是葉結(jié)點(diǎn)，則結(jié)點(diǎn)格式同葉結(jié)點(diǎn)。 所有的非葉結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中關(guān)鍵碼 Ki 與指向子樹的指針 Pi 構(gòu)成對子樹 (即下一層索引塊) 的索引項(xiàng) ( Ki, Pi )，Ki 是子樹中最小的關(guān)鍵碼。,特別地，子樹指針 P0 所指子樹上所有關(guān)鍵碼均小于 K1。結(jié)點(diǎn)格式同B_樹。 葉結(jié)點(diǎn)中存放的是對實(shí)際數(shù)據(jù)對象的索引。 在B+樹中有兩個(gè)頭指針：一個(gè)指向B+樹的根結(jié)點(diǎn)，一個(gè)指向關(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)上的這個(gè)關(guān)鍵碼。 B+樹的搜索分析類似于B_樹。 B+樹的插入僅在葉結(jié)點(diǎn)上進(jìn)行。每插入一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后都要判斷結(jié)點(diǎn)中的子樹棵數(shù)是否超出范圍。,當(dāng)插入后結(jié)點(diǎn)中的子樹棵數(shù) n m1 時(shí)，需要將葉結(jié)點(diǎn)分裂為兩個(gè)結(jié)點(diǎn)，它們的關(guān)鍵碼分別為 (m1+1)/2 和 (m1+1)/2。并且它們的雙親結(jié)點(diǎn)中應(yīng)同時(shí)包含這兩個(gè)結(jié)點(diǎn)的最小關(guān)鍵碼和結(jié)點(diǎn)地址。此后，問題歸于在非葉結(jié)點(diǎn)中的插入了。 在非葉結(jié)點(diǎn)中關(guān)鍵碼的插入與葉結(jié)點(diǎn)的插入類似，但非葉結(jié)點(diǎn)中的子樹棵數(shù)的上限為 m，超出這個(gè)范圍就需要進(jìn)行結(jié)點(diǎn)分裂。 在做根結(jié)點(diǎn)分裂時(shí)，因?yàn)闆]有雙親結(jié)點(diǎn)，就必須創(chuàng)建新的雙親結(jié)點(diǎn)，作為樹的新根。這樣樹的高度就增加一層了。,B+樹的刪除僅在葉結(jié)點(diǎn)上進(jìn)行。當(dāng)在葉結(jié)點(diǎn)上刪除一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后，結(jié)點(diǎn)中的子樹棵數(shù)仍然不少于 m1/2，這屬于簡單刪除，其上層索引可以不改變。 如果刪除的關(guān)鍵碼是該結(jié)點(diǎn)的最小關(guān)鍵碼，但因在其上層的副本只是起了一個(gè)引導(dǎo)搜索的“分界關(guān)鍵碼”的作用，所以上層的副本仍然可以保留。 如果在葉結(jié)點(diǎn)中刪除一個(gè)關(guān)鍵碼-指針?biāo)饕?xiàng)后，該結(jié)點(diǎn)中的子樹棵數(shù) n 小于結(jié)點(diǎn)子樹棵數(shù)的下限 m1/2，必須做結(jié)點(diǎn)的調(diào)整或合并工作。,刪除18,刪除12,如果右兄弟結(jié)點(diǎn)的子樹棵數(shù)已達(dá)到下限m1/2，沒有多余的關(guān)鍵碼可以移入被刪關(guān)鍵碼所在的結(jié)點(diǎn)，這時(shí)必須進(jìn)行兩個(gè)結(jié)點(diǎn)的合并。將右兄弟結(jié)點(diǎn)中的所有關(guān)鍵碼-指針?biāo)饕?xiàng)移入被刪關(guān)鍵碼所在結(jié)點(diǎn)，再將右兄弟結(jié)點(diǎn)