Наилучшая практика для заполнения иерархии объектов из набора результатов плоской базы данных?

Question

Это часто повторяющаяся проблема генерации дерева из плоского списка . Я поймал себя на том, что полагаюсь на двухуровневый метод, описанный ниже. Буду признателен всем, кто предложит лучший подход, который можно легко распространить на несколько уровней.

Описание:

• Resultset является плоским и содержит ссылку на parentId
• Корневые элементы будут иметь нулевой или нулевой parentId. В примере кода FromDb.ParseInt будет обрабатывать DBNull путем преобразования его в ноль.

<code>
using (SqlDataReader reader = command.ExecuteReader())
{
    List<ParentDataObject> results = new List<ParentDataObject>();
    ParentDataObject parent = new ParentDataObject();
    ParentDataObject previousParent = null;
    while (reader.Read())
    {
        parent.Id = FromDb.ParseInt(reader["ParentId"]);<br>
        // Parent-level
        if (previousParent == null || parent.Id != previousParent.Id)
        {
            if (previousParent != null)
            {
                results.Add(previousParent); // save previously processed ParentDataObject
            }
            parent = new ParentDataObject();
            // Fill parent object with data...
        }
        // Child-level
        ChildDataObject child = new ChildDataObject;
        // Fill child with data...
        parent.Children.Add(child);
        previousParentId = currentParentId;
    }
    // add last parent to results
    if (previousParent != null)
        results.Add(previousParent);
}

Answer 1

Как насчет этого? (Псевдо-код)

class HierarchicalObject
{
    int ID;
    List<HierarchicalObject> Children;
    // Other fields
}

...

var roots = new List<HierarchicalObject>();
var index = new Dictionary<int, HierarchicalObject>();

while (reader.Read())
{
    HierarchicalObject current = new HierarchicalObject();

    // fill in data from record

    int parentID = (int)reader["ParentID"];

    if (parentID != 0)
    {
        index[parentID].Children.Add(current);
    }
    else
    {
        roots.Add(current);
    }

    index.Add(current.ID, current);   
}

// roots now contains list of root objects; throw out index

Это предполагает, что все ваши объекты однородны, а не имеют отдельные родительские / дочерние классы, а также, что порядок таков, что вы не будете читать по дочернему элементу, прежде чем прочитаете по его родительскому ... для нескольких уровней, и вы можете адаптировать его по мере необходимости.

(Если второе предположение неверно, вы можете сначала прочитать все записи в индексе, а затем вернуться к индексу и исправить корни и потомки.)