Представление древовидной структуры из БД

Question

Я читал о различных способах представления иерархической структуры в реляционной базе данных, таких как Список смежности.

Я решил попробовать прямой путь, например, таблицу (упрощенно), сделанную так: id | name | parent, где parent - это внутренняя ссылка на id.

Этого должно быть достаточно для представления простого дерева неопределенной глубины.

Теперь, как я могу построить дерево для представления такого рода структуры данных? Например, если я хочу создать XML или серию вложенных <ul><li> для печати в формате HTML, каков наиболее эффективный способ циклического перемещения по узлам? Интересно, может ли Linq прийти на помощь, но меня также интересуют более общие (не связанные с .NET) и теоретические ответы.

Заранее спасибо.

Answer 1

По иронии судьбы, самой сложной частью этой проблемы может быть получение ограниченного набора записей из базы данных, которые удовлетворяют определенному предикату пути. Если вы не используете базу данных, которая обеспечивает поддержку иерархических запросов (например, Oracle CONNECT BY), это может оказаться довольно сложным. Проверьте этот вопрос для некоторых подходов в этой части.

Но давайте предположим, что вам удалось загрузить ваши данные ... вы можете сделать это либо в пользовательскую коллекцию объектов, либо в DataSet, либо в структуру XML (если вам не нужно манипулировать данными кроме как в виде строк). Если у вас есть пользовательский объект, вы можете добавить свойство, которое предоставляет дочернюю коллекцию, запрашивая весь набор данных для записей, которые соответствуют родительскому ключу (см. Пример ниже). Если количество записей велико, это начинает перестать выполняться из-за затрат на поиск в коллекции. Вот где блестит решение DataSet - поскольку вы можете добавить пользовательские индексы в столбец ParentID, которые повысят производительность поисков. Вы можете прочитать о Типизированных наборах данных здесь, чтобы узнать больше о том, как расширить мой пример ниже в этом направлении.

Вот пример пользовательского объекта с поддержкой древовидной навигации. Я использую структуру каталогов (папок), потому что это естественный пример иерархических данных. Опять же, будьте осторожны с использованием этого кода без индексированной структуры, так как полный дочерний переход будет O (n ² ).

class Folder  // could be converted to a DataRow-derivative
{
    public int Id          { get; set; }
    public string Name     { get; set; }
    public int? ParentId   { get; set; }

    public IEnumerable<Folder> GetChildren( IEnumerable<Folder> allFolders )
    {
        // NOTE: becomes expensive on large hierarchies on unindexed data
        //   a slightly better version, could replace IEnumerable<Folder>
        //   with IOrderedEnumerable<Folder> which would allow the use of
        //   a binary search algorithm for finding children (assuming it's
        //   ordered on the ParentId property).
        return AllFolders.Where( x => x.ParentId.HasValue && 
                                      x.ParentId.Value = this.Id );
    }
}

// elsewhere in your code...

void LoadAndPrintFolders()
{
   // load the folder data... from database, or wherever
   IEnumerable<Folder> allFolders = LoadFolders();

   // find all root folders (let's say, those that have a null ParentId
   IEnumerable<Folder> rootFolders = 
          allFolders.Where( x => !x.ParentId.HasValue );

   // iterate over all of the data as a tree structure...
   foreach( var folder in rootFolders )
   {
       PrintFolder( allFolders, folder, 0 );
   }

}

// recursive function to print all folders...
void PrintFolder( IEnumerable<Folder> allFolders, Folder f, int level )
{
    Console.WriteLine( "{0}{1}", new string('\t',level), f.Name );
    foreach( var folder in f.GetChildren( allFolders )
    {
        PrintFolder( allFolders, folder, level + 1 );
    }
}