在树中查找节点级别 [英] Find node level in a tree
问题描述
我有一棵树(嵌套类别)存储如下:
I have a tree (nested categories) stored as follows:
CREATE TABLE `category` (
`category_id` int(10) unsigned NOT NULL AUTO_INCREMENT,
`category_name` varchar(100) NOT NULL,
`parent_id` int(10) unsigned DEFAULT NULL,
PRIMARY KEY (`category_id`),
UNIQUE KEY `category_name_UNIQUE` (`category_name`,`parent_id`),
KEY `fk_category_category1` (`parent_id`,`category_id`),
CONSTRAINT `fk_category_category1` FOREIGN KEY (`parent_id`) REFERENCES `category` (`category_id`) ON DELETE SET NULL ON UPDATE CASCADE
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_spanish_ci
我需要在客户端语言(PHP)中添加节点信息(子代+父代),以便它可以在内存中构建树.我可以调整我的PHP代码,但我认为,如果我可以按所有父母先于孩子的顺序来检索行,则操作会更简单.如果我知道每个节点的级别,就可以这样做:
I need to feed my client-side language (PHP) with node information (child+parent) so it can build the tree in memory. I can tweak my PHP code but I think the operation would be way simpler if I could just retrieve the rows in such an order that all parents come before their children. I could do that if I knew the level for each node:
SELECT category_id, category_name, parent_id
FROM category
ORDER BY level -- No `level` column so far :(
您能想到一种计算节点级别的方法(视图,存储的例程等)吗?如果不是实时的,我想可以,我需要在修改节点时重新计算.
Can you think of a way (view, stored routine or whatever...) to calculate the node level? I guess it's okay if it's not real-time and I need to recalculate it on node modification.
我已经根据Amarghosh的反馈编写了这些触发器:
I've written these triggers based on feedback by Amarghosh:
DROP TRIGGER IF EXISTS `category_before_insert`;
DELIMITER //
CREATE TRIGGER `category_before_insert` BEFORE INSERT ON `category` FOR EACH ROW BEGIN
IF NEW.parent_id IS NULL THEN
SET @parent_level = 0;
ELSE
SELECT level INTO @parent_level
FROM category
WHERE category_id = NEW.parent_id;
END IF;
SET NEW.level = @parent_level+1;
END//
DELIMITER ;
DROP TRIGGER IF EXISTS `category_before_update`;
DELIMITER //
CREATE TRIGGER `category_before_update` BEFORE UPDATE ON `category` FOR EACH ROW BEGIN
IF NEW.parent_id IS NULL THEN
SET @parent_level = 0;
ELSE
SELECT level INTO @parent_level
FROM category
WHERE category_id = NEW.parent_id;
END IF;
SET NEW.level = @parent_level+1;
END//
DELIMITER ;
它似乎可以很好地插入和修改.但是它不适用于删除:从ON UPDATE CASCADE
外键更新行时,MySQL Server不会启动触发器.
It seems to work fine for insertions and modifications. But it doesn't work for deletions: MySQL Server does not launch triggers when the rows are updated from ON UPDATE CASCADE
foreign keys.
第一个显而易见的想法是编写一个新的删除触发器;但是,不允许在表categories
上的触发器修改同一表上的其他行:
The first obvious idea is to write a new trigger for deletion; however, a trigger on table categories
is not allowed to modify other rows on this same table:
DROP TRIGGER IF EXISTS `category_after_delete`;
DELIMITER //
CREATE TRIGGER `category_after_delete` AFTER DELETE ON `category` FOR EACH ROW BEGIN
/*
* Raises an error, see below
*/
UPDATE category SET parent_id=NULL
WHERE parent_id = OLD.category_id;
END//
DELIMITER ;
错误:
网格编辑错误:SQL错误(1442): 无法更新表中的类别" 存储的函数/触发器,因为它是 已经被语句使用的 调用了此存储的函数/触发器.
Grid editing error: SQL Error (1442): Can't update table 'category' in stored function/trigger because it is already used by statement which invoked this stored function/trigger.
第二次更新:有效的解决方案(除非证明是错误的)
我的第一次尝试非常明智,但是我发现一个我无法解决的问题:当您从触发器启动一系列操作时,MySQL将不允许更改同一张表中的其他行.由于删除节点需要调整所有后代的级别,所以我碰壁了.
Second update: working solution (unless proved wrong)
My first attempt was pretty sensible but I found a problem I could not manage to solve: when you launch a series of operations from a trigger, MySQL will not allow to alter other lines from the same table. Since node deletions require to adjust the level of all descendants, I had hit a wall.
最后,我使用了此处的代码,更改了方法:我没有在节点更改时校正各个级别的方法,而是使用代码来计算所有级别,并在每次编辑时触发它.由于计算速度较慢,并且获取数据需要非常复杂的查询,因此我将其缓存到表中.就我而言,这是可以接受的解决方案,因为版本应该很少.
In the end, I changed the approach using code from here: rather than correcting individual levels when a node change, I have code to calculate all levels and I trigger it on every edit. Since it's a slow calculation and fetching data requires a very complex query, I cache it into a table. In my case, it's an acceptable solution since editions should be rare.
1.缓存级别的新表:
CREATE TABLE `category_level` (
`category_id` int(10) NOT NULL,
`parent_id` int(10) DEFAULT NULL, -- Not really necesary
`level` int(10) NOT NULL,
PRIMARY KEY (`category_id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8 COLLATE=utf8_spanish_ci
2.辅助功能来计算水平
如果我真的了解它是如何工作的,它本身并不会真正返回任何有用的信息.而是将内容存储在会话变量中.
If I really got a grasp on how it works, it doesn't really return anything useful by itself. Instead, it stores stuff in session variables.
CREATE FUNCTION `category_connect_by_parent_eq_prior_id`(`value` INT) RETURNS int(10)
READS SQL DATA
BEGIN
DECLARE _id INT;
DECLARE _parent INT;
DECLARE _next INT;
DECLARE CONTINUE HANDLER FOR NOT FOUND SET @category_id = NULL;
SET _parent = @category_id;
SET _id = -1;
IF @category_id IS NULL THEN
RETURN NULL;
END IF;
LOOP
SELECT MIN(category_id)
INTO @category_id
FROM category
WHERE COALESCE(parent_id, 0) = _parent
AND category_id > _id;
IF @category_id IS NOT NULL OR _parent = @start_with THEN
SET @level = @level + 1;
RETURN @category_id;
END IF;
SET @level := @level - 1;
SELECT category_id, COALESCE(parent_id, 0)
INTO _id, _parent
FROM category
WHERE category_id = _parent;
END LOOP;
END
3.启动重新计算过程的过程
它基本上封装了复杂的查询,该查询检索由helper函数辅助的级别.
It basically encapsulates the complex query that retrieves the levels aided by the helper function.
CREATE PROCEDURE `update_category_level`()
SQL SECURITY INVOKER
BEGIN
DELETE FROM category_level;
INSERT INTO category_level (category_id, parent_id, level)
SELECT hi.category_id, parent_id, level
FROM (
SELECT category_connect_by_parent_eq_prior_id(category_id) AS category_id, @level AS level
FROM (
SELECT @start_with := 0,
@category_id := @start_with,
@level := 0
) vars, category
WHERE @category_id IS NOT NULL
) ho
JOIN category hi ON hi.category_id = ho.category_id;
END
4.触发以使缓存表保持最新状态
CREATE TRIGGER `category_after_insert` AFTER INSERT ON `category` FOR EACH ROW BEGIN
call update_category_level();
END
CREATE TRIGGER `category_after_update` AFTER UPDATE ON `category` FOR EACH ROW BEGIN
call update_category_level();
END
CREATE TRIGGER `category_after_delete` AFTER DELETE ON `category` FOR EACH ROW BEGIN
call update_category_level();
END
5.已知问题
- 如果经常更改节点,这是次优的选择.
- MySQL不允许触发器或过程中的事务或表锁定.您在编辑节点时必须注意这些细节.
推荐答案
There's an excellent series of articles here on Hierarchical Queries in MySQL that includes how to identify level, leaf nodes, loops in the hierarchy, etc.
这篇关于在树中查找节点级别的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!