Реклама
Hp presario, ipad 3g - нетбуки dell цены.
Спонсорские ссылки
-
Статья
Версия для печати
Обсудить на форуме
MySQL. Иерархические запросы. Часть 2.


Автор: RXL
Написано: 10.12.2009.
Права на статью принадлежат автору и Клубу программистов «Весельчак У».

Небольшое дополнение к ранее вышедшей статье «MySQL. Иерархические запросы». Здесь предлагаю решение той же самой задачи — выборки поддерева на связях id — parent_id, но без динамического SQL — на временных таблицах. Такой вариант работает много быстрее, но процедуры оказываются жестко привязанными к таблицам.
Для начала напомню особенности временных таблиц. Имя временной таблицы не должно совпадать с именем уже существующей таблицы, но в разных сессиях могут быть временные таблицы с одинаковыми именами. Также удобно то, что они автоматически удаляются при завершении сессии и не замусоривают базу. Временные таблицы могут быть форматов MEMORY (что полезно для скорости работы) и MYISAM.

Для начала создаем тестовую таблицу:

Код: (MySQL)
CREATE TABLE t1 (
    id INT UNSIGNED NOT NULL AUTO_INCREMENT,
    parent_id INT UNSIGNED NOT NULL,
    lvl SMALLINT UNSIGNED NOT NULL,
    PRIMARY KEY (id),
    UNIQUE KEY parent (parent_id, id),
    UNIQUE KEY lvl (lvl, id)
) ENGINE = MYISAM;

Этой процедурой заполним таблицу тестовыми данными:

Код: (MySQL)
CREATE PROCEDURE fill2(IN levels INT UNSIGNED, IN branches INT UNSIGNED)
BEGIN
    DECLARE lvl INT UNSIGNED DEFAULT 1;
    DECLARE n INT UNSIGNED;

    CREATE TEMPORARY TABLE _fill_tmp1 (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;

    INSERT INTO t1 (parent_id, lvl) VALUES (0, 0);

    WHILE lvl < levels DO
        INSERT INTO _fill_tmp1
        SELECT t1.id FROM t1
        WHERE t1.lvl = lvl - 1;

        SET n = 0;

        while n < branches DO
            INSERT INTO t1 (parent_id, lvl)
            SELECT id, lvl FROM _fill_tmp1;

            SET n = n + 1;
        END WHILE;

        TRUNCATE TABLE _fill_tmp1;

        SET lvl = lvl + 1;
    END WHILE;

    DROP TABLE _fill_tmp1;
END;

Параметрами можно регулировать количество уровней — levels и степень ветвления дерева (сколько у каждого узла будет потомков) — branches.
Заполним таблицу деревом из 6 уровней и с степенью ветвления 10. Должно получиться SUM(branchesn) узлов, где n от 0 до levels - 1. В нашем случае должно получиться 111111 узлов.

mysql> call fill2(6, 10);
Query OK, 0 rows affected (1.78 sec)

mysql> select count(*) from t1;
+----------+
| count(*) |
+----------+
|   111111 |
+----------+
1 row in set (0.00 sec)

mysql> select * from t1 order by lvl, id limit 31;
+----+-----------+-----+
| id | parent_id | lvl |
+----+-----------+-----+
|  1 |         0 |   0 |
|  2 |         1 |   1 |
|  3 |         1 |   1 |
|  4 |         1 |   1 |
|  5 |         1 |   1 |
|  6 |         1 |   1 |
|  7 |         1 |   1 |
|  8 |         1 |   1 |
|  9 |         1 |   1 |
| 10 |         1 |   1 |
| 11 |         1 |   1 |
| 12 |         2 |   2 |
| 13 |         3 |   2 |
| 14 |         4 |   2 |
| 15 |         5 |   2 |
| 16 |         6 |   2 |
| 17 |         7 |   2 |
| 18 |         8 |   2 |
| 19 |         9 |   2 |
| 20 |        10 |   2 |
| 21 |        11 |   2 |
| 22 |         2 |   2 |
| 23 |         3 |   2 |
| 24 |         4 |   2 |
| 25 |         5 |   2 |
| 26 |         6 |   2 |
| 27 |         7 |   2 |
| 28 |         8 |   2 |
| 29 |         9 |   2 |
| 30 |        10 |   2 |
| 31 |        11 |   2 |
+----+-----------+-----+
31 rows in set (0.00 sec)

Похоже на правду...
Процедура для выборки заданного поддерева:

Код: (MySQL)
CREATE PROCEDURE fetch_subtree_ids2(
    IN base INT UNSIGNED,
    IN max_levels INT UNSIGNED
)
BEGIN
    DECLARE currlevel INT DEFAULT 1;
    DECLARE cnt INT DEFAULT 0;

    DROP TABLE IS EXISTS _fst_parents, _fst_tmp, _fst_result;

    CREATE TEMPORARY TABLE _fst_parents (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;
    CREATE TEMPORARY TABLE _fst_tmp (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;
    CREATE TEMPORARY TABLE _fst_result (id INT UNSIGNED NOT NULL) ENGINE=MEMORY;

    INSERT INTO _fst_parents VALUES (base);
    INSERT INTO _fst_result VALUES (base);
   
    -- В случае если max_levels равно 0, то допускаем 100000 уровней.
    SET max_levels = IF(max_levels, max_levels, 100000);

    REPEAT
        INSERT INTO _fst_tmp
        SELECT h.id
        FROM _fst_parents t, t1 h
        WHERE h.parent_id = t.id;

        SELECT COUNT(*) INTO cnt FROM _fst_tmp;

        INSERT INTO _fst_result
        SELECT id FROM _fst_tmp;

        TRUNCATE TABLE _fst_parents;

        INSERT INTO _fst_parents
        SELECT id FROM _fst_tmp;

        TRUNCATE TABLE _fst_tmp;

        SET currlevel = currlevel + 1;
    UNTIL (cnt = 0 OR currlevel > max_levels) END REPEAT;

    SELECT COUNT(id) FROM _fst_result;
   
    DROP TABLE _fst_parents, _fst_tmp, _fst_result;
END;

Процедура чисто для демонстрации — чтобы замерить время, затрачиваемое на выборку идентификаторов поддерева. Для реальной работы надо заменить строку

Код: (MySQL)
    SELECT COUNT(id) FROM _fst_result;

на

Код: (MySQL)
    SELECT id FROM _fst_result;

Проверим работу процедуры на практике! Напоминаю, что у нас 6 уровней, фактор ветвления 10 и в итоге — 111111 узлов. Выберем все дерево:

mysql> call fetch_subtree_ids2(1, 0);
+-----------+
| COUNT(id) |
+-----------+
|    111111 |
+-----------+
1 row in set (0.67 sec)

Query OK, 0 rows affected (0.67 sec)

Полное дерево выбралось за 0.67 секунды. Это, конечно, долго, но и узлов много. Попробуем выбрать в 100 раз меньший фрагмент:

mysql> call fetch_subtree_ids2(50, 0);
+-----------+
| COUNT(id) |
+-----------+
|      1111 |
+-----------+
1 row in set (0.01 sec)

Query OK, 0 rows affected (0.01 sec)

На выборку поддерева из 1111 элементов (4 уровня) затрачено всего 10 миллисекунд! Замечу, что такое поддерево великовато для типичных задач с каталогами и на практике может потребоваться еще меньше времени.
Еще быстрее работает метод вложенных деревьев, но у него есть существенный недостаток — большие вычислительные затраты при изменении дерева (добавлении новых узлов или сжатии дерева после удаления узлов).
Версия для печати
Обсудить на форуме