Participo en el desarrollo de un sistema ERP, no te dedicaré a detalles, este es un secreto detrás de siete sellos, pero solo diré una cosa, tenemos muchos directorios en forma de árbol y su anidamiento no es limitado, el número en algunos es de varios miles, pero es necesario trabajar con ellos de la manera más eficiente y conveniente posible, tanto en términos de código como de rendimiento.
Qué necesitamos
Alcance rápidamente cualquier corte de un árbol y sus ramas, tanto hasta los padres como hasta las hojas
También podrá llegar a todos los nodos excepto las hojas.
El árbol debe ser consistente, es decir no tienen nodos faltantes en la jerarquía principal
Los caminos materializados deben construirse automáticamente
Cuando mueve o elimina un nodo, todos los nodos secundarios también se actualizan y sus rutas se reconstruyen
Aprenda de la colección plana, construya rápidamente un árbol.
Dado que hay muchos directorios, los componentes deben ser reutilizables.
Dado que está planeado llevarlo al github, use abstracciones e interfaces.
Dado que estamos usando Postgres, la elección recayó en ltree, puede leer más sobre lo que es al final del artículo.
Instalar una extensión
Ejemplo de migración para crear una extensión
<?php
use Illuminate\Database\Migrations\Migration;
use Illuminate\Support\Facades\App;
use Illuminate\Support\Facades\DB;
class CreateLtreeExtension extends Migration
{
public function up(): void
{
DB::statement('CREATE EXTENSION IF NOT EXISTS LTREE');
}
public function down(): void
{
DB::statement('DROP EXTENSION IF EXISTS LTREE');
}
}
Una tarea
Por ejemplo, tenemos productos y tenemos categorías de productos. Las categorías representan un árbol y pueden tener categorías subordinadas, el nivel de anidación es ilimitado y puede ser cualquiera. Digamos que estas son tablas.
Categorías de bienes (categorías)
carné de identidad |
bigserial |
PK |
path |
ltree |
|
parent_id |
biginteger |
|
path ,
id: 1
path: 1
parent_id: null
id: 2
path: 1.2
parent_id: 2
..
(products)
id |
bigserial |
PK |
category_id |
biginteger |
|
Postgres, , extension, Doctrine , , composer , :
composer require umbrellio/laravel-ltree
, Postgres
<?php
use Illuminate\Database\Migrations\Migration;
use Illuminate\Support\Facades\DB;
use Illuminate\Support\Facades\Schema;
use Umbrellio\Postgres\Schema\Blueprint;
class CreateCategoryExtension extends Migration
{
public function up(): void
{
Schema::table('categories', function (Blueprint $table) {
$table->bigIncrements('id');
$table->bigInteger('parent_id')->nullable();
$table->ltree('path')->nullable();
$table
->foreign('parent_id')
->references('id')
->on('categories');
$table->index(['parent_id']);
$table->unique(['path']);
});
DB::statement("COMMENT ON COLUMN categories.path IS '(DC2Type:ltree)'");
}
public function down(): void
{
Schema::drop('categories');
}
}
, , , :
SELECT * FROM categories;
, , , , . , ltree, :
SELECT * FROM categories WHERE parent_id IS NULL
, . , , , , ID :
SELECT * FROM categories WHERE parent_id = <ID>
, , , , ltree. , , , , , :
SELECT * FROM categories WHERE path @> text2ltree('<ID>')
Laravel
, ltree. , , , .. Eloquent\Model .
: LTreeInterface
<?php
namespace Umbrellio\LTree\Interfaces;
interface LTreeInterface
{
public const AS_STRING = 1;
public const AS_ARRAY = 2;
public function getLtreeParentColumn(): string;
public function getLtreeParentId(): ?int;
public function getLtreePathColumn(): string;
public function getLtreePath($mode = self::AS_ARRAY);
public function getLtreeLevel(): int;
}
: LTreeTrait
<?php
trait LTreeTrait
{
abstract public function getAttribute($key);
public function getLtreeParentColumn(): string
{
return 'parent_id';
}
public function getLtreePathColumn(): string
{
return 'path';
}
public function getLtreeParentId(): ?int
{
$value = $this->getAttribute($this->getLtreeParentColumn());
return $value ? (int) $value : null;
}
public function getLtreePath($mode = LTreeInterface::AS_ARRAY)
{
$path = $this->getAttribute($this->getLtreePathColumn());
if ($mode === LTreeModelInterface::AS_ARRAY) {
return $path !== null ? explode('.', $path) : [];
}
return (string) $path;
}
public function getLtreeLevel(): int
{
return is_array($path = $this->getLtreePath()) ? count($path) : 1;
, LTreeInterface: Category
<?php
final class Category extends Model implements LTreeInterface
{
use LTreeTrait;
protected $table = 'categories';
protected $fillable = ['parent_id', 'path'];
protected $timestamps = false;
}
, :
: LTreeTrait
<?php
use Illuminate\Database\Eloquent\Builder;
use Illuminate\Database\Eloquent\Model;
use Illuminate\Database\Eloquent\Relations\BelongsTo;
use Illuminate\Database\Eloquent\Relations\HasMany;
use Illuminate\Database\Eloquent\SoftDeletes;
use Umbrellio\LTree\Collections\LTreeCollection;
use Umbrellio\LTree\Interfaces\LTreeModelInterface;
trait LTreeTrait
{
//...
public function scopeParentsOf(Builder $query, array $paths): Builder
{
return $query->whereRaw(sprintf(
"%s @> array['%s']::ltree[]",
$this->getLtreePathColumn(),
implode("', '", $paths)
));
}
public function scopeRoot(Builder $query): Builder
{
return $query->whereRaw(sprintf('nlevel(%s) = 1', $this->getLtreePathColumn()));
}
public function scopeDescendantsOf(Builder $query, LTreeModelInterface $model): Builder
{
return $query->whereRaw(sprintf(
"({$this->getLtreePathColumn()} <@ text2ltree('%s')) = true",
$model->getLtreePath(LTreeModelInterface::AS_STRING),
));
}
public function scopeAncestorsOf(Builder $query, LTreeModelInterface $model): Builder
{
return $query->whereRaw(sprintf(
"({$this->getLtreePathColumn()} @> text2ltree('%s')) = true",
$model->getLtreePath(LTreeModelInterface::AS_STRING),
));
}
public function scopeWithoutSelf(Builder $query, int $id): Builder
{
return $query->whereRaw(sprintf('%s <> %s', $this->getKeyName(), $id));
}
:
scopeAncestorsOf - ( )
scopeDescendantsOf - ( )
scopeWithoutSelf -
scopeRoot - 1-
scopeParentsOf - scopeAncestorsOf, .
.. , , , .
, , . - , , . , .
, , , :
<?php
// ID () = 15
$categories = Category::ancestorsOf(15)->get()->pluck('id')->toArray();
$products = Product::whereIn('category_id', $caregories)->get();
, , , .
, 1 , :
SELECT * FROM categories;
, , , , - :
<?php
$a = [
[1, '1', null],
[2, '1.2', 1],
[3, '1.2.3', 2],
[4, '4', null],
[5, '1.2.5', 2],
[6, '4.6', 4],
// ...
];
:
<?php
$a = [
0 => [
'id' => 1,
'level' => 1,
'children' => [
0 => [
'id' => 2,
'level' => 2,
'children' => [
0 => [
'id' => 3,
'level' => 3,
'children' => [],
],
1 => [
'id' => 5,
'level' => 3,
'children' => [],
],
]
]
]
],
1 => [
'id' => 4,
'level' => 1,
'children' => [
0 => [
'id' => 6,
'level' => 2,
'children' => [],
]
]
]
];
, , , :
<?php
$categories = Category::all()->toTree(); // Collection
function renderTree(Collection $collection) {
/** @var LTreeNode $item */
foreach ($collection as $item) {
if ($item->children->isNotEmpty()) {
renderTree($item->children);
return;
}
}
echo str_pad($item->id, $item->level - 1, "---", STR_PAD_LEFT) . PHP_EOL;
}
, , :
<?php
trait LTreeTrait
{
//...
public function newCollection(array $models = []): LTreeCollection
{
return new LTreeCollection($models);
}
public function ltreeParent(): BelongsTo
{
return $this->belongsTo(static::class, $this->getLtreeParentColumn());
}
public function ltreeChildren(): HasMany
{
return $this->hasMany(static::class, $this->getLtreeParentColumn());
}
}
, , , .
: LTreeCollection
<?php
use Illuminate\Database\Eloquent\Collection;
use Illuminate\Database\Eloquent\Model;
use Umbrellio\LTree\Helpers\LTreeBuilder;
use Umbrellio\LTree\Helpers\LTreeNode;
use Umbrellio\LTree\Interfaces\HasLTreeRelations;
use Umbrellio\LTree\Interfaces\LTreeInterface;
use Umbrellio\LTree\Interfaces\ModelInterface;
use Umbrellio\LTree\Traits\LTreeModelTrait;
class LTreeCollection extends Collection
{
private $withLeaves = true;
public function toTree(bool $usingSort = true, bool $loadMissing = true): LTreeNode
{
if (!$model = $this->first()) {
return new LTreeNode();
}
if ($loadMissing) {
$this->loadMissingNodes($model);
}
if (!$this->withLeaves) {
$this->excludeLeaves();
}
$builder = new LTreeBuilder(
$model->getLtreePathColumn(),
$model->getKeyName(),
$model->getLtreeParentColumn()
);
return $builder->build($collection ?? $this, $usingSort);
}
public function withLeaves(bool $state = true): self
{
$this->withLeaves = $state;
return $this;
}
private function loadMissingNodes($model): self
{
if ($this->hasMissingNodes($model)) {
$this->appendAncestors($model);
}
return $this;
}
private function excludeLeaves(): void
{
foreach ($this->items as $key => $item) {
if ($item->ltreeChildren->isEmpty()) {
$this->forget($key);
}
}
}
private function hasMissingNodes($model): bool
{
$paths = collect();
foreach ($this->items as $item) {
$paths = $paths->merge($item->getLtreePath());
}
return $paths
->unique()
->diff($this->pluck($model->getKeyName()))
->isNotEmpty();
}
private function appendAncestors($model): void
{
$paths = $this
->pluck($model->getLtreePathColumn())
->toArray();
$ids = $this
->pluck($model->getKeyName())
->toArray();
$parents = $model::parentsOf($paths)
->whereKeyNot($ids)
->get();
foreach ($parents as $item) {
$this->add($item);
}
}
}
Laravel, .. . toTree, , , children - .
, , :
<?php
$categories = Category::ancestorsOf(15)->get()->toTree();
, , - , ( ):
LTreeNode
<?php
use Illuminate\Database\Eloquent\Collection;
use Illuminate\Database\Eloquent\Model;
use InvalidArgumentException;
use Umbrellio\Common\Contracts\AbstractPresenter;
use Umbrellio\LTree\Collections\LTreeCollection;
use Umbrellio\LTree\Interfaces\LTreeInterface;
use Umbrellio\LTree\Interfaces\ModelInterface;
class LTreeNode extends AbstractPresenter
{
protected $parent;
protected $children;
public function __construct($model = null)
{
parent::__construct($model);
}
public function isRoot(): bool
{
return $this->model === null;
}
public function getParent(): ?self
{
return $this->parent;
}
public function setParent(?self $parent): void
{
$this->parent = $parent;
}
public function addChild(self $node): void
{
$this
->getChildren()
->add($node);
$node->setParent($this);
}
public function getChildren(): Collection
{
if (!$this->children) {
$this->children = new Collection();
}
return $this->children;
}
public function countDescendants(): int
{
return $this
->getChildren()
->reduce(
static function (int $count, self $node) {
return $count + $node->countDescendants();
},
$this
->getChildren()
->count()
);
}
public function findInTree(int $id): ?self
{
if (!$this->isRoot() && $this->model->getKey() === $id) {
return $this;
}
foreach ($this->getChildren() as $child) {
$result = $child->findInTree($id);
if ($result !== null) {
return $result;
}
}
return null;
}
public function each(callable $callback): void
{
if (!$this->isRoot()) {
$callback($this);
}
$this
->getChildren()
->each(static function (self $node) use ($callback) {
$node->each($callback);
});
}
public function toCollection(): LTreeCollection
{
$collection = new LTreeCollection();
$this->each(static function (self $item) use ($collection) {
$collection->add($item->model);
});
return $collection;
}
public function pathAsString()
{
return $this->model ? $this->model->getLtreePath(LTreeInterface::AS_STRING) : null;
}
public function toTreeArray(callable $callback)
{
return $this->fillTreeArray($this->getChildren(), $callback);
}
/**
* Usage sortTree(['name' =>'asc', 'category'=>'desc'])
* or callback with arguments ($a, $b) and return -1 | 0 | 1
* @param array|callable $options
*/
public function sortTree($options)
{
$children = $this->getChildren();
$callback = $options;
if (!is_callable($options)) {
$callback = $this->optionsToCallback($options);
}
$children->each(static function ($child) use ($callback) {
$child->sortTree($callback);
});
$this->children = $children
->sort($callback)
->values();
}
private function fillTreeArray(iterable $nodes, callable $callback)
{
$data = [];
foreach ($nodes as $node) {
$item = $callback($node);
$children = $this->fillTreeArray($node->getChildren(), $callback);
$item['children'] = $children;
$data[] = $item;
}
return $data;
}
private function optionsToCallback(array $options): callable
{
return function ($a, $b) use ($options) {
foreach ($options as $property => $sort) {
if (!in_array(strtolower($sort), ['asc', 'desc'], true)) {
throw new InvalidArgumentException("Order '${sort}'' must be asc or desc");
}
$order = strtolower($sort) === 'desc' ? -1 : 1;
$result = $a->{$property} <=> $b->{$property};
if ($result !== 0) {
return $result * $order;
}
}
return 0;
};
}
}
LTreeBuilder
<?php
class LTreeBuilder
{
private $pathField;
private $idField;
private $parentIdField;
private $nodes = [];
private $root = null;
public function __construct(string $pathField, string $idField, string $parentIdField)
{
$this->pathField = $pathField;
$this->idField = $idField;
$this->parentIdField = $parentIdField;
}
public function build(LTreeCollection $items, bool $usingSort = true): LTreeNode
{
if ($usingSort === true) {
$items = $items->sortBy($this->pathField, SORT_STRING);
}
$this->root = new LTreeNode();
foreach ($items as $item) {
$node = new LTreeNode($item);
[$id, $parentId] = $this->getNodeIds($item);
$parentNode = $this->getNode($parentId);
$parentNode->addChild($node);
$this->nodes[$id] = $node;
}
return $this->root;
}
private function getNodeIds($item): array
{
$parentId = $item->{$this->parentIdField};
$id = $item->{$this->idField};
if ($id === $parentId) {
throw new LTreeReflectionException($id);
}
return [$id, $parentId];
}
private function getNode(?int $id): LTreeNode
{
if ($id === null) {
return $this->root;
}
if (!isset($this->nodes[$id])) {
throw new LTreeUndefinedNodeException($id);
}
return $this->nodes[$id];
}
}
:
AbstractLTreeResource
<?php
namespace Umbrellio\LTree\Resources;
use Illuminate\Http\Resources\Json\ResourceCollection;
use Illuminate\Support\Collection;
use Umbrellio\LTree\Collections\LTreeCollection;
abstract class LTreeResourceCollection extends ResourceCollection
{
/**
* @param LTreeCollection|Collection $resource
*/
public function __construct($resource, $sort = null, bool $usingSort = true, bool $loadMissing = true)
{
$collection = $resource->toTree($usingSort, $loadMissing);
if ($sort) {
$collection->sortTree($sort);
}
parent::__construct($collection->getChildren());
}
}
AbstractLTreeResourceCollection
<?php
namespace Umbrellio\LTree\Resources;
use Illuminate\Http\Resources\Json\JsonResource;
use Umbrellio\LTree\Helpers\LTreeNode;
use Umbrellio\LTree\Interfaces\LTreeInterface;
/**
* @property LTreeNode $resource
*/
abstract class LTreeResource extends JsonResource
{
final public function toArray($request)
{
return array_merge($this->toTreeArray($request, $this->resource->model), [
'children' => static::collection($this->resource->getChildren())->toArray($request),
]);
}
/**
* @param LTreeInterface $model
*/
abstract protected function toTreeArray($request, $model);
}
, JsonResource:
CategoryResource
<?php
use Umbrellio\LTree\Helpers\LTreeNode;
use Umbrellio\LTree\Resources\LTreeResource;
class CategoryResource extends LTreeResource
{
public function toTreeArray($request, LTreeNode $model)
{
return [
'id' => $model->id,
'level' => $model->getLtreeLevel(),
];
}
}
CategoryResourceCollection
<?php
use Umbrellio\LTree\Resources\LTreeResourceCollection;
class CategoryResourceCollection extends LTreeResourceCollection
{
public $collects = CategoryResource::class;
}
, CategoryController data json:
<?php
use Illuminate\Routing\Controller;
use Illuminate\Http\Request;
class CategoryController extends Controller
{
//...
public function data(Request $request)
{
return response()->json(
new CategoryResourceCollection(
Category::all(),
['id' => 'asc']
)
);
}
}
, toTree, .. Eloquent\Builder- (get, all, first ) LtreeInterface LtreeCollection, , , .
,
, , , .
, , .
, :
id |
input |
parent_id |
select |
.. , , parent_id , . path id parent_id.
, .
path
<?php
namespace Umbrellio\LTree\Services;
use Illuminate\Database\Eloquent\Model;
use Umbrellio\LTree\Helpers\LTreeHelper;
use Umbrellio\LTree\Interfaces\LTreeModelInterface;
use Umbrellio\LTree\Interfaces\LTreeServiceInterface;
final class LTreeService implements LTreeServiceInterface
{
private $helper;
public function __construct(LTreeHelper $helper)
{
$this->helper = $helper;
}
public function createPath(LTreeModelInterface $model): void
{
$this->helper->buildPath($model);
}
public function updatePath(LTreeModelInterface $model): void
{
$columns = array_intersect_key($model->getAttributes(), array_flip($model->getLtreeProxyUpdateColumns()));
$this->helper->moveNode($model, $model->ltreeParent, $columns);
$this->helper->buildPath($model);
}
public function dropDescendants(LTreeModelInterface $model): void
{
$columns = array_intersect_key($model->getAttributes(), array_flip($model->getLtreeProxyDeleteColumns()));
$this->helper->dropDescendants($model, $columns);
}
}
createPath - path ,
updatePath - path . , path , , , .. 1000 - UPDATE - .
.. , .
dropDescendants - , , , , , , , .
getLtreeProxyDeleteColumns getLtreeProxyUpdateColumns - deleted_at, updated_at, editor_id , .
<?php
class CategoryService
{
private LTreeService $service;
public function __construct (LTreeService $service)
{
$this->service = $service;
}
public function create (array $data): void
{
$model = App::make(Category::class);
$model->fill($data);
$model->save();
//
$this->service->createPath($model);
}
}
, , , , , , + , - Deadlock.
Postgres / PHP / Laravel (, ), , , .
:
composer: umbrellio/laravel-ltree
ltree ( parent_id path -)
LTreeModelInterface LTreeModelTrait Eloquent\Model-.
LTreeService /
Utilice los recursos LTreeResource y LTreeResourceCollection si tiene un SPA
Recursos para aprender
https://postgrespro.ru/docs/postgresql/13/ltree - aquí descripciones de la extensión de Postgres, con ejemplos y en ruso
https://www.postgresql.org/docs/13/ltree.html - para aquellos a quienes les gusta leer los manuales en el original
Gracias por la atención.