C#属B+tree

Question

我正在使用B+tree实现C#。

现在，据我所知，树节点应该包含许多(order - 1)键，以及指向记录或其他节点的指针的顺序数，也就是说，只有叶节点才能保存到记录的实际指针，而内部节点将保存指向其他节点的指针。

这个实现的问题在于C#泛型

Node类声明为：

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

现在，当我尝试将一个节点放入值数组中时，

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

我得到以下错误：

不能隐式地将'BTree_Library.Node‘转换为'V’

因此，我试图找到一种解决这一问题的方法，另一种选择是更改实现，以保存一个节点数组和一个记录数组。

因此，结论是：

1. In C I将使用:( void* values; )，我在寻找与C#中的类似的内容。在我们讨论这个主题时，我是否正确地理解了节点和记录对于节点指针可互换的B+tree结构？

Answer 1

您希望您的叶节点和内部节点的行为有所不同，同时仍然能够将它们称为节点。它描述继承层次结构：

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; }
}

另一种选择是使用C#等效的void*，即object，但这意味着代码不再是类型安全的，您必须在任何地方都进行强制转换。我不建议这么做。

话虽如此，你为什么要创建自己的B树呢？只有当数据保存在磁盘上，而不是在内存中时，它才有用。如果您这样做只是为了拥有关联数组，那么.Net中有一些类已经实现了它(比如Dictionary<K,V>或SortedDictionary<K,V>)，并且工作非常好。

Answer 2

假设_root.Values[0] = left是从类中执行的，并且Values是一个等价于values的属性。

如果V始终是Node的一种类型，您可以尝试如下

interface INode {
}

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

}

这将迫使V从BTree_Library.Node派生，这将允许该行编译而不会出现任何错误。

如果V不会总是从Node派生出来，那么我认为泛型可能是解决这个问题的错误方法。