Nested Intervals and their implementation under Yii2

Hi, Habr!
Most developers know what Nested Sets are, their strengths and weaknesses. Today I want to present to the public the implementation of a modification of this technique, which partially solves the shortcomings of the original algorithm, although it has its negative sides.

What are the pros and cons of the original Nested Sets:
+ quick sample of parents and children with a simple request;
+ fast selection of neighboring nodes by a simple request;
+ fast selection of empty nodes with a simple request;
+ instant receiving the number of all children in the node by the formula;
+ possibility of non-recursive tree building in one cycle;
- very slow insertion and update.

What are the reasons for the slow insert / update? Since, the values ​​of the boundaries of nodes go continuously, then any insertion, especially at the beginning of the tree, requires recalculation of the boundaries of all subsequent nodes. If the table is large enough, this process can take tens of seconds or even longer. On animation:

Nested Intervals

The first thought that came to mind when considering a picture with a visual representation of the Nested Sets: “you can not move the border if you imagine the root node as a segment in the field of real numbers”. That is, if you imagine that the borders of the root node have values ​​of 0.0 and 1.0, then you can add nodes to any place without moving others, you just need to take a real number between the target nodes. But, since we know very well that real numbers in the computer have their limits, I quickly refused this idea, in favor of whole numbers.
')
With integers, the essence is the same, only the borders of the root node are made from zero to INT_MAX. Then, when inserting a new node, we simply take any two unused values ​​between the target nodes, and do not touch anything else, everything would be fast and cool if not for one “but” - what to do if there are no more free values? Obviously, you need to move all the values ​​of the boundaries to the nearest free value, "clearing" your space for insertion. Only now the search for such a “hole” is a costly task, so the result in this case can go even slower than in the classic nested sets.


A little googling, I realized that I had not invented a bicycle, and this idea has long been called Nested Itervals. But I haven’t found any implementations, since on most resources this method was considered in a negative way, saying “we treat one, cripple the other”. And this is not unreasonable, but it became very interesting to me, I wanted to test how this algorithm is better, and what is worse, and how much.

Implementation

I started writing Behavior for Yii2, implementing the idea of ​​Nested Intervals. The first difficulty arose when writing insert methods - how to get the boundary of the neighboring node or parent with insertBefore() and insertAfter() and the boundary of the first / last node with prependTo() and appendTo() ? If in Nested Sets it is obvious - + 1 / -1 to the border of the current node, here without an additional query to the database in any way. But the good thing is that our samples are fast.

It took a lot of time to implement the search for an unallocated space, in case there is not enough space to insert a new node. But as a result, I was able to move the borders not half of the base, but only a small piece to the almost nearest “hole” from the current segment.

The next big question arose when moving existing branches to a new location. If this operation takes place within the framework of a single tree, then everything else can be done quickly, simply by swapping two blocks.

But moving from another tree turned out to be a difficult task, since there can be a lot of nodes being moved, and it would take too long to insert them one by one with the usual algorithm. At first, I generally wanted to abandon this possibility, writing off the implementation complexity. But a little later, I realized the need for the optimize() method, which would evenly distribute the boundaries of existing nodes across the range. After that, the idea arose to move the nodes of another tree by optimizing the source tree with the preparation of a “window” for the moved nodes. All this works very slowly (at the moment there is an optimization of this method only for MySQL), but it is worth noting that the operation to move from other trees is rarely required, where more often you need to move within one tree.

But it was quite easy to implement the samples - the main methods for obtaining parents and children are identical to the classic nested sets. Slightly more complicated with samples of the previous / next neighbor - two requests are required: obtaining a parent, and direct search in a range with a limit. But it became really bad with getting empty nodes getLeaves() , getLeaves() I had to do it with the help of the left join, which will certainly affect the performance.

Insert optimization

Having completed the first series of performance tests, the results were not impressive to say the least. The thing turned out to be that at first I implemented the selection of the boundaries of the inserted node simply by breaking the segment into three parts. Because of this, the gap for new nodes is rapidly reduced. Since the range of 32-bit PHP is [0 - 2147483647] (operations with large numbers are converted to float), then after inserting a total of 19 nodes into the root via appendTo() there is no room left for the 20th node (2147483647/3 ^ 19 = ~ 1.9), and you have to perform slow operations to find unoccupied places and move. So the thing, of course, will not work. We need some optimization for the distribution of space. For this, Behavior has as many as 5 options:

• First and main amountOptimize - this parameter determines for how many nodes to schedule the partitioning of the segment available for insertion. That is, with a value of 20, we will be able to insert 20 child nodes, and they will uniformly occupy the range of the parent, and then - as it will.
  As a value, you can use an array, then the value will be different for each level.
  
• noPrepend , noAppend , noInsert - these parameters help to optimize the reservation of space between borders and the position of the first node. If you only appendTo() operation (for example, comments), then you can set noPrepend = true and noInsert = true , and thus significantly reduce the likelihood of a severe case of clearing the space for the new node. More clearly the effect of these parameters is shown in the pictures.
  

  amountOptimize = 3
  amountOptimize = 3 noPrepend = true
  amountOptimize = 3 noAppend = true
  amountOptimize = 3 noInsert = true
  amountOptimize = 3 noInsert = true noPrepend = true
  amountOptimize = 3 noInsert = true noAppend = true

  
  It is worth noting that if you noPrepend = true , this does not mean that you cannot perform the prependTo() insertion, it is very likely that many such operations will be performed slowly.
  
• And the last parameter, reserveFactor , determines the size of the gaps between the borders. With one, the size of the gap is equal to the size of the inserted node. If the Behavior usage scenario implies a large number of insertBefore() and insertAfter() operations, then this parameter is better to increase.

After all these manipulations, the tests have become much more "tasty."

64 bits

If you use the BIGINT columns to store the left and right attributes and use 64-bit PHP, you can use the free optimization in the form of a wider range. Just set the range parameter = [0, 9223372036854775807]. This will make more rare cases of lack of space for new nodes.

Performance tests

As a standard for comparison, the most popular Behavior was implemented, which implements Nested Sets from the respected Alexander Kochetov (Creocoder) creocoder / yii2-nested-sets . It was also interesting to compare the results with the Adjacency List while maintaining the possibility of sorting. I did not find a suitable library for this, so I took it and wrote it myself (and even with the support of JOINs, but this is not about that now).

The first two tests are rather synthetic, since in reality, hardly anyone will fill the tree, but this procedure was necessary for me primarily to generate a more or less large base for further tests. They simply fill the levels in succession with a fixed number of children.

Tests 3–5 simulate the insertion of 20 nodes at a different place in a large table:

The following test removes 20 nodes from the beginning of the tree:

Test 7 is very illustrative, as it imitates well the use of Behavior for comments. In a cycle of 1000 nodes is added to a randomly selected node, with a level limitation. Test 8 is similar, but with even more stringent conditions - not only adding, but also any other operation is allowed.

The following two tests for moving nodes in the tree:

After writing Behavior, I wanted to find out what benefits Trait will have in place of behaviors. Therefore, I ported it to Trait with static attributes. Further sampling tests were also carried out in the variants with Trait. But the results of the use of impurities, to put it mildly, were not impressed, especially considering how much more ugly the code has become because of them.
A simple selection of all the elements of Model::find()->all() :

Selection of descendants:

Selection of ancestors:

Selection of neighbors and empty nodes:

findings

Nested Intervals - has the right to life. It has both advantages and disadvantages:
+ quick insertion (assuming a good selection of optimizing parameters);
+ quick node deletion with descendants;
+ the same speed as the Nested Sets in a sample of ancestors and descendants;
+ Also, the possibility of not recursively building a tree in one cycle remains;
- slow receipt of neighboring nodes;
- slow receipt of empty nodes;
- there is no possibility to instantly count the number of children in a node.

Implementation for Yii2

I want to note that the methods are slightly different from those proposed in the behavior of Creocoder. First, I changed the naming of methods to getParents() getDescendants() getters, this allows access to the associated nodes, similar to Relations, which allows not to make secondary queries to the database:

 $node = Node::findOne(['name' => 'test']); $children = $node->children; // relation $children = $node->getChildren()->all(); // query 

In addition, I did not drag Yii-shnye parameters to save ($ runValidation, $ attributeNames), instead I implemented the methods as an indication of the action (just like ->asArray()-> ):

 $node = new Node(); $node->makeRoot()->save(false); $node->insertAfter($node2)->save(); 

Implement Nested Intervals on GitHub .
Implementing the Adjacency List on GitHub .