Совет дня №9

В комментарии к прошлой заметке прислали ссылку на Кирилла Макевнина. Он пишет о хранении деревьев в базе, и первый абзац такой:

Обычно, для хранения деревьев в базе в таблицу добавляется поле parent_id. Это дубовое решение, которое работает хорошо в небольшом количестве ситуаций. Кому-то даже может хватить, но есть запросы, на которых такая схема не работает. Например если нам понадобится извлечь ветку этого дерева. В таком случае понадобится рекурсивно выполнять запрос с parent_id где для каждого нового запроса parent_id становится id записи из предыдущего запроса. Кто-то пытается решать эту задачу прямо в коде, создавая очень не эффективное решение, кто-то с помощью возможностей базы данных, что сильно привязывает к ней, плюс, страдает интеграция с ORM.

На мой взгляд, это неверно. Подход с parent_id – не дубовое решение, а вполне даже рабочее. Просто мне кажется, на момент написания заметки Кирилл не знал о рекурсивных запросах в Postgres (под рекурсивными запросами он имеет в виду запросы в цикле из приложения, и это конечно же плохо).

Приведу минимальный пример с деревом в базе. Предположим, мы храним вот такое дерево:

┌─────────────────────────────┐
│            ┌───┐            │
│       ┌────│ A │────┐       │
│       ▼    └───┘    ▼       │
│     ┌───┐         ┌───┐     │
│   ┌─│ B │─┐     ┌─│ C │─┐   │
│   ▼ └───┘ ▼     ▼ └───┘ ▼   │
│ ┌───┐   ┌───┐ ┌───┐   ┌───┐ │
│ │ D │   │ E │ │ F │   │ G │ │
│ └───┘   └───┘ └───┘   └───┘ │
└─────────────────────────────┘

Запишем его в базу:

create table tree(
    id text primary key,
    parent_id text null
);

insert into tree values
    ('a', null),
    ('b', 'a'),
    ('c', 'a'),
    ('d', 'b'),
    ('e', 'b'),
    ('f', 'c'),
    ('g', 'c');

Напишем запрос, чтобы выгрести поддерево, зная вершину:

prepare get_branch as
with recursive sub as (
    select tree.*, 0 as level from tree where id = $1
    UNION ALL
    select tree.*, sub.level + 1
        from tree, sub
    where tree.parent_id = sub.id
)
select * from sub order by level;

Проверка:

execute get_branch('b');
┌────┬───────────┬───────┐
│ id │ parent_id │ level │
├────┼───────────┼───────┤
│ b  │ a         │     0 │
│ d  │ b         │     1 │
│ e  │ b         │     1 │
└────┴───────────┴───────┘

Второй запрос, чтобы найти путь к вершине:

prepare get_path as
with recursive sub as (
    select tree.*, 0 as level from tree where id = $1
    union all
    select tree.*, sub.level - 1
        from tree, sub
    where tree.id = sub.parent_id
)
select * from sub order by level;

Проверка:

execute get_path('f');
┌────┬───────────┬───────┐
│ id │ parent_id │ level │
├────┼───────────┼───────┤
│ a  │ <null>    │    -2 │
│ c  │ a         │    -1 │
│ f  │ c         │     0 │
└────┴───────────┴───────┘

Как видим, в обоих случаях был один запрос, циклы не понадобились, база все сделала сама. Напоминаю, что with recursive позволяет собрать вершины вглубь и вширь, находить циклы и многое другое.

Материализованные пути, о которых пишет Кирилл, тоже бывают полезны. Скажем, если у вас система файлов и папок (виртуальное файловое хранилище), то иной раз это даже лучше, чем parent_id, потому что позволяет эффективно искать по префиксу. Но есть и недостатки: если каждый узел – UUID, путь становится огромным. Кроме того, если нужно переместить поддерево, то в случае с parent_id достаточно переключить ссылку, а materialized path требует пересчета всех путей поддерева.

Ну а отказывать себе в мощных средствах только потому, что с ними не дружит ORM… это примерно как рушить свою жизнь из-за непутевого друга.