How are B Tree nodes typically represented?

Question

I've been doing some brushing up on my B-Tree and 2-3-4 tree (B tree with order 4), and I'm attempting to implement this in C#. My question to you is, given that a B-Tree node can contains N-1 number of items and N subtrees, what is the typical representation for one of these nodes? Is it an array, series of linked-lists, or something I've not considered?

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

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

Answer 3

Don't try to combine sub-trees and items. You will need 2 arrays or List<>'s.

If your order is fixed i would use 2 arrays. Otherwise, a List<ItemClass> and a List<SubTree>