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

另一种选择是使用

void*

的 C# 等效项，即

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

，那么我认为泛型可能是解决这个问题的错误方法。

Answer 3

class Node 

{

  bool IsLeaf;

列表键；

} 

class InnerNode : Node 

{

   List<Node> Children;

}

class LeafNode : Node 

{

   List<TValue> Values;

LeafNode 下一个，上一个；

} 

class BPTree<TKey, TValue>  

{

   Node  Root;

} `