如何表示b树节点?

We're learning B-trees in class and have been asked to implement them in code. The teacher has left choice of programming language to us and I want to try and do it in C#. My problem is that the following structure is illegal in C#,

我们在课堂上学习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
        }

Specifically, one is not allowed to create a pointer to point to the structure itself. Is there some work-around or alternate approach I could use? I'm fairly certain that there MUST be a way to do this within the managed code, but I can't figure it out.

具体来说，不允许创建指向结构本身的指针。我可以使用一些变通的方法吗?我相当肯定在托管代码中一定有办法做到这一点，但我无法解决。

EDIT: Eric's answer pointed me in the right direction. Here's what I ended up using,

编辑:埃里克的回答让我找到了正确的方向。这是我最后用的，

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

3 个解决方案

#1

Coincidentally I actually just did implement a btree in C#, for a personal project. It was fun. I built a btree of lexicographically ordered variable size (up to 64 byte) keys which presented a number of challenges, particularly around figuring out when a page of storage was too full or too empty.

巧合的是，我实际上只是在c#中实现了一个btree，用于个人项目。它是乐趣。我构建了一个字典顺序的可变大小的btree(最多64个字节)，它提出了许多挑战，特别是当一个存储页面太满或太空时。

My advice, having just done that, is to build an abstraction layer that captures just the btree algorithms in their most abstract form, as an abstract base class. Once I got all the btree rules captured in that form, I specialized the base class in several different ways: as a regular fixed-key-size 2-3 btree, as one of my fancy variable-size-key btrees, and so on.

我的建议是构建一个抽象层，它以最抽象的形式捕获btree算法，作为抽象基类。一旦我获得了在该表单中捕获的所有btree规则，我就以几种不同的方式专门化了基类:作为一个普通的固定键大小的2-3 btree，作为我的一个特殊的可变大小的btree，等等。

To start with, under no circumstances should you be doing this with pointers. Unsafe code is seldom necessary and never easy. Only the most advanced C# programmers should be turning off the safety system; when you do that, you are taking responsibility for the type and memory safety of the program. If you're not willing to do that, leave the safety system turned on.

首先，在任何情况下都不应该用指针来做这个。不安全的代码很少是必要的，也不容易。只有最先进的c#程序员应该关闭安全系统;当您这样做时，您将对程序的类型和内存安全负责。如果你不愿意这样做，那就离开安全系统。

Second, there's no reason to make this a struct. Structs are copied by value in C#; a btree node is not a value.

第二，没有理由让它成为一个结构。结构在c#中按值复制;btree节点不是一个值。

Third, you don't need to keep the number of keys in a node; the array of keys knows how many keys are in it.

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

Fourth, I would use a List<T> rather than an array; they are more flexible.

第四，我将使用List 而不是数组;他们更灵活。

Fifth, you need to decide whether the key lives in the node or in the parent. Either way can work; my preference is for the key to live in the node, because I see the key as being associated with the node.

第五，您需要确定键是否存在于节点或父节点中。无论哪种方式可以工作;我的首选项是在节点中生存的键，因为我认为键与节点相关联。

Sixth, it is helpful to know whether a btree node is the root or not; you might consider having two bools, one "is this a leaf?" and one "is this the root?" Of course a btree with a single item in it has a single node that is both leaf and root.

第六，知道btree节点是否为根节点是有帮助的;你可能会考虑有两个bools，一个是“这是一片叶子吗?”还有一个是“这是根吗?”当然，有单个项目的btree有一个节点，即叶子和根节点。

Seventh, you are probably going to build this thing to be mutable; normally one does not make public mutable fields on a C# class. You might consider making them properties. Also, the list of children can be grown and shrunk, but its identity does not change, so make it referentially read-only:

第七，你可能会构建这个东西是可变的;通常情况下，不会在c#类上创建公共的可变字段。你可以考虑让它们成为属性。此外，儿童的列表也可以增长和缩小，但其身份不会改变，因此，请将其引用为只读:

So I would probably structure my basic node as:

所以我可能会把我的基本结点构造成:

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

Make sense?

有意义吗?

#2

Use a class instead of a stuct. And throw out the pointers.

使用一个类而不是stuct。然后抛出指针。

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
}

When you declare a variable of a class type, it is implicitly a reference(very similar to a pointer in c) since every class is a reference type.

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

#3

All you need to realize that a pointer in C is "somewhat similar" to a reference in C#. (There are various differences, but for the purposes of this question you can concentrate on the similarities.) Both allow a level of indirection: the value isn't the data itself, it's a way of getting to the data.

您需要了解的是，C中的指针与c#中的引用“有点类似”。(有很多不同之处，但对于这个问题，你可以把注意力集中在相似点上。)两者都允许一个间接的水平:值不是数据本身，而是一种获取数据的方式。

The equivalent of the above would be something like:

相当于上面的内容:

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

    // Members (constructors etc)
}

(I don't remember much about B-trees, but if the "keys" array here corresponds to the "keyNumber" value of each subNode, you may not want the keys variable at all.)

(我不太记得b树，但是如果这里的“键”数组对应于每个子节点的“keyNumber”值，那么您可能根本不想要这个键变量。)

#1