PostgreSQL - древовидная организация

Question

Я работаю над проектом, для которого требуется дерево категорий, организованное как id, parent, title title. Каковы наилучшие способы получения категории и ее подкатегорий (и полного дерева, если корневые категории имеют parent = 0) в Postgres? Я ищу чистое решение для базы данных, но если есть способ для Ruby и PHP - это тоже будет здорово.

Основная цель - это скорость выбора предложений, потому что данные в этой таблице не важны для скорости обновления / вставки / удаления.

UPD: будет также поиск пути, я имею в виду путь от текущей вершины (категории) до корневой категории.

Answer 1

Взгляните на "ltree" модуль contrib.

Answer 2

Я поигрался с ltree , который является модулем поста PostgreSQL, чтобы проверить, подходит ли он для многопоточных комментариев. Вы создаете столбец в своей таблице, в котором хранится путь, и создаете для него индекс ltree. Затем вы можете выполнять такие запросы:

 ltreetest=# select path from test where path ~ '*.Astronomy.*';
                     path                      
-----------------------------------------------
 Top.Science.Astronomy
 Top.Science.Astronomy.Astrophysics
 Top.Science.Astronomy.Cosmology
 Top.Collections.Pictures.Astronomy
 Top.Collections.Pictures.Astronomy.Stars
 Top.Collections.Pictures.Astronomy.Galaxies
 Top.Collections.Pictures.Astronomy.Astronauts

Я недостаточно поиграл с ним, чтобы определить, насколько хорошо он работает с такими вещами, как вставки, обновления или удаления. Я предполагаю, что удаление будет выглядеть так:

DELETE FROM test WHERE path ~ '*.Astronomy.*';

Я думаю, что многопоточная таблица комментариев может выглядеть так:

CREATE SEQUENCE comment_id_seq
  INCREMENT 1
  MINVALUE 1
  MAXVALUE 9223372036854775807
  START 78616
  CACHE 1;

CREATE TABLE comments (
comment_id int PRIMARY KEY,
path ltree,
comment text
);

CREATE INDEX comments_path_idx ON comments USING gist (path);

Вставка будет выглядеть грубо (и непроверенно):

CREATE FUNCTION busted_add_comment(text the_comment, int parent_comment_id) RETURNS void AS
$BODY$
DECLARE
    INT _new_comment_id; -- our new comment_id
    TEXT _parent_path;   -- the parent path
BEGIN
    _new_comment_id := nextval('comment_id_seq'::regclass);
    SELECT path INTO _parent_path FROM comments WHERE comment_id = parent_comment_id;

    -- this is probably busted SQL, but you get the idea... this comment's path looks like
    --   the.parent.path.US
    --
    -- eg (if parent_comment_id was 5 and our new comment_id is 43):
    --  3.5.43
    INSERT INTO comments (comment_id, comment, path) VALUES (_new_comment_id, the_comment, CONCAT(_parent_path, '.', _new_comment_id));

END;
$BODY$
LANGUAGE 'plpgsql' VOLATILE;

Или что-то в этом роде. По сути, путь - это просто иерархия, состоящая из всех первичных ключей.

Answer 3

получение категории и ее подкатегорий

Если у вас ограниченная глубина подпунктов, вы можете сделать это с помощью самостоятельного объединения, например. два уровня глубины:

SELECT *
FROM categories AS child
LEFT JOIN categories AS parent ON parent.id=child.parent
LEFT JOIN categories AS grandparent ON grandparent.id=parent.parent
WHERE child.id=(id) OR parent.id=(id) OR grandparent.id=(id);

Вы не можете сделать это для иерархии произвольной глубины, используя стандартный SQL по схеме типа «parent-id-foreign-key».

Некоторые СУБД предоставляют нестандартные иерархические инструменты, которые допускают что-то подобное различными способами, но если вы хотите придерживаться кросс-СУБД-совместимого кода, вам нужно перенастроить свою схему на одну из лучших моделей представления иерархий. , Два популярных из них:

• Вложенный набор . Сохраняет линейный порядок, представляющий поиск дерева по глубине в двух столбцах целевой таблицы (один из которых у вас уже будет, если ваша цель имеет явный порядок).

• Отношение смежности . Сохраняет каждую пару предок / потомок в отдельной таблице соединений.

У каждого подхода есть свои преимущества и недостатки, а также многочисленные варианты (например, разреженная нумерация вложенных множеств, «расстояние» в AR), которые могут влиять на то, насколько дорогостоящими являются различные типы операций добавления / удаления / перемещения позиции. Лично я склоняюсь к упрощенной модели вложенных множеств по умолчанию, поскольку она содержит меньше избыточности, чем AR.

Answer 4

Я полюбил модель вложенного множества для такой ситуации. Обновления и вставки могут быть немного хитрыми, но выбор обычно очень лаконичен и быстр. Производительность может быть даже лучше, если вы добавите фактическую ссылку на родителя узла (в некоторых случаях это исключит объединение. Также включает естественную сортировку дочерних узлов.

• Деревья в SQL

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

select name
from nestedSet c inner join nestedSet p ON c.lft BETWEEN p.lft AND p.rgt
where p.id = 1
order by lft

Несколько удачно расположенных пунктов group by также дадут вам небольшую статистику о вашем дереве.

Answer 5

Просто добавим, что статья Управление иерархическими данными в MySQL содержит хорошее объяснение модели списка смежности и моделей вложенных множеств, включая примеры SQL для манипулирования деревом и тому подобное.

Иерархии в СУБД - сложная тема. У меня есть Деревья и иерархии Джо Селко в SQL для умных в моем списке желаний, чтобы когда-нибудь купить и прочитать.

Answer 6

Существует плагин acts_as_tree для Rails, который хорошо работал для меня в прошлом. У меня было довольно маленькое дерево - около 15 000 узлов.