c# - B 树节点通常如何表示？

Question

我一直在对我的 B-Tree 和 2-3-4 树（顺序为 4 的 B 树）进行一些更新，并且我正在尝试在 C# 中实现这一点。我的问题是，鉴于 B-Tree 节点可以包含 N-1 个项目和 N 个子树，这些节点之一的典型表示是什么？它是一个数组、一系列链表，还是我没有考虑过的东西？

Answer 1

For a 2-3-4 tree, it does not really matter. For large orders, you'd use a sorted array and binary search. For variable-size keys like Strings, a trie might be a good idea.

Answer 2

不要尝试组合子树和项目。您将需要2 个数组或 List<>。

如果您的订单是固定的，我将使用 2 个数组。否则，aList<ItemClass>和 aList<SubTree>

Answer 3

Here's an interesting article on MSDN about writing a binary search tree in C#. Not exactly the same as a b-tree but you may find it useful. The author in this case uses a generic Collection base class:

public class Node<T>
{
   private T data;
   private NodeList<T> neighbors = null;
   ...
}

public class NodeList<T> : Collection<Node<T>> { ... }