Базовая схема — adjacency list с parent_id и сохранённой глубиной depth. Индекс по depth позволяет быстро выбирать один уровень, но перенос поддерева требует обновить глубины потомков.
Стратегия хранения узлов дерева по уровням в базе данных
Базовая схема — adjacency list с parent_id и сохранённой глубиной depth. Индекс по depth позволяет быстро выбирать один уровень, но перенос поддерева требует обновить глубины потомков.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Имеется иерархическая структура элементов, представленная в виде дерева: A /
B C / \ /
D E F G
H Необходимо разработать схему представления таких элементов в реляционной СУБД и привести пример определения таблицы. При этом следует учесть требование возможности выборки всех записей, принадлежащих одному уровню иерархии (например, уровень 1 — элементы B и C).
Ответ
Базовая схема — adjacency list с parent_id и сохранённой глубиной depth. Индекс по depth позволяет быстро выбирать один уровень, но перенос поддерева требует обновить глубины потомков.
CREATE TABLE nodes (
id BIGINT PRIMARY KEY,
name TEXT NOT NULL,
parent_id BIGINT REFERENCES nodes(id),
depth INTEGER NOT NULL CHECK (depth >= 0),
CHECK (parent_id IS NULL OR parent_id <> id)
);
CREATE INDEX nodes_depth_idx ON nodes(depth);
SELECT * FROM nodes WHERE depth = 1;
Корень имеет depth = 0, его дети — 1. Согласованность depth с родителем и отсутствие длинных циклов обеспечиваются логикой изменения дерева. Без сохранения depth уровень можно вычислять рекурсивным запросом. Искажённая диаграмма не позволяет уверенно восстановить все связи конкретного примера.