B+樹

B + 樹伊是一種樹仔的資料結構，通常用佇資料庫佮作業系統的檔案系統中。B + 樹仔的特點是有法度保持資料穩定有序，其插入去佮修改有較穩定的對數時間複雜度。B + 樹元素顛倒插入去，這與二元樹恰好倒反。

B + 樹仔佇節點存取時間遠遠超過節點內部取時間的時間，比現在的替代的實現有了實在的優勢。這通常佇多數節點佇次級的儲存比如硬碟中的時陣出現。通過上大化佇每一个內部節點內的子節點的數目減少樹仔的懸度，平衡操作不三時咧發生，而且效率增加矣。這款價值得確立通常需要逐个節點佇咧次級的儲存中占據完整的磁仔角抑是近來親像大細。

B + 樹背後的想法是內部節點會當有咧預定的範圍內底會當變數目的子節點。所以，B + 樹仔毋免親像其他的自平衡二箍搜揣樹仔彼款定定重新平衡。對著特定的實現在子節點數目上的低佮懸邊界是固定的。比如講，佇咧二嬸三 B 樹（定簡稱做二嬸三樹）中，每一个內部節點只有可能有兩三个子節點。若準節點有無效數目的子節點著被當做是違規狀態。

B + 樹仔的創作者 Rudolf Bayer 無解說「B」的意義，上捷看的觀點是代表「做平衡」（balanced）佮其名「Bayer」。

節點結構

佇咧 B + 樹仔中的節點通常予人表示為一組有序的元素佮子指標。若按呢 B + 樹仔的階數是 m，除了根以外每一个節點攏包含上少 $ \ lfloor m / 二 \ rfloor $ 個元素上濟 $ m 影一 $ 個元素，對任意的結點有上濟 m 子指標。對內部算的彼个點，子指標的數目總是比元素的數目加一个。所有的葉仔攏仝款的懸度上，葉結點本身揤關鍵字大細漢自細漢到大漢連結。

演算法

走揣

走揣以典型的方式來進行，類似於二箍搜揣樹仔。起頭佇咧根節點，自頂向下遍歷樹，選擇其分離值在欲走揣值的任意一爿的子指標。佇咧節點內部典型的使用是二分走揣來確定這个位置。

插入去

節點愛佇違規狀態，伊必須愛包括佇可接受範圍以外數目的元素。

一 . 首先，走揣愛插入去其中的節點的位置。來共值插入這个節點內底。二 . 若無儉儉仔就處理違規的狀態愛處理結束。三 . 若是某一个節點有過多元素，則共分裂做兩个節點，逐項攏有上細數目的元素。佇咧樹仔頂交迴向頂懸繼續這个處理一直到達根節點，若根節點去予人分裂，則建立一个新的節點。為著使伊作穡，元素的上細佮上大數目典型的著愛選擇為著使上細數無小於上大數的一半。

刪除

一 . 首先，走揣愛刣除的值。來自包括伊的節點中刪除這个值。二 . 若無儉儉仔就處理違規的狀態愛處理結束。三 . 若準儉儉違規狀態是有兩種可能情形：一 . 伊的兄弟仔節點，就是仝一个父節點的子節點，會當共一个抑是偌个伊的子節點轉移到做頭前節點，顛倒共回轉做合法的狀態。若是按呢，佇更改父節點佮兩个兄弟節點的分離值了後處理結束。二 . 伊的兄弟仔節點因為佇低邊仔爾無外口的子節點。佇這種情況下共兩个兄弟仔節點合做一个單一的節點內底，而且阮提到父節點上，因為伊予人刣掉一个子節點。繼續這个處理一直到當前節點是合法狀態抑是根節點，佇咧其上根節點的子節點予人合併而且合併以後的節點成做新的根節點。

註解

假定 L 是節點允准有子節點的上小數目，而且 U 是上大的數目。總是逐个節點總是有咧 L 和 U 之間（包含伊在內）個子節點，除了一个例外：根節點有對 _ 二 _ 到 U（包含伊在內）個子節點。嘛會使講，根節點豁免於低邊界的限制，擁有伊家己的低邊界 _ 二 _。這允准樹仔持有小數目的元素。根有一个子節點無意義，因為牢佇這个子節點頂懸的子樹會當簡單的箍牢佇這个根節點頂懸。允准根節點無囝節點嘛是無需要的，因為無元素的樹典型的表示就是無根節點。

Robert Tarjan 證明矣均擔的分裂／合併數目是二。

參見

NTFS
資料庫
二箍樹
B # Tree
B 樹
Bitmap index

外部連結

B + tree in C language
Open Source C + + B + Tree Implementation
B + tree implementation as C + + template library
Perl implementation of B + trees
java / C # / python implementations of B + trees
Your Grandmother's guide to Algorithms Java implementation of in-memory B +-Trees and other algorithms .
Study notes for B + Trees-Insertion and Deletion
Dr . Monge's B + Tree index notes
Link to how BTrees work
Evaluating the performance of CSB +-trees on Mutithreaded Architectures
Effect of node size on the performance of cache conscious B +-trees
Fractal Prefetching B +-trees
Towards pB +-trees in the field : implementations Choices and performance
Cache-Conscious Index Structures for Main-Memory Databases
B + Tree Java SortedMap Implementation