如何表示B-tree节点？

Question

我们在课堂上学习B树，并被要求在代码中实现它们。老师把编程语言的选择留给了我们，我想尝试用C#来做。我的问题是下面的结构在C#中是非法的，

unsafe struct BtreeNode
        {
            int key_num;        // The number of keys in a node
            int[] key;          // Array of keys
            bool leaf;          // Is it a leaf node or not?
            BtreeNode*[] c;     // Pointers to next nodes
        }

具体来说，不允许创建指向结构本身的指针。有没有什么变通或者替代的方法我可以使用？我相当确定在托管代码中一定有办法做到这一点，但我不能确定。

编辑:Eric的回答给我指明了正确的方向。这是我最终使用的方法，

class BtreeNode
{
        public List<BtreeNode> children;       // The child nodes
        public static int MinDeg;               // The Minimum Degree of the tree
        public bool IsLeaf { get; set; }        // Is the current node a leaf or not?
        public List<int> key;                   // The list of keys 
...
}

Answer 1

巧合的是，我刚刚在C#中为一个个人项目实现了一个btree。这很有趣。我构建了一个按字典顺序排列的可变大小(最多64字节)键的btree，这带来了许多挑战，特别是在找出存储页面太满或太空的时候。

我的建议是，构建一个抽象层，只捕获最抽象形式的btree算法，作为一个抽象基类。在获取了该表单中捕获的所有btree规则后，我以几种不同的方式指定了基类:作为常规的固定密钥大小为2-3的btree，作为我奇特的可变大小密钥btree之一，等等。

首先，在任何情况下，你都不应该使用指针。不安全的代码很少是必要的，也从来都不容易。只有最高级的C#程序员才应该关闭安全系统；当你这样做的时候，你是在对程序的类型和内存安全负责。如果你不愿意这样做，就让安全系统打开。

其次，没有理由让它成为一个结构。在C#中，结构是按值复制的；btree节点不是值。

第三，您不需要在节点中保留键的数量；键的数组知道其中有多少键。

第四，我会使用List<T>而不是数组；它们更灵活。

第五，您需要决定键是位于节点中还是位于父节点中。任何一种方式都可以工作；我的首选是键位于节点中，因为我认为键与节点相关联。

第六，知道btree节点是否是根节点很有帮助；您可以考虑使用两个bool，一个是“这是叶吗？”还有一个“这是根吗？”当然，只有一项的btree只有一个节点，既是叶节点又是根节点。

第七，您可能会将这个东西构建为可变的；通常情况下，不会在C#类上创建公共可变字段。您可以考虑将它们设置为属性。此外，子列表可以增大和缩小，但其标识不会更改，因此应将其设置为参照只读：

因此，我可能会将我的基本节点构造为：

class Node
{
    public int Key { get; set; }
    public bool IsRoot { get; set; }
    public bool IsLeaf { get; set; }
    private List<Node> children = new List<Node>();
    public List<Node> Children { get { return this.children; } }
}

讲得通?

Answer 2

使用类而不是结构。然后抛出指针。

class BtreeNode
{
    int key_num;        // The number of keys in a node
    int[] key;          // Array of keys
    bool leaf;          // Is it a leaf node or not?
    BtreeNode[] c;      // Pointers to next nodes
}

当您声明一个类类型的变量时，它隐式地是一个引用(非常类似于c中的指针)，因为每个类都是一个引用类型。

Answer 3

你只需要意识到C中的指针与C#中的引用“有些相似”。(有各种不同之处，但出于本问题的目的，您可以专注于相似之处。)两者都允许一定程度的间接性:值不是数据本身，它是获取数据的一种方式。

上面的等价物类似于：

class BtreeNode
{
    private int keyNumber;
    private int[] keys;
    private bool leaf;
    private BtreeNode[] subNodes;

    // Members (constructors etc)
}

(我对B树不太记得，但是如果这里的“subNode”数组对应于每个键的"keyNumber“值，那么您可能根本不需要keys变量。)