Какой самый эффективный / элегантный способ разбить плоский стол на дерево?
Предположим, у вас есть плоская таблица, в которой хранится иерархия упорядоченного дерева:
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, нет фреймворка, только ваши две руки. Таблица представлена в виде набора результатов, к которому можно получить произвольный доступ.
Псевдокод или простой английский в порядке, это чисто концептуальный вопрос.
Дополнительный вопрос: существует ли принципиально лучший способ хранения такой древовидной структуры в СУБД?
ИЗМЕНЕНИЯ И ДОПОЛНЕНИЯ
Чтобы ответить на вопрос одного комментатора ( Mark Bessey): корневой узел не нужен, потому что он все равно никогда не будет отображаться. ParentId = 0 - это соглашение для выражения "это верхний уровень". Столбец "Порядок" определяет порядок сортировки узлов с одним и тем же родителем.
"Набор результатов", о котором я говорил, можно представить в виде массива хэш-карт (чтобы остаться в этой терминологии). Для моего примера должен был быть уже там. Некоторые ответы проходят лишнюю милю и сначала ее строят, но это нормально.
Дерево может быть сколь угодно глубоким. Каждый узел может иметь N детей. Однако я не имел в виду дерево "миллионов записей".
Не путайте мой выбор имен узлов ("Node 1.1.1") с тем, на что можно положиться. С таким же успехом узлы могут называться "Фрэнк" или "Боб", структура имен не подразумевается, это просто для того, чтобы сделать ее читабельной.
Я опубликовал свое собственное решение, чтобы вы, ребята, могли разобрать его на части.
15 ответов
Теперь, когда MySQL 8.0 приближается к выпуску, все популярные базы данных SQL будут поддерживать рекурсивные запросы в стандартном синтаксисе.
WITH RECURSIVE MyTree AS (
SELECT * FROM MyTable WHERE ParentId IS NULL
UNION ALL
SELECT m.* FROM MyTABLE AS m JOIN MyTree AS t ON m.ParentId = t.Id
)
SELECT * FROM MyTree;
Я протестировал рекурсивные запросы в MySQL 8.0 в своей презентации Recursive Query Throwdown в 2017 году.
Ниже мой оригинальный ответ от 2008 года:
Существует несколько способов хранения древовидных данных в реляционной базе данных. То, что вы показываете в своем примере, использует два метода:
- Список смежности (родительский столбец) и
- Перечисление пути (точечные числа в вашем столбце имени).
Другое решение называется Nested Sets, и оно также может храниться в той же таблице. Прочтите " Деревья и иерархии в SQL для умников" Джо Селко, чтобы узнать больше об этих проектах.
Я обычно предпочитаю дизайн под названием Closure Table (он же "Соотношение смежности") для хранения данных с древовидной структурой. Это требует другой таблицы, но тогда запросить деревья довольно просто.
Я закрываю таблицу замыканий в своей презентации " Модели для иерархических данных с использованием SQL и PHP" и в своей книге " Антипаттерны SQL: предотвращение ловушек программирования баз данных".
CREATE TABLE ClosureTable (
ancestor_id INT NOT NULL REFERENCES FlatTable(id),
descendant_id INT NOT NULL REFERENCES FlatTable(id),
PRIMARY KEY (ancestor_id, descendant_id)
);
Сохраните все пути в таблице закрытия, где существует прямое происхождение от одного узла к другому. Включите строку для каждого узла, чтобы ссылаться на себя. Например, используя набор данных, который вы указали в своем вопросе:
INSERT INTO ClosureTable (ancestor_id, descendant_id) VALUES
(1,1), (1,2), (1,4), (1,6),
(2,2), (2,4),
(3,3), (3,5),
(4,4),
(5,5),
(6,6);
Теперь вы можете получить дерево, начиная с узла 1 следующим образом:
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1;
Вывод (в клиенте MySQL) выглядит следующим образом:
+----+
| id |
+----+
| 1 |
| 2 |
| 4 |
| 6 |
+----+
Другими словами, узлы 3 и 5 исключаются, потому что они являются частью отдельной иерархии, а не нисходящими от узла 1.
Re: комментарий от e-satun о непосредственных детях (или непосредственных родителях). Вы можете добавить "path_length"столбец к ClosureTable чтобы было проще запрашивать данные непосредственно о ближайшем ребенке или родителе (или любом другом расстоянии).
INSERT INTO ClosureTable (ancestor_id, descendant_id, path_length) VALUES
(1,1,0), (1,2,1), (1,4,2), (1,6,1),
(2,2,0), (2,4,1),
(3,3,0), (3,5,1),
(4,4,0),
(5,5,0),
(6,6,0);
Затем вы можете добавить термин в свой поиск для запроса непосредственных потомков данного узла. Это потомки, чьи path_length это 1.
SELECT f.*
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
AND path_length = 1;
+----+
| id |
+----+
| 2 |
| 6 |
+----+
Комментарий от @ashraf: "Как насчет сортировки всего дерева [по имени]?"
Вот пример запроса для возврата всех узлов, которые являются потомками узла 1, присоедините их к FlatTable, который содержит другие атрибуты узла, такие как nameи сортировать по имени.
SELECT f.name
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
WHERE a.ancestor_id = 1
ORDER BY f.name;
Re комментарий от @Nate:
SELECT f.name, GROUP_CONCAT(b.ancestor_id order by b.path_length desc) AS breadcrumbs
FROM FlatTable f
JOIN ClosureTable a ON (f.id = a.descendant_id)
JOIN ClosureTable b ON (b.descendant_id = a.descendant_id)
WHERE a.ancestor_id = 1
GROUP BY a.descendant_id
ORDER BY f.name
+------------+-------------+
| name | breadcrumbs |
+------------+-------------+
| Node 1 | 1 |
| Node 1.1 | 1,2 |
| Node 1.1.1 | 1,2,4 |
| Node 1.2 | 1,6 |
+------------+-------------+
Пользователь предложил изменить сегодня. ТАК модераторы одобрили редактирование, но я изменил его.
Редактирование предполагает, что ORDER BY в последнем запросе выше ORDER BY b.path_length, f.nameпредположительно, чтобы убедиться, что порядок соответствует иерархии. Но это не работает, потому что он будет заказывать "Node 1.1.1" после "Node 1.2".
Если вы хотите, чтобы порядок соответствовал иерархии разумным образом, это возможно, но не просто путем упорядочения по длине пути. Например, см. Мой ответ на иерархическую базу данных MySQL Closure Table - Как вытащить информацию в правильном порядке.
Если вы используете вложенные наборы (иногда называемые измененным обходом дерева предварительных заказов), вы можете извлечь всю древовидную структуру или любое поддерево в ней в древовидном порядке с помощью одного запроса за счет того, что вставки обходятся дороже, так как вам нужно управлять столбцами, которые описывают путь по порядку через древовидную структуру.
Для django-mptt я использовал такую структуру:
id parent_id tree_id level lft rght -- --------- ------- ----- --- --- 1 ноль 1 0 1 14 2 1 1 1 2 7 3 2 1 2 3 4 4 2 1 2 5 6 5 1 1 1 8 13 6 5 1 2 9 10 7 5 1 2 11 12
Который описывает дерево, которое выглядит так (с id представляя каждый элемент):
1
+ - 2
| +- 3
| +- 4
|
+ - 5
+- 6
+- 7Или, как диаграмма вложенного множества, которая делает более очевидным, как lft а также rght Ценности работы:
__________________________________________________________________________ | Корень 1 | | ________________________________ ________________________________ | | | Ребенок 1.1 | | Ребенок 1.2 | | | | ___________ ___________ | | ___________ ___________ | | | | | С 1.1.1 | | С 1.1.2 | | | | С 1.2.1 | | С 1.2.2 | | | 1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14 | |________________________________| |________________________________| | |__________________________________________________________________________|
Как вы можете видеть, чтобы получить все поддерево для данного узла, в древовидном порядке, вам просто нужно выбрать все строки, которые имеют lft а также rght значения между его lft а также rght ценности. Также легко получить дерево предков для данного узла.
level колонка немного денормализации для удобства больше всего и tree_id колонка позволяет перезапустить lft а также rght нумерация для каждого узла верхнего уровня, что уменьшает количество столбцов, затронутых вставками, перемещениями и удалениями, так как lft а также rght столбцы должны быть соответствующим образом скорректированы, когда эти операции имеют место для создания или закрытия пробелов. Я сделал несколько замечаний по разработке в то время, когда пытался сосредоточиться на запросах, необходимых для каждой операции.
С точки зрения фактической работы с этими данными для отображения дерева, я создалtree_item_iterator служебная функция, которая для каждого узла должна предоставлять вам достаточную информацию для генерирования любого вида отображения, который вы хотите.
Больше информации о MPTT:
Это довольно старый вопрос, но, поскольку у него много мнений, я думаю, что стоит представить альтернативное и, на мой взгляд, очень элегантное решение.
Чтобы прочитать древовидную структуру, вы можете использовать рекурсивные выражения общих таблиц (CTE). Это дает возможность извлекать всю древовидную структуру сразу, иметь информацию об уровне узла, его родительском узле и порядке в дочерних узлах родительского узла.
Позвольте мне показать вам, как это будет работать в PostgreSQL 9.1.
Создать структуру
CREATE TABLE tree ( id int NOT NULL, name varchar(32) NOT NULL, parent_id int NULL, node_order int NOT NULL, CONSTRAINT tree_pk PRIMARY KEY (id), CONSTRAINT tree_tree_fk FOREIGN KEY (parent_id) REFERENCES tree (id) NOT DEFERRABLE ); insert into tree values (0, 'ROOT', NULL, 0), (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);Написать запрос
WITH RECURSIVE tree_search (id, name, level, parent_id, node_order) AS ( SELECT id, name, 0, parent_id, 1 FROM tree WHERE parent_id is NULL UNION ALL SELECT t.id, t.name, ts.level + 1, ts.id, t.node_order FROM tree t, tree_search ts WHERE t.parent_id = ts.id ) SELECT * FROM tree_search WHERE level > 0 ORDER BY level, parent_id, node_order;Вот результаты:
id | name | level | parent_id | node_order ----+------------+-------+-----------+------------ 1 | Node 1 | 1 | 0 | 10 3 | Node 2 | 1 | 0 | 20 2 | Node 1.1 | 2 | 1 | 10 6 | Node 1.2 | 2 | 1 | 20 5 | Node 2.1 | 2 | 3 | 10 4 | Node 1.1.1 | 3 | 2 | 10 (6 rows)Узлы дерева упорядочены по уровню глубины. В конечном результате мы представим их в следующих строках.
Для каждого уровня они упорядочены по parent_id и node_order внутри родителя. Это говорит нам о том, как представить их в узле выходной ссылки для родителя в этом порядке.
Имея такую структуру, было бы нетрудно сделать действительно хорошую презентацию в HTML.
Рекурсивные CTE доступны в PostgreSQL, IBM DB2, MS SQL Server и Oracle.
Если вы хотите узнать больше о рекурсивных SQL-запросах, вы можете проверить документацию вашей любимой СУБД или прочитать две мои статьи на эту тему:
Начиная с Oracle 9i, вы можете использовать CONNECT BY.
SELECT LPAD(' ', (LEVEL - 1) * 4) || "Name" AS "Name"
FROM (SELECT * FROM TMP_NODE ORDER BY "Order")
CONNECT BY PRIOR "Id" = "ParentId"
START WITH "Id" IN (SELECT "Id" FROM TMP_NODE WHERE "ParentId" = 0)
Начиная с SQL Server 2005, вы можете использовать рекурсивное общее табличное выражение (CTE).
WITH [NodeList] (
[Id]
, [ParentId]
, [Level]
, [Order]
) AS (
SELECT [Node].[Id]
, [Node].[ParentId]
, 0 AS [Level]
, CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
WHERE [Node].[ParentId] = 0
UNION ALL
SELECT [Node].[Id]
, [Node].[ParentId]
, [NodeList].[Level] + 1 AS [Level]
, [NodeList].[Order] + '|'
+ CONVERT([varchar](MAX), [Node].[Order]) AS [Order]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[ParentId]
) SELECT REPLICATE(' ', [NodeList].[Level] * 4) + [Node].[Name] AS [Name]
FROM [Node]
INNER JOIN [NodeList] ON [NodeList].[Id] = [Node].[Id]
ORDER BY [NodeList].[Order]
Оба будут выводить следующие результаты.
название "Узел 1" "Узел 1.1" "Узел 1.1.1" "Узел 1.2" "Узел 2" "Узел 2.1"
Ответ Билла чертовски хорош, этот ответ добавляет кое-что к нему, что заставляет меня желать, чтобы ТА поддержали многопоточные ответы.
В любом случае я хотел поддержать древовидную структуру и свойство Order. Я включил одно свойство в каждый узел под названием leftSibling это делает то же самое Order предполагается сделать в исходном вопросе (поддерживать порядок слева направо).
mysql> desc узлов; +-------------+--------------+------+-----+-------- + ---------------- + | Поле | Тип | Null | Ключ | По умолчанию | Extra | +-------------+--------------+------+-----+ --------+----------------+ | id | int(11) | НЕТ | PRI | NULL | auto_increment | | имя | Варчар (255) | ДА | | NULL | | | leftSibling | int(11) | НЕТ | | 0 | | +-------------+--------------+------+-----+-------- +----------------+ 3 ряда в наборе (0,00 сек) mysql> desc смежности; +------------+---------+------+-----+---------+----------------+ | Поле | Тип | Null | Ключ | По умолчанию | Extra | +------------+---------+------+-----+---------+----------------+ | отношение ID | int (11) | НЕТ | PRI | NULL | auto_increment | | родитель | int (11) | НЕТ | | NULL | | | ребенок | int (11) | НЕТ | | NULL | | | pathLen | int(11) | НЕТ | | NULL | | +------------+---------+------+-----+---------+----------------+ 4 ряда в наборе (0,00 сек)
Более подробно и код SQL на моем блоге.
Спасибо, Билл, ваш ответ был полезен для начала!
Есть действительно хорошие решения, которые используют внутреннее btree представление индексов sql. Это основано на некоторых замечательных исследованиях, проведенных в 1998 году.
Вот пример таблицы (в MySQL).
CREATE TABLE `node` (
`id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`name` varchar(255) NOT NULL,
`tw` int(10) unsigned NOT NULL,
`pa` int(10) unsigned DEFAULT NULL,
`sz` int(10) unsigned DEFAULT NULL,
`nc` int(11) GENERATED ALWAYS AS (tw+sz) STORED,
PRIMARY KEY (`id`),
KEY `node_tw_index` (`tw`),
KEY `node_pa_index` (`pa`),
KEY `node_nc_index` (`nc`),
CONSTRAINT `node_pa_fk` FOREIGN KEY (`pa`) REFERENCES `node` (`tw`) ON DELETE CASCADE
)
Единственные поля, необходимые для представления дерева:
- tw: индекс предварительного заказа DFS слева направо, где root = 1.
- pa: ссылка (с использованием tw) на родительский узел, root имеет значение null.
- sz: размер ветви узла, включая самого себя.
- nc: используется как синтаксический сахар. это tw+nc и представляет двенадцать "следующего потомка" узла.
Вот пример 24 узла населения, упорядоченный по tw:
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 2 | A | 2 | 1 | 14 | 16 |
| 3 | AA | 3 | 2 | 1 | 4 |
| 4 | AB | 4 | 2 | 7 | 11 |
| 5 | ABA | 5 | 4 | 1 | 6 |
| 6 | ABB | 6 | 4 | 3 | 9 |
| 7 | ABBA | 7 | 6 | 1 | 8 |
| 8 | ABBB | 8 | 6 | 1 | 9 |
| 9 | ABC | 9 | 4 | 2 | 11 |
| 10 | ABCD | 10 | 9 | 1 | 11 |
| 11 | AC | 11 | 2 | 4 | 15 |
| 12 | ACA | 12 | 11 | 2 | 14 |
| 13 | ACAA | 13 | 12 | 1 | 14 |
| 14 | ACB | 14 | 11 | 1 | 15 |
| 15 | AD | 15 | 2 | 1 | 16 |
| 16 | B | 16 | 1 | 1 | 17 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
| 18 | D | 23 | 1 | 1 | 24 |
| 19 | E | 24 | 1 | 1 | 25 |
+-----+---------+----+------+------+------+
Каждый результат дерева может быть сделан не рекурсивно. Например, чтобы получить список предков узла в tw='22'
Предки
select anc.* from node me,node anc
where me.tw=22 and anc.nc >= me.tw and anc.tw <= me.tw
order by anc.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 1 | Root | 1 | NULL | 24 | 25 |
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Братья и сестры и дети тривиальны - просто используйте порядок полей по tw.
Потомки
Например, множество (ветвь) узлов, которые имеют корни в tw = 17.
select des.* from node me,node des
where me.tw=17 and des.tw < me.nc and des.tw >= me.tw
order by des.tw;
+-----+---------+----+------+------+------+
| id | name | tw | pa | sz | nc |
+-----+---------+----+------+------+------+
| 17 | C | 17 | 1 | 6 | 23 |
| 359 | C0 | 18 | 17 | 5 | 23 |
| 360 | C1 | 19 | 18 | 4 | 23 |
| 361 | C2(res) | 20 | 19 | 3 | 23 |
| 362 | C3 | 21 | 20 | 2 | 23 |
| 363 | C4 | 22 | 21 | 1 | 23 |
+-----+---------+----+------+------+------+
Дополнительные примечания
Эта методология чрезвычайно полезна для случаев, когда число операций чтения намного больше, чем вставок или обновлений.
Поскольку для вставки, перемещения или обновления узла в дереве необходимо настроить дерево, необходимо заблокировать таблицу перед началом действия.
Стоимость вставки / удаления высока, потому что значения индекса tw и sz (размер ветви) необходимо будет обновить на всех узлах после точки вставки и для всех предков соответственно.
Перемещение веток включает в себя перемещение значения tw ветви за пределы диапазона, поэтому также необходимо отключить ограничения внешнего ключа при перемещении ветви. По сути, для перемещения ветки требуется четыре запроса:
- Переместите ветку за пределы диапазона.
- Закройте пробел, который он оставил. (оставшееся дерево теперь нормализовано).
- Откройте пробел, куда он пойдет.
- Переместите ветку в новую позицию.
Настройте запросы дерева
Открытие / закрытие пропусков в дереве - важная подфункция, используемая методами create / update / delete, поэтому я включу ее здесь.
Нам нужны два параметра - флаг, показывающий, уменьшаем мы размер или нет, и индекс tw узла. Так, например, tw=18 (который имеет размер ветви 5). Давайте предположим, что мы сокращаем (удаляем tw) - это означает, что мы используем '-' вместо '+' в обновлениях следующего примера.
Сначала мы используем (слегка измененную) функцию предка, чтобы обновить значение sz.
update node me, node anc set anc.sz = anc.sz - me.sz from
node me, node anc where me.tw=18
and ((anc.nc >= me.tw and anc.tw < me.pa) or (anc.tw=me.pa));
Затем нам нужно настроить tw для тех, чье tw больше, чем ветвь, которую нужно удалить.
update node me, node anc set anc.tw = anc.tw - me.sz from
node me, node anc where me.tw=18 and anc.tw >= me.tw;
Затем нам нужно настроить родителя для тех, у кого pa больше чем ветвь, которую нужно удалить.
update node me, node anc set anc.pa = anc.pa - me.sz from
node me, node anc where me.tw=18 and anc.pa >= me.tw;
Хорошо, если бы у меня был выбор, я бы использовал объекты. Я бы создал объект для каждой записи, где каждый объект имеет children собирать и хранить их все в массиве (/hashtable), где Id является ключом. И пролистайте коллекцию один раз, добавив детей в соответствующие дочерние поля. Просто.
Но так как вы не веселитесь, ограничивая использование некоторых хороших ООП, я бы, вероятно, повторил на основе:
function PrintLine(int pID, int level)
foreach record where ParentID == pID
print level*tabs + record-data
PrintLine(record.ID, level + 1)
PrintLine(0, 0)
Изменить: это похоже на пару других записей, но я думаю, что это немного чище. Я добавлю одну вещь: это чрезвычайно интенсивно использует SQL. Это противно. Если у вас есть выбор, пройдите маршрут ООП.
Это было написано быстро, и это не красиво и не эффективно (плюс это много автобоксов, преобразование между int а также Integer раздражает!) но работает.
Это, вероятно, нарушает правила, так как я создаю свои собственные объекты, но эй, я делаю это как отвлечение от реальной работы:)
Это также предполагает, что resultSet / table полностью считывается в какую-то структуру перед тем, как вы начнете создавать Nodes, что не будет лучшим решением, если у вас есть сотни тысяч строк.
public class Node {
private Node parent = null;
private List<Node> children;
private String name;
private int id = -1;
public Node(Node parent, int id, String name) {
this.parent = parent;
this.children = new ArrayList<Node>();
this.name = name;
this.id = id;
}
public int getId() {
return this.id;
}
public String getName() {
return this.name;
}
public void addChild(Node child) {
children.add(child);
}
public List<Node> getChildren() {
return children;
}
public boolean isRoot() {
return (this.parent == null);
}
@Override
public String toString() {
return "id=" + id + ", name=" + name + ", parent=" + parent;
}
}
public class NodeBuilder {
public static Node build(List<Map<String, String>> input) {
// maps id of a node to it's Node object
Map<Integer, Node> nodeMap = new HashMap<Integer, Node>();
// maps id of a node to the id of it's parent
Map<Integer, Integer> childParentMap = new HashMap<Integer, Integer>();
// create special 'root' Node with id=0
Node root = new Node(null, 0, "root");
nodeMap.put(root.getId(), root);
// iterate thru the input
for (Map<String, String> map : input) {
// expect each Map to have keys for "id", "name", "parent" ... a
// real implementation would read from a SQL object or resultset
int id = Integer.parseInt(map.get("id"));
String name = map.get("name");
int parent = Integer.parseInt(map.get("parent"));
Node node = new Node(null, id, name);
nodeMap.put(id, node);
childParentMap.put(id, parent);
}
// now that each Node is created, setup the child-parent relationships
for (Map.Entry<Integer, Integer> entry : childParentMap.entrySet()) {
int nodeId = entry.getKey();
int parentId = entry.getValue();
Node child = nodeMap.get(nodeId);
Node parent = nodeMap.get(parentId);
parent.addChild(child);
}
return root;
}
}
public class NodePrinter {
static void printRootNode(Node root) {
printNodes(root, 0);
}
static void printNodes(Node node, int indentLevel) {
printNode(node, indentLevel);
// recurse
for (Node child : node.getChildren()) {
printNodes(child, indentLevel + 1);
}
}
static void printNode(Node node, int indentLevel) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < indentLevel; i++) {
sb.append("\t");
}
sb.append(node);
System.out.println(sb.toString());
}
public static void main(String[] args) {
// setup dummy data
List<Map<String, String>> resultSet = new ArrayList<Map<String, String>>();
resultSet.add(newMap("1", "Node 1", "0"));
resultSet.add(newMap("2", "Node 1.1", "1"));
resultSet.add(newMap("3", "Node 2", "0"));
resultSet.add(newMap("4", "Node 1.1.1", "2"));
resultSet.add(newMap("5", "Node 2.1", "3"));
resultSet.add(newMap("6", "Node 1.2", "1"));
Node root = NodeBuilder.build(resultSet);
printRootNode(root);
}
//convenience method for creating our dummy data
private static Map<String, String> newMap(String id, String name, String parentId) {
Map<String, String> row = new HashMap<String, String>();
row.put("id", id);
row.put("name", name);
row.put("parent", parentId);
return row;
}
}
Предполагая, что вы знаете, что корневые элементы равны нулю, вот псевдокод для вывода в текст:
function PrintLevel (int curr, int level)
//print the indents
for (i=1; i<=level; i++)
print a tab
print curr \n;
for each child in the table with a parent of curr
PrintLevel (child, level+1)
for each elementID where the parentid is zero
PrintLevel(elementID, 0)
Вы можете эмулировать любую другую структуру данных с помощью хэш-карты, так что это не страшное ограничение. Сканируя сверху вниз, вы создаете хэш-карту для каждой строки базы данных с записью для каждого столбца. Добавьте каждую из этих хеш-карт в "главную" хеш-карту, указав идентификатор. Если у какого-либо узла есть "родительский элемент", которого вы еще не видели, создайте для него запись-заполнитель в главной хэш-карте и заполните его, когда увидите реальный узел.
Чтобы распечатать его, сделайте простой проход в глубину по данным, отслеживая уровень отступа по пути. Это можно упростить, сохранив запись "children" для каждой строки и заполнив ее при сканировании данных.
Что касается того, существует ли "лучший" способ хранения дерева в базе данных, это зависит от того, как вы собираетесь использовать данные. Я видел системы с известной максимальной глубиной, которые использовали разные таблицы для каждого уровня в иерархии. Это имеет большой смысл, если уровни в дереве не совсем эквивалентны (категории верхнего уровня отличаются от листьев).
Трансверсал предварительного заказа с перечислением путей на лету в представлении смежности
Вложенные наборы из:
- Кончог /questions/30814053/kakoj-samyij-effektivnyij-elegantnyij-sposob-razbit-ploskij-stol-na-derevo/30814080#30814080
- Джонни Бьюкенен /questions/30814053/kakoj-samyij-effektivnyij-elegantnyij-sposob-razbit-ploskij-stol-na-derevo/30814064#30814064
это единственный эффективный способ обхода, который я видел, за счет более медленных обновлений. Это, вероятно, то, что большинство людей захотят сделать предварительный заказ.
Таблица закрытия из /questions/30814053/kakoj-samyij-effektivnyij-elegantnyij-sposob-razbit-ploskij-stol-na-derevo/30814067#30814067 интересна, но я не вижу, как обеспечить там предварительный заказ: Иерархическая база данных MySQL Closure Table - Как вытащить информацию в правильном порядке
В основном для удовольствия, вот метод, который рекурсивно вычисляет 1.3.2.5. префиксы на лету и сортирует по ним в конце, основываясь только на представлении родительского идентификатора/дочернего индекса.
Плюсы:
- обновлениям нужно только обновить индексы каждого брата
Недостатки:
- Наихудший случай использования памяти n^2 для сверхглубокого дерева. Это может быть довольно серьезно, поэтому я говорю, что этот метод, скорее всего, предназначен только для развлечения. Но, может быть, есть какой-то случай сверхвысокого обновления, где кто-то захочет его использовать? Кто знает
- рекурсивные запросы, поэтому чтение будет менее эффективным, чем вложенные наборы
Создайте и заполните таблицу:
CREATE TABLE "ParentIndexTree" (
"id" INTEGER PRIMARY KEY,
"parentId" INTEGER,
"childIndex" INTEGER NOT NULL,
"value" INTEGER NOT NULL,
"name" TEXT NOT NULL,
FOREIGN KEY ("parentId") REFERENCES "ParentIndexTree"(id)
)
;
INSERT INTO "ParentIndexTree" VALUES
(0, NULL, 0, 1, 'one' ),
(1, 0, 0, 2, 'two' ),
(2, 0, 1, 3, 'three'),
(3, 1, 0, 4, 'four' ),
(4, 1, 1, 5, 'five' )
;
Представленное дерево:
1
/ \
2 3
/ \
4 5
Затем для СУБД с массивами типа PostgreSQL]( https://www.postgresql.org/docs/14/arrays.html):
WITH RECURSIVE "TreeSearch" (
"id",
"parentId",
"childIndex",
"value",
"name",
"prefix"
) AS (
SELECT
"id",
"parentId",
"childIndex",
"value",
"name",
array[0]
FROM "ParentIndexTree"
WHERE "parentId" IS NULL
UNION ALL
SELECT
"child"."id",
"child"."parentId",
"child"."childIndex",
"child"."value",
"child"."name",
array_append("parent"."prefix", "child"."childIndex")
FROM "ParentIndexTree" AS "child"
JOIN "TreeSearch" AS "parent"
ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;
Это создает на лету префиксы формы:
1 -> 0
2 -> 0, 0
3 -> 0, 1
4 -> 0, 0, 0
5 -> 0, 0, 1
а затем PostgreSQL сортирует массивы в алфавитном порядке следующим образом:
1 -> 0
2 -> 0, 0
4 -> 0, 0, 0
5 -> 0, 0, 1
3 -> 0, 1
который является результатом предварительного заказа, который мы хотим.
Для СУБД без массивов, таких как SQLite, вы можете взломать, закодировав префикс строкой целых чисел фиксированной ширины. Двоичный формат был бы идеальным, но я не мог понять, как это сделать, поэтому шестнадцатеричный формат работал бы. Это, конечно, означает, что вам нужно будет выбрать максимальную глубину, которая будет соответствовать количеству выбранных байтов, например, ниже я выбираю 6, что позволяет иметь максимум 16 ^ 6 дочерних элементов на узел.
WITH RECURSIVE "TreeSearch" (
"id",
"parentId",
"childIndex",
"value",
"name",
"prefix"
) AS (
SELECT
"id",
"parentId",
"childIndex",
"value",
"name",
'000000'
FROM "ParentIndexTree"
WHERE "parentId" IS NULL
UNION ALL
SELECT
"child"."id",
"child"."parentId",
"child"."childIndex",
"child"."value",
"child"."name",
"parent"."prefix" || printf('%06x', "child"."childIndex")
FROM "ParentIndexTree" AS "child"
JOIN "TreeSearch" AS "parent"
ON "child"."parentId" = "parent"."id"
)
SELECT * FROM "TreeSearch"
ORDER BY "prefix"
;
Некоторые вложенные заметки
Вот несколько моментов, которые немного смутили меня после просмотра других вложенных ответов.
Джонни Бьюкенен показывает свою настройку вложенного множества как:
__________________________________________________________________________
| Root 1 |
| ________________________________ ________________________________ |
| | Child 1.1 | | Child 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________4 5___________6 7 8 9___________10 11__________12 13 14
| |________________________________| |________________________________| |
|__________________________________________________________________________|
что заставило меня задуматься, почему бы просто не использовать более простой вид:
__________________________________________________________________________
| Root 1 |
| ________________________________ _______________________________ |
| | Child 1.1 | | Child 1.2 | |
| | ___________ ___________ | | ___________ ___________ | |
| | | C 1.1.1 | | C 1.1.2 | | | | C 1.2.1 | | C 1.2.2 | | |
1 2 3___________| 4___________| | 5 6___________| 7___________| | |
| |________________________________| |_______________________________| |
|_________________________________________________________________________|
который не имеет дополнительного номера для каждой конечной точки.
Но затем, когда я на самом деле попытался реализовать это, я заметил, что было сложно/невозможно реализовать такие запросы на обновление, если у меня не было родительской информации, используемой Konchog. Проблема в том, что было трудно/невозможно различить родителя и родителя в одном случае, когда дерево перемещалось, и мне это было нужно, чтобы решить, буду ли я уменьшать правую сторону или нет, закрывая зазор .
Левый/размер против левого/правого: вы можете хранить его в базе данных любым способом, но я думаю, что левый/правый могут быть более эффективными, поскольку вы можете индексировать БД с помощью многоколоночного индекса (левый, правый), который затем можно использовать для ускорения запросы предков, которые имеют тип:
left < curLeft AND right > curLeft
Протестировано на Ubuntu 22.04, PostgreSQL 14.5, SQLite 3.34.0.
Чтобы расширить SQL-решение Билла, вы можете сделать то же самое, используя плоский массив. Более того, если все ваши строки имеют одинаковую длину и ваше максимальное число дочерних элементов известно (скажем, в двоичном дереве), вы можете сделать это, используя одну строку (массив символов). Если у вас произвольное количество детей, это немного усложняет... Я должен был бы проверить свои старые записи, чтобы посмотреть, что можно сделать.
Затем, пожертвовав небольшим количеством памяти, особенно если ваше дерево редкое и / или несбалансированное, вы можете, с небольшим количеством математической индексации, получить доступ ко всем строкам случайным образом, сохраняя ваше дерево, сначала ширину в массиве, например (для двоичного файла) дерево)
String[] nodeArray = [L0root, L1child1, L1child2, L2Child1, L2Child2, L2Child3, L2Child4] ...
Вы знаете свою длину строки, вы знаете это
Я сейчас на работе, поэтому не могу тратить на это много времени, но с интересом могу взять немного кода для этого.
Мы используем это для поиска в бинарных деревьях, состоящих из кодонов ДНК, процесс строит дерево, затем мы сплющиваем его для поиска шаблонов текста, и когда мы его найдем, хотя по индексу математики (наоборот) мы получаем узел обратно... очень Быстро и эффективно, хотя в нашем дереве редко были пустые узлы, но мы могли быстро найти гигабайты данных.
Если элементы расположены в древовидном порядке, как показано в вашем примере, вы можете использовать что-то вроде следующего примера Python:
delimiter = '.'
stack = []
for item in items:
while stack and not item.startswith(stack[-1]+delimiter):
print "</div>"
stack.pop()
print "<div>"
print item
stack.append(item)
То, что это делает, поддерживает стек, представляющий текущую позицию в дереве. Для каждого элемента в таблице он выталкивает элементы стека (закрывая соответствующие элементы div) до тех пор, пока не найдет родителя текущего элемента. Затем он выводит начало этого узла и помещает его в стек.
Если вы хотите вывести дерево, используя отступы, а не вложенные элементы, вы можете просто пропустить операторы печати, чтобы напечатать div, и вывести число пробелов, равное некоторому кратному размеру стека, перед каждым элементом. Например, в Python:
print " " * len(stack)
Вы также можете легко использовать этот метод для создания набора вложенных списков или словарей.
Изменить: я вижу из вашего пояснения, что имена не были предназначены для пути узлов. Это предполагает альтернативный подход:
idx = {}
idx[0] = []
for node in results:
child_list = []
idx[node.Id] = child_list
idx[node.ParentId].append((node, child_list))
Это создает дерево массивов кортежей (!). idx[0] представляет корень (и) дерева. Каждый элемент в массиве представляет собой 2-кортеж, состоящий из самого узла и списка всех его дочерних элементов. После создания вы можете удерживать idx [0] и отбрасывать idx, если только вы не хотите обращаться к узлам по их ID.
Если могут быть созданы вложенные хеш-карты или массивы, то я могу просто пойти вниз по таблице с самого начала и добавить каждый элемент во вложенный массив. Я должен проследить каждую строку до корневого узла, чтобы узнать, в какой уровень вложенного массива вставлять. Я могу использовать напоминание, чтобы мне не приходилось искать одного и того же родителя снова и снова.
Редактировать: я бы сначала прочитал всю таблицу в массив, так что он не будет повторно запрашивать БД. Конечно, это не будет практичным, если ваш стол очень большой.
После того, как структура построена, я должен сначала пройти через глубину и распечатать HTML.
Нет лучшего фундаментального способа хранения этой информации с использованием одной таблицы (хотя я могу ошибаться;), и я бы хотел найти лучшее решение). Однако, если вы создадите схему для использования динамически создаваемых таблиц БД, то вы откроете для себя целый новый мир, жертвуя простотой и риском адского SQL;).
Подумайте об использовании инструментов nosql, таких как neo4j, для иерархических структур. например, сетевое приложение, такое как linkedin, использует couchbase (другое решение nosql)
Но используйте nosql только для запросов уровня витрины данных, а не для хранения / поддержки транзакций