Nested Set for Laravel

A Laravel package for storing and querying trees (hierarchical data) in relational databases using the Nested Set Model.

This is a Lunar-maintained fork of kalnoy/nestedset by Alexander Kalnoy, kept current for modern Laravel.

Supports Laravel 12 & 13 on PHP 8.3+. If you need an older Laravel version, use the upstream kalnoy/nestedset.

What are nested sets?

Nested sets, or the Nested Set Model, are a way to effectively store hierarchical data in a relational table. From Wikipedia:

The nested set model is to number the nodes according to a tree traversal, which visits each node twice, assigning numbers in the order of visiting, and at both visits. This leaves two numbers for each node, which are stored as two attributes. Querying becomes inexpensive: hierarchy membership can be tested by comparing these numbers. Updating requires renumbering and is therefore expensive.

The model performs well when the tree is updated rarely. It is tuned to be fast at fetching related nodes, which makes it ideal for things like multi-depth menus or shop categories.

Requirements

PHP 8.3+
Laravel 12 or 13

It is strongly recommended to use a database that supports transactions (such as MySQL's InnoDB or PostgreSQL) to protect the tree from corruption during updates.

Installation

composer require lunarphp/nestedset

The schema

Add the nested set columns to your table with the nestedSet() Blueprint macro:

Schema::create('table', function (Blueprint $table) {
    // ...
    $table->nestedSet();
});

// To drop the columns:
Schema::table('table', function (Blueprint $table) {
    $table->dropNestedSet();
});

The model

Add the Lunar\Nestedset\NodeTrait trait to your model to enable nested sets:

use Illuminate\Database\Eloquent\Model;
use Lunar\Nestedset\NodeTrait;

class Category extends Model
{
    use NodeTrait;
}

Documentation

Suppose we have a model Category. A $node variable is an instance of that model and the node we are manipulating. It can be a fresh model or one loaded from the database.

Relationships

A node has the following relationships, which are fully functional and can be eager-loaded:

Node belongs to parent
Node has many children
Node has many ancestors
Node has many descendants

Inserting nodes

Moving and inserting nodes runs several database queries, so it is highly recommended to wrap these operations in a transaction. Transactions are not started automatically.

Structural manipulations are deferred until you call save() on the model. Some methods call save() implicitly and return the boolean result of the operation.

A successful save() does not necessarily mean the node was moved. If your application depends on whether the node actually changed position, use hasMoved():

if ($node->save()) {
    $moved = $node->hasMoved();
}

Creating nodes

When you create a node without specifying a parent, it is appended to the end of the tree as a root (a node without a parent):

Category::create($attributes); // Saved as root

$node = new Category($attributes);
$node->save(); // Saved as root

Making a node a root

// Implicit save
$node->saveAsRoot();

// Explicit save
$node->makeRoot()->save();

The node is appended to the end of the tree.

Appending and prepending to a parent

To make a node a child of another node, you can make it the last or first child. In the following examples, $parent is an existing node.

There are several ways to append a node:

// #1 Using deferred insert
$node->appendToNode($parent)->save();

// #2 Using the parent node
$parent->appendNode($node);

// #3 Using the parent's children relationship
$parent->children()->create($attributes);

// #4 Using the node's parent relationship
$node->parent()->associate($parent)->save();

// #5 Using the parent attribute
$node->parent_id = $parent->id;
$node->save();

// #6 Using the static method
Category::create($attributes, $parent);

And a couple of ways to prepend:

// #1
$node->prependToNode($parent)->save();

// #2
$parent->prependNode($node);

Inserting before or after a node

You can make $node a neighbor of the $neighbor node. $neighbor must exist; the target node may be fresh. If the target node exists, it is moved to the new position and its parent is changed if required.

// Explicit save
$node->afterNode($neighbor)->save();
$node->beforeNode($neighbor)->save();

// Implicit save
$node->insertAfterNode($neighbor);
$node->insertBeforeNode($neighbor);

Building a tree from an array

When you call the static create method, it checks whether the attributes contain a children key. If they do, it creates the child nodes recursively:

$node = Category::create([
    'name' => 'Foo',
    'children' => [
        [
            'name' => 'Bar',
            'children' => [
                ['name' => 'Baz'],
            ],
        ],
    ],
]);

$node->children now contains the list of created child nodes.

Rebuilding a tree from an array

You can rebuild a tree, which is useful for mass-changing its structure:

Category::rebuildTree($data, $delete);

$data is an array of nodes:

$data = [
    ['id' => 1, 'name' => 'foo', 'children' => [ /* ... */ ]],
    ['name' => 'bar'],
];

The node named foo has an id, so the existing node is filled and saved. If the node does not exist, a ModelNotFoundException is thrown. Its children are processed in the same way and saved as children of foo.

The node named bar has no primary key, so it is created.

$delete controls whether existing nodes that are not present in $data are deleted. By default, nodes are not deleted.

Rebuilding a subtree

You can constrain rebuilding to the descendants of a given node:

Category::rebuildSubtree($root, $data);

Retrieving nodes

In some examples below, $id is the primary key of the target node.

Ancestors and descendants

Ancestors form the chain of parents up to a node — useful for breadcrumbs. Descendants are all nodes in a subtree: children, children of children, and so on.

Both can be eager-loaded:

$node->ancestors;
$node->descendants;

You can also load them with a custom query:

$result = Category::ancestorsOf($id);
$result = Category::ancestorsAndSelf($id);
$result = Category::descendantsOf($id);
$result = Category::descendantsAndSelf($id);

In most cases you want ancestors ordered by level:

$result = Category::defaultOrder()->ancestorsOf($id);

Ancestors can be eager-loaded for breadcrumbs:

$categories = Category::with('ancestors')->paginate(30);

@foreach ($categories as $category)
    <small>{{ $category->ancestors->count() ? implode(' > ', $category->ancestors->pluck('name')->toArray()) : 'Top Level' }}</small><br>
    {{ $category->name }}
@endforeach

Siblings

Siblings are nodes that share the same parent:

$result = $node->getSiblings();
$result = $node->siblings()->get();

Next siblings:

// The sibling immediately after the node
$result = $node->getNextSibling();

// All siblings after the node
$result = $node->getNextSiblings();

// All siblings after the node, as a query
$result = $node->nextSiblings()->get();

Previous siblings:

// The sibling immediately before the node
$result = $node->getPrevSibling();

// All siblings before the node
$result = $node->getPrevSiblings();

// All siblings before the node, as a query
$result = $node->prevSiblings()->get();

Getting related models from another table

Imagine each category has many goods (a HasMany relationship). To get all goods of $category and every one of its descendants:

// Get the ids of the descendants
$categories = $category->descendants()->pluck('id');

// Include the category's own id
$categories[] = $category->getKey();

// Get the goods
$goods = Goods::whereIn('category_id', $categories)->get();

Including node depth

To know the level of a node:

$result = Category::withDepth()->find($id);

$depth = $result->depth;

Root nodes are at level 0, their children at level 1, and so on.

To get nodes at a specific level, apply a having constraint:

$result = Category::withDepth()->having('depth', '=', 1)->get();

Note: this will not work in database strict mode.

Default order

Nodes are organized internally, but no order is applied by default, so they may appear in an arbitrary order. This does not affect displaying a tree, and you are free to order nodes alphabetically or by another index.

When hierarchical order is essential (it is required for retrieving ancestors and useful for ordering menu items), apply defaultOrder:

$result = Category::defaultOrder()->get();

Reversed order:

$result = Category::reversed()->get();

To shift a node up or down among its siblings, affecting the default order:

$bool = $node->down();
$bool = $node->up();

// Shift the node down by 3 siblings
$bool = $node->down(3);

The return value is a boolean indicating whether the node changed position.

Constraints

Various constraints can be applied to the query builder:

whereIsRoot() — only root nodes
hasParent() — only non-root nodes
whereIsLeaf() — only leaves
hasChildren() — only non-leaf nodes
whereIsAfter($id) — every node (not just siblings) after the node with the given id
whereIsBefore($id) — every node before the node with the given id

Descendant constraints:

$result = Category::whereDescendantOf($node)->get();
$result = Category::whereNotDescendantOf($node)->get();
$result = Category::orWhereDescendantOf($node)->get();
$result = Category::orWhereNotDescendantOf($node)->get();
$result = Category::whereDescendantAndSelf($id)->get();

// Include the target node in the result set
$result = Category::whereDescendantOrSelf($node)->get();

Ancestor constraints:

$result = Category::whereAncestorOf($node)->get();
$result = Category::whereAncestorOrSelf($id)->get();

$node can be either a primary key or a model instance.

Building a tree

After fetching a set of nodes, you can convert it into a tree:

$tree = Category::get()->toTree();

This fills the parent and children relationships on every node so you can render the tree recursively:

$nodes = Category::get()->toTree();

$traverse = function ($categories, $prefix = '-') use (&$traverse) {
    foreach ($categories as $category) {
        echo PHP_EOL.$prefix.' '.$category->name;

        $traverse($category->children, $prefix.'-');
    }
};

$traverse($nodes);

This outputs something like:

- Root
-- Child 1
--- Sub child 1
-- Child 2
- Another root

Building a flat tree

You can also build a flat tree: a list of nodes where each child node immediately follows its parent. This is helpful when nodes have a custom order (e.g. alphabetical) and you want to avoid recursion:

$nodes = Category::get()->toFlatTree();

The previous example then outputs:

Root
Child 1
Sub child 1
Child 2
Another root

Getting a subtree

Sometimes you only need a subtree rather than the whole tree:

$root = Category::descendantsAndSelf($rootId)->toTree()->first();

In a single query this gets a subtree root and all of its descendants, accessible via the children relation.

If you don't need the $root node itself:

$tree = Category::descendantsOf($rootId)->toTree($rootId);

Deleting nodes

To delete a node:

$node->delete();

Important: any descendants the node has are also deleted.

Important: nodes must be deleted as models. Do not delete them with a query like the following — it will break the tree:
Category::where('id', '=', $id)->delete(); // DON'T

The SoftDeletes trait is supported, including at the model level.

Helper methods

$bool = $node->isDescendantOf($parent);
$bool = $node->isRoot();
$bool = $node->isChildOf($other);
$bool = $node->isAncestorOf($other);
$bool = $node->isSiblingOf($other);
$bool = $node->isLeaf();

Checking consistency

Check whether a tree is broken (has structural errors):

$bool = Category::isBroken();

Get error statistics:

$data = Category::countErrors();

The returned array has the following keys:

oddness — nodes with a wrong set of lft/rgt values
duplicates — nodes that share a lft or rgt value
wrong_parent — nodes with a parent_id that doesn't match their lft/rgt values
missing_parent — nodes with a parent_id pointing to a node that doesn't exist

Fixing a tree

A broken tree can be fixed. Using the inheritance information from the parent_id column, the correct _lft and _rgt values are set for every node:

Category::fixTree();

// Or constrain it to a subtree:
Category::fixSubtree($root);

Customising the query

If your model defines a global scope that interferes with the integrity checks (for example one that adds columns or self-join-unsafe where clauses), pass a callback to customise the query used by isBroken(), countErrors(), getTotalErrors(), fixTree() and fixSubtree(). The most common use is dropping a global scope:

Category::isBroken(fn ($query) => $query->withoutGlobalScopes());

Category::fixTree(null, fn ($query) => $query->withoutGlobalScopes());

Scoping

Imagine you have Menu and MenuItem models with a one-to-many relationship, where MenuItem has a menu_id attribute and uses nested sets. You'd want to process each tree separately based on menu_id. To do so, declare the scope attribute on the model:

protected function getScopeAttributes()
{
    return ['menu_id'];
}

Now, to run a custom query, you must provide the attributes used for scoping:

MenuItem::scoped(['menu_id' => 5])->withDepth()->get(); // OK
MenuItem::descendantsOf($id)->get();                     // WRONG: returns nodes from other scopes
MenuItem::scoped(['menu_id' => 5])->fixTree();           // OK

When requesting nodes from a model instance, scopes are applied automatically based on that instance's attributes:

$node = MenuItem::findOrFail($id);

$node->siblings()->withDepth()->get(); // OK

To get a scoped query builder from an instance:

$node->newScopedQuery();

Scoping and eager loading

Always use a scoped query when eager loading:

MenuItem::scoped(['menu_id' => 5])->with('descendants')->findOrFail($id); // OK
MenuItem::with('descendants')->findOrFail($id);                           // WRONG

Migrating existing data

Migrating from another nested set extension

If your previous extension used a different set of columns, override these methods on your model:

public function getLftName()
{
    return 'left';
}

public function getRgtName()
{
    return 'right';
}

public function getParentIdName()
{
    return 'parent';
}

// Map the parent id attribute mutator
public function setParentAttribute($value)
{
    $this->setParentIdAttribute($value);
}

Migrating from basic parentage info

If your tree only has parent_id information, add the two nested set columns to your schema:

$table->unsignedInteger('_lft');
$table->unsignedInteger('_rgt');

After setting up your model, fix the tree to populate _lft and _rgt:

MyModel::fixTree();

Contributing

Contributions are welcome. The test suite runs against SQLite, MySQL and PostgreSQL:

composer test      # run the test suite
composer lint      # check code style (Laravel Pint)
composer format    # fix code style
composer analyse   # run static analysis (Larastan)

See CONTRIBUTING.md for details, and CHANGELOG.md for release notes.

License

Released under the MIT license.

Name		Name	Last commit message	Last commit date
Latest commit History 15 Commits
.github/workflows		.github/workflows
resources/boost/guidelines		resources/boost/guidelines
src		src
tests		tests
.gitignore		.gitignore
CHANGELOG.md		CHANGELOG.md
CONTRIBUTING.md		CONTRIBUTING.md
LICENSE.md		LICENSE.md
README.md		README.md
UPGRADE.md		UPGRADE.md
composer.json		composer.json
phpstan-baseline.neon		phpstan-baseline.neon
phpstan.neon		phpstan.neon
phpunit.xml		phpunit.xml
pint.json		pint.json

Folders and files

Latest commit

History

Repository files navigation

Nested Set for Laravel

Contents

What are nested sets?

Requirements

Installation

The schema

The model

Documentation

Relationships

Inserting nodes

Creating nodes

Making a node a root

Appending and prepending to a parent

Inserting before or after a node

Building a tree from an array

Rebuilding a tree from an array

Rebuilding a subtree

Retrieving nodes

Ancestors and descendants

Siblings

Getting related models from another table

Including node depth

Default order

Constraints

Building a tree

Building a flat tree

Getting a subtree

Deleting nodes

Helper methods

Checking consistency

Fixing a tree

Customising the query

Scoping

Scoping and eager loading

Migrating existing data

Migrating from another nested set extension

Migrating from basic parentage info

Contributing

License

About

Resources

License

Contributing

Uh oh!

Stars

Watchers

Forks

Releases 1

Contributors

Uh oh!

Languages