И снова про деревья

Всё-таки, мысли о деревьях не дают мне покоя.

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

Структура базы данных:
[sql]CREATE TABLE `tree` (
`id` int auto_increment, -- ID узла
`pid` int, -- ID родителя
`sort` int, -- Сортировочное поле
`childs` int, -- Количество "непосредственных детей"
`level` int, -- Уровень
PRIMARY KEY (`id`)
)[/sql]
Здесь, поле `sort` и есть то поле, по которому происходит сортировка.

Пересортировка дерева:

PHP:

1. <?
2.  
3. // Классический вывод дерева, только в нашем случае он возвращает массив ID'шников
4. function get($pid = 0, $ids = array()) {
5.     $result = mysql_query("SELECT id, childs FROM tree WHERE pid = $pid ORDER BY id");
6.     while ($row = mysql_fetch_object($result)) {
7.         $ids[] = $row->id;
8.         if ($row->childs) {
9.             $ids = array_merge($ids, get($row->id));
10.         }
11.     }
12.     return $ids;
13. }
14.  
15. $ids = join(", ", get());
16. mysql_query("SET @i = 0");
17. // Вся фишка в этом запросе, в котором мы нумеруем узлы в том порядке, в котором они должны отображаться
18. mysql_query("UPDATE tree SET sort = (@i := @i + 1) ORDER BY FIELD(id, $ids)");
19.  
20. ?>

Пересортировку необходимо делать только если мы добавляем некорневой узел.

В итоге, чтобы вывести дерево достаточно выполнить запрос:
[sql]SELECT * FROM tree ORDER BY sort[/sql]

Ну как?

Сильно не ругайте, я ещё даже не студент. :-Р

 

Код (Text):

1. sort | id
2. 1    | 1
3. 2    | 3
4. 3    | 7
5. 4    | 8
6. 5    | 4
7. 6    | 9
8. 7    | 10
9. 8    | 2
10. 9    | 5
11. 10   | 11
12. 11   | 12
13. 12   | 6
14. 13   | 13
15. 14   | 14

Ты чего-то такого хотел?

Выбрать ветку 3 можно классически - рекурсивно, а можно так:
[sql]SELECT @pid := pid, @pos := sort FROM tree WHERE id = 3;
SELECT @next_pos := sort FROM tree WHERE pid = @pid AND id > 3 ORDER BY sort LIMIT 1;
SELECT * FROM tree WHERE sort > @pos AND sort < @next_pos ORDER BY sort;
-- TODO: предусмотреть обработку NULL-значений[/sql]

Хочу добавить: цель этого алгоритма - не выбор веток, а быстрый вывод всего или части дерева.

 

pid - parent id
Часть дерева - буквально, "кусок" дерева. Зачем жто нужна? Навеяло длиннющим деревом комментариев на Хабре, "куски" дерева нужны для пагинации.

 

Спрашиваете обрывками - отвечаю обрывками.