general b-tree idea

[Cpro]

I have a question regarding the b-tree.
For a binary tree, i usually declare a node like:

struct node
{
	char value;

	node *left;
	node *right;
	node *parent;
};

For a b-tree with a four key reference, it might look like:

                      [1][D][2][T][3][ ][4][ ]
                      /          \
                     /            \
                    /              \ 
[1][A][2][C][3][D][4][ ]    [1][S][2][T][3][ ][4][ ]

So, would i declare a node like:

struct node
{
	char value1;
	char value2;
	char value3;
	char value4;

	node *one
	node *two;
	node *three;
	node *four;
        node *parent;
};

So, it's like a binary tree, except with more values and pointers. Is this the proper way to do this?

Thanks.

[tabstop]

That looks like the basic idea, although perhaps one, two, three, and four aren't the world's best names. (You could maybe make it an array, node *children[4] or something.)

[CornedBee]

You'd have two arrays.

struct node
{
  node *links[CARDINALITY];
  boost::optional<VALUE> values[CARDINALITY - 1];
};