C# 泛型 B 树

Question

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

现在，据我了解，树节点应该保存许多（顺序 - 1）键，以及指向记录或其他节点的指针的顺序号，即，只有叶节点将保存指向记录的实际指针，而内部节点将保存指向其他节点的指针。

我在此实现中遇到的问题是 C# 泛型，

节点类声明为：

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

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

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

出现以下错误：

无法将类型“BTree_Library.Node”隐式转换为“V”

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

所以，总而言之：

1. 在 CI 中会使用：( void*values; ) 我正在寻找 C# 中的等效项。

2. 当我们讨论这个主题时，我是否正确理解了 B+树结构 参考节点和记录可互换的节点指针？

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 或 SortedDictionary >）并且工作得很好。

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 派生，那么我认为泛型可能是解决这个问题的错误方法。

Answer 3

class Node
{
   bool IsLeaf;
   List<TKey> Keys;
}

class InnerNode : Node
{
    List<Node> Children;
}

class LeafNode : Node
{
    List<TValue> Values;
    LeafNode Next, Prev;
}

class BPTree<TKey, TValue> 
{
    Node  Root;
}