0

示例表：

CREATE TABLE adj_list_model (
    id INT NOT NULL AUTO INCREMENT,
    parent_id INT,
    my_string varchar(255),//some random information
    PRIMARY KEY (id)
)

我正在创建的树将在同一个表中有多个“root”用户（当 parent_id = NULL 时）。这些“root”用户可能会在某个时候从某个“叶”用户（没有任何人的用户）那里获得 parent_id。我的疑问是如何确保我不会创建类似于以下的“循环”：

示例树设计：

  • 一个
    • b
    • C
      • d
        • e
        • F
          • G

如果用户“a”获取用户“g”作为其父级，则创建的循环将是：

a -> c -> d -> f -> g -> a -> c... and so on forever

问题：当用户“a”想要转到树中的用户“g”下时，检查用户“g”是否在用户“a”下的好方法是什么？（以便在这些特定情况下可以防止该动作）

需要考虑的关键点：两棵树合并为一棵树的情况经常发生。如果树中的级别数假设为 80，则进行检查以防止循环所花费的时间可能相当可观，这就是我正在寻找一种有效方法的原因。

编辑： 我目前的选择（尽管我持怀疑态度）是：

  1. 创建一个额外的列，显示表中每个用户的当前“root”用户。在这种情况下，每次“root”用户获得父用户时，他下面的每个人都必须更新为新的“root”用户，而我担心的是这会给服务器带来多大的压力，特别是如果有很多用户，如果“root”用户获得父母的频率很高。

  2. 在给他父母之前检查“root”用户路径。如果在上述情况下，用户“g”通过逐个循环遍历 g 以上的每个用户（查看他们的父级，一遍又一遍直到到达根目录）来检查他的路径，并发现根是用户“a” ，然后是的，可以阻止该操作，尽管我不确定这会对服务器造成多大的压力。如果有人有想法，请告诉我！

4

1 回答 1

1

对于带有附加root_id列的选项，在 MySql 语法中：

CREATE PROCEDURE change_root() 
BEGIN

  # this is the leaf node id, which will be the new parent of a root user
  SET @new_parent = x;
  # this is the old root user id, which will be the new child of the former leaf node
  SET @old_root = y;
  # get the leaf's root
  SET @new_root = SELECT root_id FROM adj_list_model WHERE id=x;

  # updating the dataset is possible as long as the leaf is not a child of the root user
  IF @new_root <> y THEN

    # link the former leaf to its new child
    UPDATE adj_list_model SET parent_id=x WHERE id=y;

    # @old_root is no longer a root, so update all occurences to the new root
    UPDATE adj_list_model SET root_id=@new_root WHERE root_id=@old_root;

  END IF;

END;

这实际上并没有那么复杂并且比递归解决方案快得多。但最终这取决于您的工作量和需求。

于 2016-04-19T21:23:30.250 回答