Introduction
When working with databases, you may want a table structure which allows your record to have a parent record (heirachical recordset). In simple scenarios it’s easy enough to simply have a parent_id column. However, for displaying the entire tree you’ll need a lot of recursion to go through all the top level nodes, test for children, and then test the children for children etc. It soon proves to be very long-winded and inefficient.
Instead of using the standard parent_id approach, there’s a database structure known as the Nested Set Model. The nested set model uses an algorithm which basically uses tree traversal to number each node, and once the numbering is complete it becomes very easy to query the tree and search, whether its for root nodes (base node), leaf nodes (nodes with no children) or branches (the path from the root node to a particular node).
Performance
As the tree traversal for numbering the nodes is required, the Nested Set Model requires slightly more overhead when updating the table (each node needs to be renumbered when a change is made), but as mentioned earlier, is very efficient when it comes to actually querying the table.
Example Usage Scenario
A simple use for Nested Set Model would be a category table for a website, where categories can have subcategories. And even subcategories can have subcategories. Categories are generally setup in the admin on most sites, and even then are rarely updated so the fact that updating a Nested Set can be a bit slow isn’t actually a issue. On the frontend the visitors and customers will simply be viewing categories, so they’ll be reaping the benefits of the efficiency and great performance of the Nested Set Model.
Introducing Baobab
Baobab is a free PHP/MySQL implementation of the Nested Set Model. It can be modified to work with other database systems too. Baobab uses the Nested Set Model, but also the offers the advantage of supporting multiple trees in the same table, or alternatively you can setup different trees in individual tables, depending on your requirements.
It takes an Object-Oriented approach (OOP) and provides you with an entire API of useful methods including:
- getRoot()
- appendChild()
- getTreeHeight()
- deleteNode()
Just take a look at the documentation page to see how much Baobab has to offer.
Download and Install
Getting started with Baobab is dead simple. It’s an open-source project hosted on GitHub which you can download here. Once you’ve got the code it’s a simple case of placing the classes wherever you need them, include them in your PHP and use the Simple Tree Example to get started. If you’re more confident then you can have a look at the Multiple Tree Example.
Conclusion
I’ve found Baobab particularly useful in my projects and have extended it to tie in with my own PHP library. It offers you the power of using nested sets, without requiring you to code your own implementation of nested. There’s a lot of useful functions in there, plus the default SQL structure can easily be extended to contain your own table fields too.
It’s great, it’s free and if you need to hold data in a tree structure then it’s certainly worth checking out.
Hi Sir,
I tested out the Animals example with Baobab, and it always throw an exception on the following code? What did I do wrong? thanks.
public function appendChild($id_parent=NULL,$fields_values=NULL){
$id_parent=intval($id_parent);
if (!$this->db->multi_query(”
CALL Baobab_{$this->forest_name}_AppendChild({$this->tree_id},{$id_parent},@new_id,@cur_tree_id);
SELECT @new_id as new_id,@cur_tree_id as tree_id”)) {
throw new sp_MySQL_Error($this->db);
}