这个B-Tree规范的节点结构是什么?
问题描述:
我想创建一个B树具有以下特性:这个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{
...?
}
答
名义结构绘制时是这样的。
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]
假设b-树的顺序t = 2。它可以在特定节点中包含最大值2t-1(这里是2 * 2 -1 = 3)。但是我们假设最大数组长度为Key [BTREE_ORDER],这里是2。 。有没有其他的方法来做同样的事情,或者我们可以假设数组长度是最大的。 2t-1 –
抱歉,我的订单是错误的 - 使用BTREE_ORDER-1和BTREE_ORDER – mksteve