Вычислить глубину в родительско-дочерней модели в MySQL

Как рассчитать глубину узла в родительско-дочерней модели в MySQL?

Мне понадобится глубина, среди прочего, для создания отступа в моем списке (закодированном с помощью PHP).


mysql parent-child hierarchy depth
person Ivar    schedule 28.07.2009    source источник
comment
Я только что видел ваш другой вопрос о перемещении узла в модели вложенных наборов, и похоже, что вам дали очень противоречивые ответы, поэтому я могу понять ваше разочарование :-) Перемещение узла в модели вложенных наборов на самом деле довольно просто (хотя в зависимости от размера вашего стола это может быть дорого). Дайте мне знать, если вы все еще заинтересованы в этом, и я могу добавить ответ с объяснением.   -  person ChssPly76    schedule 28.07.2009
comment
Ха-ха, верно, я очень расстроился из-за этого. Около недели назад я нашел решение, которое, я думаю, должно сработать, хотя еще не реализовал его. Но вложенные наборы не очень хорошо подходят для моих целей, поскольку, вероятно, будет много ежедневных обновлений от многих разных пользователей, а значит, много строк в таблице. По этой причине я попробую эту модель списка смежности, которая может безопасно перемещать узел. большой палец вверх   -  person Ivar    schedule 28.07.2009
comment
Удачи вам в реализации. Я обновил свой ответ, чтобы отразить модель списка смежности.   -  person ChssPly76    schedule 29.07.2009

Ответы (3)


arrow_upward
2
arrow_downward

Это зависит от фактической реализации вашей иерархии в базе данных. Если вы используете модель вложенных наборов (http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/) вы можете получить полный путь от родителя к дочернему элементу с помощью одного выбора.

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

SELECT n1.name AS lvl1, n2.name as lvl2, n3.name as lvl3, ..., nN.name as lvlN
  FROM nodes AS n1
  JOIN nodes AS n2 ON n2.parent_id = n1.id
  JOIN nodes AS n3 ON n3.parent_id = n2.id
  ...
  JOIN nodes AS nN ON nN.parent_id = n(N-1).id
WHERE nN.id = myChildNode;

Поскольку вы знаете, что ваш узел находится на уровне N, нет необходимости в левых соединениях, и, учитывая соответствующие индексы для id / parent_id, это должно быть достаточно быстро.
Недостатком этого подхода является то, что вам придется обновлять уровень узла. во время перемещения узла, но это должно быть достаточно просто и быстро, поскольку вы будете делать это только для самого узла и его дочерних элементов, а не для большей части таблицы, как вы сделали бы с вложенными множествами.

person ChssPly76    schedule 28.07.2009
comment
Да, я работал с вложенными наборами и знаю, как вычислить там глубину, но теперь мне нужна глубина из модели родитель-потомок (очевидно, только с идентификатором столбца и родителем), а не вложенный набор. - person Ivar; 28.07.2009
comment
Кстати, меня интересует глубина (целое число), а не путь. - person Ivar; 28.07.2009
comment
Тогда вы говорите о модели списка смежности. К сожалению, это далеко не идеально - вам понадобится N выборок, чтобы профинансировать глубину узла на N-м уровне. - person ChssPly76; 28.07.2009
comment
Итак, вы предлагаете мне добавить в таблицу еще один столбец с именем depth? Но я не вижу, чтобы вы использовали его в своем примере. И в этом случае будет ли это безопасно? Я бы предпочел быструю систему, которая не меняет несколько строк, если это возможно. :) - person Ivar; 29.07.2009
comment
В моем примере глубина равна N, и вы создаете один запрос с N соединениями. Не зная глубины заранее, вам придется выполнить N запросов, чтобы сделать то же самое. Если вам известна максимально возможная глубина всей вашей иерархии (например, она не может иметь более X уровней), другой возможный компромисс — переписать приведенный выше запрос с использованием X внешних соединений. Это не будет работать так хорошо, но вам не нужно будет поддерживать уровень узла для каждого узла. - person ChssPly76; 29.07.2009

arrow_upward
0
arrow_downward

Это может быть старый вопрос, но я просто хочу, чтобы другие знали, что я нашел решение несколько месяцев назад. Недавно я писал об этом здесь: http://en.someotherdeveloper.com/articles/adjacency-list-model-with-depth-calculation/

person Ivar    schedule 07.11.2010

arrow_upward
0
arrow_downward

Если вы хотите просто скопировать и вставить, вот мой пример. У меня есть табличные проекты с полями ID и PARENT_ID.

DELIMITER $$
DROP FUNCTION IF EXISTS `getDepth` $$
CREATE FUNCTION `getDepth` (project_id INT) RETURNS int
BEGIN
    DECLARE depth INT;
    SET depth=1;

    WHILE project_id > 0 DO
        SELECT IFNULL(parent_id,-1) 
        INTO project_id 
        FROM ( SELECT parent_id FROM Projects WHERE id = project_id) t;

        IF project_id > 0 THEN
            SET depth = depth + 1;
        END IF;

    END WHILE;

    RETURN depth;

END $$
DELIMITER ;
person manuel    schedule 02.02.2016