Inserting and Deleting In a Nested Set Model

Storing tree data in a database can be tricky. There are multiple approaches you can take depending on your project's needs.  For one of my projects I added and removed nodes so infrequently (like once or twice a year) but required thousands of requests per day.  The nested set model was the perfect fit and I got an excited for the chance to play with a new technique that was such a shift in thinking to adjacency lists.  I'm not going to go into what the nested set model is, I'm assuming that since you are here you know something about it.  If not then I recommend the de facto blog here: http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

I find using procedures for these tasks to be much easier than requiring users to wrap their head around the nested set model or to try and translate the code to the language in your client.

 

Inserting

One item missing from the blog is the actual code, sure it gives you snippets but not the entire picture.  For example inserting nodes is different if you are dealing with a leaf or internal node.  Just a small oversight that I thought I would resolve by creating a procedure.  It takes as input the id of the parent node that we want to insert and we pass the values for the new node.  The procedure tests if the parent is a leaf node and branches accordingly.

DELIMITER;;
CREATE PROCEDURE `node_insert`(parent_category_id INT, name VARCHAR(255))
BEGIN
 DECLARE parent_left, parent_right INT DEFAULT 0;
 SELECT lft INTO parent_left FROM nested_category 

  WHERE category_id = parent_category_id;
 SELECT rgt INTO parent_right FROM nested_category 

  WHERE category_id = parent_category_id;

 IF parent_right = (parent_left + 1) THEN
  SELECT @my_left := lft FROM nested_category 

   WHERE id = parent_category_id;
  UPDATE nested_category SET rgt = rgt + 2 

   WHERE rgt > @my_left;
  UPDATE nested_category SET lft = lft + 2  

   WHERE lft > @my_left;
  INSERT INTO nested_category(`name`, `lft`, `rgt`) 
   VALUES(name, @my_left  + 1, @my_left + 2);
 ELSE
  SELECT @my_right := rgt FROM nested_category 

   WHERE id = parent_category_id;
  UPDATE nested_category SET rgt = rgt + 2 

   WHERE rgt >= @my_right;
  UPDATE nested_category SET lft = lft + 2  

   WHERE lft >= @my_right;
  INSERT INTO nested_category(`name`, `lft`, `rgt`) 
   VALUES(name, @my_right, @my_right + 1);
 END IF;
END ;;
DELIMITER ;

To call the procedure we will need the id of the parent node and values.  For example if we were to add a node for smartwatches to the PORTABLE_ELECTRONICS that has an id of 6 we can call the procedure like this:

CALL node_insert(6, 'Smartwatch');

 

Deleting

This one is pretty easy. We take as input the id of the node we want to delete.

CREATE PROCEDURE `node_delete`(category_id INT)
BEGIN
 SELECT @my_left := `lft`, @my_right := `rgt`, @my_width := `rgt` - `lft` + 1
  FROM `nested_category`
  WHERE `category_id` = category_id;

 DELETE FROM `nested_category` 

  WHERE `lft` BETWEEN @my_left AND @my_right;

 UPDATE `nested_category` SET `rgt` = `rgt` - @my_width  

  WHERE `rgt` > @my_right;
 UPDATE `nested_category` SET `lft` = `lft` - @my_width 

  WHERE `lft` > @my_right;
END

To call the procedure we just need the id of the node.  For example if we decided that CD players were now obsolete we can delete the node "CD PLAYERS" which has an id of 9.

CALL node_delete(9);