Как реализовать быструю выборку по данным привязанным к узлу дерева?

Question

[nApoBo3]

Есть дерево. У него достаточно плоская структура, на данный момент уровень вложенности от корня составляет 4 и думаю вряд ли будет расширятся далее 6, да и 6 мало вероятно.
На каждом уровне у узла от 0 до 20 потомков, в среднем не более 5. Всего около 500 узлов.
У каждого узла имеется int идентификатор.
К каждому узлу привязываются документы.
Необходимо в свойства документа записать поле которое позволит по идентификатору узла выбрать документы относящиеся к этому узлу и всем его дочерним узлам.
По этому полю должен быть быстрый поиск с использованиеv индексов, поскольку документов достаточно много, это конечно не bigata, но речь идет о миллионах документах и быстром поиске.

Есть ли готовое решение для подобной задачи на postgres? Сейчас смотрю в направлении ltree и полей для хранения ip адресов( структура очень похожа на ip адреса и подсети ).

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

Comments

[Модератор]

Не надо ставить как можно больше тэгов. Лучше оставить один, но конкретный, с которым проблема.
См.п.3.1 Регламента.

Answer 1

[Rsa97]

Переходите в дереве от Adjacency LIst к Nested Set или Materialized Path.
И тот и другой вариант позволяют быстро выбрать все дочерние узлы дерева на полную глубину.

Comments

[nApoBo3]

Вы не могли бы несколько развернуть ваш ответ? Где именно переходить к nested set и materialized path?
Сейчас это выглядит так
У документа есть nodeId.
getDocumets( params..., nodeid )
Метод лезет в базу по params выбирает подходящие документы
Параллельно лезет в базу узлов выбирает потомков.
Дальше фильтрует полученные документы по потомкам и отдает.

Как итог:
1 Нужно лезть в базу узлов, этого бы хотелось избежать
2 Из базы документов на бэкенд иногда приходится передавать документов во много раз( от 10 до 1000 ) больше чем необходимо, а это нагрузка и на базу документов и на сеть, на сам бэк при этом нагрузка не слишком большая.

[Rsa97]

nApoBo3, Естественно, в дереве.
И Nested Set, и Materialized Path позволяют выбрать узел со всеми потомками одним условием. Вот для Nested Set:

SELECT d.*
  FROM nodes AS n
  JOIN nodes AS c ON c.id >= n.left AND c.id <= n.right
  JOIN documents AS d ON d.nodeId = c.id
  WHERE n.id = :nodeId
    AND условие по параметрам

Для Materilized Path можно в документе хранить кроме nodeId поле nodePath, тогда к таблице узлов можно не обращаться

SELECT *
  FROM documents
  WHERE nodepPath LIKE CONCAT(:nodePath, '%')
    AND условие по документам

Хотя, если узлов мало, то и Adjacency List можно использовать с рекурсивным CTE.