Geekly Articles each Day
📜 ⬆️ ⬇️

Set Yii2 Behavior for storing trees in the database and sharing them


Hi, Habr!

In one of my projects on Yii2, I wanted to combine the Adjacency List and Nested Sets. And so that in case of disconnection of the behavior of Nested Sets, the functionality remains fully functional. Then I realized that I didn't need Nested Sets, since I still had to store the full path in the database, so I decided to use the Materialized Path as a replacement. Available on GitHub Behavior ( matperez / yii2-materialized-path ) was not functional enough, so I had to write my own, and since I recently wrote my own behavior for the Adjacency List and Nested Intervals , I decided why not to make a set of such behaviors with API, and the ability to arbitrarily connect them to the model at the same time, taking advantage of each.


List of behaviors


Adjacency List


+ self supporting structure
+ fast modifications, since it does not require any recalculations and updates of the descendants
+ get immediate parent and children
- the complexity and slowness of obtaining all ancestors and descendants

The simplest form of communication, most often for its implementation, does not involve any behavior, but simply prescribe communication with the parent and children. But it is worth adding a sorting field for nodes ( insertBefore() / insertAfter() ) to the Adjacency List, then it becomes difficult here without ready-made behavior. Yes, and to get all the ancestors / descendants by some connections is already difficult.
All these problems solves the behavior. In addition, it has some chips - it allows you to make a custom number of join-s of the table with itself to reduce and speed up requests for ancestors / descendants.
Watch on github
')

Materialized Path


The method of storing the full path in each element (just like the path in the file system).
+ Quick receipt of all ancestors and descendants
+ quick insert new items
- non-optimal storage path, possible restrictions on its length
- in general, an additional depth field is needed to obtain immediate children (in implementations for a specific base this requirement is not necessary)
- when changing the path of the element, all descendants need to be updated

What did not suit me matperez / yii2-materialized-path , besides the need for a single API and the absence of some methods? First of all, by the fact that when children change the path, it has php-recursion that generates a cloud of requests to the database, which is very bad. In the behavior I implemented, this is done in one request, although I had to sacrifice some compatibility with databases - support for the CONCAT() and LENGTH() functions is required (in most databases they are mysql, pqsql, mssql). Another advantage is that in my behavior there are two modes for constructing a path: by the primary key or by another field, and not necessarily unique.
Watch on github

Nested sets


+ quick samples of ancestors, descendants, neighbors and empty nodes
+ instantly get the number of descendants in the node
+ non-recursive tree building
- very slow modifications of the tree, especially at the beginning of large bases (the insertion of one element can easily last more than 30 seconds in a large base)

For Yii2, there is already a great extension from Creocoder , but I had to rewrite it in order to support a single API, about which just below. This API has several advantages.
Watch on github

Nested Intervals


+ quick samples of ancestors, descendants
+ non-recursive tree building
+ quick insert with optimized parameters
- slow movement of nodes

This algorithm is not very popular, although it is very fast, provided that the correct parameters are chosen. More details about nested intervals can be found in this article .
Watch on github

Single API


All the behaviors listed above have a common API, so they can be replaced without rewriting the code.
The API has one big advantage - dual access to related objects through the standard Relations mechanism for Yii2:
 $parent = $model->getParent()->orderBy(['title' => SORT_DESC])->one(); //    ,  ActiveQuery $title1 = $model->parent->title; //   ,    $title2 = $model->parent->title . ' (2)'; //

There is also a feature - the methods makeRoot(), prependTo(), appendTo(), insertBefore(), insertAfter() - do not perform the action itself, but only give an indication of its type, so you need to remember to save() after them:
 $node = new Node; $node->title = 'root'; $node->makeRoot()->save();

This is done in order not to drag the parameters save($runValidation = true, $attributeNames = null) .

Trait for simultaneous use of multiple behaviors


Behavior in Yii2 is implemented in such a way that the method of the first behavior in which it exists is executed. To share several behaviors, you need to call tree-modifying methods for each connected behavior, and for the methods that choose from the base, the fastest. For this was written Trait, which performs these functions. At the same time, it eliminates the need to specify PhpDoc every time.
Watch on github

Example:
 use paulzi\adjacencylist\AdjacencyListBehavior; use paulzi\nestedsets\NestedSetsBehavior; use paulzi\autotree\AutoTreeTrait; class Node extends \yii\db\ActiveRecord { use AutoTreeTrait; public function behaviors() { return [ ['class' => AdjacencyListBehavior::className()], ['class' => NestedSetsBehavior::className()], ]; } }

Now:
 $node->parents; //   nested sets $node->parent; //   adjacency list $node->children; //   adjacency list $node->descendants; //   nested sets $node->insertAfter($node2)->save() //

The most effective combinations:
Adjacency List + Materialized Path
Adjacency List + Nested Sets
Adjacency List + Nested Intervals

Performance comparison


From the table I think it is clear what the advantages and disadvantages of each of the behavior are:
Performance table
                                                 DB query time Execution Memory

 Test 1. Filling 3 levels of 12 children
     Adjacency List 5811 1,567 ms 9,591 ms 71.3 MB
     Nested Sets 7697 6.672 ms 25.019 ms 105.9 MB
     Nested Intervals amount = 24 5813 1,765 ms 10,442 ms 78.7 MB
     Nested Intervals amount = 12 noPrepend noIns.  5813 1.750 ms 10.223 ms 78.7 MB
     Materialized Path (identity pr. Key mode) 7696 3.169 ms 13.726 ms 92.5 MB
     Materialized Path (attribute mode) 5811 1,690 ms 9,504 ms 71.6 MB

 Test 2. Filling level 6 for 3 children
     Adjacency List 3642 982 ms 5,812 ms 44.5 MB
     Nested Sets 4736 5,447 ms 17,859 ms 65.0 MB
     Nested Intervals amount = 10 3644 1,275 ms 5,976 ms 48.9 MB
     Nested Intervals amount = 3 noPrepend noIns.  3644 1.271 ms 5,993 ms 48.9 MB
     Materialized Path (identity pr. Key mode) 4735 1,316 ms 6,920 ms 57.3 MB
     Materialized Path (attribute mode) 3642 1,129 ms 5,507 ms 44.6 MB

 Test 3. Insertion at the beginning <4% (20 to 19657 knots)
     Adjacency List 100 36 ms 190 ms 4.6 MB
     PaulZi 100 15.768 ms 16.712 ms 4.7 MB
     Nested Intervals 82 21 ms 150 ms 4.7 MB
     Materialized Path (identity pr. Key mode) 120 98 ms 355 ms 4.8 MB
     Materialized Path (attribute mode) 100 74 ms 334 ms 4.6 MB

 Test 4. Insertion in the middle> 46% <50% (20 to 19657 knots)
     Adjacency List 100 24 ms 150 ms 4.6 MB
     Nested Sets 100 8,212 ms 8,799 ms 4.7 MB
     Nested Intervals 82 269 ms 593 ms 4.7 MB
     Materialized Path (identity pr. Key mode) 120 35 ms 196 ms 4.9 MB
     Materialized Path (attribute mode) 100 287 ms 494 ms 4.6 MB

 Test 5. Insertion at the end of> 96% (20 to 19657 knots)
     Adjacency List 100 31 ms 214 ms 4.5 MB
     Nested Sets 100 487 ms 899 ms 4.7 MB
     Nested Intervals 83 46 ms 187 ms 4.7 MB
     Materialized Path (identity pr. Key mode) 120 34 ms 229 ms 4.8 MB
     Materialized Path (attribute mode) 100 470 ms 718 ms 4.6 MB

 Test 6. Removal of <4% from the beginning (20 of 19657 nodes)
     Adjacency List parentJoin = 0 childrenJoin = 0 60 169 ms 257 ms 3.8 MB
     Adjacency List parentJoin = 3 childrenJoin = 3 60 87 ms 162 ms 3.8 MB
     Nested Sets 100 16,480 ms 16,902 ms 4.7 MB
     Nested Intervals 60 164 ms 250 ms 4.2 MB
     Materialized Path (identity pr. Key mode) 60 87 ms 201 ms 4.0 MB
     Materialized Path (attribute mode) 60 122 ms 219 ms 4.0 MB

 Test 7. appendTo () in a random node (5 levels, 1000 nodes)
     Adjacency List 4001 1,062 ms 5,976 ms 46.1 MB
     Nested Sets 5003 5,428 ms 17.334 ms 64.8 MB
     Nested Intervals amount = 10 8497 23.301 ms 41.060 ms 120.7 MB
     Nested Intervals x64 amount = 10 7092 11,330 ms 23,618 ms 97.5 MB
     Nested Intervals amount = 200.25 noPrep noIns 4009 1,431 ms 6,490 ms 50.2 MB
     Nested Intervals x64 a = 250.30 noPrep noIns 4003 1,421 ms 6,615 ms 50.0 MB
     Materialized Path (identity pr. Key mode) 5003 1,621 ms 8,184 ms 57.8 MB
     Materialized Path (attribute mode) 4002 1,269 ms 6,169 ms 46.2 MB
    
 Test 8. Arbitrary operation in a random node (5 levels, 1000 nodes)
     Adjacency List 4383 1,330 ms 6,147 ms 53.0 MB
     Nested Sets 5003 9.577 ms 24.334 ms 64.8 MB
     Nested Intervals amount = 10 7733 8,123 ms 24,031 ms 107.2 MB
     Nested Intervals x64 default amount = 10 5663 3,761 ms 14,084 ms 75.6 MB
     Nested Intervals amount = 200.25 4175 1,548 ms 7,223 ms 52.8 MB
     Nested Intervals x64 a = 250,30 reserve = 2,403 1,541 ms 6,753 ms 50.0 MB
     Materialized Path (identity pr. Key mode) 5392 3.211 ms 11.771 ms 65.0 MB
     Materialized Path (attribute mode) 4377 2,902 ms 10,132 ms 53.2 MB
    
 Test 9. Moving nodes at the beginning of <4% (20 of 19657 nodes)
     Adjacency List 112 39 ms 261 ms 4.5 MB
     Nested Sets 140 218 ms 566 ms 5.5 MB
     Nested Intervals 160 180 ms 573 ms 6.0 MB
     Materialized Path (identity pr. Key mode) 128 38 ms 307 ms 4.9 MB
     Materialized Path (attribute mode) 128 159 ms 495 ms 4.9 MB

 Test 10. Moving nodes from end to start <4%> 96% (20 out of 19657 nodes)
     Nested Sets 140 16,991 ms 17,845 ms 5.5 MB
     Nested Intervals 160 16,972 ms 17,854 ms 6.0 MB
     Materialized Path (identity pr. Key mode) 132 49 ms 319 ms 4.9 MB
     Materialized Path (attribute mode) 132 205 ms 502 ms 4.9 MB
     Adjacency List 112 33 ms 217 ms 4.5 MB
    
 Test 11. Selection of all nodes (19657 pcs.)
     Adjacency List 1 33 ms 890 ms 179.1 MB
     Nested Sets 1 40 ms 1,208 ms 215.2 MB
     Nested Intervals 1 42 ms 1,247 ms 225.3 MB
     Materialized Path (identity pr. Key mode) 1 46 ms 1,240 ms 209.0 MB
     Materialized Path (attribute mode) 1 44 ms 1,106 ms 209.0 MB
    
 Test 12. The choice of children and descendants (for 819 nodes in the middle of the tree from 19657 nodes)
     Adjacency List parentJoin = 0 childrenJoin = 0 2562 720 ms 1,969 ms 36.9 MB
     Adjacency List parentJoin = 3 childrenJoin = 3 2461 704 ms 1,966 ms 35.3 MB
     Nested Sets 1641 522 ms 1,585 ms 25.0 MB
     Nested Intervals 1641 579 ms 1,657 ms 25.0 MB
     Materialized Path (identity pr. Key mode) 1641 569 ms 1,626 ms 23.4 MB
     Materialized Path (attribute mode) 1641 793 ms 6,552 ms 44.7 MB

 Test 13. Picks selection (for 819 nodes in the middle of the tree from 19657 nodes)
     Adjacency List parentJoin = 0 childrenJoin = 0 3180 948 ms 2.304 ms 51.2 MB
     Adjacency List parentJoin = 3 childrenJoin = 3 1641 486 ms 1,495 ms 30.8 MB
     Nested Sets 821 3.238 ms 3.979 ms 20.7 MB
     Nested Intervals 821 3.292 ms 4,147 ms 22.0 MB
     Materialized Path (identity pr. Key mode) 821 292 ms 902 ms 21.2 MB
     Materialized Path (attribute mode) 821 582 ms 4,574 ms 24.7 MB

 Test 14. Selection of neighboring nodes (for 819 nodes in the middle of the tree from 19657 nodes)
     Adjacency List parentJoin = 0 childrenJoin = 0 1641 535 ms 1,442 ms 23.7 MB
     Adjacency List parentJoin = 3 childrenJoin = 3 1641 508 ms 1,421 ms 23.6 MB
     Nested Sets 1641 513 ms 1,428 ms 24.5 MB
     Nested Intervals 1641 19,681 ms 21,326 ms 27.5 MB
     Materialized Path (identity pr. Key mode) 1641 730 ms 1,695 ms 24.3 MB
     Materialized Path (attribute mode) 1641 1,892 ms 2,964 ms 24.3 MB

 Test 15. Selection of empty nodes (for 819 nodes in the middle of the tree from 19657 nodes)
     Adjacency List parentJoin = 0 childrenJoin = 0 1833 568 ms 1,743 ms 32.6 MB
     Adjacency List parentJoin = 3 childrenJoin = 3 1732 556 ms 1,891 ms 31.3 MB
     Nested Sets 821 305 ms 908 ms 18.4 MB
     Nested Intervals 821 10,450 ms 11,166 ms 18.8 MB
     Materialized Path (identity pr. Key mode) 821 7.968 ms 8.434 ms 18.5 MB
     Materialized Path (attribute mode) 821 14.349 ms 19.105 ms 21.3 MB

GitHub Links


Adjacency List
Materialized Path
Nested sets
Nested Intervals
Auto Tree Trait

Source: https://habr.com/ru/post/266155/

More articles:


All Articles