Построить дерево эффективнее?

Question

Мне было интересно, достаточно ли хорош этот код, или есть явный новичок, нет-нет.

По сути, я заполняю TreeView, перечисляя все отделы в моей базе данных. Вот модель Entity Framework:

Вот код вопроса:

private void button1_Click(object sender, EventArgs e)
{            
    DepartmentRepository repo = new DepartmentRepository();
    var parentDepartments = repo.FindAllDepartments()
                          .Where(d => d.IDParentDepartment == null)
                          .ToList();
    foreach (var parent in parentDepartments)
    {           
        TreeNode node = new TreeNode(parent.Name); 
        treeView1.Nodes.Add(node);

        var children = repo.FindAllDepartments()
                     .Where(x => x.IDParentDepartment == parent.ID)
                     .ToList();
        foreach (var child in children)
        {
            node.Nodes.Add(child.Name);                       
        }                
    }
}

EDIT:

Хорошие предложения до сих пор. Работа со всей коллекцией имеет смысл, я думаю. Но что произойдет, если коллекция огромна, как в 200 000 записей? Разве это не сломало бы мое программное обеспечение?

DepartmentRepository repo = new DepartmentRepository();
var entries = repo.FindAllDepartments();

var parentDepartments = entries
                      .Where(d => d.IDParentDepartment == null)
                      .ToList();
foreach (var parent in parentDepartments)
{
    TreeNode node = new TreeNode(parent.Name);
    treeView1.Nodes.Add(node);

    var children = entries.Where(x => x.IDParentDepartment == parent.ID)
                          .ToList();
    foreach (var child in children)
    {
        node.Nodes.Add(child.Name);
    }
}

Answer 1

Поскольку вы все равно получаете все отделы, почему бы вам не сделать это в одном запросе, когда вы получите все отделы, а затем выполните запросы к коллекции в памяти, а не к базе данных.Это было бы намного эффективнее.

В более общем смысле любая рекурсивная модель базы данных может привести к проблемам, особенно если это может оказаться довольно глубокой структурой.Одна возможная вещь, которую следует учесть, - это хранить в каждом отделе всех своих предков, чтобы вы могли получить их все сразу, а не запрашивать их все сразу.

Answer 2

В свете ваших правок вы можете рассмотреть альтернативную схему базы данных, которая масштабируется для обработки очень больших древовидных структур.

В блоге fogbugz есть объяснение того, как они обрабатываютиерархии.Они также ссылаются на эту статью Джо Селко для получения дополнительной информации.

Оказывается, есть довольно крутое решение этой проблемы, объясненное Джо Селко.Вместо того, чтобы пытаться поддерживать связку родительских / дочерних отношений по всей базе данных - что потребовало бы рекурсивных SQL-запросов для поиска всех потомков узла - мы помечаем каждый случай значениями «влево» и «вправо», вычисленными какПройдя по дереву сначала по глубине и считая по ходу.Значение «левого» узла задается всякий раз, когда его впервые видят во время обхода, а значение «правого» задается при переходе назад по дереву от узла.Картина, вероятно, имеет больше смысла:

Модель SQL Nested Set позволяет добавлять иерархии наблюдений без ущерба для производительности.

Как это помогает?Теперь мы просто запрашиваем все случаи с «левым» значением от 2 до 9, чтобы найти все потомки B в одном быстром индексированном запросе.Предки G можно найти, запросив узлы с «left» меньше 6 (собственный G «left») и «right» больше 6. Работает во всех базах данных.Значительно повышает производительность - особенно при запросах больших иерархий.

Answer 3

Предполагая, что вы получаете данные из базы данных, первое, что приходит на ум, - это то, что вы будете использовать базу данных n + 1 раз для того количества родителей, которое у вас есть в базе данных.,Вы должны попытаться получить всю древовидную структуру одним ударом.

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

В-третьих, независимо от того, откуда вы получаете данные, переместитеструктурирование данных в древовидную структуру данных в службу, которая возвращает вам объект, содержащий все ваши отделы, которые уже были организованы (в основном это DTO ).Это поможет вам уменьшить дублирование кода .

С чем угодно, чтобы применить принцип yagni .По сути, это говорит о том, что вы должны что-то делать только в том случае, если вам это нужно, поэтому, если код, который вы предоставили выше, завершен, не требует дополнительной работы и функционален, не трогайте его.То же самое касается проблемы с производительностью выбора n + 1, если вы не видите никаких падений производительности, ничего не делайте, поскольку это может быть преждевременная оптимизация .

---

В вашемedit

DepartmentRepository repo = new DepartmentRepository();
var entries = repo.FindAllDepartments();

var parentDepartments = entries.Where(d => d.IDParentDepartment == null).ToList();
foreach (var parent in parentDepartments)
{
    TreeNode node = new TreeNode(parent.Name);
    treeView1.Nodes.Add(node);

    var children = entries.Where(x => x.IDParentDepartment == parent.ID).ToList();
    foreach (var child in children)
    {
        node.Nodes.Add(child.Name);
    }
}

У вас все еще есть проблема n + 1.Это связано с тем, что данные извлекаются из базы данных только при вызове ToList () или при выполнении итерации по перечислению.Это было бы лучше.

var entries = repo.FindAllDepartments().ToList();

var parentDepartments = entries.Where(d => d.IDParentDepartment == null);
foreach (var parent in parentDepartments)
{
    TreeNode node = new TreeNode(parent.Name);
    treeView1.Nodes.Add(node);

    var children = entries.Where(x => x.IDParentDepartment == parent.ID);
    foreach (var child in children)
    {
        node.Nodes.Add(child.Name);
    }
}

Answer 4

Это выглядит нормально для меня, но подумайте о наборе сотен тысяч узлов. Лучший способ сделать это - асинхронная загрузка - обратите внимание, что не обязательно загружать все элементы одновременно. Ваше древовидное представление может быть свернуто по умолчанию, и вы можете загружать дополнительные уровни, когда пользователь расширяет узлы дерева. Давайте рассмотрим такой случай: у вас есть корневой узел, содержащий 100 узлов, и каждый из этих узлов содержит как минимум 1000 узлов. 100 * 1000 = 100000 узлов для загрузки - не так ли? Чтобы уменьшить трафик базы данных, вы можете сначала загрузить свои первые 100 узлов, а затем, когда пользователь расширяет один из них, вы можете загрузить его 1000 узлов. Это сэкономит значительное количество времени.

Answer 5

Вещи, которые приходят на ум:

Похоже, .ToList() не нужно. Если вы просто перебираете полученный результат, зачем использовать дополнительный шаг?

Переместите эту функцию в собственную вещь и из обработчика событий.

Как уже говорили другие, вы можете получить весь результат за один звонок. Сортировать по IDParentDepartment так, чтобы нулевые были первыми. Таким образом, вы сможете получить список отделов за один вызов и выполнить его итерацию только один раз, добавив дочерние отделы к уже существующим родительским.

Answer 6

При этом следует использовать только один (хотя и возможно большой) вызов базы данных:

Departments.Join(
        Departments,
        x => x.IDParentDepartment,
        x => x.Name,
        (o,i) => new { Child = o, Parent = i }
    ).GroupBy(x => x.Parent)
    .Map(x => {
            var node = new TreeNode(x.Key.Name);
            x.Map(y => node.Nodes.Add(y.Child.Name));
            treeView1.Nodes.Add(node);
        }
    )

Где Map - просто ForEach для IEnumerables:

public static void Map<T>(this IEnumerable<T> source, Action<T> func)
{
    foreach (T i in source)
        func(i);
}

Примечание: Это по-прежнему не поможет, если таблица Departments огромна, поскольку «Map» материализует результат оператора sql во многом так же, как «ToList ()». Вы могли бы рассмотреть ответ Петра.

Answer 7

В дополнение к ответу Бронумски и Кита Руссо Также добавьте DepartmentID с узлами (Tag), чтобы вам не приходилось повторно запрашивать базу данных, чтобы получить DepartmentID

Answer 8

Оберните модификации TreeView:

treeView.BeginUpdate (); // изменить дерево здесь. treeView.EndUpdate ();

Для повышения производительности.

Указано здесь от jgauffin