Tree/Internal

Материал из PhpWiki.

Перейти к: навигация, поиск
 Деревья в базах данных =>  Внутреннее представление
Внутреннее представление деревьев в программах

popoff

Философские замечания по поводу того, "что такое хорошо"?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дерево в скриптах на языке 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())
))
);
?>
Реклама