Showing posts with label Nested sets. Show all posts
Showing posts with label Nested sets. Show all posts

Saturday, February 27, 2010

Nested Sets

It is often required to have tree structures, even if only to manage categories. A tree structure is a tree consisting of a single or multiple root which each node can have multiple nodes son, and that with infinite depth. 
Generally the method used to do this is to have a unique identifier for each node of the tree, and insert the identifier of the father node in the registration of the node.
The disadvantage of this technique is that one is obliged to make a SQL query for each node to retrieve all the son of a node. We can improve that by downloading all the nodes in the database, and rebuilding the tree by hand using an array indexed by parent node.
This technique is not really suitable for very large tree structures of several thousands of nodes.
So why don't trying by represent the tree differently, not as a tree, but as  Nested Sets.

The Nested Set is an adjacent list realized in SQL as a tree.

For example having the following tree structure:


We can represent it as a set



The SQL for create the table is :


CREATE TABLE `tree` (
`id` INT NOT NULL AUTO_INCREMENT ,
`name` VARCHAR( 32 ) NOT NULL ,
`parentid` INT NOT NULL ,
`lft` INT NOT NULL ,
`rgt` INT NOT NULL ,
PRIMARY KEY ( `id` ))

Selection of all nodes is very simple:
SELECT
  n0.id
FROM
  tree n0,
  tree n1
WHERE
    n1.id = 0
AND n0.lft BETWEEN n1.lft AND n1.rgt;


...
ASAP I will wrote a Java classes to maintain Nested Sets

keep in touch 
Rinaldo

references: http://www.mti.epita.fr/blogs/2008/07/06/avoir-une-structure-arborescente-en-sql/