B+樹
維基百科,自由的 encyclopedia
B+樹(英語:B+ tree)是一種樹資料結構,通常用於資料庫和作業系統的檔案系統中。B+樹的特點是能夠保持資料穩定有序,其插入與修改擁有較穩定的對數時間複雜度。B+樹元素由下而上插入,這與二元樹恰好相反。
B+樹在節點訪問時間遠遠超過節點內部訪問時間的時候,比可作為替代的實現有著實在的優勢。這通常在多數節點在次級儲存比如硬碟中的時候出現。通過最大化在每個內部節點內的子節點的數目減少樹的高度,平衡操作不經常發生,而且效率增加了。這種價值得以確立通常需要每個節點在次級儲存中占據完整的磁碟塊或近似的大小。
B+樹背後的想法是內部節點可以有在預定範圍內的可變數目的子節點。因此,B+樹不需要像其他自平衡二元搜尋樹那樣經常的重新平衡。對於特定的實現在子節點數目上的低和高邊界是固定的。例如,在 2-3 B 樹(常簡稱為2-3 樹)中,每個內部節點只可能有 2 或 3 個子節點。如果節點有無效數目的子節點則被當作處於違規狀態。
B+樹的創造者Rudolf Bayer沒有解釋「B」的意義,最常見的觀點是代表「平衡」(balanced)或其名字「Bayer」。