nested trees in mysql - handy stored procedures.

Storing tree data in Mysql databases, is relatively common, however, all the existing documentation about doing this, makes the whole process rather complex.

If you google it, you will probably find the quite definitive answer at mysql.com, describing the classic  parent_id method, and the left/right numbering process. Both of these methods involve rather complex SQL to fetch and update the tree.

In seeking a better solutions for a tree that was infrequently updated, but frequently queried, I thought I'd try seeing if I could write a few stored procedures to simplify the process.

Our basic database structure looks like this:

CREATE TABLE _TREE_ (
    id int(11) NOT NULL auto_increment,
    parent_id   int(11)  NOT NULL DEFAULT 0,
    seqid int(11)  NOT NULL DEFAULT 0,
    depth int(11)  NOT NULL DEFAULT 0,
    leaf int(1)  NOT NULL DEFAULT 0,
    name varchar(128) default '',
    fullpath TEXT default '',
    PRIMARY KEY  (`id`),
    INDEX qlookup( parent_id , seqid , depth)
);

our key components are

• id (the nodes id)
  
• parent_id (the nodes parent - pretty clasic)
• name (the textual name of the node)
• seqid - the generated order item for the whole tree
• depth - how deep the node is (usefull for indenting)
• leaf - is it a leaf node (eg. has no children) - usefull for icons

The trick of the stored procedures is to correctly generate the seqid, this consists of two parts, the top level wrapper and the recursive prodedure to update the table.

DROP PROCEDURE IF EXISTS _TREE__resequence;

DELIMITER $$
CREATE PROCEDURE _TREE__resequence(i_sep VARCHAR(4))   DETERMINISTIC
  BEGIN
        DECLARE v_p, v_d, v_s INT(11);
        DECLARE v_fp TEXT;
        SET v_fp = '';
        SET v_p =0;
        SET v_d =0;
        SET v_s =0;
        SET max_sp_recursion_depth=255;
        CALL _TREE__resequence_sub(v_p, v_d, v_fp, i_sep, v_s);
        
        
    END $$
DELIMITER ;

   



DROP PROCEDURE IF EXISTS _TREE__resequence_sub;

DELIMITER $$
CREATE PROCEDURE _TREE__resequence_sub(
    i_parent INT(11),
    i_depth INT(11),
    i_fullpath TEXT,
    i_sep VARCHAR(4),
    INOUT i_seqid INT(11)
    )   DETERMINISTIC
    BEGIN
        DECLARE v_nid, v_ex_seqid  INT(11);
        DECLARE v_name VARCHAR(128);
        DECLARE v_leaf INT(1);
        DECLARE v_fullpath TEXT;
        DECLARE done INT DEFAULT 0;

        DECLARE qry CURSOR FOR SELECT id, seqid, name  FROM _TREE_ 
              WHERE parent_id = i_parent ORDER BY seqid;
        DECLARE CONTINUE HANDLER FOR NOT FOUND SET done = 1;
        OPEN qry;
        
        REPEAT
            FETCH qry INTO v_nid, v_ex_seqid, v_name;
            
            IF NOT done THEN
                IF v_ex_seqid != i_seqid THEN 
                    UPDATE _TREE_ SET seqid = i_seqid, depth=i_depth WHERE id=v_nid;
                END IF;
                IF i_depth > 0 THEN 
                    SET v_fullpath = CONCAT(i_fullpath, i_sep, v_name);
                ELSE 
                    SET v_fullpath = v_name;
                END IF;
                SET v_leaf =0;
                SELECT COUNT(id) INTO v_leaf FROM _TREE_ where parent_id = v_nid;
                
                UPDATE _TREE_ SET 
                    fullpath = v_fullpath,
                    leaf = IF (v_leaf > 0, 0 , 1)
                    WHERE id=v_nid;
                
                SET i_seqid = i_seqid +1;
                #// do the children..
                CALL _TREE__resequence_sub(v_nid, i_depth+1, v_fullpath, i_sep, i_seqid);
            END IF;
        UNTIL done END REPEAT;
        
        CLOSE qry;
    
    END $$
DELIMITER ;

This does the hard work of iterating through the tree, and updating the sequence number, depth, leaf field and filling in the fullpath field

Now our simple add node code just adds the node in the correct place, bumps the seqid along, so that you can then regenerate the tree.

DROP FUNCTION IF EXISTS _TREE__add_node;

DELIMITER $$
CREATE FUNCTION _TREE__add_node(
    i_parent INT(11),
    i_after INT(11),
    i_name VARCHAR(128)
    ) RETURNS INT(11) DETERMINISTIC
    BEGIN
        
        DECLARE v_depth INT(11);
        DECLARE v_seqid INT(11);
        DECLARE v_ret INT(11);
        DECLARE v_tmp INT(11);
         
        SET v_depth = 0;
        SET v_seqid = 0;
        SET v_ret = 0;
        SET v_tmp = 0;
         
        
        #// grap parent depth.
        SELECT depth +1, seqid + 1 INTO v_depth, v_seqid FROM _TREE_ WHERE  id= i_parent LIMIT 1;
        #// grab previous id..
        IF i_after > 0 THEN 
            SELECT seqid INTO v_tmp FROM _TREE_ WHERE id = i_after AND parent_id = i_parent LIMIT 1;
            IF v_tmp > -1 THEN 
                SET v_seqid = v_tmp+1;
            END IF;
        END IF;
            
        
        
        INSERT INTO _TREE_ SET 
            depth = v_depth , 
            seqid = v_seqid , 
            parent_id =  i_parent,
            name = i_name;
        
        
        SELECT LAST_INSERT_ID() INTO v_ret;
        
        #// fix the seqend id 
        
        
        UPDATE   _TREE_ SET seqid = seqid +1   WHERE seqid >= v_seqid  AND id != v_ret;
        
        RETURN v_ret;
        
    END $$
DELIMITER ;

You can now create a generic tree code by replacing my _TREE_ word with your table name:
eg.

#sed -e "s/_TREE_/yourtable/g" tree.js | mysql yourdb -f 

Once all that is done the SQL to create tree nodes is very simple:

 delete from nametree; alter table nametree AUTO_INCREMENT =1 ;
 
 select nametree_add_node(0,0, 'one at top'); 
 call nametree_resequence(':');

 select nametree_add_node(1,0, 'two on one'); 
 call nametree_resequence(':');

 select nametree_add_node(1,0, 'three on one (first)'); 
 call nametree_resequence(':');
 
 select nametree_add_node(1,2, 'four on one (last)'); 
 call nametree_resequence(':');
 
 select nametree_add_node(0,1, 'five on top (last)');
 call nametree_resequence(':');
 
 select nametree_add_node(0,0, 'six is first'); 
 call nametree_resequence(':');

 SELECT * FROM nametree ORDER BY seqid;

Gives you a nice little table

+----+-----------+-------+-------+------+----------------------+---------------------------------+
| id | parent_id | seqid | depth | leaf | name                 | fullpath                        |
+----+-----------+-------+-------+------+----------------------+---------------------------------+
|  6 |         0 |     0 |     0 |    1 | six is first         | six is first                    | 
|  1 |         0 |     1 |     0 |    0 | one at top           | one at top                      | 
|  3 |         1 |     2 |     1 |    1 | three on one (first) | one at top:three on one (first) | 
|  2 |         1 |     3 |     1 |    1 | two on one           | one at top:two on one           | 
|  4 |         1 |     4 |     1 |    1 | four on one (last)   | one at top:four on one (last)   | 
|  5 |         0 |     5 |     0 |    1 | five on top (last)   | five on top (last)              | 
+----+-----------+-------+-------+------+----------------------+---------------------------------+

Enjoy tree.js (I name my mysql stored procs as js, just so my editor works better with them)