Baum

翻译地址，欢迎大家一起来：
https://github.com/leienshu/baum

Baum是Laravel 5's的EloquentORM的嵌套集模式的实现。

For Laravel 4.2.x compatibility, check the 1.0.x branch branch or use the latest 1.0.x tagged release.

文档

• 关于嵌套集
• 背后的原理，TL; DR版本
• 安装
• 入门
• 用法
• 了解更多
• 贡献

关于嵌套集

嵌套集是实现有序树的智能方法，允许快速，非递归查询。 例如，无论树有多深，您都可以在单个查询中获取节点的所有后代。 缺点是插入/移动/删除需要复杂的SQL，但这是由这个包在幕后处理的！

嵌套集适用于有序树（例如菜单，电商分类）和必须有效查询的大型树（例如，threaded posts）。

有关详细信息，请参阅嵌套集的维基百科条目。 此外，这是一个很好的入门教程：https://leijingwei.com/archives/41.html

背后的原理，TL; DR版本

可视化嵌套集如何工作的一种简单方法是考虑围绕其所有子节点的父实体及其周围的父节点等。所以这个树：

root
  |_ Child 1
    |_ Child 1.1
    |_ Child 1.2
  |_ Child 2
    |_ Child 2.1
    |_ Child 2.2

可以像这样形象化：

 ___________________________________________________________________
|  Root                                                             |
|    ____________________________    ____________________________   |
|   |  Child 1                  |   |  Child 2                  |   |
|   |   __________   _________  |   |   __________   _________  |   |
|   |  |  C 1.1  |  |  C 1.2 |  |   |  |  C 2.1  |  |  C 2.2 |  |   |
1   2  3_________4  5________6  7   8  9_________10 11_______12 13  14
|   |___________________________|   |___________________________|   |
|___________________________________________________________________|

数字代表左右边界。这个表可能看起来像这样：

id | parent_id | lft  | rgt  | depth | data
 1 |           |    1 |   14 |     0 | root
 2 |         1 |    2 |    7 |     1 | Child 1
 3 |         2 |    3 |    4 |     2 | Child 1.1
 4 |         2 |    5 |    6 |     2 | Child 1.2
 5 |         1 |    8 |   13 |     1 | Child 2
 6 |         5 |    9 |   10 |     2 | Child 2.1
 7 |         5 |   11 |   12 |     2 | Child 2.2

要获取父节点的所有子节点，你可以:

SELECT * WHERE lft IS BETWEEN parent.lft AND parent.rgt

为了获得子节点的数量，你可以：

(right - left - 1)/2

为了获得子节点的数量，你可以：

SELECT * WHERE node.lft IS BETWEEN lft AND rgt

正如您所看到的那样，在普通树上递归且过于缓慢的查询突然变得非常快。 漂亮，不是吗？

安装

Baum与Laravel 5合作。 您可以使用以下命令将其添加到composer.json文件中：

"baum/baum": "~1.1"

运行 composer install 来安装它。

与大多数Laravel 5包一样，您需要注册Baum *service provider*。 进入 config/app.php 文件 添加下面一行到providers 数组中:

'Baum\Providers\BaumServiceProvider',

入门

正确安装软件包后，最简单的方法是运行提供的生成器：

php artisan baum:install MODEL

使用您计划用于嵌套集模型的类名替换上面的MODEL。

生成器将在您的应用程序中安装一个迁移和一个模型文件，该文件被配置为使用Baum提供的嵌套集行为。 您应该看看这些文件，因为每个文件都描述了如何自定义它们。

接下来，您可能会运行php artisan migrate来应用迁移。

模型配置

为了使用Baum，您必须确保您的模型类继承了Baum\Node。
最简单的方法：

class Category extends Baum\Node {

}

这是一个稍微复杂的例子，我们自定义了列名：

class Dictionary extends Baum\Node {

  protected $table = 'dictionary';

  // 'parent_id' column name
  protected $parentColumn = 'parent_id';

  // 'lft' column name
  protected $leftColumn = 'lidx';

  // 'rgt' column name
  protected $rightColumn = 'ridx';

  // 'depth' column name
  protected $depthColumn = 'nesting';

  // guard attributes from mass-assignment
  protected $guarded = array('id', 'parent_id', 'lidx', 'ridx', 'nesting');

}

请记住，显然，列名必须与数据库表中的列名匹配。

迁移配置

您必须确保支持Baum模型的数据库表具有以下列：

• parent_id: 父节点的引用 (int)
• lft: 左索引边界 (int)
• rgt: 右索引边界 (int)
• depth: 嵌套深度 (int)

这是一个迁移文件（migrations file）的例子：

class Category extends Migration {

  public function up() {
    Schema::create('categories', function(Blueprint $table) {
      $table->increments('id');

      $table->integer('parent_id')->nullable();
      $table->integer('lft')->nullable();
      $table->integer('rgt')->nullable();
      $table->integer('depth')->nullable();

      $table->string('name', 255);

      $table->timestamps();
    });
  }

  public function down() {
    Schema::drop('categories');
  }

}

您可以自由修改列名称，前提是您在迁移和模型中都进行了更改。

用法

在配置模型并运行迁移后，您现在可以将Baum与您的模型一起使用了。 以下是一些例子。

• 创建根节点
• 插入节点
• 删除节点
• 获取节点的嵌套级别
• 移动节点
• 判定节点请求
• 关系
• 根和叶范围
• 访问祖先/后代链
• 限制子节点返回的层级
• 自定义排序列
• 转储层次结构树
• 模型事件: moving and moved
• Scope 支持
• 验证
• 树重建
• 软删除
• seeding和批量赋值
• 其他功能

创建根节点

默认所有节点都是以根节点的形式创建的:

$root = Category::create(['name' => 'Root category']);

或者你也可以根据需要将节点转换为根节点:

$node->makeRoot();

或者你也可以取消parent_id列，来实现同样的功能:

// 此方法与$node->makeRoot()同效果
$node->parent_id = null;
$node->save();

插入节点

// 直接使用关系
$child1 = $root->children()->create(['name' => 'Child 1']);

// 使用`makeChildOf`方法
$child2 = Category::create(['name' => 'Child 2']);
$child2->makeChildOf($root);

删除节点

$child1->delete();

已删除节点的后代也将被删除，并且将重新计算所有lft和rgt界限。 请注意，目前，不会触发删除和删除后代的模型事件。

获取节点的嵌套级别

getLevel() 方法将返回节点的当前嵌套级别或深度。

$node->getLevel() // 节点是root的时候为0 

移动节点

Baum提供了许多方法来移动节点：

• moveLeft(): 找到左边的兄弟并向左移动。
• moveRight(): 找到右边的兄弟并向右移动。
• moveToLeftOf($otherNode): 移动到某节点左侧的节点。
• moveToRightOf($otherNode): 移动到某节点右侧的节点。
• makeNextSiblingOf($otherNode): moveToRightOf` 的别名。
• makeSiblingOf($otherNode): makeNextSiblingOf的别名。
• makePreviousSiblingOf($otherNode): moveToLeftOf的别名。
• makeChildOf($otherNode): 使这个节点成为某某的子节点。
• makeFirstChildOf($otherNode): 使这个节点成为某某的第一个子节点。
• makeLastChildOf($otherNode): makeChildOf的别名。
• makeRoot(): 使当前节点设置为根节点。

例如：

$root = Creatures::create(['name' => 'The Root of All Evil']);

$dragons = Creatures::create(['name' => 'Here Be Dragons']);
$dragons->makeChildOf($root);

$monsters = new Creatures(['name' => 'Horrible Monsters']);
$monsters->save();

$monsters->makeSiblingOf($dragons);

$demons = Creatures::where('name', '=', 'demons')->first();
$demons->moveToLeftOf($dragons);

判定节点请求

你可以使用下面的方法来询问节点的一些属性：

• isRoot(): 如果是根节点返回true。
• isLeaf(): 如果是叶节点（分支的末尾）返回true。
• isChild(): 如果是子节点返回true。
• isDescendantOf($other): 如果节点是另一个的后代，则返回true。
• isSelfOrDescendantOf($other): 如果节点是自己或后代，则返回true。
• isAncestorOf($other): 如果节点是另一个的祖先，则返回true。
• isSelfOrAncestorOf($other): 如果节点是自己或祖先，则返回true。
• equals($node): 当前节点实例等于另一个。
• insideSubtree($node): 检查给定节点是否在由左右索引定义的子树内。
• inSameScope($node): 如果给定节点与当前节点在同一范围内，则返回true。 也就是说，是否scoped属性中的每个列在两个节点中都具有相同的值。

使用上一个示例中的节点：

$demons->isRoot(); // => false

$demons->isDescendantOf($root) // => true

节点关系

Baum为您的节点提供了两种自我指导的Eloquent关系：parent和children.

$parent = $node->parent()->get();

$children = $node->children()->get();

跟节点和叶节点的范围

Baum提供了一些非常基本的查询范围来访问根节点和叶节点：

// 查询范围以所有根节点为目标
Category::roots()

// 查询范围以所有叶节点（所有分支的末尾）为目标
Category:allLeaves()

您也可能只对第一个根节点感兴趣:

$firstRootNode = Category::root();

访问祖先和后代链

There are several methods which Baum offers to access the ancestry/descendancy
chain of a node in the Nested Set tree. The main thing to keep in mind is that
they are provided in two ways:

First as query scopes, returning an Illuminate\Database\Eloquent\Builder
instance to continue to query further. To get actual results from these,
remember to call get() or first().

• ancestorsAndSelf(): Targets all the ancestor chain nodes including the current one.
• ancestors(): Query the ancestor chain nodes excluding the current one.
• siblingsAndSelf(): Instance scope which targets all children of the parent, including self.
• siblings(): Instance scope targeting all children of the parent, except self.
• leaves(): Instance scope targeting all of its nested children which do not have children.
• descendantsAndSelf(): Scope targeting itself and all of its nested children.
• descendants(): Set of all children & nested children.
• immediateDescendants(): Set of all children nodes (non-recursive).

Second, as methods which return actual Baum\Node instances (inside a Collection
object where appropiate):

• getRoot(): Returns the root node starting at the current node.
• getAncestorsAndSelf(): Retrieve all of the ancestor chain including the current node.
• getAncestorsAndSelfWithoutRoot(): All ancestors (including the current node) except the root node.
• getAncestors(): Get all of the ancestor chain from the database excluding the current node.
• getAncestorsWithoutRoot(): All ancestors except the current node and the root node.
• getSiblingsAndSelf(): Get all children of the parent, including self.
• getSiblings(): Return all children of the parent, except self.
• getLeaves(): Return all of its nested children which do not have children.
• getDescendantsAndSelf(): Retrieve all nested children and self.
• getDescendants(): Retrieve all of its children & nested children.
• getImmediateDescendants(): Retrieve all of its children nodes (non-recursive).

Here's a simple example for iterating a node's descendants (provided a name
attribute is available):

$node = Category::where('name', '=', 'Books')->first();

foreach($node->getDescendantsAndSelf() as $descendant) {
  echo "{$descendant->name}";
}

Limiting the levels of children returned

In some situations where the hierarchy depth is huge it might be desirable to limit the number of levels of children returned (depth). You can do this in Baum by using the limitDepth query scope.

The following snippet will get the current node's descendants up to a maximum
of 5 depth levels below it:

$node->descendants()->limitDepth(5)->get();

Similarly, you can limit the descendancy levels with both the getDescendants and getDescendantsAndSelf methods by supplying the desired depth limit as the first argument:

// This will work without depth limiting
// 1. As usual
$node->getDescendants();
// 2. Selecting only some attributes
$other->getDescendants(array('id', 'parent_id', 'name'));
...
// With depth limiting
// 1. A maximum of 5 levels of children will be returned
$node->getDescendants(5);
// 2. A max. of 5 levels of children will be returned selecting only some attrs
$other->getDescendants(5, array('id', 'parent_id', 'name'));

Custom sorting column

By default in Baum all results are returned sorted by the lft index column
value for consistency.

If you wish to change this default behaviour you need to specify in your model
the name of the column you wish to use to sort your results like this:

protected $orderColumn = 'name';

Dumping the hierarchy tree

Baum extends the default Eloquent\Collection class and provides the
toHierarchy method to it which returns a nested collection representing the
queried tree.

Retrieving a complete tree hierarchy into a regular Collection object with
its children properly nested is as simple as:

$tree = Category::where('name', '=', 'Books')->first()->getDescendantsAndSelf()->toHierarchy();

Model events: moving and moved

Baum models fire the following events: moving and moved every time a node
is moved around the Nested Set tree. This allows you to hook into those points
in the node movement process. As with normal Eloquent model events, if false
is returned from the moving event, the movement operation will be cancelled.

The recommended way to hook into those events is by using the model's boot
method:

class Category extends Baum\Node {

  public static function boot() {
    parent::boot();

    static::moving(function($node) {
      // Before moving the node this function will be called.
    });

    static::moved(function($node) {
      // After the move operation is processed this function will be
      // called.
    });
  }

}

Scope support

Baum provides a simple method to provide Nested Set "scoping" which restricts
what we consider part of a nested set tree. This should allow for multiple nested
set trees in the same database table.

To make use of the scoping funcionality you may override the scoped model
attribute in your subclass. This attribute should contain an array of the column
names (database fields) which shall be used to restrict Nested Set queries:

class Category extends Baum\Node {
  ...
  protected $scoped = array('company_id');
  ...
}

In the previous example, company_id effectively restricts (or "scopes") a
Nested Set tree. So, for each value of that field we may be able to construct
a full different tree.

$root1 = Category::create(['name' => 'R1', 'company_id' => 1]);
$root2 = Category::create(['name' => 'R2', 'company_id' => 2]);

$child1 = Category::create(['name' => 'C1', 'company_id' => 1]);
$child2 = Category::create(['name' => 'C2', 'company_id' => 2]);

$child1->makeChildOf($root1);
$child2->makeChildOf($root2);

$root1->children()->get(); // <- returns $child1
$root2->children()->get(); // <- returns $child2

All methods which ask or traverse the Nested Set tree will use the scoped
attribute (if provided).

Please note that, for now, moving nodes between scopes is not supported.

Validation

The ::isValidNestedSet() static method allows you to check if your underlying tree structure is correct. It mainly checks for these 3 things:

• Check that the bound indexes lft, rgt are not null, rgt values greater
  than lft and within the bounds of the parent node (if set).
• That there are no duplicates for the lft and rgt column values.
• As the first check does not actually check root nodes, see if each root has
  the lft and rgt indexes within the bounds of its children.

All of the checks are scope aware and will check each scope separately if needed.

Example usage, given a Category node class:

Category::isValidNestedSet()
=> true

Tree rebuilding

Baum supports for complete tree-structure rebuilding (or reindexing) via the
::rebuild() static method.

This method will re-index all your lft, rgt and depth column values,
inspecting your tree only from the parent <-> children relation
standpoint. Which means that you only need a correctly filled parent_id column
and Baum will try its best to recompute the rest.

This can prove quite useful when something has gone horribly wrong with the index
values or it may come quite handy when converting from another implementation
(which would probably have a parent_id column).

This operation is also scope aware and will rebuild all of the scopes
separately if they are defined.

Simple example usage, given a Category node class:

Category::rebuild()

Valid trees (per the isValidNestedSet method) will not get rebuilt. To force the index rebuilding process simply call the rebuild method with true as the first parameter:

Category::rebuild(true);

Soft deletes

Baum comes with limited support for soft-delete operations. What I mean
by limited is that the testing is still limited and the soft delete
functionality is changing in the upcoming 4.2 version of the framework, so use
this feature wisely.

For now, you may consider a safe restore() operation to be one of:

• Restoring a leaf node
• Restoring a whole sub-tree in which the parent is not soft-deleted

Seeding/Mass-assignment

Because Nested Set structures usually involve a number of method calls to build a hierarchy structure (which result in several database queries), Baum provides two convenient methods which will map the supplied array of node attributes and create a hierarchy tree from them:

• buildTree($nodeList): (static method) Maps the supplied array of node attributes into the database.
• makeTree($nodeList): (instance method) Maps the supplied array of node attributes into the database using the current node instance as the parent for the provided subtree.

Both methods will create new nodes when the primary key is not supplied, update or create if it is, and delete all nodes which are not present in the affecting scope. Understand that the affecting scope for the buildTree static method is the whole nested set tree and for the makeTree instance method are all of the current node's descendants.

For example, imagine we wanted to map the following category hierarchy into our database:

• TV & Home Theater
• Tablets & E-Readers
• Computers
  • Laptops
  • PC Laptops
  • Macbooks (Air/Pro)
  • Desktops
  • Monitors
• Cell Phones

This could be easily accomplished with the following code:

$categories = [
  ['id' => 1, 'name' => 'TV & Home Theather'],
  ['id' => 2, 'name' => 'Tablets & E-Readers'],
  ['id' => 3, 'name' => 'Computers', 'children' => [
    ['id' => 4, 'name' => 'Laptops', 'children' => [
      ['id' => 5, 'name' => 'PC Laptops'],
      ['id' => 6, 'name' => 'Macbooks (Air/Pro)']
    ]],
    ['id' => 7, 'name' => 'Desktops'],
    ['id' => 8, 'name' => 'Monitors']
  ]],
  ['id' => 9, 'name' => 'Cell Phones']
];

Category::buildTree($categories) // => true

After that, we may just update the hierarchy as needed:

$categories = [
  ['id' => 1, 'name' => 'TV & Home Theather'],
  ['id' => 2, 'name' => 'Tablets & E-Readers'],
  ['id' => 3, 'name' => 'Computers', 'children' => [
    ['id' => 4, 'name' => 'Laptops', 'children' => [
      ['id' => 5, 'name' => 'PC Laptops'],
      ['id' => 6, 'name' => 'Macbooks (Air/Pro)']
    ]],
    ['id' => 7, 'name' => 'Desktops', 'children' => [
      // These will be created
      ['name' => 'Towers Only'],
      ['name' => 'Desktop Packages'],
      ['name' => 'All-in-One Computers'],
      ['name' => 'Gaming Desktops']
    ]]
    // This one, as it's not present, will be deleted
    // ['id' => 8, 'name' => 'Monitors'],
  ]],
  ['id' => 9, 'name' => 'Cell Phones']
];

Category::buildTree($categories); // => true

The makeTree instance method works in a similar fashion. The only difference
is that it will only perform operations on the descendants of the calling node instance.

So now imagine we already have the following hierarchy in the database:

• Electronics
• Health Fitness & Beaty
• Small Appliances
• Major Appliances

If we execute the following code:

$children = [
  ['name' => 'TV & Home Theather'],
  ['name' => 'Tablets & E-Readers'],
  ['name' => 'Computers', 'children' => [
    ['name' => 'Laptops', 'children' => [
      ['name' => 'PC Laptops'],
      ['name' => 'Macbooks (Air/Pro)']
    ]],
    ['name' => 'Desktops'],
    ['name' => 'Monitors']
  ]],
  ['name' => 'Cell Phones']
];

$electronics = Category::where('name', '=', 'Electronics')->first();
$electronics->makeTree($children); // => true

Would result in:

• Electronics
  • TV & Home Theater
  • Tablets & E-Readers
  • Computers
  • Laptops
    • PC Laptops
    • Macbooks (Air/Pro)
  • Desktops
  • Monitors
  • Cell Phones
• Health Fitness & Beaty
• Small Appliances
• Major Appliances

Updating and deleting nodes from the subtree works the same way.

Misc/Utility functions

Node extraction query scopes

Baum provides some query scopes which may be used to extract (remove) selected nodes
from the current results set.

• withoutNode(node): Extracts the specified node from the current results set.
• withoutSelf(): Extracts itself from the current results set.
• withoutRoot(): Extracts the current root node from the results set.

$node = Category::where('name', '=', 'Some category I do not want to see.')->first();

$root = Category::where('name', '=', 'Old boooks')->first();
var_dump($root->descendantsAndSelf()->withoutNode($node)->get());
... // <- This result set will not contain $node

Get a nested list of column values

The ::getNestedList() static method returns a key-value pair array indicating
a node's depth. Useful for silling select elements, etc.

It expects the column name to return, and optionally: the column
to use for array keys (will use id if none supplied) and/or a separator:

public static function getNestedList($column, $key = null, $seperator = ' ');

An example use case:

$nestedList = Category::getNestedList('name');
// $nestedList will contain an array like the following:
// array(
//   1 => 'Root 1',
//   2 => ' Child 1',
//   3 => ' Child 2',
//   4 => '  Child 2.1',
//   5 => ' Child 3',
//   6 => 'Root 2'
// );

了解更多

您可以在Wiki中找到有关Baum的其他信息，用法示例和/或常见问题解答。

完成本自述文件后，请随意浏览wiki：

贡献

如果你也想贡献自己的绵薄之力？ 也许你发现了一些讨厌的bug？ 你可以按照下面的方法来做。

1. Fork & clone 项目: git clone git@github.com:your-username/baum.git。
2. 运行测试，确定项目通过你的设置: phpunit。
3. 创建你的 bugfix/feature 分支并且把你的改动写入。 把测试写入改动当中。
4. 确定所有测试都通过了: phpunit.
5. 推送分支并且提交一个pull请求。

Please see the CONTRIBUTING.md file for extended guidelines and/or recommendations.

License

Baum根据MIT License许可证的条款获得许可
(查看LICENSE文件看更多细节）。

---

最早由 Estanislau Trepat (etrepat) 编写。 这是他的twitter
@etrepat 。

本作品采用《CC 协议》，转载必须注明作者和本文链接