Prestashop Category Tree as a Nested Set

Nested set is one of the approaches to represent a tree in relational databases.

how it works

Take a look at the example pictures from wikipedia:

This is just a tree with some numbers attached to node labels. Those numbers make a lot more sense if the tree is presented a nested sets (sets inside sets):

Note that reading all numbers from left to right is the ordered sequence of integer numbers. This is how the nested set are built and how the hierarchy is restored basing on those numbers.

Let's say, we've got a leaf node inside a tree. If this is just a normal tree (not a nested set), walking through all parents until reaching the root node will cost one subquery per each parent. But if we have a nested set, we can do this all with just one query by manipulating the left/right values of the sets - this is all what nested sets are here for.

parent of (a parent of (...)) a node

Walking from a specific node to the root node of the tree is used in the product display page. The breadcrumb section shows the path from the root node to the main category the product belongs to (product.id_category_default in the database). The Product::getParentCategories() method is called to find all parents of a chosen category:

WHERE c.nleft < (int)$category['nleft']
AND c.nright > (int)$category['nright']
ORDER BY c.nleft

You can imagine this as widening the left/right range. Take a look at the picture above: Jackets have the range of 6 : 7 (7 - 6 = 1 which is the smallest possible subset = the leaf). The left value will be decreased (the smaller one) while the right value will be increased (the bigger one). The parent of Jackets is Suits with the range of 3 : 8 (8 - 3 = 5). Men's category, the parent of Suits, will be found in the same way - decreasing the left value and increasing the right value, 2:9. If the left value equals 1, you're already at the root node.

children of a node

Finding all children of a specific node is done in the opposite way. You take all subsets of a given set. As everything is ordered, all nested subsets will have their left/right values inside the range of the chosen node:

WHERE c.nleft > (int)$category['nleft']
AND c.nright < (int)$category['nright']
ORDER BY c.nleft

In other words, we'll get all nodes that are situated between the left and the right border of the chosen node area. All nodes that are beyond this area are not the children of the chosen category.

Finding all children of a category tree node is used in the Category::getAllChildren() method.

nested sets in prestashop

Such approach was introduced in category structure in prestashop since version 1.4.0.5, released on December 22, 2010.

For anyone having older versions of the platform, prestashop provides special functionality which fills up all nested set data. It is implemented in Category class in Category::regenerateEntireNtree() method.

upgrading

Each new version of prestashop is provided with a small SQL script which enables to update the database structure to fit new functionalities - take a look at the install/sql/upgrade directory. It works just like doctrine migrations in symfony 1.x. The 1.4.0.5.sql script from the directory above includes the following lines:

ALTER TABLE `PREFIX_category` ADD `nleft` INT UNSIGNED NOT NULL DEFAULT '0' AFTER `level_depth`;
ALTER TABLE `PREFIX_category` ADD `nright` INT UNSIGNED NOT NULL DEFAULT '0' AFTER `nleft`;
ALTER TABLE `PREFIX_category` ADD INDEX `nleftright` (`nleft`, `nright`);

Those lines create 2 columns which store the left/right values which will be used to traverse the tree from child nodes to their parents.

database performance

Selects are faster with such structure. But be aware that each modification you make on any category tree node will fire regenerating entire nested set values - prestashop doesn't check where the modified node is - it builds the nested set from scratch (Category::regenerateEntireNtree()). If you have a really big tree, inserting a new category node can take quite a lot of time.