Welcome to php club

PHP FAQ from PHPclub.ru: Tree/Internal ...

Начало | Каталог | Изменения | НовыеКомментарии | Вам запрещён доступПользователи | Вам запрещён доступРегистрация | Вход:  Пароль:  

Деревья в базах данных => Внутреннее представление

Внутреннее представление деревьев в программах


Философские замечания по поводу того, «что такое хорошо»? Можно не читать до следующей горизонтальной линии.


Если в Вашем проекте весь код, работающий с деревьями, зависит от того, каким способм это дерево представлено в базе данных, при изменении способа хранения дерева потребуется переписать весь этот код, и Вас это устраивает, то задумываться над внутренним представлением деревьев в программах Вам не нужно.


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


Другое дело, если Вы хотите сделать так, что бы одни части Вашего проекта (вывод дерева, его обработка и т.п.) не зависили от того, как устроены другие его части (способ его хранения, способ его загрузки и т.п.). Мы будем считать, что загрузка дерева и вывод дерева – это два разных скрипта, каждый из которых должен работать независимо от того, как устроен внутри другой скрипт; внесение изменений в один из скриптов не должно затрагивать другой скрипт. Для того, что бы эти два разных скрипта могли взаимодействовать, необходимо договориться о том, какие данные будут передаваться между этими скриптами.


Справедливости ради следует отметить, что такая договоренность требует дополнительных вычислительных ресурсов для преобразования одних данных в другие. Если бы мы не рассматривали загрузку и вывод дерева как два разных ПОЛНОСТЬЮ независимых скрипта, то такое преобразования нам не потребовалось бы: мы загружаем дерево так, как нам удобно и потом специально под этот способ загрузки пишем скрипт вывода этого дерева:


загрузка дерева -> вывод дерева


Если же мы хотим, что бы вывод дерева не зависел от способа хранения дерева, то в некоторых случаях может потребоваться добавить еще один этап обработки данных:


загрузка дерева -> преобразование данных -> вывод дерева


Вот это самое «преобразование данных» и требует дополнительного времени на обработку. От него можно было бы отказаться. Но...


  • начинающие программисты думают, что самое важное в программах – это скорость. Именно поэтому некоторые говорят (и даже считают!), что «функции – это лучше, чем объекты, потому что функции быстрее работают». Даже если и быстрее (хотя не факт), разность в скорости не столь велика. А гибкость, предоставляемая объектным подходом, теряется, если Вы используете функции.
  • пользователи (дизайнеры, заказчики, и Вы, когда Вам потребуется переписать «вывод дерева» для другого способа хранения дерева) думают, что самое важное в программах – это гибкость

Чем отличается новичек от программиста с опытом?


  • программист с опытом уже потратил много своего времени на переписывание одних и тех же кусков собственного (и чужого) кода и при определении важности «скорости выполнения скрипта» учитывает так же время на разработку
  • новичек еще ничего не переписывал заново – он все пишет первый раз. Именно поэтому он считает, что ничего переписывать ему не потребуется.

Если все же я Вас не убедил, то я скажу Вам правду, для чего я описал здесь эту стркутуру. Я ее описал здесь потому, что многие приведенные мной примеры загрузки дерева загружают его именно в такой форме. А большинство приведенных мной примеров вывода дерева требуют на вход дерево, представленное именно в такой форме.


Итак, договоримся, что скрипты загрузки дерева будут возвращать данные в форме, которая описана ниже. Скрипты вывода дерева для правильной работы требуют данные в форме, которая описана ниже.


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


Я выбрал такую структуру потому, что такая структура лично мне показалась наиболее естественной для представления деревьев вообще, она не зависит от способа хранения дерева в базе данных и потому, что эта структура лучше всего подходит для тех примеров, которые я здесь приводил.




Дерево в скриптах на языке php хранится в массиве – списке вершин уровня. Индексами этого массива является порядковый номер вершины в уровне, начиная с 0, без пропусков.


Вершина – это массив, в которм содержатся следующие элементы:


  • k_item – идентификатор вершины дерева – служит для связи с другими таблицами
  • s_name – название вершины дерева (строка)
  • a_tree – список дочерних вершин для этой вершины. Если у этой вершины нет дочерних вершин, то здесь содержится пустой массив.

Пример дерева

1  1
2  1.1
3  1.1.1
4  1.1.2
5  1.1.3
6  1.1.3.1
7  1.2
8  1.3
9  1.3.1
10 1.3.2
11 1.4
12 1.4.1
13 2
14 3
15 3.1


Соответствующий этому дереву массив

<?php
$a_tree
=array(
  array(
'k_item' =>1,'s_name' =>'1','a_tree' => array(
    array(
'k_item' =>2,'s_name' =>'1.1','a_tree' => array(
      array(
'k_item' =>3,'s_name' =>'1.1.1','a_tree' => array()),
      array(
'k_item' =>4,'s_name' =>'1.1.2','a_tree' => array()),
      array(
'k_item' =>5,'s_name' =>'1.1.3','a_tree' => array(
        array(
'k_item' =>6,'s_name' =>'1.1.3.1','a_tree' => array())
        )),
      )),
    array(
'k_item' =>7,'s_name' =>'1.2','a_tree' => array()),
    array(
'k_item' =>8,'s_name' =>'1.3','a_tree' => array(
      array(
'k_item' =>9,'s_name' =>'1.3.1','a_tree' => array()),
      array(
'k_item' =>10,'s_name' =>'1.3.2','a_tree' => array())
      )),
    array(
'k_item' =>11,'s_name' =>'1.4','a_tree' => array(
      array(
'k_item' =>12,'s_name' =>'1.4.1','a_tree' => array())
      )),
    )),
  array(
'k_item' =>13,'s_name' =>'2','a_tree' => array()),
  array(
'k_item' =>14,'s_name' =>'3','a_tree' => array(
    array(
'k_item' =>15,'s_name' =>'3.1','a_tree' => array())
    ))
  );
?>


Функции для формирования этого массива в зависимости от способа хранения деревьев смотрите в соответствующих разделах:
Как загрузить дерево, которое хранится в виде списков смежности
Как загрузить дерево, которое хранится в виде вложенных множеств


 
Комментариев нет. [Показать комментарии/форму]