Дерево

class Cake\ORM\Behavior\TreeBehavior

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

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

TreeBehavior („Поведение деревьев“) помогает вам поддерживать иерархическую структуру данных в базе данных. Структура может быть запрошена без значительных издержек и помогает восстановить данные дерева для поиска и отображения процессов.

Требования

Это поведение требует наличия следующих столбцов в таблице БД:

  • parent_id (nullable) Столбец, содержащий идентификатор родительской строки
  • lft (integer, signed) Столбец, используется для поддержания древовидной структуры
  • rght (integer, signed) Столбец, используется для поддержания древовидной структуры

Вы можете изменить имена этих полей, если это вам нужно.

Более подробную информацию о значении полей и их использовании можно найти в этой статье, описывающей логику MPTT

Предупреждение

TreeBehavior, пока что, не поддерживает составные первичные ключи.

Быстрый тур

Активируется TreeBehavior, добавлением его в таблицу, в которой вы хотите сохранить иерархические данных, следующим образом:

class CategoriesTable extends Table
{
    public function initialize(array $config)
    {
        $this->addBehavior('Tree');
    }
}

После добавления, вы уже можете позволить CakePHP построить внутреннюю структуру, если в вашей таблице уже есть несколько строк:

$categories = TableRegistry::get('Categories');
$categories->recover();

Вы можете проверить, работает ли TreeBehavior, например, выбрав из таблицы любую строку и запросив количество её потомков:

$node = $categories->get(1);
echo $categories->childCount($node);

Получение „плоского“ списка потомков для узла так же просто:

$descendants = $categories->find('children', ['for' => 1]);

foreach ($descendants as $category) {
    echo $category->name . "\n";
}

Если вам необходимо пройтись по списку потомков, используя нужные вам условия, то сделайте это используя стандартный синтаксис SQL:

$descendants = $categories
    ->find('children', ['for' => 1])
    ->where(['name LIKE' => '%Foo%']);

foreach ($descendants as $category) {
    echo $category->name . "\n";
}

Если вам нужен „потоковый“ список, где дети для каждого узла вложены в иерархии, то вы можете использовать „threaded“ («резьбовой») поиск:

$children = $categories
    ->find('children', ['for' => 1])
    ->find('threaded')
    ->toArray();

foreach ($children as $child) {
    echo "{$child->name} has " . count($child->children) . " direct children";
}

Для прохождения по результам возвращённым с использованием „threaded“ поиска, обычно требуются рекурсивные функции, но если вам требуется только набор результатов, содержащий одно поле с каждого уровня, чтобы вы могли отобразить список, например, в HTML-элементе, лучше использовать поиск „treeList“ („Список деревьев“):

$list = $categories->find('treeList');

// В файле шаблона CakePHP:
echo $this->Form->control('categories', ['options' => $list]);

// Или вы можете выводить его в виде обычного текста, например, в скрипте CLI
foreach ($list as $categoryName) {
    echo $categoryName . "\n";
}

Вывод будет аналогичен:

My Categories
_Fun
__Sport
___Surfing
___Skating
_Trips
__National
__International

Инструмент treeList принимает несколько параметров:

  • keyPath: Путь, разделенный точками, для выбора поля, для использования ключа массива, или замыкание, чтобы вернуть ключ из предоставленного ряда.
  • valuePath: Путь, разделенный точками, для получения поля, для использования значения ключа массива, или замыкание, чтобы вернуть ключ из предоставленной строки.
  • spacer : Cтрока, которая будет использоваться в качестве префикса для обозначения глубины в дереве для каждого элемента

Пример использования опций:

$query = $categories->find('treeList', [
    'keyPath' => 'url',
    'valuePath' => 'id',
    'spacer' => ' '
]);

Одна очень общая задача - найти путь дерева от определенного узла к корню дерева. Это полезно, например, для добавления списка „breadcrumbs“ („Хлебных крошек“) для показа структуры меню:

$nodeId = 5;
$crumbs = $categories->find('path', ['for' => $nodeId]);

foreach ($crumbs as $crumb) {
    echo $crumb->name . ' > ';
}

Деревья, созданные с помощью TreeBehavior, не могут быть отсортированы по какому-либо столбцу. Столбец lft, нужен, так как, внутреннее представление дерева зависит от этой сортировки. К счастью, вы можете изменить порядок узлов на одном уровне без необходимости смены родителя:

$node = $categories->get(5);

// Переместим узел, чтобы он отображался на одну позицию вверх, при отображении дочерних элементов.
$categories->moveUp($node);

// Переместим узел в верхнюю часть списка, текущего уровня.
$categories->moveUp($node, true);

// Переместим узел в самый низ.
$categories->moveDown($node, true);

Конфигурация

Если имена столбцов, по умолчанию, используемые TreeBehavior, не соответствуют вашим собственным схемам, вы можете указать им псевдонимы:

public function initialize(array $config)
{
    $this->addBehavior('Tree', [
        'parent' => 'ancestor_id', // Используйте это вместо parent_id
        'left' => 'tree_left', // Используйте это вместо lft
        'right' => 'tree_right' // Используйте это вместо rght
    ]);
}

Уровень узла (Глубина)

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

$this->addBehavior('Tree', [
    'level' => 'level', // По умолчанию значение null, то есть без сохранения уровня
]);

Если вы не хотите кэшировать уровень с помощью поля db, вы можете использовать TreeBehavior::getLevel() - метод для получения уровня узла.

Область видимости и несколько деревьев

Иногда у вас есть необходимость сохранить более одной древовидной структуры внутри одной и той же таблицы, и вы можете это сделать, используя конфигурацию „scope“. Например, для таблицы „locations“ (местоположений), вы можете создать по одному дереву на страну:

class LocationsTable extends Table
{

    public function initialize(array $config)
    {
        $this->addBehavior('Tree', [
            'scope' => ['country_name' => 'Brazil']
        ]);
    }

}

В предыдущем примере, все операции дерева будут привязаны только к строкам столбца country_name и привязаны к „Brazil“. Но вы можете изменить область охвата на лету, используя функцию „config“:

$this->behaviors()->Tree->config('scope', ['country_name' => 'France']);

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

$this->behaviors()->Tree->config('scope', function ($query) {
    $country = $this->getConfigureContry(); // Выделенная функция
    return $query->where(['country_name' => $country]);
});

Восстановление с помощью настраиваемого поля сортировки

По умолчанию, функция restore() сортирует элементы с использованием первичного ключа. Это отлично работает если это числовой (auto increment) столбец, но может привести к странным результатам, если вы использовали UUID.

Если вам нужна специальная сортировка для восстановления, вы можете установить пользовательский порядок показа в вашей конфигурации:

$this->addBehavior('Tree', [
    'recoverOrder' => ['country_name' => 'DESC'],
]);

Сохранение иерархии данных

При использовании поведения Tree вам обычно не нужно беспокоиться о внутреннем представление иерархической структуры. Позиции, где узлы помещаются в дерево, выводятся из столбца „parent_id“ в каждом из ваших объектов:

$aCategory = $categoriesTable->get(10);
$aCategory->parent_id = 5;
$categoriesTable->save($aCategory);

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

Вы можете сделать узел корнем дерева, установив столбец „parent_id“ в ноль:

$aCategory = $categoriesTable->get(10);
$aCategory->parent_id = null;
$categoriesTable->save($aCategory);

Дети, для нового корневого узла, будут сохранены.

Удаление узлов

Удаление узла и всего его поддерева (любые дочерние элементы, которые он может иметь на любой глубине в нутри дерева) тривиально:

$aCategory = $categoriesTable->get(10);
$categoriesTable->delete($aCategory);

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

$aCategory = $categoriesTable->get(10);
$categoriesTable->removeFromTree($aCategory);
$categoriesTable->delete($aCategory);

Все дочерние узлы будут сохранены, и им будет назначен новый родитель.

Удаление узла основано на левом и правом значениях объекта. Это важно отметить, когда цикл проходит через различные дочерние узлы для проверки условия для удаления:

$descendants = $teams->find('children', ['for' => 1]);

foreach ($descendants as $descendant) {
    $team = $teams->get($descendant->id); // поиск обновленной сущности объекта
    if ($team->expired) {
        $teams->delete($team); // удаление изменяет порядок слева и справа от записей в базе данных
    }
}

TreeBehavior переупорядочивает значения lft и rght записей в таблице, когда узел удаляется. Таким образом, значения lft и rght сущностей внутри $descendants (сохраненный до операции удаления) будут неточными. Объекты должны быть загружены и изменены «на лету», чтобы предотвратить несоответствия в таблице.