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

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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

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

Answer 3

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

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

Answer 4

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

http://www.artfulsoftware.com/mysqlbook/sampler/mysqled1ch20.html

Answer 5

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

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

Answer 6

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