私はERPシステムの開発に参加しています。詳細については説明しません。これは、7つのシールの背後にある秘密ですが、1つだけ言います。ツリーのようなディレクトリがたくさんあり、そのネストは制限されていません。数千の数もありますが、コードとパフォーマンスの両方の観点から、可能な限り効率的かつ便利にそれらを操作する必要があります。
私たちは何が必要なのか
木の切り株とその枝に、親まで、そして葉まですばやく到達します
葉を除くすべてのノードに到達することもできます
ツリーは一貫している必要があります。親階層に欠落しているノードはありません
マテリアライズドパスは自動的に作成する必要があります
ノードを移動または削除すると、すべての子ノードも更新され、それらのパスが再構築されます
フラットコレクションから学び、すばやくツリーを構築します。
ディレクトリがたくさんあるので、コンポーネントは再利用可能でなければなりません。
それをgithubに持っていくことが計画されているので、抽象化とインターフェースを使用してください。
Postgresを使用しているため、選択はltreeに委ねられました。記事の最後で、それが何であるかについて詳しく読むことができます。
拡張機能のインストール
拡張機能を作成するための移行例
<?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');
}
}
仕事
たとえば、製品と製品カテゴリがあります。カテゴリはツリーを表し、下位のカテゴリを持つことができます。ネストレベルは無制限で、任意のレベルにすることができます。これらがテーブルだとしましょう。
商品のカテゴリー(カテゴリー)
id |
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 /
SPAがある場合は、LTreeResourceおよびLTreeResourceCollectionリソースを使用します
学習のためのリソース
https://postgrespro.ru/docs/postgresql/13/ltree-Postgres拡張機能の説明と例およびロシア語
https://www.postgresql.org/docs/13/ltree.html-オリジナルのマニュアルを読みたい人のために
ご清聴ありがとうございました。