是否存在执行分层权限检查的算法？

Question

我有一个代表层次结构的数据结构。

• 文件夹
  • 文件夹
    • 文件夹
    • 文件
  • 文件
  • ETC。

权限存储在一个平面表中：

| pKey | type | bitperms |

当执行搜索等全局操作时，我们需要在树中递归地检查权限。

检查与树结构的各个叶子内联的权限很容易。然而，考虑节点上的权限需要两种已知方法之一：

• 获取过滤后的叶子后，对每个叶子进行后期处理以检查其父项权限
  • 费用被推迟到之后
  • 可能会发现很多最初的叶子，但处理完父母后，什么也没有留下，导致做无用的工作

• 提前预先计算所有根（授予权限的节点），并在获取叶子时将其用作查询过滤器

  • 如果存在许多根，则可能会产生巨大的查询，从而导致处理每个叶子花费过多的时间

  是否存在任何算法可以更有效地做到这一点？也许重新组织权限数据或向层次结构添加更多信息？

  也许添加一些启发式方法来应对极端情况？

Answer 1

不知道关于这方面的完整论文，但这是我的想法。

1. 显然，您需要在某个时刻检查从叶到根的整个路径。
2. 我假设没有从侧面介绍权限规则（即您正在处理树，而不是一般图）。
3. 我假设少数“文件夹”节点上有很多叶子。
4. 我还假设您有一种包含权限（对位掩码进行 OR 运算）或排除权限（对位掩码进行 NOTAND 运算）的方法。
5. 权限主要授予角色/组，而不是单个用户（在后一种情况下，您需要为该用户创建“临时角色/组”之类的东西）。
6. 权限不会上树，只会下到叶子。

然后，我会从根部向上预先计算文件夹的所有权限，并在文件夹的某些权限发生更改（或添加角色等）时将它们与文件夹节点一起保存。当调用特定文件/叶子时，您只需检查文件/叶子权限及其文件夹权限。

您还可以将某些文件夹标记为“不继承父级的权限”，这可能会在根权限更改时缩短您的计算...

这将使以下操作变得便宜：

• 检查叶子的权限（加入叶子及其父权限）。
• 更改不包含更多文件夹的文件夹的权限。

这些操作成本高昂，但由于它们不需要在任何叶子/文件上工作，因此它们只需要接触整个树的一小部分：

• 更改/扩展权限模型（例如，通过添加角色/组，这可能会扩大您的位掩码，具体取决于您的实现）。
• 更改 root 权限。