Предположим, у вас есть плоская таблица, в которой хранится иерархия упорядоченного дерева:
Id Name ParentId Order
1 'Node 1' 0 10
2 'Node 1.1' 1 10
3 'Node 2' 0 20
4 'Node 1.1.1' 2 10
5 'Node 2.1' 3 10
6 'Node 1.2' 1 20
Вот схема, где мы имеем [id] Name
. Корневой узел 0 вымышленный.
[0] ROOT / \ [1] Узел 1 [3] Узел 2 / \ \ [2] Узел 1.1 [6] Узел 1.2 [5] Узел 2.1 / [4] Узел 1.1.1
Какой минималистический подход вы бы использовали для вывода этого в HTML (или текст, если на то пошло) как правильно упорядоченное, правильно отступающее дерево?
Предположим далее, что у вас есть только базовые структуры данных (массивы и хэш-карты), нет причудливых объектов со ссылками родитель / потомок, нет ORM, нет фреймворка, только ваши две руки. Таблица представлена в виде набора результатов, к которому можно получить произвольный доступ.
Псевдокод или простой английский в порядке, это чисто концептуальный вопрос.
Бонусный вопрос: существует ли принципиально лучший способ хранить древовидную структуру, подобную этой, в СУБД?
ИЗМЕНЕНИЯ И ДОПОЛНЕНИЯ
Чтобы ответить на вопрос одного комментатора ( Марка Бесси ): корневой узел не нужен, потому что он все равно никогда не будет отображаться. ParentId = 0 - это соглашение для выражения «это верхний уровень». Столбец «Порядок» определяет порядок сортировки узлов с одним и тем же родителем.
«Набор результатов», о котором я говорил, можно представить в виде массива хэш-карт (чтобы остаться в этой терминологии). Для моего примера должно было быть уже там. Некоторые ответы проходят лишнюю милю и сначала ее строят, но это нормально.
Дерево может быть сколь угодно глубоким. Каждый узел может иметь N детей. Хотя я не имел в виду дерево «миллионов записей».
Не путайте мой выбор имен узлов ('Node 1.1.1') с тем, на что можно положиться. С таким же успехом узлы можно было бы назвать «Фрэнк» или «Боб», структура имен не подразумевалась, это было сделано лишь для того, чтобы сделать его читаемым.
Я опубликовал свое собственное решение, чтобы вы, ребята, могли разобрать его на части.
Ответы:
Теперь, когда MySQL 8.0 поддерживает рекурсивные запросы , мы можем сказать, что все популярные базы данных SQL поддерживают рекурсивные запросы в стандартном синтаксисе.
Я тестировал рекурсивные запросы в MySQL 8.0 в своей презентации Recursive Query Throwdown в 2017 году.
Ниже мой оригинальный ответ от 2008 года:
Существует несколько способов хранения древовидных данных в реляционной базе данных. То, что вы показываете в своем примере, использует два метода:
Другое решение называется Nested Sets , и оно также может храниться в той же таблице. Прочтите « Деревья и иерархии в SQL для умников » Джо Селко, чтобы узнать больше об этих проектах.
Я обычно предпочитаю проект под названием Closure Table (он же «Соотношение смежности») для хранения данных с древовидной структурой. Требуется другая таблица, но тогда запросить деревья довольно просто.
Я закрываю таблицу замыканий в своей презентации « Модели для иерархических данных с использованием SQL и PHP» и в своей книге « Антипаттерны SQL: предотвращение ловушек программирования баз данных» .
Сохраните все пути в таблице закрытия, где существует прямое происхождение от одного узла к другому. Включите строку для каждого узла, чтобы ссылаться на себя. Например, используя набор данных, который вы указали в своем вопросе:
Теперь вы можете получить дерево, начинающееся с узла 1 следующим образом:
Вывод (в клиенте MySQL) выглядит следующим образом:
Другими словами, узлы 3 и 5 исключены, потому что они являются частью отдельной иерархии, а не нисходящими от узла 1.
Re: комментарий от e-satun о непосредственных детях (или непосредственных родителях). Вы можете добавить
path_length
столбец " " в,ClosureTable
чтобы упростить запрос специально для непосредственного потомка или родителя (или любого другого расстояния).Затем вы можете добавить термин в свой запрос для запроса непосредственных потомков данного узла. Это потомки которых
path_length
1.Комментарий от @ashraf: «Как насчет сортировки всего дерева [по имени]?»
Вот пример запроса, чтобы вернуть все узлы, которые являются потомками узла 1, соединить их с FlatTable, который содержит другие атрибуты узла, такие как
name
, и отсортировать по имени.Re комментарий от @Nate:
Пользователь предложил изменить сегодня. ТАК модераторы одобрили редактирование, но я изменил его.
Редактирование предположило, что ORDER BY в последнем запросе выше
ORDER BY b.path_length, f.name
, вероятно, должен убедиться, что порядок соответствует иерархии. Но это не работает, потому что он будет заказывать «Node 1.1.1» после «Node 1.2».Если вы хотите, чтобы порядок соответствовал иерархии разумным образом, это возможно, но не просто путем упорядочения по длине пути. Например, см. Мой ответ на иерархическую базу данных MySQL Closure Table - Как вытащить информацию в правильном порядке .
источник
parent_id
) имеет только одну строку, чтобы выразить каждое отношение родитель-потомок, но у таблицы закрытия есть много.Если вы используете вложенные наборы (иногда называемые измененным обходом дерева предзаказа), вы можете извлечь всю древовидную структуру или любое поддерево в ней в древовидном порядке с помощью одного запроса, за счет того, что вставки обходятся дороже, так как вам нужно управлять столбцами, которые описывают путь по порядку через древовидную структуру.
Для django-mptt я использовал такую структуру:
Который описывает дерево, которое выглядит следующим образом (с
id
представлением каждого элемента):Или, как диаграмма вложенного множества, которая делает более очевидным, как работают значения
lft
иrght
:Как вы можете видеть, чтобы получить все поддерево для данного узла в древовидном порядке, вам просто нужно выбрать все строки, которые имеют
lft
иrght
значения между егоlft
иrght
значениями. Также легко получить дерево предков для данного узла.level
Колонка немного денормализации для удобства более чем что - либо , аtree_id
столбец позволяет перезапуститьlft
иrght
нумерацию для каждого узла верхнего уровня, что уменьшает количество столбцов , затронутых вставки, движения и удаления, какlft
иrght
столбцы должны быть скорректированы соответственно, когда эти операции имеют место, чтобы создать или закрыть пробелы. Я сделал несколько замечаний по разработке в то время, когда пытался сосредоточиться на запросах, необходимых для каждой операции.Что касается фактической работы с этими данными для отображения дерева, я создал
tree_item_iterator
вспомогательную функцию, которая для каждого узла должна предоставлять вам достаточную информацию для генерирования любого вида отображения, который вы хотите.Больше информации о MPTT:
источник
lft
иrght
для имен столбцов, я имею в виду, сколько символов нам не нужно было вводить? один?!Это довольно старый вопрос, но, поскольку у него много мнений, я думаю, что стоит представить альтернативное и, на мой взгляд, очень элегантное решение.
Чтобы прочитать древовидную структуру, вы можете использовать рекурсивные выражения общих таблиц (CTE). Это дает возможность извлекать всю древовидную структуру сразу, иметь информацию об уровне узла, его родительском узле и порядке внутри дочерних узлов родительского узла.
Позвольте мне показать вам, как это будет работать в PostgreSQL 9.1.
Создать структуру
Написать запрос
Вот результаты:
Узлы дерева упорядочены по уровню глубины. В конечном результате мы представим их в следующих строках.
Для каждого уровня они упорядочены по parent_id и node_order внутри родителя. Это говорит нам о том, как представить их в узле выходной ссылки для родителя в этом порядке.
Имея такую структуру, было бы нетрудно сделать действительно хорошую презентацию в HTML.
Рекурсивные CTE доступны в PostgreSQL, IBM DB2, MS SQL Server и Oracle .
Если вы хотите узнать больше о рекурсивных SQL-запросах, вы можете проверить документацию вашей любимой СУБД или прочитать две мои статьи на эту тему:
источник
Начиная с Oracle 9i, вы можете использовать CONNECT BY.
Начиная с SQL Server 2005, вы можете использовать рекурсивное общее табличное выражение (CTE).
Оба будут выводить следующие результаты.
источник
Ответ Билла чертовски хорош, этот ответ добавляет к нему некоторые вещи, которые заставляют меня желать, чтобы ТАК поддерживали многопоточные ответы.
В любом случае я хотел поддержать древовидную структуру и свойство Order. Я включил одно свойство в каждый названный узел,
leftSibling
которое делает то же самоеOrder
, что и в первоначальном вопросе (поддерживает порядок слева направо).Более подробно и код SQL на моем блоге .
Спасибо, Билл, ваш ответ был полезен для начала!
источник
Хорошо, если бы у меня был выбор, я бы использовал объекты. Я бы создал объект для каждой записи, где у каждого объекта есть
children
коллекция, и сохранил бы их все в ассоциированном массиве (/ hashtable), где Id - это ключ. И пролистайте коллекцию один раз, добавив детей в соответствующие дочерние поля. Просто.Но поскольку вам не весело, ограничивая использование некоторых хороших ООП, я бы, вероятно, повторил на основе:
Изменить: это похоже на пару других записей, но я думаю, что это немного чище. Я добавлю одну вещь: это чрезвычайно интенсивно использует SQL. Это противно . Если у вас есть выбор, пройдите маршрут ООП.
источник
Это было написано быстро, и не является ни красивым, ни эффективным (плюс это много автобоксов, преобразование между
int
иInteger
раздражает!), Но это работает.Возможно, это нарушает правила, так как я создаю свои собственные объекты, но эй, я делаю это как отвлечение от реальной работы :)
Это также предполагает, что resultSet / таблица полностью считывается в какую-то структуру перед тем, как вы начнете создавать узлы, что не будет лучшим решением, если у вас есть сотни тысяч строк.
источник
Есть действительно хорошие решения, которые используют внутреннее btree представление индексов sql. Это основано на некоторых замечательных исследованиях, проведенных в 1998 году.
Вот пример таблицы (в MySQL).
Единственные поля, необходимые для представления дерева:
Вот пример 24 узла населения, упорядоченный по tw:
Каждый результат дерева может быть сделан не рекурсивно. Например, чтобы получить список предков узла в tw = '22 '
Предки
Братья и сестры и дети тривиальны - просто используйте порядок полей по tw.
Потомки
Например, набор (ветвь) узлов, которые имеют корни в tw = 17.
Дополнительные замечания
Эта методология чрезвычайно полезна для случаев, когда число операций чтения намного больше, чем вставок или обновлений.
Поскольку для вставки, перемещения или обновления узла в дереве требуется корректировка дерева, необходимо заблокировать таблицу перед началом действия.
Стоимость вставки / удаления высока, потому что значения индекса tw и sz (размер ветви) необходимо будет обновить на всех узлах после точки вставки и для всех предков соответственно.
Перемещение веток включает в себя перемещение значения tw ветви за пределы диапазона, поэтому также необходимо отключить ограничения внешнего ключа при перемещении ветви. По сути, для перемещения ветки требуется четыре запроса:
Настройте запросы дерева
Открытие / закрытие пробелов в дереве является важной подфункцией, используемой методами create / update / delete, поэтому я включу ее здесь.
Нам нужны два параметра - флаг, показывающий, уменьшаем мы размер или нет, и индекс tw узла. Так, например, tw = 18 (который имеет размер ветви 5). Давайте предположим, что мы сокращаем (удаляем tw) - это означает, что мы используем '-' вместо '+' в обновлениях следующего примера.
Сначала мы используем (слегка измененную) функцию предка, чтобы обновить значение sz.
Затем нам нужно настроить tw для тех, чье tw больше, чем ветвь, которую нужно удалить.
Затем нам нужно настроить родителя для тех, у кого pa больше чем ветвь, которую нужно удалить.
источник
Предполагая, что вы знаете, что корневые элементы равны нулю, вот псевдокод для вывода в текст:
источник
Вы можете эмулировать любую другую структуру данных с помощью хэш-карты, так что это не страшное ограничение. Сканируя сверху вниз, вы создаете хэш-карту для каждой строки базы данных с записью для каждого столбца. Добавьте каждую из этих хеш-карт в «главную» хеш-карту, указав идентификатор. Если у какого-либо узла есть «родительский элемент», которого вы еще не видели, создайте для него запись-заполнитель в главной хэш-карте и заполните его, когда увидите реальный узел.
Чтобы распечатать его, сделайте простой проход в глубину по данным, отслеживая уровень отступа по пути. Это можно упростить, сохранив запись «children» для каждой строки и заполнив ее при сканировании данных.
Что касается того, существует ли «лучший» способ хранения дерева в базе данных, это зависит от того, как вы собираетесь использовать данные. Я видел системы с известной максимальной глубиной, которые использовали разные таблицы для каждого уровня в иерархии. Это имеет большой смысл, если уровни в дереве не совсем эквивалентны (категории верхнего уровня отличаются от листьев).
источник
Если могут быть созданы вложенные хеш-карты или массивы, то я могу просто пойти вниз по таблице с самого начала и добавить каждый элемент во вложенный массив. Я должен проследить каждую строку до корневого узла, чтобы узнать, в какой уровень вложенного массива вставлять. Я могу использовать напоминание, чтобы мне не приходилось искать одного и того же родителя снова и снова.
Редактировать: я бы сначала прочитал всю таблицу в массив, чтобы он не запрашивал БД несколько раз. Конечно, это не будет практичным, если ваш стол очень большой.
После того, как структура построена, я должен сначала пройти через глубину и распечатать HTML.
Нет лучшего фундаментального способа хранения этой информации с использованием одной таблицы (хотя я могу ошибаться;), и я бы хотел найти лучшее решение). Однако, если вы создадите схему для использования динамически создаваемых таблиц БД, то вы откроете для себя целый новый мир, жертвуя простотой и риском адского SQL;).
источник
Если элементы расположены в древовидном порядке, как показано в вашем примере, вы можете использовать что-то вроде следующего примера Python:
То, что это делает, поддерживает стек, представляющий текущую позицию в дереве. Для каждого элемента в таблице он выталкивает элементы стека (закрывая соответствующие элементы div), пока не найдет родителя текущего элемента. Затем он выводит начало этого узла и помещает его в стек.
Если вы хотите вывести дерево, используя отступы, а не вложенные элементы, вы можете просто пропустить операторы print, чтобы напечатать div, и вывести число пробелов, равное некоторому кратному размеру стека, перед каждым элементом. Например, в Python:
Вы также можете легко использовать этот метод для создания набора вложенных списков или словарей.
Изменить: я вижу из вашего пояснения, что имена не были предназначены для пути узлов. Это предполагает альтернативный подход:
Это создает дерево массивов кортежей (!). idx [0] представляет корень (и) дерева. Каждый элемент в массиве представляет собой 2-кортеж, состоящий из самого узла и списка всех его дочерних элементов. После создания вы можете удерживать idx [0] и сбрасывать idx, если только вы не хотите обращаться к узлам по их ID.
источник
Чтобы расширить SQL-решение Билла, вы можете сделать то же самое, используя плоский массив. Более того, если все ваши строки имеют одинаковую длину и ваше максимальное число дочерних элементов известно (скажем, в двоичном дереве), вы можете сделать это, используя одну строку (массив символов). Если у вас произвольное количество детей, это немного усложняет ... Я должен был бы проверить мои старые записи, чтобы посмотреть, что можно сделать.
Затем, пожертвовав небольшим количеством памяти, особенно если ваше дерево редкое и / или несбалансированное, вы можете, с небольшим количеством математической индексации, получить доступ ко всем строкам случайным образом, сохраняя ваше дерево, сначала ширину в массиве, например (для двоичного файла) дерево)
Вы знаете свою длину строки, вы знаете это
Я сейчас на работе, поэтому не могу тратить на это много времени, но с интересом могу принести немного кода для этого.
Мы используем это для поиска в двоичных деревьях, состоящих из кодонов ДНК, процесс строит дерево, затем мы сплющиваем его для поиска шаблонов текста, и когда найдем, хотя по индексу математики (наоборот) мы получаем узел обратно ... очень быстро и эффективно, хотя в нашем дереве редко были пустые узлы, но мы могли быстро найти гигабайты данных.
источник
Подумайте об использовании таких инструментов nosql, как neo4j, для иерархических структур. например, сетевое приложение, такое как linkedin, использует couchbase (другое решение nosql)
Но используйте nosql только для запросов уровня витрины данных, а не для хранения / поддержки транзакций
источник