Структура базы данных для древовидной структуры данных

151

Как лучше всего реализовать настраиваемую (то есть древовидную структуру с неизвестным числом уровней) древовидную структуру данных в базе данных?

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

Какие еще реализации вы можете увидеть, и имеет ли эта реализация смысл?

CodeMonkey1313
источник

Ответы:

80

Вы упомянули наиболее часто реализуемый, который является списком смежности: https://blogs.msdn.microsoft.com/mvpawardprogram/2012/06/25/hierarchies-convert-adjacency-list-to-nested-sets

Есть и другие модели, включая материализованные пути и вложенные множества: http://communities.bmc.com/communities/docs/DOC-9902

Джо Селко (Joe Celko) написал книгу на эту тему, которая является хорошим справочным материалом с общей точки зрения SQL (она упоминается в ссылке на вложенный набор статей выше).

Кроме того, Ицик Бен-Ганн имеет хороший обзор наиболее распространенных вариантов в своей книге «Внутри Microsoft SQL Server 2005: запросы T-SQL».

Основные моменты, которые следует учитывать при выборе модели:

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

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

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

JeremyDWill
источник
Привет, я столкнулся с точно такой же проблемой, указанной в вопросе, и хотел бы задать вам вопрос по вышеуказанным темам. Рассматривая структуру, как в теме номер один (организационная структурированная таблица (не структурированная по сотрудникам) с идентификатором ParentId, указанным в той же таблице), мне нужно установить, кто является руководителем определенной области. Я назначу всех сотрудников этой специфической области непосредственно этому. Куда бы вы положили босса этой конкретной области? Внутри той же области или один груп выше? Мой подход заключается в том, чтобы отнести его / ее к вышеприведенной группе, что, на мой взгляд, дает мне лучшую структуру. Спасибо.
Маркос Бурке
1
Первая ссылка, кажется, не работает.
Хорхе Лейтао
Отличный ответ. Спасибо @ JeremyDWill!
Бобокопия
56

Посмотрите на Управление иерархическими данными в MySQL . В нем рассматриваются два подхода для хранения и управления иерархическими (древовидными) данными в реляционной базе данных.

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

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

Айман Хуриех
источник
Ваша ссылка имеет очень интересную тему, которая обсуждается. Спасибо!
Фриц
9

Если вам нужно использовать реляционную базу данных для организации древовидной структуры данных, то в Postgresql есть классный модуль ltree, который предоставляет тип данных для представления меток данных, хранящихся в иерархической древовидной структуре. Вы можете получить идею оттуда. (Для получения дополнительной информации см .: http://www.postgresql.org/docs/9.0/static/ltree.html )

Обычно LDAP используется для организации записей в иерархической структуре.

yurilo
источник
2

Наличие таблицы с внешним ключом само по себе имеет смысл для меня.

Затем вы можете использовать обычное табличное выражение в SQL или оператор предварительного соединения в Oracle для построения вашего дерева.

Аарон Дэниелс
источник
У меня есть таблица журнала со столбцом идентификаторов LogID и столбец ParentLogID с FK, который указывает на столбец LogID. Когда записывается первая строка журнала в транзакции, я беру SCOPE_IDENTITY (). Все остальные записи журнала записываются с этим значением в столбец ParentLogID. Это действительно полезно для группировки строк, которые принадлежат друг другу. Это единственный реальный способ увидеть, что произошло, без этого это был бы огромный беспорядок в строках журнала из нескольких транзакций, смешанных вместе.
КМ.
@KM - Он сказал, что «имеет смысл», а не «не имеет смысла»
Джон Раш
1

Я использовал следующую реализацию на SQL SERVER 2005. Проверьте здесь

emzero
источник
0

Если кто-либо, использующий MS SQL Server 2008 и более поздние версии, ответит на этот вопрос: в SQL Server 2008 и более поздних версиях появилась новая функция «ierarchyId », разработанная специально для этой задачи.

Более подробная информация на https://docs.microsoft.com/en-us/sql/relational-databases/hierarchical-data-sql-server

Alex
источник