複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/B+樹/7845683
複製
複製成功

B+樹

鎖定
B+樹是一種樹數據結構，通常用於數據庫和操作系統的文件系統中。B+樹的特點是能夠保持數據穩定有序，其插入與修改擁有較穩定的對數時間複雜度。B+樹元素自底向上插入，這與二叉樹恰好相反。
中文名
B+樹
外文名
B+ Tree
性    質
樹數據結構
特    點
包含根節點、內部節點和葉子節點

目錄

  1. 1 簡介
  2. 2 定義
  3. 3 節點結構
  1. 4 特徵
  2. 5 算法
  3. ▪ 查找
  1. ▪ 插入
  2. ▪ 刪除
  3. 6 B+樹與B-樹

B+樹簡介

B+樹在節點訪問時間遠遠超過節點內部訪問時間的時候，比可作為替代的實現有着實在的優勢。這通常在多數節點在次級存儲比如硬盤中的時候出現。通過最大化在每個內部節點內的子節點的數目減少樹的高度，平衡操作不經常發生，而且效率增加了。這種價值得以確立通常需要每個節點在次級存儲中佔據完整的磁盤塊或近似的大小。 [1] 
B+背後的想法是內部節點可以有在預定範圍內的可變數目的子節點。因此，B+樹不需要象其他自平衡二叉查找樹那樣經常的重新平衡。對於特定的實現在子節點數目上的低和高邊界是固定的。 [1] 
B+ 樹的創造者Rudolf Bayer沒有解釋B代表什麼。最常見的觀點是B代表平衡(balanced)，因為所有的葉子節點在樹中都在相同的級別上。B也可能代表Bayer，或者是波音（Boeing），因為他曾經工作於波音科學研究實驗室。 [1] 

B+樹定義

B+樹是B樹的一種變形形式，B+樹上的葉子結點存儲關鍵字以及相應記錄的地址，葉子結點以上各層作為索引使用。一棵m階的B+樹定義如下: [2] 
(1)每個結點至多有m個子女； [2] 
(2)除根結點外，每個結點至少有[m/2]個子女，根結點至少有兩個子女； [2] 
(3)有k個子女的結點必有k個關鍵字。 [2] 
B+樹的查找與B樹不同，當索引部分某個結點的關鍵字與所查的關鍵字相等時，並不停止查找，應繼續沿着這個關鍵字左邊的指針向下，一直查到該關鍵字所在的葉子結點為止。 [2] 

B+樹節點結構

在 B+ 樹中的節點通常被表示為一組有序的元素和子指針。如果此B+樹的序數（order）是m ，則除了根之外的每個節點都包含最少
個元素最多 m-1 個元素，對於任意的節點有最多 m 個子指針。對於所有內部節點，子指針的數目總是比元素的數目多一個。因為所有葉子都在相同的高度上，節點通常不包含確定它們是葉子還是內部節點的方式。 [1] 
每個內部節點的元素充當分開它的子樹的分離值。例如，如果內部節點有三個子節點（或子樹）則它必須有兩個分離值或元素a1和a2。在最左子樹中所有的值都小於等於a1，在中間子樹中所有的值都在a1和a2之間((a1，a2]），而在最右子樹中所有的值都大於a2。 [1] 

B+樹特徵

B+樹是B樹的一種變形，比B樹具有更廣泛的應用，m階 B+樹有如下特徵: [3] 
(1)每個結點的關鍵字個數與孩子個數相等，所有非最下層的內層結點的關鍵字是對應子樹上的最大關鍵字，最下層內部結點包含了全部關鍵字。 [3] 
(2)除根結點以外，每個內部結點有
到m個孩子。 [3] 
(3)所有葉結點在樹結構的同一層，並且不含任何信息(可看成是外部結點或查找失敗的結點)，因此，樹結構總是樹高平衡的。 [3] 

B+樹算法

B+樹查找

查找以典型的方式進行，類似於二叉查找樹。起始於根節點，自頂向下遍歷樹，選擇其分離值在要查找值的任意一邊的子指針。在節點內部典型的使用是二分查找來確定這個位置。 [1] 

B+樹插入

節點要處於違規狀態，它必須包含在可接受範圍之外數目的元素。 [1] 
  1. 首先，查找要插入其中的節點的位置。接着把值插入這個節點中。 [1] 
  2. 如果沒有節點處於違規狀態則處理結束。 [1] 
  3. 如果某個節點有過多元素，則把它分裂為兩個節點，每個都有最小數目的元素。在樹上遞歸向上繼續這個處理直到到達根節點，如果根節點被分裂，則創建一個新根節點。為了使它工作，元素的最小和最大數目典型的必須選擇為使最小數不小於最大數的一半。 [1] 

B+樹刪除

  1. 首先，查找要刪除的值。接着從包含它的節點中刪除這個值。 [1] 
  2. 如果沒有節點處於違規狀態則處理結束。 [1] 
  3. 如果節點處於違規狀態則有兩種可能情況： [1] 
    1. 它的兄弟節點，就是同一個父節點的子節點，可以把一個或多個它的子節點轉移到當前節點，而把它返回為合法狀態。如果是這樣，在更改父節點和兩個兄弟節點的分離值之後處理結束。 [1] 
    2. 它的兄弟節點由於處在低邊界上而沒有額外的子節點。在這種情況下把兩個兄弟節點合併到一個單一的節點中，而且我們遞歸到父節點上，因為它被刪除了一個子節點。持續這個處理直到當前節點是合法狀態或者到達根節點，在其上根節點的子節點被合併而且合併後的節點成為新的根節點。 [1] 

B+樹B+樹與B-樹

B+樹是應文件系統所需而產生的一種B-樹的變形樹。一棵m階的B+樹和m階的B樹的差異在於: [4] 
(1)有n棵子樹的結點中含有n個關鍵碼； [4] 
(2)所有的葉子結點中包含了全部關鍵碼的信息，及指向含有這些關鍵碼記錄的指針，且葉子結點本身依關鍵碼的大小自小而大的順序鏈接； [4] 
(3)所有的非終端結點可以看成是索引部分，結點中僅含有其子樹根結點中最大(或最小)關鍵碼。 [4] 
參考資料
  • 1.    Giampaolo, Dominic (1999). Practical File System Design with the Be File System (PDF). Morgan Kaufmann. ISBN 1-55860-497-9.
  • 2.    劉凌波．數據結構學習指導：河海大學出版社，2000.12：205
  • 3.    唐九寧．數據結構與算法分析．成都：四川大學出版社，2006：235
  • 4.    崔巍主編；蔣本珊，孫衞真，白龍飛副主編．2014考研計算機學科專業基礎綜合輔導講義：北京航空航天大學出版社，2013.05：第101頁