Nested Sets + MySQL TRIGGER
Task
The task is the same as in the previous article , only applicable to MySQL.
Rake
Good news guys! MySQL has no problem with recursive triggers! MySQL developers just stupidly lock a table being changed even at the trigger level, here are the radishes. But, in fact, we can only stop the outage.
There is a small loophole, with ... pooled tables. Although I did not find confirmation in the documentation that this was so intentionally intended, there was no denial either. True, there is a possibility that this loophole may be covered, although I do not see the point.
Alas, the trigger mechanism in MySQL is new and rather raw, which imposes some restrictions on its use, but still it is enough to solve our problem.
So, the source table:
SQL code (1)
CREATE TABLE `ns_tree` (
`id` int (11) NOT NULL auto_increment,
`left_key` int (11) NOT NULL default '0',
`right_key` int (11) NOT NULL default '0',
`level` int (11) NOT NULL default '0',
`parent_id` int (11) NOT NULL default '0',
`tree` int (11) NOT NULL default '1',
`field1` text,
PRIMARY KEY (`id`)
) ENGINE = MyISAM;
Based on it, we are doing exactly the same table, with exactly the same set of fields:
SQL code (2)
CREATE TABLE `_ns_tree` (
`id` int (11) NOT NULL auto_increment,
`left_key` int (11) NOT NULL default '0',
`right_key` int (11) NOT NULL default '0',
`level` int (11) NOT NULL default '0',
`parent_id` int (11) NOT NULL default '0',
`tree` int (11) NOT NULL default '1',
`field1` text,
PRIMARY KEY (`id`)
) ENGINE = MERGE INSERT_METHOD = LAST UNION = (`ns_tree`);
The key word - MERGE in essence, we create a view of our table, with which we can work as with a table. In general, the MERGE mechanism is also slightly damp. The structure of the merged table must be exactly the same as the original.
IMPORTANT!!! When changing the structure of the source table, the connection between the tables is lost, but between already connected rows it is NO! Be careful. When changing the structure of the source table, the same change is necessarily applied to the merged one!
Also, the source table should be MyISAM, which is understandable, in this case transactions are not applicable due to the fact that the tables cannot lock each other, and the data in them are the same. However, this is not terrible for us, since the source table will be locked within the trigger, and we will change the data of the merged table from triggers, so there can be no intersection of queries.
I also wanted to draw attention to: I strongly recommend not using root nodes within the same tree (which I mentioned in the previous article), since the table is completely blocked, and too long a queue can form.
Create a record
The MySQL dialect of triggers differs somewhat from the PostgreSQL dialect:
- It is not necessary to declare variables at the beginning of the procedure;
- It is impossible to interrupt the execution of a trigger, it must work out completely;
- As mentioned above, we are not afraid of recursion, so we don’t need extra checks and additional fields;
- Variables appear along the code;
- Instead of returning from a trigger, we wrap the code in terms;
- All changes concerning the structure of the tree are applied to the auxiliary joint table;
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_ins_tr` BEFORE INSERT ON` ns_tree`
FOR EACH ROW
BEGIN
SET @left_key: = 0;
SET @level: = 0;
- If we indicated a parent:
IF NEW.parent_id IS NOT NULL AND NEW.parent_id> 0 THEN
SELECT right_key, `level` + 1 INTO @left_key, @level
FROM ns_tree
WHERE id = NEW.parent_id AND tree = NEW.tree;
END IF;
- If we specified the left key:
IF NEW.left_key IS NOT NULL AND NEW.left_key> 0 AND
(@left_key IS NULL OR @left_key = 0) THEN
SELECT id, left_key, right_key, `level`, parent_id
INTO @tmp_id, @tmp_left_key, @tmp_right_key, @tmp_level, @tmp_parent_id
FROM ns_tree
WHERE tree = NEW.tree AND (left_key = NEW.left_key OR right_key = NEW.left_key);
IF @tmp_left_key IS NOT NULL AND @tmp_left_key> 0 AND NEW.left_key = @tmp_left_key THEN
SET NEW.parent_id: = @tmp_parent_id;
SET @left_key: = NEW.left_key;
SET @level: = @tmp_level;
ELSEIF @tmp_left_key IS NOT NULL AND @tmp_left_key> 0 AND NEW.left_key = @tmp_right_key THEN
SET NEW.parent_id: = @tmp_id;
SET @left_key: = NEW.left_key;
SET @level: = @tmp_level + 1;
END IF;
END IF;
- If the parent or left key is not specified, or we did not find anything
IF @left_key IS NULL OR @left_key = 0 THEN
SELECT MAX (right_key) + 1 INTO @left_key
FROM ns_tree
WHERE tree = NEW.tree;
IF @left_key IS NULL OR @left_key = 0 THEN
SET @left_key: = 1;
END IF;
SET @level: = 0;
SET NEW.parent_id: = 0;
END IF;
- Set new key values
SET NEW.left_key: = @left_key;
SET NEW.right_key: = @left_key + 1;
SET NEW.`level`: = @level;
- We form a gap in the tree
UPDATE _ns_tree
SET left_key = CASE WHEN left_key> = @left_key
THEN left_key + 2
ELSE left_key + 0
END,
right_key = right_key + 2
WHERE tree = NEW.tree AND right_key> = @left_key;
END;
')
Change record
The principle is the same with the use of the dialect.
SQL code (4)
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_upd_tr` BEFORE UPDATE ON` ns_tree`
FOR EACH ROW
BEGIN
- Forbid to change fields, or send nasty things
SET NEW.tree: = OLD.tree;
SET NEW.right_key: = OLD.right_key;
SET NEWlevel`: = OLD .level`;
SET @return_flag: = 0;
IF NEW.parent_id IS NULL THEN SET NEW.parent_id: = 0; END IF;
- Check whether there are changes associated with the tree structure
IF NEW.parent_id <> OLD.parent_id OR NEW.left_key <> OLD.left_key THEN
- We are still rebuilding the tree, well, let's start:
SET @left_key: = 0;
SET @level: = 0;
SET @skew_tree: = OLD.right_key - OLD.left_key + 1;
- Determine where we transfer it:
- If parent_id is changed:
IF NEW.parent_id <> OLD.parent_id THEN
- If in submission to another evil:
IF NEW.parent_id> 0 THEN
SELECT right_key, level + 1
INTO @left_key, @level
FROM ns_tree
WHERE id = NEW.parent_id AND tree = NEW.tree;
- Otherwise, we transfer to the root of the tree:
ELSE
SELECT MAX (right_key) + 1
INTO @left_key
FROM ns_tree
WHERE tree = NEW.tree;
SET @level: = 0;
END IF;
- If suddenly the parent is in the range of the node being moved, check:
IF @left_key IS NOT NULL AND
@left_key> 0 AND
@left_key> OLD.left_key AND
@left_key <= OLD.right_key THEN
SET NEW.parent_id: = OLD.parent_id;
SET NEW.left_key: = OLD.left_key;
SET @return_flag: = 1;
END IF;
END IF;
- If not parent_id, then left_key is changed, or if parent_id change did not give anything
IF @left_key IS NULL OR @left_key = 0 THEN
SELECT id, left_key, right_key, `level`, parent_id
INTO @tmp_id, @tmp_left_key, @tmp_right_key, @tmp_level, @tmp_parent_id
FROM ns_tree
WHERE tree = NEW.tree AND (right_key = NEW.left_key OR right_key = NEW.left_key - 1)
LIMIT 1;
IF @tmp_left_key IS NOT NULL AND
@tmp_left_key> 0 AND
NEW.left_key - 1 = @tmp_right_key THEN
SET NEW.parent_id: = @tmp_parent_id;
SET @left_key: = NEW.left_key;
SET @level: = @tmp_level;
ELSEIF @tmp_left_key IS NOT NULL AND
@tmp_left_key> 0 AND
NEW.left_key = @tmp_right_key THEN
SET NEW.parent_id: = @tmp_id;
SET @left_key: = NEW.left_key;
SET @level: = @tmp_level + 1;
ELSEIF NEW.left_key = 1 THEN
SET NEW.parent_id: = 0;
SET @left_key: = NEW.left_key;
SET @level: = 0;
ELSE
SET NEW.parent_id: = OLD.parent_id;
SET NEW.left_key: = OLD.left_key;
SET @return_flag = 1;
END IF;
END IF;
- Now we know where we move the tree.
- Check whether it is worth doing
IF @return_flag IS NULL OR @return_flag = 0 THEN
SET @skew_level: = @level - OLD .level`;
IF @left_key> OLD.left_key THEN
- Move up the tree
SET @skew_edit: = @left_key - OLD.left_key - @skew_tree;
UPDATE _ns_tree
SET left_key = CASE WHEN right_key <= OLD.right_key
THEN left_key + @skew_edit
ELSE CASE WHEN left_key> OLD.right_key
THEN left_key - @skew_tree
ELSE left_key
END
END,
`level` = CASE WHEN right_key <= OLD.right_key
THEN `level` + @skew_level
ELSE `level`
END,
right_key = CASE WHEN right_key <= OLD.right_key
THEN right_key + @skew_edit
ELSE CASE WHEN right_key <@left_key
THEN right_key - @skew_tree
ELSE right_key
END
END
WHERE tree = OLD.tree AND
right_key> OLD.left_key AND
left_key <@left_key AND
id <> OLD.id;
SET @left_key: = @left_key - @skew_tree;
ELSE
- Move down the tree:
SET @skew_edit: = @left_key - OLD.left_key;
UPDATE _ns_tree
SET
right_key = CASE WHEN left_key> = OLD.left_key
THEN right_key + @skew_edit
ELSE CASE WHEN right_key <OLD.left_key
THEN right_key + @skew_tree
ELSE right_key
END
END,
`level` = CASE WHEN left_key> = OLD.left_key
THEN `level` + @skew_level
ELSE `level`
END,
left_key = CASE WHEN left_key> = OLD.left_key
THEN left_key + @skew_edit
ELSE CASE WHEN left_key> = @left_key
THEN left_key + @skew_tree
ELSE left_key
END
END
WHERE tree = OLD.tree AND
right_key> = @left_key AND
left_key <OLD.right_key AND
id <> OLD.id;
END IF;
- Tree rebuilt, only our current node remains
SET NEW.left_key: = @left_key;
SET NEW.`level`: = @level;
SET NEW.right_key: = @left_key + @skew_tree - 1;
END IF;
END IF;
END;
ATTENTION!!! In MySQL, the order of enumeration of fields in the UPDATE query is important, since the fields that are changed during the query in the query itself change the value to a new one, so if we continue using these fields in the conditions, the result will be inadequate.
Delete record
Due to the lack of problems with recursion of triggers, deletion in general becomes a trivial task.
Trigger for option: “delete entire branch”:
SQL code (5)
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_del_tr` AFTER DELETE ON` ns_tree`
FOR EACH ROW
BEGIN
- Remove child nodes:
DELETE FROM _ns_tree
WHERE
tree = OLD.tree AND
left_key> OLD.left_key AND
right_key <OLD.right_key;
- Remove the gap in the keys:
SET @skew_tree: = OLD.right_key - OLD.left_key + 1;
UPDATE _ns_tree
SET left_key = CASE WHEN left_key> OLD.left_key
THEN left_key - @skew_tree
ELSE left_key
END,
right_key = right_key - @skew_tree
WHERE right_key> OLD.right_key AND
tree = OLD.tree AND
id <> OLD.id;
END;
Trigger for the option: “delete a node with the displacement of child nodes on the level in top”:
SQL code (6)
CREATE DEFINER = 'user' @ 'localhost' TRIGGER `ns_tree_before_del_tr` AFTER DELETE ON` ns_tree`
FOR EACH ROW
BEGIN
- Remove the gap in the keys:
UPDATE _ns_tree
SET left_key = CASE WHEN left_key <OLD.left_key
THEN left_key
ELSE CASE WHEN right_key <OLD.right_key
THEN left_key - 1
ELSE left_key - 2
END
END,
parent_id = CASE WHEN right_key <OLD.right_key AND `level` = OLD.level + 1
THEN OLD.parent_id
ELSE parent_id
END,
`level` = CASE WHEN right_key <OLD.right_key
THEN `level` - 1
ELSE `level`
END,
right_key = CASE WHEN right_key <OLD.right_key
THEN right_key - 1
ELSE right_key - 2
END
WHERE (right_key> OLD.right_key OR
(left_key> OLD.left_key AND right_key <OLD.right_key)) AND
tree = OLD.tree;
END;
I want to draw attention to the fact that changes affecting the tree structure should be made not in batches, but sequentially for each node, so that its integrity is preserved.
Actually everything. It remains only to put down the indices (again, I am lazy to write SQL commands here, so I’ll just voice them):
- Composite is not unique to fields ( left_key, right_key, level, tree );
- Not unique on the field ( parent_id );
Enjoy ;-)
Sergey Tomulevich aka Phoinix (July 8, 2009)
Source: https://habr.com/ru/post/63883/
All Articles