🤸🏿 🤲🏽 🕴️ Wie man Freunde ltree und Laravel findet 🧀 🤦 🚗

Ich beteilige mich an der Entwicklung eines ERP-Systems, ich werde Sie nicht den Details widmen, dies ist ein Geheimnis hinter sieben Siegeln, aber ich werde nur eines sagen: Wir haben viele baumartige Verzeichnisse und ihre Verschachtelung ist nicht begrenzt. In einigen Fällen sind es mehrere Tausend, aber Sie müssen so effizient und bequem wie möglich mit ihnen arbeiten, sowohl in Bezug auf Code als auch in Bezug auf die Leistung.

Was brauchen wir

Erreichen Sie schnell alle Schnitte eines Baumes und seiner Äste, sowohl bis zu den Eltern als auch bis zu den Blättern
Auch in der Lage sein, alle Knoten außer Blättern zu erreichen
Der Baum muss konsistent sein, d.h. Es fehlen keine Knoten in der übergeordneten Hierarchie
Materialisierte Pfade sollten automatisch erstellt werden
Wenn Sie einen Knoten verschieben oder löschen, werden auch alle untergeordneten Knoten aktualisiert und ihre Pfade neu erstellt
Lernen Sie aus der flachen Sammlung und bauen Sie schnell einen Baum.
Da es viele Verzeichnisse gibt, müssen die Komponenten wiederverwendbar sein.
Verwenden Sie Abstraktionen und Schnittstellen, da geplant ist, es zum Github zu bringen.

Da wir Postgres verwenden, fiel die Wahl auf ltree. Weitere Informationen finden Sie am Ende des Artikels.

Erweiterung installieren

Beispielmigration zum Erstellen einer Erweiterung

<?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');
    }
}

Eine Aufgabe

Zum Beispiel haben wir Produkte und wir haben Produktkategorien. Kategorien stellen einen Baum dar und können untergeordnete Kategorien haben. Die Verschachtelungsebene ist unbegrenzt und kann beliebig sein. Angenommen, dies sind Tabellen.

Warengruppen (Kategorien)

Ich würde	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 /
Verwenden Sie die Ressourcen LTreeResource und LTreeResourceCollection , wenn Sie über ein SPA verfügen

Ressourcen zum Lernen

https://postgrespro.ru/docs/postgresql/13/ltree - hier Beschreibungen der Postgres-Erweiterung mit Beispielen und in russischer Sprache
https://www.postgresql.org/docs/13/ltree.html - für diejenigen, die Handbücher im Original lesen möchten

Vielen Dank für Ihre Aufmerksamkeit.

Wie man Freunde ltree und Laravel findet

Was brauchen wir

Erweiterung installieren

Eine Aufgabe

Laravel

,

Ressourcen zum Lernen

More articles: