greabock/Смежные вершины.md

## Смежные вершины.md

      
    Raw
  

              Смежные вершины.md
            
          
    #Волшебный Eloquent
И снова здравствуйте! Помните я говорил, что хочу рассказать в следющей статье о выборке данных? Так вот - я соврал.
Нет, я по-прежнему хочу рассказать о практической работе с моделями... но люди из нашего дружного чата убедили меня, что пока еще рано и тема сисек стрктур данных раскрыта не доконца. А ведь все мы прекрасно знаем, как (до зуда в пятой точке) неприятно, когда остается некая недосказанность...


Итак... Я все же засскажу о выборке, но касаться это будет древовидных структур.
##Часть вторая."Ландшафтный Дизайн" или "Будни Садовода"
И так древовидные структуры...
Они же - замыкающиеся связи.

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

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

К сожаелению,  Laravel не предоставяет решений для древовидных структур из коробки.
#Конец

Нет! Ну конечно же не конец! Мне еще есть что вам сказать.

Во-первых: есть множество готовых пакетов для работы с различными древовидными структурами.

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

Ниже я привожу четыре, известных мне, типа древовидных структур (далее - "ДС"):

Adjасency Lists
Matherialized Path
Closure Table
Nested Sets

Начнем выращивать деревья?
####Глава первая. Adjаcency Lists
Первый тип - AL (смежные списки), это отец всех древовидных структур. Он прост и понятен настолько, насколько это вообще возможно.
У каждого из вас есть отчество, верно? Ну если Вы не уроженец Объединенного Пиндостана, конечно. Так вот Ваше отчество - это что-то вроде внешнего ключа на общую "таблицу людей". Это указание на Вашего родителя. Стоп. Так вы же и сами из "таблицы людей"? Нет? Хм... странно. И все же, предположим, что вы - человеки. Тогда внешний ключ отчества из вашей таблицы людей ссылается на идентификатор человека - вашего родителя - в вашей же таблице. То есть - замыкается. Это именно то, почему ДС иногда называют замыкающимися связями. Таблица в этом случае будет выглядеть так:


id
name
parent_id


1
God
null


2
Adam
1


3
Cain
2


4
Abel
2


5
Seth
2


6
Enoch
3


7
Enos
5


Модель:
class Client extends Eloquent{
  
    public function children()
    {
        return $this->hasMany('Client', 'parent_id', 'id');
    }
    
     public function parent()
    {
        return $this->belongsTo('Client', 'parent_id', 'id');
    }
    
}

Как видно из структуры модели, мы можем выбрать детей для родителя, или родителя для ребенка, используя соответствующие методы children() (дети) и parent() (родитель).  Еще мы можем легко переместить всю ветвь дерева, просто поменяв родителя у корня ветви. Кроме того, мы можем выбрать все записи дерева и построить из них дерево основываясь на полях id и parent_id, используя рекурсивную функцию, или построив ссылочную рекурсию.

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

Здесь все довольно очевидно.
/**
* Внимание! НЕ ДЕЛАЙТЕ ТАК! 
**/

use Illuminate\Database\Eloquent\Collection as Collection;

class Client extends Eloquent{

    public function getDescendants($id = null)
	{
		if( ! isset($this->descendants) ) $this->descendants = new Collection;
		if( ! $id) $id = $this->id;
		
		foreach($this->whereParentId($id)->get() as $object)
		{
			$this->descendants->add($object);
			$this->getDescendants($object->id); // рекурсия внутри цикла
		}
		
		return $this->descendants;
	}
}
Сложность вычисления алгоритма зашкаливает. Фактически, каждый выбраный элемент генерирует новый запрос в базу данных, если у него есть дети, то для каждого из них генерируется новый запрос и т.д.
$client = Client::find(1);
$descendants = $client->getDescendants();


Вывод: так делать нельзя.
Путь второй: рекурсивная выборка по слоям
Давайте немного уменьшим количество запростов к бд...
/**
* Так делать можно... иногда.
**/
use Illuminate\Database\Eloquent\Collection as Collection; 

class Client extends Eloquent{

    public function getDescendants( array $ids = [] )
    {
		if( ! isset($this->descendants) ) $this->descendants = new Collection;

		if( ! $ids ) $ids = [$this->id];

		$nestedIds = [];
        
		foreach($this->whereIn('parent_id', $ids)->get() as $object)
		{
				$this->descendants->add($object);
				
				$nestedIds[] = $object->id;
		}
        
		if( $nestedIds ) $this->getDescendants($nestedIds);
        
		return $this->descendants;
	}
    
}
Ну вот, теперь из полей id полученых клиентов формируется массив, и для кажого уровня вложенности генерируется лишь один запрос... Тоесть сложность алгоритма зависит от количества уровней вложеннности.
$client = Client::find(1);
$descendants = $client->getDescendants();


Для небольшой вложенности, вполне себе приемлемый вариант.
Путь третий: составление рекурсивного  запроса

И все же, есть вариант, вытащить все записи одним запросом... но с некоторыми оговорками...
Во-первых, нужно заранее знать конечную степень вложенности.

Во-вторых, степень вложенности может быть ограничена настройками/возможностями бд.
В-третьих, может случиться так, что сам запрос будет работать медленнее чем несколько запросов попроще.
use Illuminate\Database\Eloquent\Collection as Collection; 

class Client extends Eloquent{
    public function getDescendants($levels = 0, $id = null)
	{
		if( ! $id) $id = $this->id;

		$base = "SELECT * FROM `clients` WHERE `parent_id` = $id";
		
		if ( $levels > 1)
		{
			$subRequests = [];
			$outer = '( SELECT * FROM `clients` WHERE `parent_id` IN %nested% )';
			$inner = "( SELECT `id` FROM `clients` WHERE `parent_id` = $id )";
			
			if($levels > 2)
			{
				$core =  '( SELECT `id` FROM `clients` WHERE `parent_id` IN %nested% )';
				$tempInner = $inner;
				
				for($i = $levels-2; $i > 0; $i--)
				{
					$subRequests[] = str_replace('%nested%', str_replace('%nested%',  $tempInner, $core), $outer);
					$tempInner = str_replace('%nested%', $temp, $core);
				}
			}
			$subRequests[] = str_replace('%nested%', $inner, $outer);
			$subRequests[] = '( '. $base . ')';

			$base = implode(' UNION ALL ', $subRequests);

			$base .= ' ORDER BY `id`';
		}

		$this->descendants = new Collection;
		
		return $this->descendants->make(DB::select($base));
	}
}
Эм... как бы вам это объяснить? :) Это велосипедистый костыль на UNION'ax...
Он формирует множество вложенных подзапросов вида:
( SELECT * FROM `clients` WHERE `parent_id` = 1 )
UNION ALL
( SELECT * FROM `clients` WHERE `parent_id` IN
    ( SELECT `id` FROM `clients` WHERE `parent_id` = 1 ))
UNION ALL
 ( SELECT * FROM `clients` WHERE `parent_id` IN 
    ( SELECT `id` FROM `clients` WHERE `parent_id` IN
        ( SELECT `id` FROM `clients` WHERE `parent_id` = 1 )))
// И так далее...
Чем больше уровней вложенности, тем длиннее запрос.
$client = Client::find(1);
$descendants = $client->getDescendants(3); //где 3 - это уровень вложенности.


Как я и говорил: костыльно, но зато одним запросом.
Кроме того, я не раз слышал, что подобный запрос можно реализовать на JOIN'ax, но сам я сходу не додумался как это сделать, а пятиминутное гугление не принесло плодов. Если есть читатели, которые знают как это сделать при помощи оператора JOIN, то пусть отпишутся в комментариях.
Updated:
поступила инфа, что финальный запрос на JOIN'ax должен выглядеть приблизительно так:
SELECT *
FROM clients AS l1
LEFT JOIN clients AS l2 ON l2.parent_id = l1.id
LEFT JOIN clients AS l3 ON l3.parent_id = l2.id
WHERE l1.parent_id = 1
результат выборки:


Правда, построить дерево из такой структуры не так легко. (кореспондент - VladShcherbin)

Ну а теперь, на сладкое, немного волшебства от Big-Shark'a...
Путь четвертый: средствами Eloquent
Client::with('children.children.children')->find(1);

По дополнительному запросу, для каждого уровня вложенности. Ну и как видно из кода, конечная вложенность должна быть известна.
Из плюсов, можно отметить, что на выходе получается уже готовое дерево.
#####Добавление элементов
Осуществляется без проблем, простым указанием parent_id. В Laravel можно использовать метод associate();
#####Перемещение ветвей
Это самая простая операция, возможная в AL. У корня ветви просто меняется parent_id. Все готово.
#####Удаление ветвей
Собираем id всех потомков в массив и делаем Client::whereIn('id', $ids)->delete().
Если в реляционной таблице установлен on delete cascade то достаточно удалить сам корень.
###заключение
Мы рассмотрели самую базовую ДС.  Все прочие структуры используют ее в той или иной степени. В следующей главе разговор пойдет о Matherialized Path. Удачи!

ссылки по теме:

рекурсивная функция

ссылочная рекурсия