m-way B-tree可以奇怪嗎？

Question

我讀的書CLRS，我們有M路B樹，其中m爲偶數。但是有沒有B樹是m的奇數，如果有的話，我們該如何修改本書給出的代碼。

Answer 1

由M路B樹我假設你的意思是B樹，每個內部節點被允許最多有米以下的兒童。根據CLRS對B樹的定義：

節點對於它們可以包含的鍵的數量有上限和下限。我們用一個固定的整數t≥2表示這些邊界，稱爲B樹的最小度數：...一個內部節點最多可以有2t兒童。

所以兒童的最大數量將始終是甚至 - 由這個定義不能是奇數。

---

但是，這不是B樹的唯一定義。有許多定義略有差異，最終對整體性能沒有什麼影響。這可能會導致混淆。有一些B樹定義允許奇數上限和那些沒有的上限。 CLRS的定義確實爲孩子們不要奇上限內部節點的數量。然而，B樹的另一個正式定義是Knuth [1998]（The Art of Computer Programming，Volume 3（Second ed。），Addison-Wesley，ISBN 0-201-89685-0）。 Knuth的定義確實允許奇數上限。儘管CLRS列舉了t≥2的形式（t，2t）的所有最小最大樹範圍，但Knuth枚舉了k≥2的形式（ceil（k/2），k）的所有樹界。

Knuth Order, k | (min,max) | CLRS Degree, t 
---------------|-------------|--------------- 
    0   |  -  |  – 
    1   |  –  |  – 
    2   |  –  |  – 
    3   | (2,3) |  – 
    4   | (2,4) |  t = 2 
    5   | (3,5) |  – 
    6   | (3,6) |  t = 3 
    7   | (4,7) |  – 
    8   | (4,8) |  t = 4 
    9   | (5,9) |  – 
    10  | (5,10) |  t = 5 

因此，例如，一個2-3 tree，（2,3），是B樹Knuth的順序3.但由於它具有奇數上限它不是有效的CLRS樹。

---

更改代碼並不容易，因爲B樹根據變量t有很多代碼。其中最大的變化將是裏面：B-TREE分裂孩子（X，I），你需要找到一種方式來分割孩子奇數兒童（偶數鍵）爲節點y和z。這兩個結果節點中的一個將比另一個擁有更多的密鑰。如果您正在尋找代碼，我建議您在Internet上查找使用類似於Knuth的定義的B樹的實現（例如，搜索「Knuth Order B-tree」）。