是否有更适合存储此类数据的解决方案？

Question

我需要做一些关于数据结构的研究，但我不确定要搜索哪个名称。

假设的场景是这样的:我有一家拥有数千名员工的企业。每个员工可以向他们上面的多个人报告(树向上分支)，每个员工也可以监督他们下面的许多人(树也向下分支)。

下面是我目前使用的两个非常简单的表格：

employee (id, Firstname, Lastname)
employee_structure (id, ParentID, ChildID)

我使用一个递归的PHP函数来显示一个员工的树(向下的树方向)。但是在每个级别上运行SELECT查询来查找每个“节点”的下一个级别是非常耗时的。这就产生了超过30万个直接和间接的关系。随着结构随着时间的推移而增长，情况只会变得更糟。

我需要找出是否有更适合于存储和检索这样的结构的解决方案(在MySQL中，甚至是其他语言)。

如果有人能给我指出正确的方向，或者给出一些有用的提示，我将不胜感激。

Answer 1

员工之间存在m:n关系。在MySql数据库中使用连接表是正确的。

要显示树，您不需要为每个节点运行SELECT。

查询输出应如下所示

+--------------------------------------+
| id | Firstname | Lastname | ChildIDs |
+--------------------------------------+

其中ChildIDs是相关ID的GROUP_CONCAT值。

查询：

SELECT 
e.id, e.Firstname, e.Lastname, GROUP_CONCAT(c.ChildID) 
FROM employee AS e
JOIN employee_structure AS c ON c.ParentID = e.id

如果数据太大，内存耗尽，请使用某种分页来使结果保持较小。

然后，您可以遍历此结果并显示完整的树，而无需运行另一个SELECT。

function printEmployees($id, $indent) {
    echo str_repeat(' ', $indent * 2) . $employees[$id]['Firstname'] . ' ' . $employees[$id]['Lastname'] . PHP_EOL;
    if (!empty($employees[$id]['ChildIDs'])) {
        foreach (explode(',', $employees[$id]['ChildIDs']) as $childID) {
            printEmployees($childID, $indent + 1);
        }
    }
}

Answer 2

大多数分层模型都基于树的概念(嵌套集、邻接、线程二进制)-其中每个节点只有一个父节点。这在你的情况下显然不是真的。现在您有一个网络模型(考虑使用像OQGraph这样的图形数据库引擎？)。

按照它的立场，你有一个大数据完整性问题，确保图是非循环的(某人不是自己的老板)。这可能发生在简单的自连接树层次结构中，但由于数据模型更简单且更容易识别，这种情况发生的可能性要小得多。据我所知，避免这种情况的唯一方法是添加一个明确的属性，指示每个员工的级别-每个员工只能监督较低级别的员工。

现在先把它放在一边(尽管解决方案取决于级别的概念，至少相对于起始点是这样)，如果是我，我会使用临时表和递归存储过程，类似于...

CREATE TEMPORARY TABLE oversees (
   employee_id INT NOT NULL,
   level INT NOT NULL,
   PRIMARY KEY employee_id
);

CREATE PROCEDURE populate_oversees(p_emp_id INT, p_max_levels INT)
(
   INSERT INTO oversees (employee_id, level) VALUES (p_emp_id, p_max_levels);
   call recurse_oversees(max_levels);
);
CREATE PROCEDURE recurse_oversees(p_level INT)
(
   INSERT INTO oversees o1 (employee_id, level)
   SELECT e.id, p_level-1
   FROM employee e
   INNER JOIN employee_structure es
   ON e.id=es.ChildId
   WHERE es.ParentId IN (
      SELECT o2.employee_id
      FROM oversees o2
      WHERE level=p_level
   );

   IF (p_level>1) THEN recurse_oversees(p_level-1);
);

SELECT *
FROM oversees
ORDER BY level DESC;

Answer 3

请看一看Managing Hierarchical Data in MySQL文章，特别是The Nested Set Model部分。在这篇文章的末尾你也有很好的参考资料。

归根结底，就是在您的SQL表中使用left和right值(父id之外)来表示树节点。这种方法使您能够在单个查询中检索完整的树、节点路径、所有叶节点和更多内容。

这种方法的缺点是插入和删除节点有点复杂，因为您必须正确地维护left和right的值。