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
Truncated by Planet PHP, read more at the original (another 3410 bytes)
