Глубина дерева в SQL - PullRequest
       29

Глубина дерева в SQL

4 голосов
/ 26 августа 2009

Предполагая, что есть таблица с именем tree_node, у которой есть первичный ключ с именем id и столбец, который может иметь значение NULL, с именем parent_id, и в таблице есть древовидная структура (или лес), как можно вычислить глубину эффективного узла в дереве / лесу в SQL?

Ответы [ 3 ]

6 голосов
/ 26 августа 2009

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

WITH RECURSIVE node_ancestors(node_id, parent_id) AS (
        SELECT id, id FROM tree_node WHERE id IN (1, 2, 3)
    UNION ALL
        SELECT na.node_id, tree_node.parent_id
            FROM node_ancestors AS na, tree_node
            WHERE tree_node.id = na.parent_id AND tree_node.parent_id IS NOT NULL
)
SELECT node_id, COUNT(parent_id) AS depth FROM node_ancestors GROUP BY node_id;

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

2 голосов
/ 26 августа 2009

Обычный способ обработки деревьев, в дополнение к обычным столбцам KEY и PARENT, у вас также есть столбцы типа PATH, которые содержат строковое значение, содержащее ключи узлов, составляющих путь, от корень, вплоть до самого узла, ограниченный символом, который не может быть частью самого ключа.

Позвольте привести пример:

KEY        PARENT         PATH
1          -              *1*
  2        1              *1*2*
  3        1              *1*3*
    4      3              *1*3*4*
  5        1              *1*5*
    6      5              *1*5*6*

Это в основном используется с деревьями, которые не слишком сильно меняются, например, иерархии отделов или тому подобное.

Я знаю, что такая строка не совсем соответствует теориям нормализации, поскольку кажется, что она делает недействительными несколько правил (многоключевые, многозначные поля и т. Д.), Но она весьма полезна во многих сценариях, включая Вы просите.

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

Вот SQL, чтобы дать вам приведенный выше список узлов с их глубиной:

select KEY, PARENT, LEN(PATH)-LEN(REPLACE(PATH, '*', ''))-1 as DEPTH
from NODES

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

1 голос
/ 26 августа 2009

Если глубина не ограничена, то проблема рекурсивная, и на самом деле не существует простого и эффективного решения. (Могут быть простые и эффективные решения.) Если у вас есть контроль над схемой, и вам необходимо регулярно получать доступ к данным такого рода, то вы можете реорганизовать таблицу как вложенный набор с левыми и правыми границами содержания для каждого элемента. Это позволит вам вычислить глубину узла в одном запросе с элементарными условиями, примерно:

select count(*) from tree_node
    where left < myLeft
    and right > myRight
...