popoff.donetsk.ua title

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

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

Следует помнить, что элементы массива $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 (для каждого узла - левое и правое значение; корневой узел не может быть перемещен, и поэтому не учитывается).

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

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

02.09.05 13:10 popoff

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

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

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

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

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

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

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

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

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

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

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

T=O(n^2),

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

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

n=O(2*x),

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

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

n=O(x^2)

URL сообщения | Ответить и цитировать