Как обычно представлены узлы B-дерева?

Question

Я занимался очисткой своего B-дерева и дерева 2-3-4 (B-дерево с порядком 4), и я пытаюсь реализовать это в C #. Мой вопрос к вам, учитывая, что узел B-Tree может содержать N-1 количество элементов и N поддеревьев, каково типичное представление для одного из этих узлов? Это массив, серия связанных списков или что-то, чего я не рассматривал?

Answer 1

Для дерева 2-3-4 это не имеет большого значения.Для больших заказов вы бы использовали отсортированный массив и бинарный поиск.Для ключей переменного размера, таких как Strings, неплохо было бы использовать trie.

Answer 2

Не пытайтесь комбинировать поддеревья и предметы.Вам понадобятся 2 массивы или списки <>.

Если ваш заказ фиксирован, я бы использовал 2 массива.В противном случае, List<ItemClass> и List<SubTree>

Answer 3

Вот интересная статья на MSDN о написании бинарного дерева поиска в C #. Не совсем то же самое, что b-дерево, но вы можете найти его полезным. Автор в этом случае использует базовый базовый класс Collection:

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

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