Jul 20 2015 at 15:00

Как быстро расставить lft и rgt

Invite pending

Встала задача добавить в таблицу, содержащую иерархию поля lft и rgt для более быстрого получения дочерних элементов.
Пример

Вся сложность заключается в том, что вам необходимо двигаться рекурсивно не только вниз, но и обратно вверх.
Был вариант идти рекурсивно от родителя к дочерним и обратно через SQL запросы, но это работало ОЧЕНЬ медленно.

* Лирическое отступление

Код может быть не красиво оформлен и не оптимизирован и его необходимо расценивать только как альтернатива устоявшемуся способу движения по дереву.

Для примера возьмем, то что предлагают нам в статье.

1. Нам необходим будет массив, в котором мы будем хранить ссылки на какие то участки другого массива.

# Массив содержания ссылки
$arrayLink = array();

# Массив дерева
$ArrayTree = array();

Алгоритм построения будет следующим

$ArrayExample = array(
    'Ltr'        => 0, 		# левый указатель
    'Rgt'        => 0, 		# правый указатель
    'Parent'     => 0, 		# родитель элемента
    'Child'      => array() 	# дочерние элементы
  );

  # Перебираем элементы с разбивкой на группы
  foreach( model::All()->GroupBy(100)->Elements as $iModelGroup){

  # Перебираем группу
    foreach( $iModelGroup->Elements as $iModel){

  # Если это корневой элемент
       if( $iModel->Parent->Id == 0 ){	
					$ArrayTree[$iModel->Id] = $ArrayExample;
					$arrayLink[$iModel->Id] = & $ArrayTree[$iModel->Id]['Child'];

  # Дочерние
				}else{
				
					$ParentModel = $iModel->Place;
				       
                    # Проверим на существование родителя
					if( !$ParentModel->Is ){
						continue;
					}
				
					$ArrayExample['Parent'] = $ParentModel ->Id;
					$arrayLink[$ParentModel ->Id][$iModel->Id] = $ArrayExample;
					$arrayLink[$iModel->Id] = & $arrayLink[$ParentModel ->Id][$iModel->Id]['Child'];
				}
    }
    $iModelGroup->ElementsFreeMem;
  }

Как это рабоает

$arrayLink = array(
   [parent_id [ 1 ] ] +--+
   [parent_id [ 2 ] ] +--|--+
);                       |  |
                 v-------+  |
$ArrayTree = array(         |
   array(                   |
                        <---+
   )
)

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

Ltr и Rgt мы будем высчитывать, а Parent и Child нам понадобятся для навигации внутри дерева.

Приступаем к обходу нашего массива и сохранению результата в базу данных.

Код

# Выставляем указатель в 0
		$Pointer = 0;
		
		# Если нужно, то здесь надо выставить начало транзакции
		
		# Начинаем перебирать рекурсивно дерево и будем по нему опускаться и подниматься
		foreach($ArrayTree as $id_elem => $attrs){
			$Pointer++;
			if( !empty( $attrs['Child'] ) ){
				# Начальные элементы. Опускаемся вниз
				$Model = model::Find($id_elem);
				$Model->Update(
					array(
						'Lft' => $Pointer
					)
				);
				$Model->Save();
                # Опускаемся вниз массива
				self::ReplaceToDownPointer( $ArrayTree[$id_elem]['Child'] , $arrayLink , $Pointer );
			}
			# Поднимаемся вверх по массиву
			self::ReplaceToUpPointer( $id_elem , $ArrayTree[$id_elem]['Parent'] , $arrayLink , $Pointer );
		}
		
		# Если нужно, то здесь надо выставить конец транзакции

Далее собственно пишем 2 метода

ReplaceToDownPointer и ReplaceToUpPointer

# Опускаемся рекурсивно
	static function ReplaceToDownPointer( & $array = array() , & $arrayLink = array() , & $Pointer ){
		foreach($array as $id_elem => $attrs){
			$Pointer++;
			$Model = model::Find($id_elem);
			$Model->Update(
				array(
					'Lft' => $Pointer
				)
			);
			$Model->Save();
			if( !empty( $attrs['Child'] ) ){
				self::ReplaceToDownPointer( $array[$id_elem]['Child'] , $arrayLink , $Pointer );
			}
			
			self::ReplaceToUpPointer( $id_elem , $array[$id_elem]['Parent'] , $arrayLink , $Pointer );
		}
	}
	
	# поднимаемся рекурсивно
	static function ReplaceToUpPointer( $id_elem = 0 , $parent = 0 , & $arrayLink = array() , & $Pointer ){	
		$Pointer++;
		$Model = model::Find($id_elem);
		$Model->Update(
			array(
				'Rgt' => $Pointer
			)
		);
		$Model->Save();
	}

Примерные результаты на 1000 записей по данному алгоритму
1.82 сек
9.17 Mb

По алгоритму с рекурсивным запросом дочерних элементов.
6.45 сек
45 Mb
* Этот код был написан на коленке, так как желания писать одно и то же в рабочее время не особо было.

Tags:

Hubs: