C# generic B+tree

I'm implementing a B+tree using C#.

Now as i understand it, a tree node should hold a number of (order - 1) keys, and order number of pointers to records or other nodes, i.e., only the leaf nodes would hold actual pointers to records , and internal nodes would hold pointers to other nodes.

The problem I'm having with this implementation is with C# generics

the Node Class is Declared as:

class Node< K,V >
{
    K [] keys ;
    V [] values;
}

Now when i attempt to place a node into the values array as such

_root.Values[0] = left ; // left being of type Node<K,V> 

I get the following Error:

Cannot implicitly convert type 'BTree_Library.Node' to 'V'

So, I'm trying to find a way to work around this, the other option is to change the implementation to hold one array for nodes and one for records.

So, in conclusion :

1. In C I would have used :( void* values; ) I'm looking for an equivalent of that in C# .

2. While we're on the subject did I understand the B+tree structure correctly in reference to nodes and records being interchang开发者_JS百科eable for the nodes pointers?

You want your leaf nodes and your inner nodes to act differently, while still being able to refer to both of them as nodes. That describes an inheritance hierarchy:

abstract class Node<K, V>
{
    public K[] Keys { get; protected set; }
}

class LeafNode<K, V> : Node<K, V>
{
    public V[] Values { get; protected set; }
}

class InnerNode<K, V> : Node<K, V>
{
    public Node<K, V> Children { get; protected set; }
}

Another option would be to use the C# equivalent of void*, which is object, but that would mean the code is not type-safe anymore and you would have to have casts everywhere. I would not recommend doing this.

That being said, why are you creating your own B-tree? It's useful only when keeping the data on disk, not in memory. If you're doing it only to have associative array, there are classes in .Net that already implement it (like Dictionary<K,V> or SortedDictionary<K,V>) and that work perfectly fine.

Assuming _root.Values[0] = left is being executed from within the class and that Values is a property equivalent to values.

If V will always be a type of Node, you can try something like

interface INode {
}

class Node<K, V> : INode where V : INode {

}

This will force V to derive from BTree_Library.Node, which will allow that line to compile without any errors.

If V will not always derive from Node, then I think generics might be the wrong way to tackle this.