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

Question

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

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

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

Answer 1

получить категорию и ее подкатегории

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

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 над «родитель-Ид внешнего ключа» типа схемы.

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

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

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

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

Answer 2

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

Answer 3

Я играл с ltree, который является модулем Contributor 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); 

Вкладыш бы грубо (и непроверенные-LY) выглядит следующим образом:

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 4

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

Answer 5

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

• Trees in 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 6

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

Иерархии в СУБД - сложная тема. У меня есть Joe Celko’s Trees and Hierarchies in SQL for Smarties в моем списке желаний, чтобы купить и прочитать.