What is a tree?
A tree is a scructure of data used for categories, showing hierarchy and so on. In web applications usually the most used case is creating category hierarchy, menu hierarchy or page hierarchy. Currently there are a lot of ways to create tree scructures in PHP, but we will use just one example, one that is very flexible and adaptable for many usecases.
Example of a tree
For the sake of simplicity, we will use a very simple tree for example. Our tree looks like this:
This is a one depth tree with four nodes in total. In trees, the nodes that have children are called branches and the ones that have none are called leaves.
How to store a tree
When working with simple trees, storing the hierarchy is not that hard. Usually, in the database we can create a parent column that contains the parent of a given node. In tree structures, every node can have only one parent, the only exception being the root. The root node has no parent.
Now, if we know how deep our tree will be, using just the parent for information, we are set. If we do not know the depth exactly, things are a bit more complicated. Since people created databases, a lot of storing methods have been born that help store recursive data linearly. Each is different in a way and each is good at something, but bad at other.
Our example is a basic linear representation and is pretty quick. It contains some extra info that some might consider an overhead, but it is simple, logical, and it works.
| Id | Parent | Tree | Slug | Name | Path | Children |
|---|---|---|---|---|---|---|
| 1 | NULL | 1 | root | Root | |2,3| | |
| 2 | 1 | 1 | node1 | Node1 | |1| | |4,5| |
| 3 | 1 | 1 | nod2 | Node2 | |1| | |
| 4 | 2 | 1 | child1 | Child1 | |1-2| | |
| 5 | 2 | 1 | child2 | Child2 | |1-2| |
This is how we store the data. Every row is a node. The columns are as following:
Id: this is the autoincrement unique id of every node.
Parent: This contains one integer, the Id of the parent node. This is mainly formality and is used in simple cases.
Tree: with this field, we can have more than one tree in one table. This is an integer and is the id of the tree we work with. Every tree has a root node that is mandatory
Slug: this is a slug, created from the given name and is always unique in the table. This is an additional unique field besides the Id.
Name: this is the name of the node.
Path: this column coontains the ids of the nodes that are before our node on the branch from the root, merged into a string. This contains the full path from the root till the node. This is handy in building the hierarchy in PHP.
Children: contains all the ids of the children of a node, merged into a string. This also stores the order of the children.
Handling tree in PHP
In PHP, we can easily manipulate this data. We will have some basic examples to show the perks of this type of DB structure.
For start, how do you get the tree? With one simple query, we can get the whole tree, or just a subtree, using the id of the root node. The nodes that have paths that contain the given id, all belong to the same subtree. This looks like this:
|
1 2 3 4 5 |
SELECT * FROM `table_name` WHERE `path` LIKE "%-:parent-%" OR `path` LIKE "%|:parent-%" OR `path` LIKE "%-:parent|%" OR `path` LIKE "%|:parent|%" |
When we have the data, we have to convert the strings into actual PHP arrays for us to be able to easily use them later. We do this like:
|
1 2 3 4 5 |
$node->path = array_filter(explode('-', str_replace('|', '', $node->path))); $node->children = array_filter(explode(',', str_replace('|', '', $node->children))); $node->path = array_filter(explode('-', str_replace('|', '', $node->path))); $node->children = array_filter(explode(',', str_replace('|', '', $node->children))); |
One other important aspect is moving the nodes from a parent to another, being able to move the whole subtree if necessary. In our case this is not hard, we just have to update some strings. In PHP this means slicing and rearranging our arrays of children and path. Something like this:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
// Get old parent $old_parent = $this->getNode($node->parent); $old_parent->children = array_diff($old_parent->children, array($node->id)); $this->_storage->begin_transaction(); try { $this->_storage->updateNode($old_parent); $arr2 = array_slice($to->children, $order-1); $arr1 = array_diff($to->children, $arr2); $to->children = array_merge($arr1, array($node->id), $arr2); $this->_storage->updateNode($to); $node->parent = $to->id; $node->path = array_merge($to->path, array($to->id)); $this->_storage->updateNode($node); foreach( $subtree as $subnode ) { $subnode->path = array_merge( $to->path, array($to->id, $node->id), array_diff($subnode->path, array_merge($node->path, array($node->id))) ); $this->_storage->updateNode($subnode); } $this->_storage->commit_transaction(); return true; } catch(Exception $e) { $this->_storage->rollback_transaction(); $this->_errors['move'] = $e->getMessage(); return false; } |
Ordering is also easy. Ordering is done on a given level, so we use the children column to order the nodes. The code would look like this:
|
1 2 3 4 5 6 |
$children = array_diff($to->children, array($node->id)); $arr2 = array_slice($children, $order-1); $arr1 = array_diff($children, $arr2); $to->children = array_merge($arr1, array($node->id), $arr2); $this->_storage->updateNode($to); |
Upon deletion, using the move section, you can prompt the user to move the subtree to root, or delete the whole subtree.
Using LIKE syntax in SQL, you can achieve a lot of things.
One last thing that needs mentioning is the recursive function that builds the N depth out of linear data we just got from DB. Here it is:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
private function _build_tree(Node $root, $data) { $mapped_node = array( 'node' => $root, 'subnodes' => array() ); if ( !empty($root->children) ) { foreach( $root->children as $child ) { if ( array_key_exists($child, $data) ) { $mapped_node['subnodes'][] = $this->_build_tree($data[$child], $data); } } } return $mapped_node; } |
Conclusion
You can find all these pieces of code in the PHPInfinityTree repository on GitLab. This is probably not the best solution, but is simple, understandable and is quick. Since recursivity cannot be used in many databases, we have to store the data linearly. Then we go trough it linearly and build up the tree itself.
You can find a working example on PHPInfinityTree.
Also, you can find the packed and documented package of Infinity Tree in the Store.
