> Как определить в SQL, что узел является корневым, листом или внутренним узлом (Go)

Короткий ответ

В SQL тип узла в иерархической структуре определяется через связи с родителем и детьми. Корневой узел - тот, у которого нет родителя (parent_id IS NULL). Лист - узел без детей (отсутствуют записи, ссылающиеся на него как на родителя). Внутренний узел - имеет и родителя, и хотя бы одного ребёнка. Для проверки наличия детей используется EXISTS с подзапросом или LEFT JOIN с группировкой. В PostgreSQL удобно использовать рекурсивные CTE, но для классификации узлов достаточно простых запросов.

Подробное объяснение

В реляционных базах иерархия обычно моделируется через self-reference: таблица содержит id и parent_id, где parent_id ссылается на id того же узла. Классификация узла зависит от двух фактов: есть ли у него родитель и есть ли у него дети.

Корневой узел - parent_id IS NULL. Таких узлов может быть несколько, если дерево на самом деле лес.

Лист - узел, на который не ссылается ни одна другая запись как на родителя. Это проверяется через NOT EXISTS по подзапросу, ищущему записи с parent_id = текущий_id.

Внутренний узел - комбинация: parent_id IS NOT NULL и существует хотя бы один ребёнок.

Важный нюанс: если в таблице есть узлы с parent_id, указывающим на несуществующий id (нарушение целостности), классификация может быть некорректной. Поэтому в production обычно ставят внешний ключ FOREIGN KEY (parent_id) REFERENCES table(id).

Для больших таблиц критично иметь индекс по parent_id - без него проверка наличия детей превращается в full scan.

На практике

На практике чаще всего нужно не просто классифицировать один узел, а получить все узлы с их типом одним запросом. Оптимальный способ - один LEFT JOIN с агрегацией:

SQL
SELECT
    t.id,
    CASE
        WHEN t.parent_id IS NULL AND COUNT(c.id) = 0 THEN 'root'  -- одиночный узел
        WHEN t.parent_id IS NULL THEN 'root'
        WHEN COUNT(c.id) = 0 THEN 'leaf'
        ELSE 'internal'
    END AS node_type
FROM tree t
LEFT JOIN tree c ON c.parent_id = t.id
GROUP BY t.id, t.parent_id;

Этот запрос даёт классификацию для всех узлов за один проход. Для одиночного узла (без родителя и без детей) он попадает в root, что логично - он одновременно и корень, и лист, но по соглашению обычно считается корнем.

Если нужно только проверить конкретный узел, эффективнее использовать EXISTS:

SQL
SELECT
    CASE
        WHEN parent_id IS NULL THEN 'root'
        WHEN NOT EXISTS (SELECT 1 FROM tree c WHERE c.parent_id = t.id) THEN 'leaf'
        ELSE 'internal'
    END AS node_type
FROM tree t
WHERE t.id = ?;

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

Пример кода

Полный пример на PostgreSQL с тестовыми данными:

SQL
CREATE TABLE tree (
    id INT PRIMARY KEY,
    parent_id INT REFERENCES tree(id)
);

INSERT INTO tree VALUES
(1, NULL),  -- корень
(2, 1),     -- внутренний
(3, 1),     -- внутренний
(4, 2),     -- лист
(5, 2),     -- лист
(6, 3);     -- лист

-- Классификация всех узлов
SELECT
    t.id,
    CASE
        WHEN t.parent_id IS NULL THEN 'root'
        WHEN NOT EXISTS (SELECT 1 FROM tree c WHERE c.parent_id = t.id) THEN 'leaf'
        ELSE 'internal'
    END AS node_type
FROM tree t
ORDER BY t.id;

-- Результат:
-- id | node_type
-- 1  | root
-- 2  | internal
-- 3  | internal
-- 4  | leaf
-- 5  | leaf
-- 6  | leaf

Для Go-приложения типичный паттерн - загрузить все узлы одним запросом и классифицировать в памяти:

GO
type Node struct {
    ID       int
    ParentID *int
    Type     string
}

func classifyNodes(nodes []Node) map[int]string {
    childrenCount := make(map[int]int)
    for _, n := range nodes {
        if n.ParentID != nil {
            childrenCount[*n.ParentID]++
        }
    }

    result := make(map[int]string)
    for _, n := range nodes {
        switch {
        case n.ParentID == nil:
            result[n.ID] = "root"
        case childrenCount[n.ID] == 0:
            result[n.ID] = "leaf"
        default:
            result[n.ID] = "internal"
        }
    }
    return result
}

Как отвечать на собеседовании

Начните с определения трёх типов узлов через связи. Скажите, что корень - это parent_id IS NULL, лист - отсутствие детей, внутренний - наличие и родителя, и детей. Затем предложите два подхода: через EXISTS для одного узла и через LEFT JOIN с GROUP BY для всех узлов сразу. Упомяните про индекс на parent_id и про edge case с одиночным узлом.

Если интервьюер спрашивает про производительность, объясните, что EXISTS эффективнее COUNT(*) для проверки наличия детей, потому что останавливается на первой найденной записи. Для массовой классификации один LEFT JOIN лучше, чем N подзапросов.

В Go-контексте добавьте, что часто выгоднее выгрузить все узлы и классифицировать в памяти - это один запрос к БД и O(n) по времени.

Что проверяет интервьюер

Интервьюер оценивает:

• понимание модели self-reference в SQL
• умение формулировать условия через EXISTS и JOIN
• знание разницы между EXISTS и COUNT(*) по производительности
• внимание к edge cases (одиночный узел, несколько корней)
• способность перенести задачу на язык программирования (Go), если это backend-позиция

Для senior-уровня важно, что вы сразу думаете об индексах и сложности запроса, а не просто пишете рабочий вариант.

Типичные ошибки

• Использование COUNT(*) вместо EXISTS для проверки наличия детей - на больших таблицах это заметно медленнее.
• Забывают про индекс на parent_id - без него запрос деградирует.
• Не учитывают случай, когда parent_id ссылается на несуществующий узел - классификация будет некорректной.
• Путают лист и корень: лист - это отсутствие детей, а не отсутствие родителя.
• В Go-коде пытаются делать N запросов к БД для каждого узла вместо одного запроса и классификации в памяти.
• Не обрабатывают случай одиночного узла - он одновременно и корень, и лист, и нужно явно решить, как его классифицировать.