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

Question

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

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

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

| pKey | type | bitperms |

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

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

• 获取过滤后的叶子后，对每个叶子进行后期处理以检查它的父母烫发
  • 成本延迟到之后
  • 可能找到很多初始叶子，但是在处理父母之后，什么都没有留下，导致做无用的工作

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

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

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

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

Answer 1

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

1. 您显然需要在某个时候检查从叶子到根的整个路径。
2. 我假设没有从侧面介绍权限规则（即您正在处理一棵树，而不是一般图表）。
3. 我假设在几个“文件夹”节点上有很多叶子。
4. 我还假设您有一种方法可以包括权限（位掩码上的 ORing）或排除权限（位掩码上的 NOTANDing）。
5. 权限主要授予角色/组，而不是单个用户（在后一种情况下，您需要为该用户创建 s.th.，例如“临时角色/组”）。
6. 权限不会上树，只会下到叶子。

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

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

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

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

这些操作成本很高，但由于它们不需要处理任何叶子/文件，它们只需要触及整个树的一小部分：

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