Nested Sets. Триггеры в PostgreSQL

Задача

Управление древовидными структурами в PostgreSQL предполагает компромисс: структуры Nested Sets удобны для выборок, но сложны в управлении, тогда как id→parent_id удобны для управления, но требуют рекурсивных запросов при выборках.

Два подхода реализации:

Использование хранимых процедур (отклонён как неудобный).
Использование триггеров для максимальной прозрачности работы.

Таблица

CREATE TABLE ns_tree (
    id                      SERIAL,
    left_key                INTEGER       NOT NULL,
    right_key               INTEGER       NOT NULL,
    level                   INTEGER       NOT NULL DEFAULT 0,
    tree                    INTEGER       NOT NULL,
    parent_id               INTEGER       NOT NULL DEFAULT 0,
    _trigger_lock_update    BOOLEAN       NOT NULL DEFAULT FALSE,
    _trigger_for_delete     BOOLEAN       NOT NULL DEFAULT FALSE,
    field_1                 ...,
    PRIMARY KEY (id)
);

Вспомогательная функция блокировки

CREATE OR REPLACE FUNCTION lock_ns_tree(integer)
    RETURNS boolean AS
$BODY$
DECLARE tree_id ALIAS FOR $1;
    _id INTEGER;
BEGIN
    SELECT id
        INTO _id
        FROM ns_tree
        WHERE tree = tree_id FOR UPDATE;
    RETURN TRUE;
END;
$BODY$
  LANGUAGE 'plpgsql' VOLATILE;

Создание записи

Триггер поддерживает три варианта добавления узла: по parent_id, по left_key, в конец дерева.

Триггер BEFORE INSERT выполняет:

Блокировку дерева через lock_ns_tree(NEW.tree).
Определение left_key и level на основе parent_id или left_key.
Сдвиг существующих ключей: UPDATE ns_tree SET left_key = left_key + 2, right_key = right_key + 2.

Полный код триггера — на оригинальной странице.

Изменение записи

Триггер BEFORE UPDATE обрабатывает перемещение узлов:

Если parent_id или left_key не изменились — выходит без изменений.
Вычисляет новое расположение узла.
Обновляет ключи затронутых узлов с учётом смещения.

Удаление записи

Два варианта триггеров AFTER DELETE:

Вариант 1 — с потомками: удаляет узел и всю его ветку, затем сдвигает оставшиеся ключи.

Вариант 2 — без потомков (смещение на уровень вверх): при удалении узла его потомки поднимаются на уровень родителя.

Индексы

Рекомендуемые индексы:

Композитный неуникальный: (left_key, right_key, level, tree).
Неуникальный: (parent_id).

Nested Sets. Использование триггеров в PostgreSQL