Какие типы данных для древовидных структур поддерживаются в PostgreSQL

Что проверяют

Знаете ли вы, что отдельного «типа дерева» в ядре PostgreSQL нет, и умеете ли выбрать модель хранения под нагрузку. Следом обычно просят написать запрос «все потомки узла» и спрашивают, как вы соберёте дерево в Go.

Как отвечать

Честный ответ: специальный тип для деревьев один, это расширение ltree, остальное способы моделирования на обычных типах.

• ltree: расширение из поставки PostgreSQL, включается через CREATE EXTENSION ltree. Хранит путь меток вида catalog.electronics.phones, операторы @> и <@ проверяют предка и потомка, ~ сопоставляет с шаблоном lquery. Под эти операторы нужен GiST-индекс;
• список смежности: колонка parent_id и WITH RECURSIVE. Проще всего в записи и переносе узлов, чтение поддерева стоит рекурсии. С PostgreSQL 14 есть SEARCH DEPTH FIRST для порядка обхода и CYCLE для защиты от циклов;
• путь на массиве: bigint[] с идентификаторами предков, GIN-индекс и поиск потомков через @>;
• nested sets: пары lft и rgt, быстрые выборки поддерева, но вставка сдвигает границы в среднем у половины таблицы;
• closure table: отдельная таблица пар «предок, потомок, глубина», быстрое чтение любых срезов ценой объёма;
• jsonb: когда дерево читается и пишется целиком, например конфиг меню, а не когда нужно искать и двигать отдельные узлы.

В Go поддерево достают одним рекурсивным запросом плоским списком, а дерево собирают в памяти за один проход через map[int64][]*Node по parent_id. Значение ltree проще всего читать строкой, приводя в запросе path::text.

Где спотыкаются

Называют hstore и геометрический тип path типами для деревьев. hstore это плоские пары ключ-значение, а path в PostgreSQL это ломаная из точек на плоскости, к иерархиям он отношения не имеет.

Обходят дерево из Go циклом запросов: корень, потом дети, потом дети детей. Это N+1 по уровням, и один WITH RECURSIVE заменяет десятки походов в базу.

Забывают про перенос узла. В ltree и в пути на массиве перенос ветки означает обновить пути всех потомков, и это надо учесть, если дерево часто меняется.