 |
|
Деревья в базах данных => Внутреннее представление
Внутреннее представление деревьев в программах
Философские замечания по поводу того, «что такое хорошо»? Можно не читать до следующей горизонтальной линии.
Если в Вашем проекте весь код, работающий с деревьями, зависит от того, каким способм это дерево представлено в базе данных, при изменении способа хранения дерева потребуется переписать весь этот код, и Вас это устраивает, то задумываться над внутренним представлением деревьев в программах Вам не нужно.
Если Вас не интересует разедение логики и представления, Вы выводите дерево в одном цикле вместе с выборкой из базы данных, то о внутреннем представлении тоже говорить не приходится.
Другое дело, если Вы хотите сделать так, что бы одни части Вашего проекта (вывод дерева, его обработка и т.п.) не зависили от того, как устроены другие его части (способ его хранения, способ его загрузки и т.п.). Мы будем считать, что загрузка дерева и вывод дерева – это два разных скрипта, каждый из которых должен работать независимо от того, как устроен внутри другой скрипт; внесение изменений в один из скриптов не должно затрагивать другой скрипт. Для того, что бы эти два разных скрипта могли взаимодействовать, необходимо договориться о том, какие данные будут передаваться между этими скриптами.
Справедливости ради следует отметить, что такая договоренность требует дополнительных вычислительных ресурсов для преобразования одних данных в другие. Если бы мы не рассматривали загрузку и вывод дерева как два разных ПОЛНОСТЬЮ независимых скрипта, то такое преобразования нам не потребовалось бы: мы загружаем дерево так, как нам удобно и потом специально под этот способ загрузки пишем скрипт вывода этого дерева:
загрузка дерева -> вывод дерева
Если же мы хотим, что бы вывод дерева не зависел от способа хранения дерева, то в некоторых случаях может потребоваться добавить еще один этап обработки данных:
загрузка дерева -> преобразование данных -> вывод дерева
Вот это самое «преобразование данных» и требует дополнительного времени на обработку. От него можно было бы отказаться. Но...
- начинающие программисты думают, что самое важное в программах – это скорость. Именно поэтому некоторые говорят (и даже считают!), что «функции – это лучше, чем объекты, потому что функции быстрее работают». Даже если и быстрее (хотя не факт), разность в скорости не столь велика. А гибкость, предоставляемая объектным подходом, теряется, если Вы используете функции.
- пользователи (дизайнеры, заказчики, и Вы, когда Вам потребуется переписать «вывод дерева» для другого способа хранения дерева) думают, что самое важное в программах – это гибкость
Чем отличается новичек от программиста с опытом?
- программист с опытом уже потратил много своего времени на переписывание одних и тех же кусков собственного (и чужого) кода и при определении важности «скорости выполнения скрипта» учитывает так же время на разработку
- новичек еще ничего не переписывал заново – он все пишет первый раз. Именно поэтому он считает, что ничего переписывать ему не потребуется.
Если все же я Вас не убедил, то я скажу Вам правду, для чего я описал здесь эту стркутуру. Я ее описал здесь потому, что многие приведенные мной примеры загрузки дерева загружают его именно в такой форме. А большинство приведенных мной примеров вывода дерева требуют на вход дерево, представленное именно в такой форме.
Итак, договоримся, что скрипты загрузки дерева будут возвращать данные в форме, которая описана ниже. Скрипты вывода дерева для правильной работы требуют данные в форме, которая описана ниже.
Не спрашивайте меня, почему я выбрал именно такой способ внутреннего представления дерева. На самом деле я этого не знаю – если у Вас есть другие соображения, Вы можете использовать в Ваших проектах любую другую структуру. Приведенную ниже структуру Вы можете использовать как пример для определения своего собственного способа передачи дерева между скриптами.
Я выбрал такую структуру потому, что такая структура лично мне показалась наиболее естественной для представления деревьев вообще, она не зависит от способа хранения дерева в базе данных и потому, что эта структура лучше всего подходит для тех примеров, которые я здесь приводил.
Дерево в скриптах на языке 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())
))
);
?>
Функции для формирования этого массива в зависимости от способа хранения деревьев смотрите в соответствующих разделах:
Как загрузить дерево, которое хранится в виде списков смежности
Как загрузить дерево, которое хранится в виде вложенных множеств