Выведите все подкатегории раздела каталога на любой глубине вложенности с помощью рекурсивного запроса
Проверила команда Сопровод · Обновлено
Короткий ответ
Напишите WITH RECURSIVE из двух частей. Якорь выбирает сам раздел, рекурсивный шаг присоединяет к найденным строкам их детей по parent_id, пока новых строк не останется. По дороге копите уровень и путь в массиве, в конце сортируйте по этому массиву. Добавьте массив пройденных id: проверка по нему остановит рекурсию, если в данных есть цикл.
Почему этот вопрос задают
Деревья хранят во многих базах: категории, оргструктуру, комментарии. Senior здесь показывает, что знает устройство рекурсивного запроса и заранее думает о порядке строк и плохих данных.
Условие задачи
В магазине электроники дерево каталога лежит в таблице categories(id, parent_id, name), у разделов верхнего уровня parent_id пустой. Выведите раздел «Компьютеры» и все его подкатегории на любой глубине: имя, уровень (у самого раздела 1) и путь от верха дерева через знак «>». За каждой категорией идут ее потомки, соседние категории — по алфавиту.
Как подойти к решению
- Опишите якорь: выберите строку самого раздела и задайте ей уровень 1
- Присоедините в рекурсивной части детей к уже найденным строкам по
parent_id - Копите по дороге уровень, путь из имен и массив пройденных
id - Отсекайте строку, чей
idуже есть в массиве пройденных, иначе цикл в данных сделает рекурсию бесконечной - Отсортируйте результат по массиву пути, чтобы потомки шли сразу за родителем
Решение
Якорь дает одну строку, каждый шаг добавляет следующий уровень, и рекурсия кончается, когда новых детей нет. Массив пути сравнивается поэлементно, поэтому ветка «Комплектующие» целиком идет раньше ветки «Ноутбуки». Условие c.id <> ALL (t.ids) на чистом дереве ничего не меняет и защищает от цикла.
WITH RECURSIVE tree AS (
SELECT id, name, 1 AS level, ARRAY[id] AS ids, ARRAY[name] AS path
FROM categories
WHERE id = 1
UNION ALL
SELECT c.id, c.name, t.level + 1, t.ids || c.id, t.path || c.name
FROM categories c
JOIN tree t ON c.parent_id = t.id
WHERE c.id <> ALL (t.ids)
)
SELECT name, level, array_to_string(path, ' > ') AS full_path
FROM tree
ORDER BY path;name | level | full_path ------------------+-------+------------------------------------------ Компьютеры | 1 | Компьютеры Комплектующие | 2 | Компьютеры > Комплектующие Видеокарты | 3 | Компьютеры > Комплектующие > Видеокарты Процессоры | 3 | Компьютеры > Комплектующие > Процессоры Ноутбуки | 2 | Компьютеры > Ноутбуки Игровые ноутбуки | 3 | Компьютеры > Ноутбуки > Игровые ноутбуки Ультрабуки | 3 | Компьютеры > Ноутбуки > Ультрабуки (7 rows)
Что спросят следом
Как сделать то же встроенными средствами PostgreSQL 14 и новее?
Как найти путь от категории вверх до корня?
В каталоге миллион категорий, и дерево читают на каждой странице. Что сделаете?
Доступно по подписке
Ответы на эти вопросы
Частые ошибки
«Порядок строк и так будет правильный, рекурсия идет по дереву»
Без
ORDER BYпорядок не гарантирован. На деле PostgreSQL выдает строки по уровням, в ширину. Соберите путь в массив и сортируйте по нему«Напишу
UNIONвместоUNION ALL, и от цикла это защитит»UNIONотбрасывает только полностью одинаковые строки. Когда в строке копится уровень или путь, при цикле каждая строка новая, и запрос не остановится. Проверяйте пройденныеidявно«Отсортирую по
level, потом по имени»Так строки встанут по уровням, и потомки оторвутся от родителей. Порядок обхода дает только сортировка по полному пути
«Склею путь в строку и отсортирую по тексту»
Сортировка текста зависит от правил сравнения базы: в части локалей пробелы и знаки при первом сравнении не учитываются. Массив сравнивается поэлементно, и ветки не перемешаются
Сигналы для интервьюера
Сильный ответ
Сам считает, сколько шагов сделает рекурсия на этих данных, и сверяет число строк в ответе с размером ветки
Тревожный сигнал
Собирает дерево тремя LEFT JOIN на фиксированную глубину и переходит к рекурсии только после подсказки
Красный флаг
Готов вытаскивать уровни по одному запросу в цикле приложения и не видит, сколько обращений к базе это даст
Как еще могут спросить
- Как обойти древовидную структуру в SQL с помощью
WITH RECURSIVE? - Выведите всех потомков узла дерева, которое хранится через
parent_id - Как работает рекурсивный CTE и когда он останавливается?
- Как получить всю иерархию категорий одним запросом?











