當前位置:網站首頁>B+樹介紹

B+樹介紹

2022-01-28 11:01:57 程序員社區

 


回到頂部

B+樹

B+樹和二叉樹、平衡二叉樹一樣,都是經典的數據結構。B+樹由B樹和索引順序訪問方法(ISAM,是不是很熟悉?對,這也是MyISAM引擎最初參考的數據結構)演化而來,但是在實際使用過程中幾乎已經沒有使用B樹的情况了。

B+樹的定義十分複雜,因此只簡要地介紹B+樹:B+樹是為磁盤或其他直接存取輔助設備而設計的一種平衡查找樹,在B+樹中,所有記錄節點都是按鍵值的大小順序存放在同一層的葉節點中,各葉節點指針進行連接。

我們先來看一個B+樹,其高度為2,每頁可存放4條記錄,扇出(fan out)為5。

B+樹介紹插圖

可以看出,所有記錄都在葉節點中,並且是順序存放的,如果我們從最左邊的葉節點開始順序遍曆,可以得到所有鍵值的順序排序:5、10、15、20、25、30、50、55、60、65、75、80、85、90。

B+樹的插入操作

B+樹的插入必須保證插入後葉節點中的記錄依然排序,同時需要考慮插入B+樹的三種情况,每種情况都可能會導致不同的插入算法,如錶5-1所示。 

B+樹介紹插圖1

我們用實例來分析B+樹的插入,我們插入28這個鍵值,發現當前Leaf Page和Index Page都沒有滿,我們直接插入就可以了。

B+樹介紹插圖2

這次我們再插入一條70這個鍵值,這時原先的Leaf Page已經滿了,但是Index Page還沒有滿,符合錶5-1的第二種情况,這時插入Leaf Page後的情况為50、55、60、65、70。我們根據中間的值60拆分葉節點。

B+樹介紹插圖3

因為圖片顯示的關系,這次我沒有能在各葉節點加上雙向鏈錶指針。最後我們來插入記錄95,這時符合錶5-1討論的第三種情况,即Leaf Page和Index Page都滿了,這時需要做兩次拆分。

B+樹介紹插圖4

 

可以看到,不管怎麼變化,B+樹總是會保持平衡。但是為了保持平衡,對於新插入的鍵值可能需要做大量的拆分頁(split)操作,而B+樹主要用於磁盤,因此頁的拆分意味著磁盤的操作,應該在可能的情况下盡量减少頁的拆分。因此,B+樹提供了旋轉(rotation)的功能。

旋轉發生在Leaf Page已經滿了、但是其左右兄弟節點沒有滿的情况下。這時B+樹並不會急於去做拆分頁的操作,而是將記錄移到所在頁的兄弟節點上。通常情况下,左兄弟被首先檢查用來做旋轉操作,這時我們插入鍵值70,其實B+樹並不會急於去拆分葉節點,而是做旋轉,50,55,55旋轉。

 B+樹介紹插圖5

可以看到,采用旋轉操作使B+樹减少了一次頁的拆分操作,而這時B+樹的高度依然還是2。

B+樹的删除操作

B+樹使用填充因子(fill factor)來控制樹的删除變化,50%是填充因子可設的最小值。B+樹的删除操作同樣必須保證删除後葉節點中的記錄依然排序,同插入一樣,B+樹的删除操作同樣需要考慮如錶5-2所示的三種情况,與插入不同的是,删除根據填充因子的變化來衡量。 

B+樹介紹插圖6

首先,删除鍵值為70的這條記錄,該記錄符合錶5-2討論的第一種情况,删除後。

B+樹介紹插圖7

接著我們删除鍵值為25的記錄,這也是錶5-2討論的第一種情况,但是該值還是Index Page中的值,因此在删除Leaf Page中25的值後,還應將25的右兄弟節點的28更新到Page Index中,最後可得到圖。

B+樹介紹插圖8

最後我們來看删除鍵值為60的情况,删除Leaf Page中鍵值為60的記錄後,填充因子小於50%,這時需要做合並操作,同樣,在删除Index Page中相關記錄後需要做Index Page的合並操作,最後得到圖。

B+樹介紹插圖9

 

 

版權聲明
本文為[程序員社區]所創,轉載請帶上原文鏈接,感謝
https://cht.chowdera.com/2022/01/202201281101573664.html

隨機推薦