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

Question

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

• 文件夹
  • 文件夹
    • 文件夹
    • 文件
  • 文件
  • 等等

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

| pKey | type | bitperms |

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

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

• 获取过滤后的叶子后，对每个叶子进行后处理以检查它的父权限
  • 成本推迟到之后
  • 可能会找到很多初始叶，但在处理完父节点后，什么都没有留下，导致完成了无用的工作

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

  • 如果存在许多根导致在处理每个叶子上花费过多的时间，则可能是一个巨大的查询

  是否存在任何算法可以更有效地执行此操作？也许重新组织权限数据或向层次结构添加更多信息？

  或许添加一些启发式方法来处理极端情况？

Answer 1

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

1. 您显然需要在某个时刻检查从叶节点到根节点的整个路径。
2. 我假设没有从侧面引入许可规则(即您正在处理树，而不是一般图)。
3. 我假设在几个“文件夹”节点上有很多叶子。
4. 我还假设您有一种方法来包含权限(在位掩码上进行 ORing)或排除它们(在位掩码上进行 NOTAND)。
5. 权限主要授予角色/组，而不是个人用户(在后一种情况下，您需要创建诸如该用户的“临时角色/组”之类的东西)。
6. 权限不会上升到树上，只会下降到叶子。

然后我会预先计算从根目录开始的文件夹的所有权限，并在文件夹的某些权限发生变化(或添加角色等)时将它们与文件夹节点一起保存。调用特定文件/叶子时，您只需检查文件/叶子权限及其文件夹权限。

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

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

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

这些操作代价高昂，但由于它们不需要处理任何叶子/文件，因此它们只需要触及整棵树的一小部分:

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