Baobab ( a library applying the nested set model )

Baobab is a library to save tree structured data in a relational database.

Currently there is only a PHP implementation working with MySQL, but it shouldn’t be too difficult to port to other languages or databases (the hard work is done via pure SQL queries and the code is mostly a support to them).

The technique used is [1] Joe Celko’s [2] nested set model, modified so that a table can hold more than one tree, to help with cases such as storing threads of a forum (each thread is a tree and they all have an identical structure).

In fact when the library often asks you for a “forest name”, because each table created can hold more than one tree.

We have more than one hundred tests to ensure the library is doing The Right Thing (™), a straightforward thread safe API and a clean documentation.

The nested set model in brief

lft	rgt	label
1	18	animals
2	9	vertebrates
3	4	mollusks
5	8	insects
6	7	mantis
10	17	invertebrates
11	16	mammals
12	13	tiger
14	15	horse

Each node in the graph has two numbers (left and right) assigned to it during a [3] depth-first search of the tree: we assign the left (lft) value the first time we pass by and the right (rgt) value the following time. Well, the nested set model is all about assigning this numbers and maintain them coherent whenever a node is inserted, moved or deleted.
With this numbers in place we gain various benefits. The tree structure of the data is maintained in a relational database and we’re able to do some really fast searches. Normally slow operations like finding the path between two nodes, knowing all the descendants of a node or discover if a node is ancestor of another are blazing fast. Too, the horizontal order is preserved without the need of others attributes.

Some simple properties of this data structure ...

• root node has halfways lft = 1
• the number of a node’s descendants is ⌊(rgt-lft)/2⌋
• the ancestors of a node have both lft < nodeLft and rgt > nodeRgt
• a leaf has always rgt = lft+1

This is just an introduction, if you want to know more about nested set models I suggest you to read [4] Trees and hierarchies in SQL for smarties and/or [5] SQL for smarties, both written by Joe Celko. Online you could read a couple [6] more resources.

How can Baobab help ?

Baobab leverages the works of administering such table. In particular moving or inserting after a particular node can be pretty complicated, and Baobab does the hard work for you.
If you feel like so, you can use Baobab for all the tree changing tasks (the most tedious queries) and write your own queries to search what you want in the most optimized way for your schema.
However Baobab provides functions for the laziest programmers.

Here are the functions the Baobab class provide

• create
  • build()
  • destroy()
  • upgrade()
• retrieve
  • getRoot()
  • getParent()
  • getDescendants()
  • getLeaves()
  • getLevels()
  • getPath()
  • getChildren()
  • getFirstNChildren()
  • getFirstChild()
  • getLastChild()
  • getChildAtIndex()
  • getTree()
  • getSize()
  • getTreeHeight()
  • getNodeData()

• insert
  • appendChild()
  • insertAfter()
  • insertBefore()
  • insertChildAtIndex()
• edit
  • updateNode()
• move
  • movefter()
  • moveBefore()
  • moveNodeAtIndex()
• delete
  • deleteNode()
  • clean()
  • cleanAll()
  • closeGaps()
• data liberation
  • import()
  • export()

All of the *_index() functions accept negative numbers too, and all the functions that modify the tree preserve the lft/rgt consistency.

Dependencies

• PHP >= 5.2 with mysqli module (tested on PHP 5.2 -> 5.5)
• MySQL >= 5.0 with innodb tables available (tested on MySQL 5.1, 5.5)

Footnotes

[1]

Joe Celko

[2]	Wikipedia on Nested set model

[3]	Depth-first search

[4]	Joe Celko’s Trees and hierarchies in SQL for smarties

[5]	Joe Celko’s SQL for smarties: advanced SQL programming

[6]	Managing Hierarchical Data in MySQL