2

递归数据结构的常用方法是在每个对象中都有一个父指针。我的问题是通常的实现无法在一次操作中回答以下问题；相反，我需要多次查询我的数据库。有没有一种解决方案可以在单个查询中为我提供结果？

  • 获取节点所有子节点的列表

  • 查找所有父节点（== 到根节点的最短路径）

注意：我在规划阶段，所以我还没有局限于某个数据库。

4

2 回答 2

2

如果“所有子节点”仅表示直接子节点，则只需在每个节点上放置一个子节点列表以及指向父节点的指针。请注意，这会使将节点移动到另一个父节点的成本更高，因为所有（大）子节点也必须更新。

如果“所有子项”真的意味着所有子项，则一种选择是构建每个父项的 ID 字符串，并将其添加为索引列。例如，如果您有A, with the child B, with the grandchild C，那么您将在Cvalue 列中A/B/C。现在要找到A你们所有的孩子，只需LIKE在"A/%". 但是，当您需要更改具有子节点的父节点时，这同样会很昂贵。

如果您需要能够快速更改父母，我认为您将需要将父母信息作为链接列表进行维护。但是，您可以使用存储过程来执行此查询操作，只需一次数据库往返。

于 2011-02-21T08:35:55.737 回答
2

至少 Oracle 可以做分层查询。考虑 db 用户角色的示例：

CREATE TABLE my_dba_role_privs(
   grantee        VARCHAR2(30),
   granted_role   VARCHAR2(30)
);   

-- assigning roles to roles
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CLIENT', 'SELECT_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CREATE_ORDERS');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('COMMERCIAL_DEP', 'CLIENT');

-- assigning roles to users
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_MATT', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CL_JOHN', 'CLIENT');
INSERT INTO my_dba_role_privs( grantee, granted_role ) VALUES('CM_MARY', 'COMMERCIAL_DEP');

现在选择用户“CM_MARY”的所有角色：

SELECT DISTINCT GRANTED_ROLE role_name
  FROM my_dba_role_privs
 START WITH GRANTEE = 'CM_MARY'
       CONNECT BY GRANTEE = PRIOR GRANTED_ROLE;

结果：
COMMERCIAL_DEP
CREATE_ORDERS
CLIENT
SELECT_ORDERS

选择拥有角色“客户”的所有角色和用户

SELECT GRANTEE role_name
  FROM my_dba_role_privs
 START WITH GRANTED_ROLE = 'CLIENT'
       CONNECT BY GRANTED_ROLE = PRIOR GRANTEE;

结果：
CL_JOHN
CL_MATT
COMMERCIAL_DEP
CM_MARY

更新：
既然你提到，树将是相当静态的，尝试Joe Celko 的树可能会很有趣（大约 180 行要阅读）。它根本不需要自我加入！所以，我希望它的执行速度比 CONNECT BY 快。虽然我刚刚在 30 分钟前读过它，但不知道它在现实世界中有多好

更新 2：使用 MySQL 的“嵌套集模型”：在 MySQL 中管理分层数据这与上面 Joe Celko 的树相同，但有更多示例和解释。

于 2011-02-21T09:03:28.617 回答