Какие-либо подсказки того, как обработать иерархические деревья в реляционной модели?
У меня есть древовидная структура, которая может быть n-уровнями глубоко без ограничения. Это означает, что каждый узел может иметь другого n узлы.
Что лучший способ состоит в том, чтобы получить дерево как этот, не выпуская тысячи запросов к базе данных?
Я посмотрел на несколько других моделей, как плоская модель таблицы, Алгоритм Обхода дерева Перед порядком, и таким образом.
Вы у парней есть какие-либо подсказки или предложения того, как реализовать эффективную древовидную модель? Моя цель в реальном конце состоит в том, чтобы иметь один или два запроса, которые плюнули бы целым деревом для меня.
С достаточной обработкой я могу отобразить дерево в точечной сети, но это было бы в клиентской машине, таким образом, не большая часть грандиозного предприятия.
О, просто отбросив еще некоторую информацию здесь:
среда: Oracle или PostgreSQL, C# и Winforms.
Спасибо за внимание
8 ответов
Предполагая, что ваша единственная забота - это выбор, а не вставка / обновление / удаление, это зависит от потребностей, например:
- do вам нужно знать, на каком уровне находится каждый узел?
- нужно ли вам знать, есть ли у каждого узла какие-либо дочерние элементы при его рендеринге?
- вам нужно отсортировать братьев и сестер по имени?
Однако, если в дерево действительно вносятся минимальные изменения, то почти не имеет значения, какую схему вы используете, поскольку вы можете выполнять всю работу на уровне приложения и кэшировать вывод.
Изменить:
Когда порядок имеет значение, я обычно использую метод материализованного пути и добавляю дополнительный столбец 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 . Это необходимо для того, чтобы два родственных узла с одинаковым именем всегда возвращались в одном и том же порядке.
Мы с большим успехом использовали модель, в которой для каждого узла сохраняли строку, содержащую идентификатор каждого узла от вершины до этого узла, разделенные знаком '.'. Получение дерева становится сверхэффективным, только сортировка по строке.
У этой модели, конечно, есть ограничение на то, насколько глубоко может заходить иерархия. Но это в первую очередь ограничено максимальным размером столбца строки идентификатора. В SQL Server с использованием varchar (max) ограничение составляет 2 ^ 31-1 байта, что создает довольно глубокие иерархии.
Вложенные наборы - медленно для обновления, но быстро для запросов.
Джо Селко предлагает решение этой проблемы в своей книге «SQL for Smarties» (глава 29). Вставки, обновления и удаления немного сложны, но выбор выполняется очень быстро. Я использую его уже несколько лет, и он работает очень хорошо.
На мой взгляд, это зависит от размера вашего дерева и типа запроса, который вы хотите выполнить.
Насколько я могу судить, у вас есть два элемента данных. MyId и MyParent. Если бы вы создали простую таблицу только с этими двумя элементами, вы могли бы спросить и ответить, кто мои дети и кто мои родители.
Если бы вы хотели построить полное дерево для интенсивного анализа, я бы запросил все данные и построил дерево сам. База данных на этом этапе выступает только в качестве хранилища информации.
Если бы мое дерево было большим или его создание занимало более полусекунды, я бы сохранил его на своем сервере и сделал доступным с помощью ajax-вызовов для клиента. Это работает лучше всего, если дерево статично для всех клиентов.
Если дерево динамическое, я бы настаивал на том, чтобы клиент ждал, пока данные будут получены с сервера и дерево будет построено локально. Это увеличит скорость использования.
Если бы вы предоставили больше информации о том, что вы имели в виду, когда сказали "разделить дерево", я мог бы предложить лучшее мнение. Но в целом я не нашел идеального дерева в базе данных. Однако OLAP может иметь такой инструмент, о котором я не знаю.
Я заметил, что вы указали ваши БД как Oracle или PostgreSQL. Если вы можете придерживаться Oracle, вы можете использовать команды start with и connect by, чтобы легко сделать то, что вам нужно. Существует множество вариантов, которые также изящно справятся с зацикливанием, или если вам нужно отфильтровать ветку на основе некоторых критериев. Я лично использовал это в производственной системе, в которой были как интенсивные чтения, так и записи без каких-либо проблем с производительностью.
Быстрый поиск показывает, что вы можете сделать нечто подобное (хотя и более сложное с точки зрения sql) в PostgreSQL, используя команду with recursive. Я лично не использовал этот метод, поэтому не могу дать вам больше информации.
Не существует эффективной модели дерева.
SQL 2008 - hierarchyid. Есть новый тип данных для работы с иерархиями, но со временем он становится большим.
Или: обычный. Родительское поле в таблице, указывающее на ID родительской таблицы.
Для запросов...
- Вы можете сделать это немного более оптимально с помощью лучшего SQL (один оператор НА УРОВЕНЬ, плюс использование временной таблицы). Это действительно сложная часть.
- Что мы сделали в CMS, где у нас было то же самое, так это то, что каждый узел знал своего родителя, верхний узел (для нескольких графов) и следующий более высокий контейнерный узел. Некоторые узлы были помечены как контейнеры - они содержали подэлементы, но они логически принадлежали другому контейнеру (например: веб-сайт с папками, затем документ с ресурсами, такими как изображения).
Вы можете пронумеровать узлы от 1 до M по мере построения дерева и хранить дочерние ссылки в терминах этих индексов. Теперь просто напишите дерево. Вы можете получить все узлы за одно чтение. Схема нумерации содержит информацию о дереве,