Главная страница статей --> Хитрости при программировании php, заметки по базам данных

Работа с MySQL. Деревья

Источник: realcoding.net

Необходимость вывода данных структурированных в форме деревьев возникает при написании собственного форума или каталога сайтов. Готовых каталогов и форумов в сети можно найти предостаточно, однако иногда чужое в готовом не годится, а переделывать написанное другим займёт гораздо больше времени, чем написать своё.

Структуру данных лучше взять общепринятую - в записи сообщения или рубрики форума содержится идентификатор родителя. Для организации вывода дерева напрашивается рекурсивная функция. Именно так сделано в Phorumе. Файл include/multi-threads.php содержит функцию thread, которая строит вызывается для каждого корневого сообщения и рекурсивно вызывает себя для ответов на них:

<?php
function thread ($seed = 0) {
...

    if(@
is_array($messages[$seed][replies])) {
       
$count = count($messages[$seed][replies]);
        for(
$x = 1;$ x <= $count; $x++) {
            
$key = key($messages[$seed][replies]);
            
thread ($key);
            
next ($messages[$seed][replies]);
        }
    }
}
?>

Но вызов рекурсивной функции при выводе вызывает у меня сомнения: повторять построение дерева сообщений при каждом выводе нерационально. Структура дерева меняется только при добавлении, изменении и удалении сообщений. Данную процедуру лучше было бы вызывать при таких действиях, хранить структуру в таблице и при выводе дерева не делать никаких вычислений.

Для построения дерева достаточно знать последовательность вывода рубрик и их уровень в дереве. Добавим два поля с этими данными в таблицу: level (TINYINT(4). 127 уровней - хватит?) и sortorder (VARCHAR(128)).

---------
id parent
---------
3      0
5      0
7      0
10      3
11      7
12      5
13      3
16     10
21     16
26     11
30      3
47      7
60     10
73     13
75     47
---------

   

o- 3

+-
o- 10

+-
o- 16

+-
o- 21

+-
o- 60

+-
o- 13

+-
o- 73

+-
o- 30

o
- 5

+-
o- 12

o
- 7

+-
o- 11

+-
o- 26

+-
o- 47
 

  +-
o- 75

Всё, что нам нужно для построения дерева - это идентификатор рубрики и её родителя. Допустим, мы имеем в каталоге несколько рубрик такого содержания:

Структура дерева, подобие которой мы хотим получить такова:

Правда, данный алгоритм позволит нарисовать дерево, но без веток виде линий, как сделано на этом рисунке. Структура дерева будет нарисована при помощи отступов слева.

Вернёмся ещё раз к таблице id-parent. Это рубрики, уже отсортированные по некоторому признаку, по которому мы хотим сортировать элементы одинакового уровня. Например, по убыванию числа сайтов. Кроме id и родительской рубрики мы знаем и номер каждой из них в данном списке. Выровняем эти номера до нужной длины, добавив слева нули. После этого для каждой рубрики сделаем текстовую строку с номерами всех её родителей от самого корня:

При сортировке по полю sortorder мы получим именно то, что нам нужно:

------------------------------
id sort parent sortorder level
------------------------------
3    1      0 01            0
5    2      0 02            0
7    3      0 03            0
10    4      3 0104          1
11    5      7 0305          1
12    6      5 0206          1
13    7      3 0107          1
16    8     10 010408        2
21    9     16 01040809      3
26   10     11 030510        2
30   11      3 0111          1
47   12      7 0312          1
60   13     10 010413        2
73   14     13 010714        2
75   15     47 031215        2
------------------------------

   

------------------------------
id sort parent sortorder level
------------------------------
3    1      0 01            0
10    4      3 0104          1
16    8     10 010408        2
21    9     16 01040809      3
60   13     10 010413        2
13    7      3 0107          1
73   14     13 010714        2
30   11      3 0111          1
5    2      0 02            0
12    6      5 0206          1
7    3      0 03            0
11    5      7 0305          1
26   10     11 030510        2
47   12      7 0312          1
75   15     47 031215        2
------------------------------

Отступ слева делается, учитывая поле level.

Важно так же отметить, что нам не нужно ничего сортировать в самом скрипте. Для формирования полей sortorder и level нужно заблокировать таблицу от записи (чтобы не произошло изменения структуры веток), выбрать из базы идентификатор рубрики и её родителя, отсортировав по нужному признаку, и записать их в простой двухмерный массив. Затем обработать массив последовательно от первого до последнего уровня и записать поля sortorder и level в таблицу.

Для формирования sortorder не нужно рекурсии (хотя можно, и, вероятно, она работать будет даже быстрее). Достаточно пройтись по массиву одним и тем же циклом. В нём, если рубрика не обработана, для неё формируется поле sortorder из поля sort и родительского sortorder. Если родительская рубрика ещё не обработана, поднимается флаг $unprocessed_rows_exist и цикл запускается ещё раз.

<?php
mysql_query
(LOCK TABLES dir WRITE);

$result = mysql_query(SELECT id, IFNULL(parent,0) as parent FROM dir
    ORDER BY sites DESC, title
);

while (
$row = mysql_fetch_array($result)) {
   
$count++;
   
$data[parent][$row[id]] = $row[parent];
   
$data[sort][$row[id]] = $count;
}

reset($data);

$unprocessed_rows_exist = true;
while(
$unprocessed_rows_exist) {
   
$unprocessed_rows_exist = false;
    while (list(
$i, $v) = each($data[parent])) {
        if((
$data[parent][$i] == 0 !isset($data[sort][$data[parent][$i]]))
                && !isset(
$data[sortorder][$i])) {
            
$data[sortorder][$i] = str_pad($data[sort][$i], $max, 0, STR_PAD_LEFT);
            
$data[level][$i] = 0;
        }
        elseif(!isset(
$data[sortorder][$i]) &&
                isset(
$data[sortorder][$data[parent][$i]])) {
            
$data[sortorder][$i] = $data[sortorder][$data[parent][$i]].
               
str_pad($data[sort][$i], $max, 0, STR_PAD_LEFT);
            
$data[level][$i] = $data[level][$data[parent][$i]] + 1;
        }
        elseif(!isset(
$data[sortorder][$i]) && isset($data[sort][$data[parent][$i]])) {
            
$unprocessed_rows_exist = true;
        }
    }

reset($data);
?>

Отмечу, что данный алгоритм не зацикливается при наличии строк с битым полем parent и не пропускает их, а делает корневыми. Рекурсивный алгоритм их просто пропустит.

После выполнения этого цикла мы имеем массивы "id => level" и "id => sortorder". Отправляем в базу всего один запрос, пользуясь внутренними функциями MySQL ELT и FIND_IN_SET:

<?php mysql_query(UPDATE dir SET sortorder=ELT(FIND_IN_SET(id,. implode(,, array_keys($data[sortorder])). ),. implode(,, $data[sortorder]). ), level=ELT(FIND_IN_SET(id,. implode(,, array_keys($data[level])). ),. implode(,, $data[level]). ) WHERE id IN (. implode(,, array_keys($data[sortorder])). )); ?>

Конечно же, в отличие от дерева рубрик каталога, в большом форуме много сообщений. Передёргивать их всех при добавлении одного нового нет смысла.

В форумах чаще всего используется сортировка по дате написания сообщения. Поэтому поле sortorder можно смело делать из своего и родительского timestampа, выровненного функцией str_pad до 11-значной длины.



Похожие статьи:
- Раскручиваем url
- Создание таблиц Excel на PHP
- Генерация HTTP запросов
- ЧПУ и PHP (revisited)
- Имитация файлов и директорий
- Защита от спама на сайте
- Тщательная перетасовка колоды карт
- Вывод сообщений пользователю в веб-приложениях.
- Абстрактные классы и интерфейсы
- Хэширование паролей в PHP
- Ajax Master-detail
- XML на экране броузера
- Полезные советы по оптимизации ASP-приложений


Оглавление | Обсудить на форуме | Главная страница сайта | Карта сайта |

Контакты
Редакция:
[0.001]