[Pre class]B-Trees

  B樹是一種樹資料結構,常見於資料庫與檔案系統之中。B樹能夠使資料保持有序,並擁有均勻的對數處理時間的插入和刪除動作。B樹的元素通常會自底向上插入,有別於多數自頂向下插入的二元樹。
[@more@]

  B樹在節點訪問時間遠遠超過節點內部訪問時間的時候,比可作為替代的實現有著實在的優勢。這通常在多數節點在次級存儲比如硬碟中的時候出現。通過最大化在每個內部節點內的子節點的數目減少樹的高度,平衡操作不經常發生,而且效率增加了。這種價值得以確立通常需要每個節點在次級存儲中佔據完整的磁碟塊或近似的大小。

  B背後的想法是內部節點可以有在預定範圍內的可變數目的子節點。因此,B樹不需要象其他自平衡二元搜尋樹那樣經常的重新平衡。對於特定的實現在子節點數目上的低和高邊界是固定的。例如,在 2-3 B樹(常簡稱為2-3 樹)中,每個內部節點只可能有2或3個子節點。如果節點有無效數目的子節點則被當作處於違規狀態。

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

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

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