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> 

我收到以下错误:

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

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

所以，总而言之:

1. 在 C 中我会使用 :( 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<K,V> 或 SortedDictionary<K,V> )并且工作得很好。