Древовидные структуры в SQL в одну таблицу06.05.2024 14:16

Инициализация

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

create table node
(
id        bigint primary key generated always as identity,
parent_id bigint,
  
foreign key (parent_id)
    references node (id)
);

Тип id и способ его генерации выбраны произвольно и на логику не влияют. Вы можете менять их на свое усмотрение.

Проблема №1: Получение всего дерева

Вопрос, а как получить все дерево из базы? Неужели придется доставать корень по id, а каждый следующий уровень получать отдельным запросом? К счастью, нет. Чтобы этого избежать, добавим идентификатор для каждого дерева (строка 5):

create table node
(
id        bigint primary key generated always as identity,
parent_id bigint,
tree_id   bigint not null,
  
foreign key (parent_id)
    references node (id)
);

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

Проблема №2: Множественные корни

В текущей схеме получается, что каждое tree_id может иметь не по одной иерархии узлов, которые будут независимы друг от друга, т.е. не иметь общего корня. Как этого избежать? Нужно сделать так, чтобы у каждого дерева был только один узел с parent_id == null. Получается, при каждом сохранении нового узла с parent_id == null нужно проверять в базе наличие такой записи? Вновь, нет. Поможет уникальный индекс. Для каждого корня (когда parent_id == null) должен быть уникальный tree_id (строка 10):

create table node
(
id        bigint primary key generated always as identity,
parent_id bigint,
tree_id   bigint not null,
  
foreign key (parent_id)
    references node (id)
);
create unique index on node(tree_id) where parent_id is null;

Такими уникальными индексами с условием можно гарантировать максимум однократное хранение некоторого значения у атрибута в рамках одной родительской сущности (в нашем случае максимум однократное значение null в parent_id в рамках tree_id). Как максимум однократное хранение превратить в ровно однократное увидим позже.

Проблема №3: Смешение деревьев

В текущей схеме узлы одного дерева могут ссылаться на узлы другого. Неужели при каждой вставке придется проверять tree_id родителя? И снова, нет. Здесь поможет составной внешний ключ. Т.е. теперь не только атрибут parent_id должен быть равен id родителя, но и tree_id дочери должен быть равен tree_id родителя. Для этого нужно, чтобы пара id и tree_id была уникальна. Фактически это уже так (id уникален в рамках таблицы), но для создания составного внешнего ключа нужно явно создать уникальный индекс на пару id, tree_id (строки 7,9,10):

create table node
(
id        bigint primary key generated always as identity,
parent_id bigint,
tree_id   bigint not null,
  
unique (id, tree_id),

foreign key (parent_id, tree_id)
    references node (id, tree_id)
);
create unique index on node (tree_id) where parent_id is null;

Проблема №4: Удаление узла

При попытке удалить узел, у которого есть дочки, получим ошибку нарушения внешнего ключа. Неужели придется искать всех дочек и удалять все сразу по массиву id? Не обязательно. Настроим внешний ключ на каскадное удаление (строка 11):

create table node
(
id        bigint primary key generated always as identity,
parent_id bigint,
tree_id   bigint not null,
  
unique (id, tree_id),

foreign key (parent_id, tree_id)
    references node (id, tree_id)
    on delete cascade
);
create unique index on node (tree_id) where parent_id is null;

Проблема №5: Циклы

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

Здесь запись ссылается сама на себя. Такой вариант решается запретом на равенство между id и parent_id в рамках одной записи (строка 7):

create table node
(
id        bigint primary key generated always as identity,
parent_id bigint,
tree_id   bigint not null,
  
constraint node_cycle_check check (parent_id != id),

unique (id, tree_id),

foreign key (parent_id, tree_id)
    references node (id, tree_id)
    on delete cascade
);
create unique index on node (tree_id) where parent_id is null;

Но ситуация может быть сложнее, например:

Неужели все-таки придется в триггере проходиться по всей цепочке родителей в поисках образовавшегося цикла? Нет, попробуем в очередной раз схитрить. Можно проверять наличие цикла прямо в рамках одной записи. Но для этого нужно дополнительно хранить массив id всех родителей до корня и проверять, содержится ли в нем текущий id. Кстати, в таком случае проверка на parent_id ≠ id уже выглядит избыточной (строки 6, 8):

create table node
(
id         bigint primary key generated always as identity,
parent_id  bigint,
tree_id    bigint not null,
parent_ids bigint[],
  
constraint node_cycle_check check (not (parent_ids @> array[id])),

unique (id, tree_id),

foreign key (parent_id, tree_id)
    references node (id, tree_id)
    on delete cascade
);
create unique index on node (tree_id) where parent_id is null;

Предвосхищаю много вопросов к такому шагу, но прошу запастись терпением, дальше будут все ответы. Оператор (@>) проверяет, содержит ли массив другой массив. Заметим, что parent_ids nullable. Атрибут будет принимать null только для корня. Можно было бы сделать его обязательным, и для корня задавать пустой массив (сейчас это будет работать). Однако, забегая вперед, скажу, что лучше остановиться на nullable.

Проблема №6: Консистентность parent_ids

Сейчас в parent_ids можно передать что угодно. Как можно гарантировать, что этот атрибут будет отражать действительное состояние базы? Все-таки придется триггером пробегаться по родителям? Нет. Здесь снова поможет расширение внешнего ключа. Нужно сделать так, чтобы атрибут задавался не произвольно, а зависел от родительской записи. Но на что его ссылать? Очевидным образом parent_ids родителя будет всегда отличаться от parent_ids дочери на один элемент. Тогда вновь схитрим и создадим еще один атрибут, который будет состоять из parent_ids и текущего id. А parent_ids будет ссылаться на него. Для этого создадим атрибут, добавим его в индекс и расширим внешний ключ (строки 7, 11, 13, 14):

create table node
(
id                 bigint primary key generated always as identity,
parent_id          bigint,
tree_id            bigint   not null,
parent_ids         bigint[],
parent_ids_with_it bigint[] not null,
  
constraint node_cycle_check check (not (parent_ids @> array [id])),

unique (id, tree_id, parent_ids_with_it),

foreign key (parent_id, tree_id, parent_ids)
    references node (id, tree_id, parent_ids_with_it)
    on delete cascade
);
create unique index on node (tree_id) where parent_id is null;

Стоит заметить, что этот атрибут не nullable, т.к. минимальный размер этого массива == 1 (для корня).

Проблема №7: Консистетность parent_ids_with_it

Теперь parent_ids_with_it задается произвольно. Что делать с ним? Может быть, тут пробежимся по родителям? Ни в коем случае. Он будет генерироваться автоматически на основе parent_ids. С «generated always as» мы чаще всего сталкиваемся при генерации id, но и здесь он будет кстати. Для этого нужно в массив parent_ids добавить текущий id (строка 7):

create table node
(
id                 bigint primary key generated always as identity,
parent_id          bigint,
tree_id            bigint   not null,
parent_ids         bigint[],
parent_ids_with_it bigint[] not null generated always as (parent_ids || id) stored,

constraint node_cycle_check check (not (parent_ids @> array [id])),

unique (id, tree_id, parent_ids_with_it),

foreign key (parent_id, tree_id, parent_ids)
    references node (id, tree_id, parent_ids_with_it)
    on delete cascade
);
create unique index on node (tree_id) where parent_id is null;

Функция генерации (parent_ids || id) добавляет в конец массива id. Таким образом, этот атрибут нельзя задать вручную, он всегда будет вычисляться автоматически. В случае, когда parent_ids == null (для корня) оператор вернет массив с одним элементом (текущим id).

Стоит обратить внимание на stored. Этот параметр определяет, будет ли атрибут сохраненным или виртуальным (т.е. высчитываться каждый раз при обращении). Для наших целей подошел бы второй вариант, чтобы не занимать лишнее дисковое пространство, однако PostgreSQL до сих пор (по 16 версию включительно) не поддерживает виртуальные атрибуты, поэтому в явном виде столбец определяется сохраненным.

Проблема №8: Корректность parent_ids в корне

Теперь при сохранении новой записи нужно задать parent_ids, который будет равен parent_ids_with_it родителя. Все это прекрасно работает для дочек. А что делать с корнем? Ведь его parent_id == null, а значит его внешний ключ не работает (не ищет референса). Таким образом можно передать в parent_ids любой массив, который затем будет отражаться на всех дочках. Т.е. нужно сделать так, чтобы для корня и parent_id, и parent_ids были null (строка 10):

create table node
(
id                 bigint primary key generated always as identity,
parent_id          bigint,
tree_id            bigint   not null,
parent_ids         bigint[],
parent_ids_with_it bigint[] not null generated always as (parent_ids || id) stored,

constraint node_cycle_check check (not (parent_ids @> array [id])),
constraint node_root_check check ((parent_ids is null) = (parent_id is null)),

unique (id, tree_id, parent_ids_with_it),

foreign key (parent_id, tree_id, parent_ids)
    references node (id, tree_id, parent_ids_with_it)
    on delete cascade
);
create unique index on node (tree_id) where parent_id is null;

Проблема №9: Актуальность parent_ids

Как поддерживать актуальными parent_ids? Например, мы переместили узел (т.е. изменили его parent_id и parent_ids). Как актуализировать этот атрибут у всех его дочерей? Здесь за нас поработает каскадное изменение. Эта настройка внешнего ключа позволяет автоматически изменять сам ключ вслед за изменением атрибута (ов), на который ключ ссылается (строка 17):

create table node
(
id                 bigint primary key generated always as identity,
parent_id          bigint,
tree_id            bigint   not null,
parent_ids         bigint[],
parent_ids_with_it bigint[] not null generated always as (parent_ids || id) stored,

constraint node_cycle_check check (not (parent_ids @> array [id])),
constraint node_root_check check ((parent_ids is null) = (parent_id is null)),

unique (id, tree_id, parent_ids_with_it),

foreign key (parent_id, tree_id, parent_ids)
    references node (id, tree_id, parent_ids_with_it)
    on delete cascade
    on update cascade

);
create unique index on node (tree_id) where parent_id is null;

Теперь достаточно изменить родителя у некоторого узла (можно даже перенести в другое дерево) и все изменения подтянутся у всех его дочерей.

Будьте внимательны! Настройку каскадного обновления можно включать только тогда, когда есть проверка на циклы. Что будет в противном случае? Допустим, есть 2 записи: корень и его дочка:

Ссылаем корень на свою дочку:

update node set parent_id = 2, parent_ids = [1,2] where id = 1;

В этот момент БД пересчитает parent_ids_with_it у корня, и вместо {1} получится {1,2,1}. Тогда у дочки будет обновлен parent_ids на {1,2,1}, а parent_ids_with_it пересчитан на {1,2,1,2}. Что заставит обновить parent_ids у корня на {1,2,1,2} и пересчитать parent_ids_with_it на {1,2,1,2,1}… Как видите, круг замыкается, и БД проделывает эти обновления бесконечно. Запрос повисает до принудительного прерывания.

Проблема №10: Ровно один корень на дерево

Вернемся к вопросу количества корней для одного дерева. Ранее удалось добиться максимум однократного хранения корня. А как все-таки гарантировать ровно один корень? Неожиданным образом это уже сделано. Дело в том, что у дерева (т.е. в рамках tree_id) может не быть корня (т.е. отсутствовать узел с parent_id==null) только в двух случаях: корень ссылается на узел другого дерева или корень ссылается на одну из своих дочек (в том числе на себя). Оба этих сценария уже невозможны в текуще схеме. Можно констатировать — если в БД есть дерево, оно имеет ровно 1 корень.

Оптимизация

Итак, перед нами готовый вариант настройки таблицы для хранения деревьев. Можно брать и пользоваться. Однако есть еще пара оптимизаций.

1. Если внимательно посмотреть на схему, можно заметить, что после появления parent_ids, parent_id сам по себе избыточен. Теперь он не несет никакой информации, которой бы не было в parent_ids, а к тому же еще раздувает индекс, внешний ключ и требует дополнительной проверки на null для корня. Но можно ли безболезненно избавиться от него? Вполне. Теперь составной индекс будет содержать 2 атрибута: tree_id и parent_ids_with_it. Можно ли гарантировать уникальность этой пары? Да. Последний элемент массива во втором атрибуте всегда будет соответствовать id текущей записи. Так как id уникален, то и последний элемент массива никогда не повторится. Значит, уникален массив. Значит, уникальна пара. После удаления parent_id схема выглядит так:

   create table node
   (
   id                 bigint primary key generated always as identity,
   tree_id            bigint   not null,
   parent_ids         bigint[],
   parent_ids_with_it bigint[] not null generated always as (parent_ids || id) stored,
   
   constraint node_cycle_check check (not (parent_ids @> array [id])),
   
   unique (tree_id, parent_ids_with_it),
   
   foreign key (tree_id, parent_ids)
       references node (tree_id, parent_ids_with_it)
       on delete cascade
       on update cascade
   
   );
   create unique index on node (tree_id) where parent_ids is null;

   Удалено:
   — атрибут parent_id
   — проверка node_root_check
   — parent_id в индексе и внешнем ключе
   — изменено условие в уникальном индексе на tree_id — теперь проверка на null происходит сразу по массиву parent_ids. 

   Возращаясь к вопросу о том, делать ли parent_ids nullable для корня или задавать пустой массив, — в данном варианте parent_ids обязан быть null для корня, а не пустым массивом, т.к. в противном случае БД будет искать родителя с пустым массивом в parent_ids_with_it.

2. Но и это еще не все. В некоторых сценариях можно еще сильнее упростить схему. Дело в том, что атрибут tree_id вводился для двух вещей: «прикреплять» дерево к другой сущности (пользователю, организации и т.п.) и запрашивать все дерево одним запросом по tree_id. В первом случае нам до сих пор необходим tree_id. Но, представим, что у нас стоит задача хранить деревья в обезличенном виде и выдавать их по id корня. Тогда можно обойтись без tree_id:

   create table node
   (
   id                 bigint primary key generated always as identity,
   parent_ids         bigint[],
   parent_ids_with_it bigint[] not null generated always as (parent_ids || id) stored,
   
   constraint node_cycle_check check (not (parent_ids @> array [id])),
   
   unique (parent_ids_with_it),
   
   foreign key (parent_ids)
       references node (parent_ids_with_it)
       on delete cascade
       on update cascade
   );

   Удалено:
   — атрибут tree_id
   — tree_id в индексе и внешнем ключе
   — уникальный индекс на tree_id

   Как в таком случае получить все дерево? Через первый элемент в массиве parent_ids_with_it. Именно он всегда равен корню своего дерева. Запрос на дерево по id корня будет выглядеть так:

   select * from node where parent_ids_with_it[1] = :id;

   Обратите внимание, что нумерация элементов начинается с 1, а не с 0.

   Самая красивая реализация. Однако есть ряд задач, в которых наличие внешнего идентификатора критично, но об этом как-нибудь потом.

Приятные бонусы:

Наличие parent_ids_with_it позволяет делать дополнительные проверки и запросы, которые были бы невозможны без него.

1. Максимальная вложенность:

   Ограничить максимальную вложенность в дереве можно проверкой размера массива parent_ids_with_it:

   constraint node_depth_check check (cardinality(parent_ids_with_it) <= 100)

2. Получение полного пути от корня до узла (вертикальный поиск):

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

   select * from node where id in (select parent_ids_with_it from node where id = :node_id);

3. Получение всех узлов на определенном уровне (горизонтальный поиск):

   Получить все узлы на определенном уровне (пусть даже с разными родителями) можно с помощью проверки размера parent_ids_with_it:

   select * from node where tree_id = :tree_id and cardinality(parent_ids_with_it) = :depth;

   select * from node where parent_ids_with_it[1] = :root_id and cardinality(parent_ids_with_it) = :depth;

4. Получение поддерева:

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

   select * from node where parent_ids_with_it @> array [:node_id];

5. Получение поддерева, ограниченного глубиной:

   А что делать, если деревья настолько велики, что запрос на поддерево уже не спасает? Нужно ограничивать запрашиваемую глубину. Для этого используется уже знакомая проверка на размер parent_ids_with_it:

   1. Для корня:

      select * from node where tree_id = :tree_id and cardinality(parent_ids_with_it) <= :depth;

      select * from node where parent_ids_with_it[1] = :root_id and cardinality(parent_ids_with_it) <= :depth;

   2. Для произвольного узла:

      select * from node where parent_ids_with_it @> array [:node_id] and cardinality(parent_ids_with_it) <= cardinality((select parent_ids_with_it from node where id = :node_id)) + :depth - 1;