課程資源-復(fù)試數(shù)據(jù)庫chindexing btree

1B/B+樹索引文件B/B+樹是一種多級索引組織方法，是適合于組織存放在外存的大型磁盤文件的一種樹狀索引結(jié)構(gòu)。其中用得比較多的是B+樹。下面的討論如不特別聲明都是指B+樹索引文件B/B+樹的結(jié)點劃分葉結(jié)點：B/B+樹的最下一級索引是樹的葉結(jié)點內(nèi)部結(jié)點：B/B+樹中的其它結(jié)點(非葉結(jié)點)根結(jié)點：B/B+樹的最上一級索引是樹的根結(jié)點在B/B+樹中，由葉結(jié)點所構(gòu)成的最下面的一級索引通常采用稠密索引，而其它層次上的索引則采用稀疏索引2023/1/42B/B+樹索引文件(續(xù))B+樹的特點平衡性(balance)從樹的根結(jié)點到每個葉子結(jié)點的路徑都是等長的。過半性(halffull)每個結(jié)點（除根結(jié)點外）所對應(yīng)的磁盤塊至少被占用一半的存儲空間。順序性既提供從根結(jié)點開始的隨機查找關(guān)鍵字功能，也能根據(jù)索引關(guān)鍵字的值的排序進(jìn)行順序訪問。自適應(yīng)性自動保持與數(shù)據(jù)文件大小相適應(yīng)的索引層次。B+樹索引文件上的查找算法隨機查找算法給定一個索引關(guān)鍵字值K，查找關(guān)鍵字值為K的所有記錄指針范圍查找算法索引項的插入算法索引項的刪除算法32007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

42007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

算法1：B+樹上的隨機查找算法輸入：索引關(guān)鍵字值K輸出：關(guān)鍵字值為K的記錄指針?biāo)惴ǎ航Y(jié)點N:=B+樹的根結(jié)點；若結(jié)點N是葉子結(jié)點，則轉(zhuǎn)步驟4）；設(shè)結(jié)點N有m個關(guān)鍵字K1,K2,…,Km和m+1個指針P1,P2,…,Pm+1若K<K1，則令結(jié)點N:=P1所指向的子樹的根結(jié)點；若K≥Km，則令結(jié)點N:=Pm+1所指向的子樹的根結(jié)點；若Kj≤K<Kj+1，則令結(jié)點N:=Pj+1所指向的子樹的根結(jié)點；返回步驟2）設(shè)結(jié)點N有m個關(guān)鍵字K1，K2，…,Km和m+1個指針P1,P2,…,Pm+1，若找到一個索引關(guān)鍵字Kj==K，則返回記錄指針Pj，否則返回空指針，查找失敗。P1K1P2K2……PmKmPm+152007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例6：由2到47之間的所有素數(shù)所構(gòu)成的B+樹（秩為3）62007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))不存在關(guān)鍵字為12的記錄從根結(jié)點開始例：檢索關(guān)鍵字值等于12的記錄72007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))指向關(guān)鍵字值為29的記錄從根結(jié)點開始例：檢索關(guān)鍵字值等于29的記錄82007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))指向關(guān)鍵字值為31的記錄從根結(jié)點開始例：檢索關(guān)鍵字值等于31的記錄92007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

算法2：B+樹上的范圍查詢輸入：索引關(guān)鍵字值的范圍[a,b]輸出：滿足條件的記錄指針集合利用算法1找到關(guān)鍵字a所在的葉子結(jié)點N；在結(jié)點N中尋找第一個大于或等于a的關(guān)鍵字Ki。如果沒有找到，則轉(zhuǎn)步驟5；在結(jié)點N中搜索從Ki開始的每一個關(guān)鍵字K；對每一個關(guān)鍵字值K作如下比較：若K≤b，則將關(guān)鍵字K所對應(yīng)的記錄指針加入結(jié)果集中，并繼續(xù)比較下一個關(guān)鍵字值；若K>b，則轉(zhuǎn)步驟7)；如果結(jié)點N的下一個葉子結(jié)點指針為空，則轉(zhuǎn)步驟7)；否則結(jié)點N:=下一個葉子結(jié)點；從結(jié)點N的第一個關(guān)鍵字值K1開始，返回步驟4繼續(xù)比較；算法終止，返回結(jié)果集。102007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))【拓展】對算法2稍做調(diào)整，可以得到有關(guān)a<K<b、a<K≤b、a≤K<b、K≤a、K≥a、K<a、K>a等范圍查詢算法112007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))從根結(jié)點開始尋找關(guān)鍵字值10所在的葉結(jié)點例：檢索關(guān)鍵字值10K25的記錄找到第一個滿足條件的關(guān)鍵字值，并將其記錄指針加入到結(jié)果集中直至查到第一個不滿足條件的關(guān)鍵字值為止，查找結(jié)束122007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))從第一個葉結(jié)點開始例：檢索關(guān)鍵字值小于等于14的記錄直至查到第一個不滿足條件的關(guān)鍵字值為止，查找結(jié)束132007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))從根結(jié)點開始尋找關(guān)鍵字值30所在的葉結(jié)點例：檢索關(guān)鍵字值大于等于30的記錄下一個葉結(jié)點的第一個關(guān)鍵字值一定是大于30的在找到的第一個葉子結(jié)點中查找所有滿足條件的關(guān)鍵字如果第一個葉子結(jié)點向右有相鄰葉節(jié)點，則遍歷其右邊的所有葉節(jié)點142007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))3.B+樹中的插入操作算法3：在一個秩為n的B+樹中插入一個關(guān)鍵字值為K的索引項（在索引文件中不允許出現(xiàn)重復(fù)的關(guān)鍵字值）算法的思想尋找插入操作的最初執(zhí)行結(jié)點（葉結(jié)點）插入一個關(guān)鍵字值為K的索引項當(dāng)當(dāng)前結(jié)點的關(guān)鍵字?jǐn)?shù)目超過其上限時，當(dāng)前結(jié)點將被分裂為兩個結(jié)點，并將其中間關(guān)鍵字值插入到當(dāng)前結(jié)點的父結(jié)點中去父結(jié)點中的插入操作又有可能引起父節(jié)點的分裂，這樣的結(jié)點分裂過程可能會一直波及到根結(jié)點，而根結(jié)點的分裂則會產(chǎn)生新的根結(jié)點，并導(dǎo)致樹的高度的增加152007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）利用算法1查找到關(guān)鍵字值K應(yīng)該插入的葉子結(jié)點N；在結(jié)點N中查找關(guān)鍵字K，如果該關(guān)鍵字已經(jīng)存在，則不允許再做該關(guān)鍵字的插入操作，轉(zhuǎn)步驟7）。將由關(guān)鍵字K及其記錄（子樹）指針構(gòu)成的索引項插入到結(jié)點N的相應(yīng)位置上。如果結(jié)點N中的關(guān)鍵字?jǐn)?shù)目沒有超過其上限，則轉(zhuǎn)步驟7）；否則將結(jié)點N分裂為兩個結(jié)點N和N’，其中N’

是新申請的結(jié)點。并且：162007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）如果是葉結(jié)點的分裂：則將原結(jié)點N中的后(n+1)/2個索引項轉(zhuǎn)移到新結(jié)點N’

中去；結(jié)點N’

的后續(xù)葉結(jié)點指針指向原結(jié)點N的后續(xù)葉結(jié)點，而結(jié)點N的后續(xù)葉結(jié)點指針指向新結(jié)點N’；由新結(jié)點N’

的第一個關(guān)鍵字值K’

和指向新結(jié)點N’

的子樹指針P’

構(gòu)成一個新索引項（K’，P’）172007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）如果是內(nèi)部結(jié)點的分裂令：m1=(n+1)/2，m2=(n-1)/2則將原結(jié)點N中的前m1個索引關(guān)鍵字值和前（m1+1）個子樹指針仍然保留在結(jié)點N中；后m2個索引關(guān)鍵字值和（m2+1）個子樹指針轉(zhuǎn)移到新結(jié)點N’

中去；提取原結(jié)點N的中間關(guān)鍵字值K’（第m1+1個索引關(guān)鍵字值），并和指向新結(jié)點N’

的子樹指針P’

構(gòu)成一個新索引項（K’，P’）182007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）如果原結(jié)點N不是根結(jié)點，則轉(zhuǎn)步驟3），在原結(jié)點N的根結(jié)點中的相應(yīng)位置上插入索引關(guān)鍵字值K’

和子樹指針P’。原結(jié)點N是根結(jié)點，則申請一個新的結(jié)點R，并且將指向原結(jié)點N的子樹指針PN、索引關(guān)鍵字值K’

和子樹指針P’

插入到新結(jié)點R中，并且將新結(jié)點R設(shè)置為該索引文件的根結(jié)點。算法結(jié)束。192007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

例7：在下面的B+樹中插入一個關(guān)鍵字值為40的索引記錄202007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）首先找到執(zhí)行插入操作的葉結(jié)點212007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）插入關(guān)鍵字40及其記錄指針222007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）葉結(jié)點的分裂232007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）將新結(jié)點的第一個關(guān)鍵字值40以及新結(jié)點的指針插入到父結(jié)點中去。242007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）又引起父結(jié)點（內(nèi)部結(jié)點）的分裂252007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）因父結(jié)點的分裂而導(dǎo)致在更高層次上的插入操作。注意：內(nèi)部結(jié)點分裂與葉結(jié)點分裂的區(qū)別。262007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）例7：鍵40插入之初272007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B+樹中的插入算法（續(xù)）例7：鍵40插入完成后282007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))4．B+樹中的刪除操作算法3：在B+樹中刪除一個關(guān)鍵字值為K的索引項尋找刪除操作的最初執(zhí)行結(jié)點（葉結(jié)點）刪除關(guān)鍵字值為K的索引項如果當(dāng)前結(jié)點的關(guān)鍵字?jǐn)?shù)目低于其下限時，在當(dāng)前結(jié)點與其相鄰的兄弟結(jié)點之間重新分配索引項，并修改父結(jié)點中的相關(guān)關(guān)鍵字的值。如果其兄弟結(jié)點沒有多余的索引項時，需要將相鄰的兩個兄弟結(jié)點合并為一個結(jié)點，并引起在父結(jié)點中的刪除操作。當(dāng)根結(jié)點中的索引項個數(shù)被減為0時，將形成新的根結(jié)點，并導(dǎo)致樹的高度減1。292007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

4.B+樹中的刪除算法（續(xù)）利用算法1查找到關(guān)鍵字值為K的索引項所在的葉子結(jié)點N，若沒有找到，則算法結(jié)束；在結(jié)點N中刪除關(guān)鍵字值為K的索引項；若結(jié)點N中的關(guān)鍵字?jǐn)?shù)目滿足最低限度要求，則算法結(jié)束；檢查與結(jié)點N相鄰的兄弟結(jié)點（即具有同一個父結(jié)點的結(jié)點）中是否存在多余（即超過半數(shù)的）的鍵：若有，則從兄弟結(jié)點中移一個最近的關(guān)鍵字過來，同時需要修改其父結(jié)點中相應(yīng)位置上的關(guān)鍵字值。若沒有，則將結(jié)點N與其某個相鄰的兄弟結(jié)點合并為一個結(jié)點（合并后的新結(jié)點中的索引關(guān)鍵字的個數(shù)不會超過其上限要求），并在其父結(jié)點中刪除相應(yīng)的索引項（轉(zhuǎn)步驟2））。在父結(jié)點中執(zhí)行的刪除操作又有可能引起父結(jié)點的合并。如果結(jié)點的合并操作一直波及到根結(jié)點，則會減低樹的高度。302007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))首先尋找關(guān)鍵字值等于7的索引項所在的葉結(jié)點從根結(jié)點開始例：刪除關(guān)鍵字值為7的索引項312007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例：刪除關(guān)鍵字值為7的索引項刪除關(guān)鍵字等于7的索引項后的結(jié)果322007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))尋找關(guān)鍵字值等于11的索引項所在的葉結(jié)點例：再刪除關(guān)鍵字值等于11的索引項332007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))刪除關(guān)鍵字11并合并相鄰葉結(jié)點后的最初結(jié)果例：再刪除關(guān)鍵字值等于11的索引項342007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))整個刪除操作全部完成后的結(jié)果例：再刪除關(guān)鍵字值等于11的索引項352007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例：再刪除關(guān)鍵字值等于13的索引項23134331532292341373147431917131917刪除關(guān)鍵字值等于13的索引項后的結(jié)果這是一個在葉結(jié)點中并不存在的關(guān)鍵字值，但在內(nèi)部結(jié)點中可以起到導(dǎo)航的作用362007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例：再刪除關(guān)鍵字值等于17的索引項23134331292341373147435321917372007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例：再刪除關(guān)鍵字值等于17的索引項2313433129234137314743刪除關(guān)鍵字值等于17的索引項后的最初情況19532382007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例：再刪除關(guān)鍵字值等于17的索引項2313433129234137314743195進(jìn)行索引項遷移后的最終結(jié)果532結(jié)點內(nèi)容的修改只在局部范圍內(nèi)進(jìn)行392007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))例：再刪除關(guān)鍵字值等于3的索引項23543312923413731474332195402007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

B/B+樹索引文件(續(xù))2354331292341373147432195刪除關(guān)鍵字值等于3的索引項后的最初結(jié)果412007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

234331292341373147431952合并相鄰的兄弟葉結(jié)點（將右葉結(jié)點中的索引項移到左葉節(jié)點中），拋棄已經(jīng)被置空的葉節(jié)點（修改葉結(jié)點之間的指針），從而引起其父結(jié)點中的關(guān)鍵字值及子樹指針的減1422007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

234331292341373147431952該結(jié)點中的關(guān)鍵字值的個數(shù)（0）已經(jīng)低于其下限值（1），需要從其相鄰的某個兄弟結(jié)點中遷移一個關(guān)鍵字值過來432007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

312343292341373147431952在內(nèi)部結(jié)點中進(jìn)行了索引項的遷移后的結(jié)果，被更新的僅限于這三個索引結(jié)點中的值442007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

312343292341373147431952例：再刪除關(guān)鍵字值等于19的索引項452007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

3123432923413731474352刪除關(guān)鍵字值等于19的索引項后的結(jié)果462007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

3123432923413731474352例：再刪除關(guān)鍵字值等于5的索引項472007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

312343292341373147432刪除關(guān)鍵字值等于5的索引項后的最初結(jié)果。其中：第一個葉子結(jié)點中的關(guān)鍵字值的個數(shù)已經(jīng)低于其下限值（2），且其相鄰的兄弟結(jié)點中也沒有多余的關(guān)鍵字值，因而必須合并它們482007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

3143413731474329232結(jié)點的合并操作必然會引起其上一層父結(jié)點中的索引項的刪除操作。492007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

3143413731474329232該結(jié)點中的關(guān)鍵字值的個數(shù)也已經(jīng)低于其下限值（0），且其兄弟結(jié)點中也沒有多余的關(guān)鍵字值，因而必須與某個相鄰的兄弟結(jié)點進(jìn)行合并502007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

3143？413731474329232內(nèi)部結(jié)點在合并后需要增加一個索引關(guān)鍵字值，以滿足子樹指針等于關(guān)鍵字值的個數(shù)+1的要求。同時需要將指向被清空結(jié)點的子樹指針從其父結(jié)點中刪除（當(dāng)然也需要同時從其父結(jié)點中刪除一個索引關(guān)鍵字值）512007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

4331413731474329232合并后要從它們的父結(jié)點中遷移一個關(guān)鍵字值過來，以實現(xiàn)前述的兩點要求。522007年度-教育部-IBM精品課程-南京大學(xué)計算機科學(xué)與技術(shù)系

4331413731474329232拋棄已經(jīng)為空的舊的根結(jié)點，合并后的結(jié)點將成為新的根結(jié)點，從