Иерархии в PostgreSQL: сравниваем четыре модели хранения

Сначала определите, что будет меняться чаще

Для дерева категорий, подразделений или папок в PostgreSQL 16 нет одной лучшей схемы. Список родителей проще обновлять, но для обхода дерева нужны рекурсивные запросы. Путь ускоряет поиск предков и потомков ценой обновления всего поддерева. Таблица замыканий делает чтение связей быстрым, но усложняет запись. Вложенные множества удобны для чтения диапазонов, зато добавление и перемещение узлов часто обходятся дорого.

Выбирать нужно не по числу таблиц, а по типичным операциям: вы чаще добавляете и перемещаете узлы или читаете целые ветки? Ниже — четыре модели и критерии выбора для PostgreSQL 16. Примеры схем предполагают, что у узла есть числовой идентификатор и он принадлежит не более чем одному родителю.

1. Список родителей: простой старт и гибкие запросы

В узле хранится ссылка на родителя. Для корневого узла значение parent_id равно NULL. Это естественная модель для дерева, где узлы часто меняют место, а запросы обычно затрагивают один уровень или отдельные ветки.

CREATE TABLE category (
    id bigint PRIMARY KEY,
    parent_id bigint REFERENCES category(id),
    name text NOT NULL
);

CREATE INDEX category_parent_id_idx ON category(parent_id);

Список непосредственных дочерних узлов получается обычным фильтром по parent_id. Чтобы получить всех потомков, в PostgreSQL 16 используют рекурсивный CTE:

WITH RECURSIVE subtree(id, parent_id, depth, visited) AS (
    SELECT id, parent_id, 0, ARRAY[id]
    FROM category
    WHERE id = $1

    UNION ALL

    SELECT child.id, child.parent_id, subtree.depth + 1,
           subtree.visited || child.id
    FROM category AS child
    JOIN subtree ON child.parent_id = subtree.id
    WHERE NOT child.id = ANY(subtree.visited)
)
SELECT id, parent_id, depth
FROM subtree
WHERE depth > 0
ORDER BY depth, id;

Защита через visited не даёт запросу зациклиться, если в данных случайно появилась циклическая ссылка. Но это не замена проверке целостности при записи: в обычной схеме внешний ключ запрещает ссылку на отсутствующий узел, а не цикл. Перемещение узла в собственного потомка нужно отдельно запрещать в логике приложения или транзакции.

2. Путь в строке или ltree: быстро читать ветки

Если приложение часто спрашивает «покажи всех потомков этого узла», путь позволяет искать поддерево по префиксу или с помощью операторов расширения ltree. В PostgreSQL 16 расширение можно включить командой CREATE EXTENSION ltree — при этом оно должно быть доступно в установленной сборке сервера.

CREATE EXTENSION ltree;

CREATE TABLE category_path (
    id bigint PRIMARY KEY,
    path ltree NOT NULL
);

CREATE INDEX category_path_gist_idx
    ON category_path USING gist (path);

Каждому узлу нужен путь из меток, например n1.n7.n42. Метки стоит строить из стабильных идентификаторов, а не названий: название меняется, идентификатор обычно нет. Оператор @> проверяет, является ли путь слева предком пути справа. Поэтому поиск потомков узла с путём n1.n7 можно записать так:

SELECT id, path
FROM category_path
WHERE path <@ 'n1.n7'::ltree;

Индекс GiST помогает таким запросам, но модель переносит цену с чтения на изменение. При перемещении узла придётся исправить пути у него и всех потомков; обновление затронет много строк и соответствующих индексов. Хранить вместе parent_id и путь можно, но тогда приложение должно поддерживать их согласованность.

3. Таблица замыканий: предки и потомки отдельными строками

Таблица замыканий хранит пары «предок — потомок» и расстояние между ними. В неё добавляют и строку связи узла с самим собой с расстоянием ноль. Прямое родительство остаётся в основной таблице, а таблица замыканий обслуживает запросы по всей глубине.

CREATE TABLE category_closure (
    ancestor_id bigint NOT NULL REFERENCES category(id),
    descendant_id bigint NOT NULL REFERENCES category(id),
    depth integer NOT NULL CHECK (depth >= 0),
    PRIMARY KEY (ancestor_id, descendant_id)
);

CREATE INDEX category_closure_descendant_idx
    ON category_closure (descendant_id, ancestor_id);

Потомков можно получить одним соединением без рекурсивного обхода: выбирайте строки, где искомый узел — предок, а depth > 0. Цена — больше записей и более сложное обслуживание. При добавлении узла нужно внести связь с самим собой и связи с предками его родителя. При перемещении — удалить старые связи с внешними предками и построить новые. Эти операции важно выполнять согласованно в транзакции.

4. Вложенные множества: для редких изменений и чтения диапазонов

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

Обратная сторона — цена сдвига границ. Добавление узла или перенос ветки может потребовать обновить значения у множества других узлов. Это создаёт конкуренцию за строки и усложняет запись, особенно если дерево активно меняется. Модель не запрещает циклы сама по себе: корректность интервалов тоже нужно поддерживать при каждой операции.

Сравнение: где платите за скорость

Сравнение описывает форму работы, а не гарантированную скорость. Результат зависит от размера дерева, глубины, распределения веток, индексов и доли записей. На реальных данных измеряйте запросы через EXPLAIN (ANALYZE, BUFFERS): сравните время, число прочитанных страниц и объём работы на переносе ветки.

Модель хранения определяет не только скорость SELECT. Она задаёт, сколько строк придётся изменить, чтобы дерево оставалось правильным.

Когда какую модель выбирать

• Начните со списка родителей, если дерево меняют регулярно, а запросы в основном идут к детям или отдельным веткам. Это понятная база, которую проще проверять и поддерживать.
• Выбирайте ltree, если частые запросы ищут целую ветку, а перемещение узлов — редкая операция. Заранее решите, как обновлять пути атомарно.
• Берите таблицу замыканий, если приложению нужны быстрые запросы по предкам и потомкам на разных уровнях, и команда готова тестировать транзакции записи.
• Рассматривайте вложенные множества для почти неизменяемой структуры, когда важнее читать большие диапазоны, чем удобно редактировать дерево.

Не выбирайте модель только потому, что у дерева «может быть много уровней». Для списка родителей стоимость обхода зависит от запроса и плана выполнения; для ltree и замыканий платой становятся обновления и дополнительные данные. Сначала соберите профиль операций: частота чтения потомков, поиск предков, перемещения, глубина и число узлов.

Что ломается и что проверить до запуска

Самый неприятный дефект — не медленный запрос, а рассинхронизация структуры. В таблице родителей узел может стать собственным потомком. В ltree путь может не соответствовать родителю. В замыканиях можно забыть часть связей. Во вложенных множествах пересекающиеся или неверно сдвинутые границы портят выборки.

До запуска проверьте четыре сценария: создание корня, добавление ребёнка, перенос ветки и удаление узла. Для каждого тестируйте результат чтения потомков и предков, включая пустое дерево и узел без детей. Операцию переноса выполняйте в транзакции и отдельно проверяйте, что она не создаёт цикл. Если есть несколько процессов записи, подумайте, как они не смогут одновременно изменить одну ветку в противоречащих друг другу направлениях.

Термин: транзитивное замыкание — набор всех пар «предок — потомок», включая не только прямые связи, но и связи через любое число промежуточных узлов. Именно эти пары хранят в таблице замыканий.

Что делать дальше

Возьмите типичный запрос из приложения и один сценарий переноса ветки. Реализуйте их на модели списка родителей, измерьте чтение и запись на копии реальных данных, затем сравните с кандидатом, который должен ускорить ваш узкий участок. Следите не только за временем запроса, но и за числом обновлённых строк, блокировками и ростом индексов. Если выигрыша в измерениях нет, простая модель обычно дешевле в сопровождении.