B-Tree - 爲什麼不能有一個偶數個鍵的節點？

Question

我試圖根據「算法簡介」中的「B-Trees」一章來實現B樹。

我不明白的是「最低程度」。在書中指出，度是一個數字，它表示節點可以容納的密鑰數量的下限/上限。它進一步說：至少

1. 每個非根節點店在t - 1鍵和具有t孩子。
2. 每個節點最多存儲2*t - 1密鑰並且有2*t子女。

所以，你得到的T = 2：

1. t - 1 = 1個鍵和t = 2名兒童
2. 2*t - 1 = 3個鍵和4個孩子

當t = 3

1. t - 1 = 2個鍵和t = 3個ch ildren
2. 2*t - 1 = 5鍵和6個孩子

現在，這裏的問題：它似乎在B樹的節點只能存儲一個奇數字鍵的時候都充分。

爲什麼不能有一個節點，讓我們說至多4個鍵和5個孩子？它與分裂節點有關嗎？

Answer 1

看來B樹中的節點只能存儲奇數個鍵？

絕對不是。您所寫的數字分別是最小和最大鍵數，因此對於t = 2，允許使用帶有1，2，3鍵的節點。對於t = 3，允許具有2,3,4,5個密鑰的節點。

而且，樹的根允許只有1個鍵。

可以定義（並實現）具有例如樹的樹。 1個或2個鍵在一個節點（所謂的2-3樹）。 B樹被定義爲容納多一個的原因是，這導致更快的性能。特別是，這允許分期付款O(1)（計數拆分和連接操作）刪除和插入操作。

Answer 2

這不是不可能的，但不是最理想的。如何將一個節點與奇數個孩子分開？