B-樹、B+樹和B*樹

目錄

• • 一. B-樹(B樹）
  • • 1. 基礎知識
    • 2. 插入操作
    • 3. 删除操作
    • 4. B樹的磁盤IO優勢和搜尋效率
  • 二. B+樹
  • • 1. m階B+樹和m階B樹的差別
    • 2. B+樹比B樹更适合作業系統的檔案索引和資料庫索引的原因
  • 三. B*樹

一. B-樹(B樹）

1. 基礎知識

m階-平衡樹，一個節點有m個位址域，m-1個資料域，B樹的所有葉子節點都在同一層。

B-樹除根節點和葉子節點外，其他節點的孩子至少有一半個數的孩子（指針域）（比如說有5個孩子，ceil(5/2)=3，至少有3個孩子）

應用場景：檔案索引系統的實作。

2. 插入操作

• 如果葉子結點空間足夠，即該節點的關鍵字樹小于m-1，則直接插入葉子結點的左邊或右邊（節點内的元素是有順序的）；
• 如果空間滿了以至沒有足夠的空間去添加新元素，即該節點的關鍵字數已經有了m個，則需要将該節點進行“分裂”，将一半數量的關鍵字元素分裂到新的其相鄰右節點中，中間元素上移到父節點中，而且當節點中關鍵元素向右移動了，相關的指針也需要向右移；
• 此外，如果在上述中間關鍵字上移到父節點的過程中，導緻根節點空間滿了，那麼根節點也要進行分裂操作，這樣原來的根節點中的中間關鍵字元素向上移動到新的根節點中，是以導緻樹的高度增加一層。

【例如】 插入以下字元字母到一顆空的5階B樹中：C、N、G、A、H、E、K、Q、M、F、W、L、T、Z、D、P、R、X、Y、S

分析：5階B樹，非根節點關鍵字個數n滿足2<=n<=4，每個節點最多含有5個孩子，出根節點葉子結點外，其他節點至少有兩個資料，三個指針域。

對于B樹來說，分裂都是向上分裂的，是非常平衡的。所有的葉子節點都在同一層，且滿足搜尋樹的性質

3. 删除操作

首先查找B樹中要删除的元素，若元素存在，則進行删除，删除該元素後，需要判斷該元素是否有左右孩子節點

• 如果有，則上移孩子節點中的相近元素（左孩子中最右邊的節點或者右孩子中最左邊的節點）到父節點中去。
• 如果沒有，直接删除。

調整操作

删除元素，然後進行元素移動之後，如果節點關鍵字數目不滿足條件（小于ceil(m/2)-1），則需要看其相鄰的兄弟節點是否豐滿(關鍵字個數大于ceil(m/2)-1)

• 如果豐滿，則向父節點借一個元素來滿足
• 如果其相鄰兄弟都剛脫貧，即借了之後其節點數目小于ceil(m/2)-1，則該節點與其相鄰的某一兄弟節點進行“合并”成一個節點，以此來滿足條件。

依次删除H、T、R、E

4. B樹的磁盤IO優勢和搜尋效率

Windows和linux的檔案搜尋，以及資料庫的索引，都用到了B+樹結構（修改原始B樹結構可得到）

在系統中的資料搜尋中：大量的資料都是存儲在磁盤上的。為了增加系統的搜尋速度，我們一般會給資料建立索引。而所謂的建立索引，就是給資料進行排序，然後進行資料搜尋就更加快速。

如果想對磁盤上存儲的資料進行快速搜尋查找需要解決兩個問題：

• 更少的磁盤I/O
• 更快的搜尋算法

我們在這裡采用m階平衡樹（節點分裂調平衡）。紅黑樹不是平衡樹，是二階非平衡樹。

對比AVL樹以及B樹的效率

作業系統管理記憶體都是按頁面（4K）配置設定，管理磁盤是按塊（16K）配置設定。我們的檔案在磁盤存儲，從磁盤讀1個檔案，讀4個位元組，實際上，作業系統從磁盤是按block（16K）來讀取的。

磁盤的最小機關是扇區，一個扇區大小為512位元組，一個block是16K，16K除以512就是扇區的個數。

假如現在從磁盤讀取10000000個索引，建構索引樹，對比B樹和AVL樹的花費：

• 如果用AVL樹（相當于2階B樹）建構索引樹來存儲10000000個索引，需要24層。一個節點就是存儲着一個索引資料，最差情況就是每個節點的資料都不在一個磁盤block上，一個節點對應一個磁盤I/O，我們查找一個資料最多查找24次，即最多需要24次磁盤I/O。
• 同理，使用300階B樹，查找一次資料最多找3層，花費3次磁盤I/O。

故在建構索引樹的時候，我們更多的使用B樹

二. B+樹

1. m階B+樹和m階B樹的差別

• B+樹的非葉子節點隻存資料，不存資料位址
• 索引項全部出現在葉子節點當中，索引項對應的資料也全部在葉子節點。是以在B+樹中搜尋每一個資料所花費的磁盤I/O一樣，而B樹是離根節點越近的搜尋越快
• 把葉子結點，即全部資料串在一條連結清單中，這條連結清單是有序的。是以當我們進行區間查找及整表搜尋不用周遊這顆複雜的B+樹，直接周遊葉子結點即可。
• B+樹存儲的索引值是有重複的，且每個節點中的關鍵字是有序的

  

2. B+樹比B樹更适合作業系統的檔案索引和資料庫索引的原因

B+樹的磁盤讀寫代價更低，B+樹的内部節點沒有指向關鍵字具體資訊的指針，是以内部節點相對B樹更小。如果把所有同一内部節點的關鍵字放在同一塊磁盤中，盤塊盤塊所能容納的關鍵字數量也就越多，一次性讀入記憶體中的需要查找的關鍵字也就越多，相對IO讀寫次數降低。

例如，假設磁盤中的一個盤塊容納16bytes，而一個關鍵字2bytes，一個關鍵字具體資訊指針2bytes。一顆9階B-tree（一個節點最多8個關鍵字）的内部節點需要兩個盤塊。而B+樹内部節點隻需要1個盤塊。當需要把内部節點讀入記憶體中的時候，B樹就比B+樹多一個盤塊查找時間（在磁盤中就是盤片旋轉的時間）

三. B*樹

是B+樹的變體，在B+樹的非根節點和非葉子節點再增加指向兄弟節點的指針。

B*樹定義了非葉子節點關鍵字個數至少為(2 / 3) * M，即塊的最低使用率為2/3（代替B+樹的1/2）

B+樹和B*樹的分裂比較

• B+樹的分裂：當一個節點滿時，配置設定一個新的節點，并将原節點中1/2的資料複制到新節點，最後在父節點中增加新節點的指針；B+樹的分裂隻影響原節點和父節點，而不會影響兄弟節點，是以它不需要指向兄弟的指針
• B*樹的分裂：當一個節點滿時，如果它的下一個兄弟節點未滿，那麼将一部分資料移到兄弟節點中，再在原節點插入關鍵字，最後修改父節點中兄弟節點的關鍵字（因為兄弟節點的關鍵字範圍變了）；如果兄弟也滿了，則在原節點與兄弟節點之間增加新節點，并各複制1/3的資料到新節點，最後在父節點增加新節點的指針

是以B*樹配置設定新節點的機率比B+樹要低，空間使用率更高，在B+樹基礎上，為非葉子節點也增加連結清單指針，将節點的最低使用率從1/2提高到2/3。