Выбор всех потомков узла дерева

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

DELIMITER //

CREATE PROCEDURE get_descendants(node_id INT)
    BEGIN

    DROP TEMPORARY TABLE IF EXISTS descendants;
    CREATE TEMPORARY TABLE descendants (id INT, name VARCHAR(100), parent_id INT);

    INSERT INTO descendants
        SELECT *
        FROM nodes
        WHERE parent_id <=> node_id;

    -- ...?

    END//

DELIMITER ;

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

Мне нужно как-то перебрать результаты и выдать новый оператор SELECT для каждой строки. Я читал, что здесь могут помочь курсоры, но я не понимаю, как это сделать. Кажется, что с курсорами вы должны выбрать все заранее, а затем повторить.


mysql stored-procedures adjacency-list
person Adam Siler    schedule 27.04.2012    source источник
comment
Вложенные наборы — не единственный вариант. Таблицы закрытия также заслуживают внимания.   -  person eggyal    schedule 28.04.2012
comment
На самом деле, я только что открыл для себя закрывающие таблицы сегодня днем! Они кажутся многообещающими, но не очень хорошо справляются с операциями перемещения. mysqlperformanceblog.com/2011/02/14/ В этом смысле они похожи на вложенные наборы. Я буду продолжать учиться.   -  person Adam Siler    schedule 28.04.2012
comment
Выбор подходящей структуры данных для ваших нужд заключается в понимании того, как часто вам придется выполнять различные типы операций, поскольку каждое решение по-разному компенсирует время и пространство. Если ваш граф довольно статичен и вам часто нужно проверять пути через него, то список смежности, вероятно, не лучший выбор; однако это может быть идеальным решением, если граф очень динамичен и вам редко нужно проверять больше, чем соседние соседи любого заданного узла.   -  person eggyal    schedule 28.04.2012

Ответы (1)


arrow_upward
0
arrow_downward

Это соотношение до read : write. Если у вас очень высокая скорость чтения, будет очень полезно составить полную таблицу отношений, а не временную.

Псевдоподход (не настоящий код!):

1. node(1) has child node(2)
     -> Insert a row with (parent_id = 1, child_id = 2, direct = True)

2. node(2) has child node(3)
     -> Insert a row with (parent_id = 2, child_id = 3, direct = True)
     -> Choose all ascendants of node(2)
     -> Ascendants of node(2) : [node(1)]
     -> Insert a row with (parent_id = 1, child_id = 3, direct = False)

3. To retrieve all descendants of node(1)
     -> SELECT child_id FROM [table] WHERE parent_id = 1;

4. To retrieve children of node(1)
     -> SELECT child_id FROM [table] WHERE parent_id = 1 AND direct = True;

5. To retrieve all ascendants of node(3)
     -> SELECT parent_id FROM [table] WHERE child_id = 3;

6. To retrieve parent of node(3)
     -> SELECT parent_id FROM [table] WHERE child_id = 3 AND direct = True;

+-----------+----------+--------+
| parent_id | child_id | direct |
+-----------+----------+--------|
|         1 |        2 | True   |
|         1 |        3 | False  |
|         2 |        3 | True   |
....
+-----------+----------+--------+
Index 1 on ( parent_id, direct )
Index 2 on ( child_id, direct )

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

person lqez    schedule 08.06.2012