权限控制设计笔记

题目

如图，root拥有最高权限，R1-12代表权限组

问题1 我们要如何设计才能容易判断出 权限组之间的上下级关系，比如R4>R10 如何轻易添加一个权限组到树中的任意节点

成哥方案（方案1）

在设计表字段的时候给每个权限组定义两个数值，左值和右值 具体值如下图（root右边还有25）

所以每次增加一个字节点，比如在R5下面增加一个Rx的节点，那么需要判断所有的节点的右值，如果大于或者等于R5的右值，就都加2，然后Rx根据要添加的父亲节点的左右值，增加两个左右值，那么变成如下图

所以遍历了权限表之后，整体结构发生了变化。同理如果删除Rx这个节点，反向操作就可以了。

观察1，我们可以通过左值右值的差值-1 再除以2获得当前节点下的子节点个数

删除子树

如果我们要删除R4这颗子树（R4，R9，R10）那我们只需要判断任意节点满足左值大于等于R4的左值并且右值小于等于R4的右值。

但是，如果我们删除子树，并且需要保持值的连续性，也就是维持观察1的定义，那么我们就需要从叶子节点开始删除，也就是设置一个递归删除，叶子节点的判断条件便是左值和右值相差1

添加子树

如果我们要把R7的子树添加到R10下面，值的注意的是我们要保持维护R7子树的结构关系，同理R7的左右差值是固定的，进行一个递归添加。

任意两个权限组的关系比较

通过左右值的关系可以发现，如果Rx是Ry的父亲节点，必定满足Rx的左值小于Ry的左值，右值相反，这两点必须同时满足。而不满足表示没有关系。

权限与人

如果p1拥有R1，R2的两个权限组，p2拥有R4，R5两个权限组，如何判断p1是否是p2的上级？此时可以判断p2的所有权限组的权限范围是否在p2的权限范围之内。可能需要循环遍历。

方案2

思路

给每个权限进行一个编号，假设十个权限，注意是使用二进制位来表示权限

• 权限1:1
• 权限2:10
• 权限3:100
• 权限4:10000
• …

所以新增权限是通过高位新增的方式来增加的。

权限表示

所以如果有十个权限，root的权限就应该是十个权限的逻辑或操作

root的权限=已经有的权限|新增权限

比如root初始权限

11_1111_1111

我们新增一个编号权限

100_0000_0000

那么

root的权限=11_1111_1111|100_0000_0000=111_1111_1111

所以任意一个权限组的权限内容可以通过具体权限编号进行一个或运算的到一个最终值

权限删除

假设权限组Rx他的权限值(高位部分的0其实可以忽略不写)

00_1100_1110

我们可以显然看出Rx拥有权限2，3，4，7，8的权限

我们要删除Rx的权限3（编号100）的权限，那么需要执行以下公式

异或操作相同为0不同为1

新的权限值=旧的权限值^要删除的权限值

新的权限值=00_1100_1110 ^ 00_0000_0100 = 00_1100_1010

可以看出权限确实被删除了，而就算删除的权限本来就没有，这样的一个操作也不会多大影响比如试图删除权限9但是其实Rx本来就没有权限9

任意两个权限的比较（比较Rx是否覆盖了Ry的所有权限）

假设Rx=111，Ry=101

那么我们应该先进行一个与操作，这个与操作的实际含义是找Rx覆盖Ry的最小子集

的到的值是101，再去比较最小子集是否大于等于Ry如果大于说明Ry是在Rx里面的。

上面那个假设是刚好相等，判断出Ry是Rx子集

如果Ry=1101

第一步，与结果=111 & 1101 =101

101和1101比较，小于，说明Ry不是Rx的子集

权限与人

那么人员1如果需要拥有R1和R2两个权限，那就两个权限进行一个或操作，只需要一个字段存储。

还有一个人员2拥有R2和R3权限，同理进行或操作存储

比较人员1是否是人员2的上级，此时，跟任意两个权限的比较的思路是一样的。

第三种思路

总结

• 我的方案当权限数量增加（叶子节点数量）当叶子节点数量为1 2 3 4 5的时候需要的位数 2 4 8 16 指数增加。所以32位int形就是可以表示32种权限，以我们讨论的那棵树有7个权限需要空间是2^7。不在乎有多少个叶子节点或者子节点的组合数量，因为一开始就是按照最大复杂度设计的。劣势是空间占领大。
• 成哥的方案,需要的位数取决于节点数量2，它所需的空间取决于当前有多少个节点（实际意义也就是权限组合有多少种），那么存储空间是有一个范围的，这个范围就是最小是只有一个root其他都是叶子节点（只有一种权限组合），它所占领的最小空间为 权限数量2+2位。所占领的最大空间数量也是2^7,也就是进行了修剪
• 庄晨的方案，root字段最短，第二层所需的位数应该是取决于树的第二层的节点数量，比如root是空字符串，第二层有三个节点第二层是不是应该00 01 10 第三层就是第二层的长度+该节点（比如00下有两个节点）子节点数量两个的话00 01，所以有0000 0001.按照这种方案，空间的大小取决于树的深度和广度，但是不会大于2^7