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

12/3/2014 - 9:10 AM

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

Rendered
Source

#Волшебный 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. Удачи!

ссылки по теме:
рекурсивная функция
ссылочная рекурсия

Cacher is the code snippet organizer for pro developers

We empower you and your team to get more done, faster

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