如何創建B +樹數據結構

Question

我想了解如何創建一個B +樹，其順序（分支因子）爲3，節點的最大條目數爲3.我搜索了很多小程序，但他們中的大多數人不能正常工作，而偉大的人似乎不遵循維基百科上發現的這些步驟。

按照這些步驟

1. 如果桶沒有滿（最多b - 插入後1項），添加記錄。
2. 否則，拆分桶。
3. 分配新葉子並將桶元素的一半移動到新桶中。
4. 將新葉子的最小密鑰和地址插入父級。

我相信插入的新值應該發生在第4步之前。是否有更好的描述版本的算法？

隨着20,15,5,1,3,9,2,12作爲輸入，我得到了下面的樹：

        |1|5| | 

          |2|5| |   |9| | | 


       |1|2| | |3|5| |  |9| | |  |15|20| | 

是否正確按照這些步驟是什麼？任何人都可以指出一個小程序來驗證這個例子嗎？

Answer 1

你的樹不正確。節點中的每個值（不是葉節點）都應該是分支的斷點。爲了說明這點，讓我們考慮以下節點：

---------------------------------------- 
|   7  |  23   | 
---------------------------------------- 
| pointer to | pointer to | pointer to | 
| branch with| branch with| branch with| 
| values  | values  | values  | 
| < 7  | 7 <= x < 23| >= 23  | 
---------------------------------------- 

此節點有2個值和3個分支。值7和23表示第二和第三分支中的最小值。第一個分支的最小值沒有在此級別表示。 （除非它是整個樹的最小值，這將是一些更高的水平。）

隨着b = 4插入值的規則可以概括爲：

• 找到鬥（第一個值小於第一個值，下一個桶的第一個值大於我們要插入的值）
• 如果插入後桶中的項目數爲4，則必須拆分桶
  • 當桶被拆分時，2個值爲le如果父節點變滿（4個值），則將兩個值移動到新桶中
  • 將新桶（具有較大值的那個）的第一個值插入父桶/節點
  • ），它分裂以同樣的方式，但插入到它的父值從桶中取出

讓我們考慮用數字1..9樹：

 3,5,7 
    |----------------| 
1,2 3,4 5,6 7,8,9 

如果我們現在插入numbe r 10進入樹中，最右邊的葉變得太滿（7,8,9,10），所以它必須分成兩片葉子（1,8）和（9,10）。按照該規則，數字9（上分裂桶的最低值）被髮送到父：

 3,5,7,9 
|---------------------| 
1,2 3,4 5,6 7,8 9,10 

這使得母體充分，並且它具有被分裂：

3,5  7,9 
|-------| |---| 
1,2 3,4 5,6 7,8 9,10 

當父節點被拆分，新節點的第一個值被髮送到它的父節點。在該樹中的新節點（7,9），因此值被取出併發送到父是7。不存在這樣的父，則創建新的根節點：

  7 
    |---------| 
    3,5  9 
|-------| |---| 
1,2 3,4 5,6 7,8 9,10 

---

讓我們建立與數字20,15,5,1,3,9,2,12樹和b = 4

首先三個值配合在一個葉（其是在同一時間的根節點） ：

5,15,20 

當數字1被插入時，剷鬥分裂和新桶的第一值被髮送到父（新的根）：

15 
|-----| 
1,5 15,20 

應當注意的是，沒有什麼是曾經從葉節點取出。刪除僅在分裂的父節點中發生。

值3可以插入到其存儲桶中，沒有問題（存儲桶將變爲1,3,5）。但是，嘗試插入數字9會使桶溢出（1,3,5,9），並且會分裂。新桶（5）的第一個值將被插入到父項中。

5,15 
|----------| 
1,3 5,9 15,20 

值2和12適合於他們的水桶沒有分裂，這樣的樹是：

 5,15 
    |--------------| 
1,2,3 5,9,12 15,20 

---

要看看會發生什麼，當一箇中間節點分割，讓我們考慮以下三種：

      26 
       |-----------------------------| 
      8,14,20      30,34 
    |--------------------------|  |-----------| 
2,4,6 8,10,12 14,16,18 20,22,24 26,28 30,32 34,36 

現在我們將值13添加到樹中。這將觸發分裂桶（8,10,12,13）分爲兩個：

      26 
      |-----------------------------------| 
     8,12,14,20       30,34 
    |-------------------------------|  |-------------| 
2,4,6 8,10 12,13 14,16,18 20,22,24 26,28 30,32 34,36 

有對中間偏左的節點（8,12,14,20），孩子太多，所以它必須是駁：

      26 
     |---------------------------------------| 
     8,12    14,20    30,34 
    |-------------|  |---------|  |-------------| 
2,4,6 8,10 12,13 14,16,18 20,22,24 26,28 30,32 34,36 

我們分割父節點，我們已經申請了增加的規則，新桶的第一項必須插入到父，並從該節點刪除，即14從帶走（14,20）：

      14,26 
      |------------------------------------| 
     8,12    20    30,34 
    |-------------|  |---------|  |-------------| 
2,4,6 8,10 12,13 14,16,18 20,22,24 26,28 30,32 34,36 

Th e樹也用來說明規則：每個父節點攜帶除第一個子樹以外的每個子樹的最低值。

---

的問題應該引起（如果我沒有犯了太多錯誤）的例子：

  5 
    |----------| 
    3   15 
|---| |-------| 
1,2 3 5,9,12 15,20