Optimizing the Nested Set model in PHPixie

Just 2 hours ago, I added the last test to a new connection type for PHPixie ORM - Nested Set. I have long thought whether to use this approach or Closure Table for storing trees in SQL databases. But as a result, the Closure Table lost due to the quasi-quadratic sizes to which the link table grows (with 20 nodes, in the worst case 190 records can already be obtained). So the next task was to optimize the classic Nested Set approach, and I really liked the result.


')
One of the main problems in using Nested Set is the cost of inserting a node. The more left the insertion position, the more entries must be shifted to the right. For example, we have a tree like this:



Suppose we need to insert the Fay subcategory in the Pixies, the result is:



As you can see, all the nodes in the tree will have to be changed. Now imagine that you are saving the article comment tree in this way. Every time someone adds a new comment, you have an update of the heap of records, in addition, you must do it all in a transaction, and it is desirable to prevent changes to these lines from parallel requests. If all this is not done, then even several active users commenting at the same time can easily break the entire index. Yes, and the performance of the system obviously suffers too.

I found an elegant way to solve this problem by just slightly changing the standard Nested Set. The idea is simple, although implementation is much more difficult in some places. To all the nodes, add the identifier of the subtree in which they are located, for example, the root id. In each subtree, the numbering left and right start over. The above example with this approach would look like this:



When inserting, we need to change only the nodes that are in the same subtree:



As you can see, the Plants subtree has not changed at all. From a practical point of view, this reduces the number of modified rows in the database by orders of magnitude. If the changes take place in different subtrees, they do not interfere with each other at all, and even if one of them breaks the indexing, this will in no way affect the others.

For these amenities have to pay more complex code. It is easy to make a mistake and forget to change the root field when transferring a node to another subtree or moving it to the root, the procedure of turning records into an object tree, etc., is also a bit more complicated. That's why it took so much time to write tests for all cases.

Use in PHPixie

The full dock will appear on the site soon, but here’s a small guide for those who want to use the new connection right now.

First add 4 INTEGER fields to the table in which the elements are stored: left , right , rootId , depth (of course, the field names are fully customizable, these are only default ones). Then add the link to /bundes/app/assets/config/orm.php

return array( 'relationships' => array( //.... array( 'model' => 'category' // , 'type' => 'nestedSet' ) ) ); 

Then everything is simple:

 $fairies->children->add($sprites); $fairies->children->add($pixies); //   $pixies->parent->set($fairies); //    $pixies->parent->remove(); //     //  where('depth', 0), //         //      (   ) $categories = $orm->query('category')->where('depth', 0)->find(array('children')); 

By the way, PHPixie itself will monitor the removal of entities and correct indexes.

I hope everyone will like the new functionality, and for those who do not use PHPixie, an optimization approach may be useful.
If you are interested in some details or just want to chat, go to our chat .