這個B-Tree規範的節點結構是什麼？

每個節點x包含以下屬性：

XN存在於節點x
x.key1按鍵的數量， x.key2，..... x.keyx.n是存在於節點中的密鑰
x.c1，x.c2，......... x.cx.n，x.cx .n + 1是指向子節點的指針
x.leaf是一個布爾變量，顯示節點是否爲葉節點

在此基礎上規範，我將如何實施的節點結構：

struct Node{ 
    ...? 
}

來源

2016-01-24 Naman Gupta

名義結構繪製時是這樣的。

 a  b  c  d 
    / |  |  |  \ 
    la  bab bbc bcd gd 

    la = less than a 
    bab = between a and b 
    bbc = between b and c 
    bcd = between c and d 
    gd = greater than d

指針比元素多的地方。

因此，N階B樹至多有N個孩子。因此，使用BTREE_ORDER作爲此值，並確保BTREE_ORDER大於1

結構是最有效地完成作爲

struct Node{ 
    size_t numNodes; 
    KEY_TYPE Key[BTREE_ORDER -1]; 
    struct Node * Children[BTREE_ORDER]; 
}

所以它有空間BTREE_ORDER-1鍵和BTREE_ORDER子節點。該排列取決於代碼，並且是

Children[0] Key[0] Children[1] Key[1] .... Key[numNodes - 2] Children[ numNodes - 1]

來源

2016-01-24 07:33:10 mksteve

假設b-樹的順序t = 2。它可以在特定節點中包含最大值2t-1（這裏是2 * 2 -1 = 3）。但是我們假設最大數組長度爲Key [BTREE_ORDER]，這裏是2。。有沒有其他的方法來做同樣的事情，或者我們可以假設數組長度是最大的。 2t-1 –

抱歉，我的訂單是錯誤的 - 使用BTREE_ORDER-1和BTREE_ORDER – mksteve

這個B-Tree規範的節點結構是什麼？

回答

相關問題