B樹學習筆記

文章目錄

• 前言
• 一、B樹是什麼？
• 二、B樹的基本操作
• • 1.搜尋
  • 2.插入
  • 3.删除
• 總結

前言

距離上次記錄紅黑樹的學習筆記已經過了十多天了，真是懈怠懈怠呀，在這十來天的時間裡面看了動态規劃，貪心算法、攤還分析（攤還分析看的寥寥草草，啥都沒看明白，等後面如果有第二遍學習的話一定要重點看一下時間分析這一塊）和B樹。先記錄一下B樹的相關知識。

一、B樹是什麼？

書中把B樹定義為有以下性質的有根樹：

1. 每個節點x有以下性質
   • x.n儲存目前節點的關鍵字個數
   • 關鍵字key以非降序存放
   • x.leaf标注目前節點是否為葉節點
2. 每個内部節點x還有x.n+1個指向其孩子的指針x.c，葉節點沒有孩子，也沒有x.c屬性

3. 關鍵字x.key對存儲在各子樹中的關鍵字範圍加以分割：如果 k i k_i ki​是存儲在以 x . c i x.c_i x.ci​為根的子樹中的任意關鍵字，那麼：

   k 1 ≤ x . k e y 1 ≤ k 2 ≤ x . k e y 2 . . . . . ≤ k n + 1 k_1\leq x.key_1\leq k_2 \leq x.key_2 ..... \leq k_{n+1} k1​≤x.key1​≤k2​≤x.key2​.....≤kn+1​

4. 每個葉節點具有相同的深度，即樹高h

5. 每個節點所包含的關鍵字的個數有上界和下界，用一個被稱為B樹的最小度數 t ≤ 2 t\leq2 t≤2來表示

   a. 除了根節點每個節點的至少有t-1個關鍵字

   b.每個節點最多包含2t-1個關鍵字

B樹的高度遵循h的大小為： h ≤ log ⁡ t n + 1 2 h\leq \log_t\frac{n+1}2 h≤logt​2n+1​相比于紅黑樹的高度 h ≤ log ⁡ 2 ( n + 1 ) h\leq \log_2(n+1) h≤log2​(n+1)。高度根據t的取值下降的會更快。

二、B樹的基本操作

在B樹的實際應用場景基本上都是磁盤檢索，是以每次要對除去根節點的其他節點進行操作時都要先進行DISK-READ從磁盤中讀取，如果對節點做了更改那還要進行DISK-WRITE将節點重新寫入磁盤。

1.搜尋

搜尋操作是在二叉樹的基礎上進行的進一步擴充，逐個周遊目前節點上的關鍵字，直到k大于等于key或者周遊完所有關鍵字。如果關鍵字被周遊完或者k ！= key，讀取 x . c i x.c_i x.ci​節點進行搜尋。否則則找到了關鍵字

2.插入

B樹插入的關鍵思想就是單次周遊，盡量的減少重複的從磁盤中讀取節點。B樹再插入一個新的關鍵字時可能會導緻目前節點的度大于2t-1，是以就會要對目前節點進行分裂得到兩個t-1的節點，中間的關鍵字會被提升到父結點中，但是這樣父節點也會存在分裂的可能。B樹在插入時為了避免找到待插入位置後分裂導緻要回溯父節點，在開始尋找周遊的時候就對滿節點進行分裂，是以沒當要分裂一個節點的時候就能夠保證其父節點不是滿的。這樣要插入一個關鍵字時隻需要對每個節點周遊一次，從磁盤中讀出來一次，而不需要回溯造成重複讀取。

這裡對插入的情況做簡要的記錄：

對關鍵字進行搜尋要從根節點開始，如果根節點為滿節點，那就要對根節點進行分裂，即建立一個新節點，将中間節點提到新結點中，然後将原節點分為連個t-1的節點。

如果目前節點是内部節點，搜尋k在目前節點的哪一個子節點中，找到後判斷該子節點是否已經滿了，如果滿了則對其進行分裂，将該節點中心節點提上去，然後分裂為兩個子節點，再把k和中心節點比較後選擇哪一個子節點作為新的搜尋對象。

如果目前節點為葉子節點，那麼找到适當的位置直接插入就行，因為根據上面的操作可以保證目前節點是一個不滿的節點。

3.删除

删除的操作會更加複雜一點，因為插入節點都是在葉節點上進行插入，而删除可能會對内部節點删除。而且一個簡單的删除算法會導緻在删除一個具有最小關鍵位元組點中的節點時向上回溯，因為可能要進行合并等操作。為了能夠避免回溯，減少從磁盤讀取節點的次數，要對遇到不同節點時做不同的處理。

首先從根節點中開始查找關鍵字k（這裡根節點同樣看作内部節點，因為根沒有最小界不需要進行預處理）,如果k不在目前内部節點x中那麼一定在x的子樹 x . c i x.c_i x.ci​中。如果 x . c i . n x.c_i.n x.ci​.n正好為t-1那麼就要進行處理，分為兩種情況

1. x . c i x.c_i x.ci​的兄弟都隻有t-1個内部節點，那麼就要将 x . c i x.c_i x.ci​和他的一個兄弟合并，并将 x . k i x.k_i x.ki​下降為合并後節點的中心關鍵字。

   

2. x . c i x.c_i x.ci​的一個兄弟節點有大于t-1個節點，那麼将 x . k e y i x.key_i x.keyi​降到 x . c i x.c_i x.ci​中，然後将兄弟節點的末尾（左兄弟）或者開頭（右兄弟）上升至 x . k e y i x.key_i x.keyi​的位置，這樣就把兄弟節點多出來的轉移到了 x . c i x.c_i x.ci​中。

在目前的節點中找到了k時，如果目前節點是内部節點時，按照第一步的操作目前節點的關鍵字的數目一定大于t-1

1. 判斷 x . c i . n x.c_i.n x.ci​.n是否大于t-1,就把前于 k e y i key_i keyi​的子節點 x . c i x.c_i x.ci​中 k e y i key_i keyi​的前驅(最末尾的值)複制到 x . k e y i x.key_i x.keyi​（目的是保持B樹的結構），然後遞歸的删除 x . c i x.c_i x.ci​中的值。

   否則判斷 x . c i + 1 . n x.c_{i+1}.n x.ci+1​.n是否大于t-1，做對稱的操作

   

2.否則将 x . c i + 1 和 x . c 和 k e y i （作為新節點的中心值） x.c_{i+1}和x.c_和key_i（作為新節點的中心值） x.ci+1​和x.c和​keyi​（作為新節點的中心值）合并成一個節點，然後在現節點中删除 k e y i key_i keyi​，然後遞歸的在新節點中删除 k e y i key_i keyi​。

如果為葉子節點，那麼可以直接删除（第一步保證了關鍵字數目大于t-1）

總結

emm，B樹删除和添加的關鍵思想就是避免回溯，使得讀取磁盤的次數盡可能少。比如在添加的時候如果不在目前節點中要保證包含它的子節點不滿，删除的時候不在目前節點的時候保證子節點關鍵字大于t-1。這裡要注意的是根節點的沒有要大于等于t-1的限制，是以在删除的時候不要單獨拿出來讨論。