Adjacency List. Введение

Что это такое?

Adjacency List — один из самых простых методов хранения древовидных структур данных. Узел содержит прямую связь с родителем через два поля: id и pid. Однако наследование ограничено одним уровнем — за один шаг можно вычислить только родительский узел или детей, но не более дальних родственников.

Создание таблицы

CREATE TABLE my_tree (
    id              INTEGER         NOT NULL,
    pid             INTEGER,
    field1          TEXT,
    PRIMARY KEY (id)
);

Как использовать

Выборка данных из Adjacency List считается сложной задачей. Необходимо решить четыре основные задачи:

• Родительский узел.
• Подчинённые узлы.
• Родительская ветка.
• Подчинённые ветви.

Родительский узел и подчинённые узлы

-- Родительский узел
SELECT * FROM my_tree WHERE id = [pid];

-- Подчинённые узлы
SELECT * FROM my_tree WHERE pid = [id];

Родительская ветка

Рекурсивный запрос PostgreSQL (8.4+)

WITH RECURSIVE parents AS (
    SELECT *, ARRAY[t.id] AS exist, FALSE AS cycle
    FROM my_tree AS t
    WHERE id = [item.pid]
    UNION ALL
        SELECT t.*, exist || t.id, t.id = ANY(exist)
        FROM parents AS p, my_tree AS t
        WHERE t.id = p.pid AND NOT cycle
)
SELECT * FROM parents WHERE NOT cycle LIMIT [max_deep];

Поле exist содержит массив уже полученных ID для предотвращения бесконечной рекурсии.

Хранимая процедура PostgreSQL

CREATE OR REPLACE FUNCTION "public"."get_parents" (
    pid_in      INTEGER,
    deep        INTEGER      DEFAULT NULL
) RETURNS SETOF "public"."my_tree" AS
$body$
DECLARE
    exist_ids   INTEGER[]   := ARRAY[0];
    pid_now     INTEGER     := pid_in;
    deep_now    INTEGER     := deep;
    item        my_tree;
BEGIN
    WHILE
        pid_now IS NOT NULL AND
        pid_now > 0 AND
        pid_now <> ALL (exist_ids) AND
        (deep_now IS NULL OR deep_now > 0)
    LOOP
        SELECT * INTO item
            FROM my_tree
            WHERE id = pid_now;
        IF item.id IS NULL THEN
            EXIT;
        END IF;
        RETURN NEXT item;
        pid_now := item.pid;
        exist_ids := exist_ids || item.id;
        IF deep_now IS NOT NULL THEN
            deep_now := deep_now - 1;
        END IF;
    END LOOP;
    RETURN;
END;
$body$
LANGUAGE 'plpgsql';

Подчинённые ветви

Основное отличие — подчинённых узлов может быть более одного на каждом уровне. Простые JOIN-запросы неэффективны.

Рекурсивный запрос PostgreSQL

WITH RECURSIVE children AS (
    SELECT *,
           pid || '|' || [order_field]          AS ord,
           ARRAY[id]                            AS exist,
           FALSE                                AS cycle
    FROM my_tree
    WHERE pid = [item.id]
    UNION ALL
        SELECT t.*,
               ord || '.' || t.pid || '|' || t.[order_field],
               exist || t.id,
               t.id = ANY(exist)
        FROM children AS c,
             my_tree  AS t
        WHERE t.pid = c.id AND
              NOT cycle AND
              array_length(exist, 1) < [max_deep]
)
SELECT * FROM children WHERE NOT cycle ORDER BY ord LIMIT [limit];

Оптимизированный циклевой алгоритм

Для избежания множественных запросов используется выборка списком для каждого уровня:

SELECT children.*
FROM my_tree AS children
    JOIN my_tree AS parents
        ON parents.id = children.pid
WHERE children.pid = ANY([parents_array])
ORDER BY parents.[order_field], children.[order_field];