Как получить всех родителей узла в древовидной структуре? (Линк к сущности)

Question

У меня есть таблица древовидной структуры:

CREATE TABLE [dbo].[Nodes](
    [Id] [bigint] IDENTITY(1,1) NOT NULL,
    [Name] [nvarchar](max) NOT NULL,
    [ParentId] [bigint] NULL)

Каков эффективный способ найти путь узла в виде списка родительских идентификаторов с минимальным подключением?

В моем дереве не будет более 200 узлов.

Answer 1

Я протестировал следующее решение на 100 000 записей с глубиной 30 уровня. Я получаю все элементы дерева, затем метод рекурсивно выбираю пути до. Конечным условием был нулевой родительский идентификатор. Это займет около 4-5 секунд. Эта длительность допустима, пока в древовидной таблице будет храниться не более 400 записей.

Answer 2

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

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

Смотрите здесь: http://www.codeproject.com/Articles/4155/Improve-hierarchy-performance-using-nested-sets

Если бы вы были настроены таким образом, запрос для извлечения необходимых вам данных был бы что-то вроде

SELECT [Id]
FROM [dbo].[Nodes]
WHERE [LeftExtent] < @CurrentNodeLeftExtent
AND [RightExtent] > @CurrentNodeRightExtent
ORDER BY [LeftExtent]

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