Любые советы о том, как обрабатывать иерархические деревья в реляционной модели?

Question

У меня есть древовидная структура, которая может быть n-уровня глубиной без ограничений. Это означает, что каждый узел может иметь еще n узлов.

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

Я рассмотрел несколько других моделей, таких как модель плоских таблиц, алгоритм обхода дерева предзаказа и т. Д.

Ребята, есть ли у вас какие-либо советы или предложения по реализации эффективной модели дерева? Моя цель в действительности состоит в том, чтобы иметь один или два запроса, которые бы выплевывали мне целое дерево.

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

О, просто добавьте сюда дополнительную информацию:

среда: Oracle или PostgreSQL, C # и Winforms.

Спасибо за внимание

Answer 1

Я заметил, что вы перечислили свои БД как Oracle или PostgreSQL. Если вы можете придерживаться Oracle, вы можете использовать команды start with и connect by, чтобы легко делать то, что вам нужно. Есть много опций, которые также будут корректно обрабатываться, если есть петли, или если вам нужно отфильтровать ветку на основе некоторых критериев. Я лично использовал это в производственной системе, которая выполняла как тяжелые операции чтения, так и записи без каких-либо проблем с производительностью.

Быстрый поиск показывает, что вы можете сделать нечто похожее (хотя и более сложное) с postgreSQL, используя команду with recursive. Я лично не использовал этот метод, поэтому я не могу дать вам больше информации, чем это.

Answer 2

Не существует эффективной модели дерева.

SQL 2008 - иерархия.Существует новый тип данных для работы с hiearchies, но со временем он становится большим.

Или: обычно.Родительское поле в таблице, указывающее на идентификатор родительской таблицы.

Для запросов ...

• Вы можете сделать это немного более оптимальным с помощью лучшего SQL (один оператор на УРОВЕНЬ, плюс использование временной таблицы).Это действительно сложная часть.
• То, что мы делали в CMS, где у нас было то же самое, было то, что каждый узел знал своего родителя, верхний узел (для нескольких графиков) и следующий более высокий контейнерный узел.Некоторые узлы были помечены как контейнеры - они содержали подэлементы, но они логически принадлежали к другому содержанию (например: веб-сайт, с папками, затем документ с ресурсами, такими как изображения).

Answer 3

Для меня это зависит от размера вашего дерева и типа запроса, который вы хотите выполнить.

Из того, что я могу сказать, у вас есть два элемента данных. MyId и MyParent. Если бы вы создали простую таблицу с этими двумя вещами, вы могли бы спросить и ответить, кто мои дети, а кто мои родители.

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

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

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

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

Answer 4

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

Эта модель, конечно, имеет ограничение относительно глубины иерархии. Но это в первую очередь ограничено максимальным размером столбца строки идентификатора. В SQL Server, использующем varchar (max), ограничение составляет 2 ^ 31-1 байт, что создает довольно глубокие иерархии.

Answer 5

Вложенные наборы - медленно для обновления, но быстро для запросов.

Answer 6

У Джо Селко есть решение для этого в его книге SQL для умных (глава 29). Вставки, обновления и удаления немного сложны, но выбор выполняется очень быстро. Я использую его уже несколько лет, и он работает очень хорошо.

Answer 7

Вы могли бы нумеровать узлы от 1.M, когда вы строите дерево, и хранить дочерние ссылки в терминах этих индексов. Теперь просто напишите дерево. Вы можете получить все узлы за одно чтение. Схема нумерации содержит информацию о дереве,

Answer 8

Если ваша единственная задача - выбирать, а не вставлять / обновлять / удалять, это зависит от потребностей, таких как:

• Вам нужно знать, на каком уровне находится каждый узел?
• вам нужно знать, есть ли у каждого узла дочерние элементы при рендеринге?
• вам нужно сортировать братьев и сестер по имени?

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

Изменить:

Когда порядок имеет значение, я обычно использую метод материализованный путь и добавляю дополнительный столбец SortPath. Таким образом, вы можете отсортировать результаты по сиблингу, что является денормализацией, которая делает рендеринг дерева в HTML чрезвычайно простым, поскольку вы можете выписать все дерево (или любую его часть) в том порядке, в каком вы получили записи, используя один запрос. , Это оптимально для скорости и является самым простым способом сортировки более чем одного уровня за раз.

например.,

CREATE TABLE [dbo].[MatPath](
    [ID] [int] NULL,
    [Name] [varchar](50) NULL,
    [Path] [varchar](max) NULL,
    [SortPath] [varchar](max) NULL
) 

insert into MatPath (ID, Name, Path, SortPath) values (1, 'Animal', '1', 'Animal-1')
insert into MatPath (ID, Name, Path, SortPath) values (2, 'Dog', '1.2', 'Animal-1|Dog-2')
insert into MatPath (ID, Name, Path, SortPath) values (3, 'Horse', '1.3', 'Animal-1|Horse-3')
insert into MatPath (ID, Name, Path, SortPath) values (4, 'Beagle', '1.2.4', 'Animal-1|Dog-2|Beagle-4')
insert into MatPath (ID, Name, Path, SortPath) values (5, 'Abyssinian', '1.3.5', 'Animal-1|Horse-3|Abyssinian-5')
insert into MatPath (ID, Name, Path, SortPath) values (6, 'Collie', '1.2.6', 'Animal-1|Dog-2|Collie-6')

select * 
from MatPath
order by SortPath

Выход:

ID     Name            Path        SortPath
------ --------------- ----------- --------------------------------
1      Animal          1           Animal-1
2      Dog             1.2         Animal-1|Dog-2
4      Beagle          1.2.4       Animal-1|Dog-2|Beagle-4
6      Collie          1.2.6       Animal-1|Dog-2|Collie-6
3      Horse           1.3         Animal-1|Horse-3
5      Abyssinian      1.3.5       Animal-1|Horse-3|Abyssinian-5

(6 row(s) affected)

Вы можете определить уровень каждого узла путем подсчета каналов (или периодов) на прикладном уровне или в SQL, используя любые встроенные или пользовательские функции, которые могут подсчитывать вхождения строки .

Кроме того, вы заметите, что я добавляю ID к Name при сборке SortPath. Это необходимо для того, чтобы два дочерних узла с одинаковым именем всегда возвращались в одном и том же порядке.