这个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规范的节点结构是什么？

回答

相关问题