[Закрыть]
 
popoff.donetsk.ua
Использование флагов чем-то напоминает использование GOTO. Те, кому нравится этот оператор, как правило, избавляются от него введением флагов. Но ведь можно немножко подумать и получить красивый и понятный код без этого оператора и без флагов.
Начало | Новости | Статьи | Форум | Опросы | Карта сайта | Обо мне
popoff.donetsk.ua - Статьи - Программирование - Модули - mysql - mysql.tree - mysql_tree_move
Я это делаю
Персональное меню
Голосование
Деньги, либо любимое занятие? Постоянный адрес этого вопроса
Деньги, но неинтересная работа и невозможность уделить время семье
Интересная работа, возможность саморазвиваться, но нищенский заработок
Ваш возраст (не обязательно)
Почему? (не обязательно)

Голосование закрыто.

Поиск по сайту
Реклама
Обмен электронных валют
money.dn.ua
Статистика

mysql_tree_move

Постоянный адрес статьи

mysql_tree_move -- Перемещение узлов дерева вместе со всеми дочерними узлами в новые места

Содержание

Описание

mixed mysql_tree_move(string $table, array $data[, bool $is_ignore=false]);

Требуемая библиотека: mysql.tree

Перемещает узлы дерева вместе со всеми дочерними узлами в новые места дерева.

$table
Имя таблицы, в которой хранится дерево. Эта таблица должны быть создана при помощи функции mysql_tree_create.
$data
$data - это массив элементов. Каждый элемент содержит в себе информацию о том, какой узел куда требуется переместить. Каждый элемент - это массив, в котором содержатся следующие поля:
from
i_id узла, который требуется переместить. Это поле является обязательным для всех элементов.
to
i_id элемента, к которому требуется переместить узел from. Значение этого поля трактуется по-разному, в зависимости от значения поля sibling. Узел to не может являться ребенком узла from.
sibling
Задает размещение перемещаемого узла относительно узла to. Значение по умолчанию - false. Если значение этого поля истино, то:
  • Если задано значение узла to, то узел from вставляется братом узла to слева или справа от узла to, в зависимости от значения поля left.
  • Если значение поля to не задано, то узел from, не изменяя своего родителя, перемещается на один узел правее или на один узел левее относительно текущего расположения, в зависимости от значения поля left. Если значение поля to не задано, то поле left является обязательным.
Если значение этого поля ложно или не указано, то:
  • Если задано значение узла to, то узел from вставляется левым или правым ребенком узла to, в зависимости от значения поля left.
  • Если значение поля to не задано, то узел from, не изменяя своего родителя, становится левым или правым ребенком своего родителя (перемещается в крайнюю левую или в крайнюю правую позицию), в зависимости от значения поля left.

    Если значение поля to не задано, то узел from становится левым или правым ребенком, смотря куда ближе («приклеивается» к самому ближнему концу списка своих братьев). При этом близость определяется не количеством братьев, а количеством братьев с учетом всех дочерних узлов этих братьев. Если слева от узла - 1 брат (у которого 20 дочерних вершин), а справа - 10 (у которых нет дочерних вершин), то считается, что этот узел ближе к правому краю.
left
Задает размещение узла from относительно узла to. Это поле может принимать следующие значения:
  • если значение этого поля не указано, то оно принимается равным true или false, в зависимости от того, для какого значения потребуется пересчитать меньшее число узлов дерева. Значение поля left не может быть не указано, если в поле sibling передана истина и значение поля to не указано.
  • если значение этого поля - true, то узел from вставляется либо левым ребенком, либо левым братом узла to, в зависимости от значения поля sibling. Если значение поля sibling - истинно, и значение поля to не указано, то узел from перемещается на одну позицию левее.
  • если значение этого поля - false, то узел from вставляется либо правым ребенком, либо правым братом узла to, в зависимости от значения поля sibling. Если значение поля sibling - истинно, и значение поля to не указано, то узел from перемещается на одну позицию правее.
right
Если задано значение этого поля, то значение поля left считается по формуле:
left=!right;
Исходное значение поля left в таком случае игнорируется.
$is_ignore
Определяет реакцию функции в случае ошибок. Если $is_ignore=true, то некоторые ошибки могут быть проигнорированы. Все «хорошие» элементы массива $data в таком случае будут перемещены. Если $is_ignore=false, то в случае ошибки не будет перемещен ни один узел.

Возвращаемые значения:

-1
Внутренняя ошибка, которая не отлавливается этой функцией. Например, ошибка при выполнении sql-запроса.
0
Все узлы успешно перемещены.
false
Может быть возвращено только если в $is_ignore передано значение истина. Такой результат означает, что некоторые узлы - успешно перемещены, а некоторые элементы массива $data были проигнорированы.
1
В качестве аргумента $data был передан не массив, либо один из элементов этого массива не является массивом. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
2
Значение поля from не указано, либо не является числовым. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
3
Значение поля to не указано, либо не является числовым. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
4
Значение поля to совпадает со значением поля from, либо узел to является дочерним по отношению к узлу from. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore передана истина.
5
Узел from не существует. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore передана истина.
6
Узел to не существует. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore передана истина.
7
Узел to является корневым и в качестве значения поля sibling передана истина. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore передана истина.
8
Значение поля sibling истинно, значение поля to не указано и узел from является самым левым (или самым правым) узлом. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore передана истина.
9
Значение поля sibling истинно, и не указано ни значение поля to, ни значение поля left. В случае такой ошибки генерируется так же сообщение об ошибке при помощи trigger_error.
10
Узел from является корневым. Корневой узел нельзя перемещать. Эта ошибка может быть проигнорирована, если в качестве аргумента $is_ignore передана истина.

Следует помнить, что элементы массива $data обрабатываются по очереди, один за одним. Поскольку в этом массиве Вы можете задать любую последовательность перемещений в дереве, то это означает, что в некоторый момент узел to может оказаться дочерним узлом для узла from, даже если в исходном дереве такого родства не было. Это несколько затрудняет проверку исходных данных, если они приходят из формы. Либо передавайте истину в качестве $is_ignore, если Вы допускаете перемещения откуда угодно куда угодно, либо ограничьте пользователя в том, откуда куда он может перемещать узлы.

Пример. Использование mysql_tree_move().
<?php
$a
=array(
  
//узел 2 сделать потомком узла 3, поместить его справа или слева,
  //  куда будет ближе
  
array('from' => 2,'to' => 3),
  
//узел 4 переместить на один узел левее
  
array('from' => 4,'sibling' => true,'left' => true),
  
//узел 5 расположить слева от узла 6
  
array('from' => 5,'to' => 6,'sibling' => true,'left' => true),
  
//узел 7 сделать правым ребенком узла 2
  
array('from' => 7,'to' => 2,'left' => false),
  
//узел 8 расположить справа или слева от узла 7, куда будет ближе
  
array('from' => 8,'to' => 7,'sibling' => true),
  
//следующий элемент вызовет ошибку, поскольку в результате
  //  предыдущих перемещений
  //  узел 8 стал дочерним по отношению к узлу 3
  //  (узел 2 стал ребенком 3, узел 7 стал ребенком 2,
  //   а узел 8 стал братом узла 7, и, следовательно,
  //   ребенком узла 2)
  
array('from' => 3,'to' => 8,'sibling' => true),
  );
$r=mysql_tree_move('light_text_tree',$a,true);
if(
$r===false) $r=-2;
switch(
$r)
{
  case
0:
    echo
«Все успешно перемещено»;
    break;
  case -
2:
    echo
«Некоторые элементы не были перемещены в результате ошибок»;
    break;
  case
2:
  case
3:
    echo
«Вы указали несуещствующие узлы дерева»;
    break;
  default:
    
trigger_error(Invalid function result (.$r.));
    echo
«На сервере произошла внутренняя ошибка.»;
}

?>

Детали реализации

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

Функция устроена таким образом, что она пытается выполнить несколько перемещений одним sql-запросом. Это может значительным образом сократить общее время перемещения всех необходимых вершин в дереве, поскольку для перемещения каждой отдельной вершины может потребоваться пересчитать значительную часть дерева, которую так же придется пересчитывать при перемещении остальных вершин.

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

Скорость построения sql-запроса в значительной степени зависит от того, на скольких разных интервалах следует произвести пересчет узлов дерева.

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

При перемещении одного узла, седует пересчитать все узлы на двух разных интервалах. При перемещении нескольких узлов, количество разных интервалов зависит от характера перемещения узлов.

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

Если перемещается некоторый узел дерева А, а потом перемещается узел В, который в исходном дереве был родительским для узла А, то при перемещении узла В потребуется произвести пересчет не по двум дополнительным разным интервалам, а уже по трем дополнительным разным интервалам (интервал для узла В раньше был одним интервалом, который включал в себя интервал для узла А, а теперь это два разных интервала + отдельный интервал для узла А). Не сложно посчитать, на скольких разных интервалах нужно будет пересчитать дерево, если потребуется так же переместить узел С, который в исходном дереве являлся родительским для узла В.

Экспериментальным путем установлено, что в наихудшем случае (когда по всему дереву случайные вершины перемещаются в случайных направлениях; дерево маленькое, в нем содержится всего 1000 вершин) функция не будет вызывать замедления процесса перемещения, если количество разных интервалов, на которых следует произвести пересчет узлов, не превышает 70. Функция устроена таким образом, что при превышении этого лимита она генерирует новый sql-запрос.

В большинстве реальных случаев, однако, перемещения будут выполняться одним sql-запросом. Ограничение «70 разных интервалов» означает, что за один проход перемещается порядка 30-40 узлов в разных направлениях. Если же узлы перемещаются в одном направлении, есть варианты, когда узлы были и остаются смежными, то количество узлов, которые можно переместить, не превысив это ограничение, возрастает.

Кроме того, если общее число узлов в дереве не превышает 36, то любое количество перемещений в любых направлениях будет выполнено за один проход, поскольку для такого дерева максимальное количество принципиально возможных разных интервалов равно 70 (для каждого узла - левое и правое значение; корневой узел не может быть перемещен, и поэтому не учитывается).

Скачать

Библиотека функций для работы с деревьями:
zip-архив, 21 155 байт:
скачать с этого сайта
скачать с зеркала

Разработчикам

Полнофункциональный бесплатный framework на php + mysql с открытыми исходными кодами, который может быть использован для создания интернет-портала:
почитать о возможностях и скачать

Последняя модификация: 29.08.05 17:29

Обсуждение статьи в форуме

Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>

02.09.05 13:10 popoff


моя модель либы как раз отличается от твоей тем, что она содержит много спец. функций, которые занимаются тока тем, чем их наделили - поэтому запросы строятся под конкретную задачу. у тебя универсальнее, у меня (должно быть) - быстрее

kvf77PHP Club форумы

Насчет скорости - вполне можно сравнить. У меня там есть автоматические тесты, можно их переделать и запустить на твоем классе.

Насчет универсальности - она не на пустом месте возникла. Исходная задача состояла в том, что для увеличения скорости обновления дерева при перемещении нескольких узлов, можно было бы обновлять дерево одним запросом. При обновлении нескольикими запросами может оказаться, что одни и те же узлы дерева обновляются несколько раз; при обновлении одним запросом они обновляются один раз - за счет этого и достигается ускорение. А так же (возможно, даже, в основном) за счет того, что индексы очень часто не используются и поэтому осуществляется проход по всему дереву. При обновлении несколькими запросами осуществляется несколько проходов.

Процедура построения запроса для переноса нескольких узлов - это довольно сложная процедура, как бы мы ни фиксировали переносимые узлы. Единственное отличие при переносе в разных направлениях (братьями, детьми, справа, слева и т.п.) состоит в том, что нужно пересчитывать дерево на разных интервалах. Определение этих интервалов - задача несравнимо более простая, чем определение пересечения интервалов: как дерево нужно было пересчитать после перемещения первой вершины и как его нужно пересчитать, если при этом переместить еще и вторую вершину. Универсальность возникла исключительно в связи с простотой задачи определения интервалов пересчета для каждого конкретного варианта перемещения.

~~~~~ 2 Сен 2005, 16:03 ~~~~~

да, я о том же - вот я как раз создал библиотеку, где каждая функция делает тока одно (максимум 2) дела. Соответственно, рассчеты запросов произведены заранее - функции подставляют в них лишь нужные данные. Это позволяет работать много быстрее, мне кажется. Вот щас выложу новую версию - если есть желание - глянь на функцию ChangePositionAll - там 4 заранее подготовленных запроса. Да, мы увеличили несколько код класса, зато скорость по идее должна также возрасти значительно, поскольку функции надо лишь выбрать нужный запрос и подставить в него данные, не требующие особых вычислений. Я пошел в своей либе по этому пути.

kvf77PHP Club форумы

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

Насколько я понял, особенность твоей либы - не в возможности перемещения (в той или иной мере это позволяют делать практически все известные мне библиотеки для работы с деревьями), а в том, что она поддерживает несколько разных баз данных.

О скорости мы не можем ничего говорить, пока у нас нет экспериментов. Мне кажется (да, собственно, об этом и в документации по MySQL написано), что основной тормоз возникает при обращении к винчестеру. Операции построения запроса на обновление дерева не обращаются к винчестеру, хоть они реализованы как у тебя (специально для конкретных типов перемещения и для перемещения одной вершины), хоть - как у меня (универсально и с возможностью перемещения нескольких вершин). Если речь идет об одной вершине, то виртуально я могу предположить, что по времени отличие будет не слишком большое. На современных машинах, тем более с учетом того, что операция перемещения выполняется крайне редко - это вообще просто никакое время.

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

На вскидку (очень приблизительно, мог некоторые важные детали не учесть) я мог бы предложить формулу типа

T=O(n^2),

где
n - это количество интервалов

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

n=O(2*x),

где
х - это количество перемещаемых вершин,

в худшем случае (когда каждая следующая перемещаемая вершина в исходном дереве является родителем предыдущей перемещенной вершины) количество интервалов можно оценить по формуле

n=O(x^2)

Просмотреть все комментарии в режиме форума. Всего комментариев: 1
Не проходите мимо! Оставьте Ваш комментарий в форуме! >>>