【IT168技术文档】

  背景

  框图

  上图中，Role和被设置Permission的Resource都是可以有任意层级继承关系的。

  举例

  举一个网站的例子来说：

  如果，User表示网站用户；Role表示角色；Resource表示所有可访问的URL；Permission是对每一个URL的某一个权限（如：查看，修改等）。

  Role可以有任意层级继承关系，如：用户角色可以分为Normal User和Admin User，Admin User下又可以分为Super Admin、Content Admin、Support Admin等。

  URL这种Resource也可以有任意层级继承关系的，如：对http://abc.com/A/A1/A11/A111.aspx这样一个链接，可以认为http://abc.com/A1是一个URL Resource，http://abc.com/A/A1/A11是他的一个子Resource，http://abc.com/A/A1/A11/A111.aspx又是http://abc.com/A/A1/A11的一个子Resource。

  对某一个Role来说，他对某一个Resource – R1的具体的Permissions，等于关联到这个Role的Resource - R1及其所有父级Resource的Permissions的并集。

  对于某一个User来说，他对某一个Resource的Permissions，等于他所属的所有Roles的Permissions的并集。

  问题

  各元素之间的关系容易理解，关键的难点在于，因为Role和Resource都可以是有无限层级继承关系的，如何保证权限信息验证具有较高的性能呢？当继承关系较复杂时，递归检测的性能无疑是不可接受的。

  数据库表

User（ID，Name）
Role（ID，Name，ParentID，LeftIndex，RightIndex）
UsersInRoles（UserID，RoleID）
Resource（ID，Name，ParentID，LeftIndex，RightIndex）
PermissionsOfRole（PermissionsValue，ResourceID，RoleID）

  这里简单起见，对于Permissions，使用一个二进制位表示一个具体的Permission。我们需要事先定义一个PermissionsValue的每一个二进制位表示的Permission。例如：如果PermissionsValue的二进制值为10101010，表示从低位到高位第2、4、6、8位所代表的权限的并集。

  使用二进制位表示一个具体的Permission的好处是，处理Permissions的并操作可以转换为二进制的OR；缺点是，具体的Permission想不能特别多，因为多一个就意味着PermissionsValue的最大值大一个2的次方。8位二进制的最大值是2的8次方，这不算很大，但是，1000位二进制的最大值是2的1000次方，这就是个不可想象的巨大数字了。好在，一般来讲，具体的Permission项目不会特别多的。

  该方案的关键，就在于Role和Resource表的LeftIndex和RightIndex这两个字段了，我们将使用这两个字段，在避免递归的情况下，实现较高性能的取某个继承节点的所有子元素或所有父元素的算法。

  算法

  我们以Role为例，首先Role表中有且只有一条记录存放所有Roles的顶层父节点（1，“Root Role”，1，2）。当他没有子节点时，其LeftIndex和RightIndex的值分别为1和2。当对其插入子节点时，LeftIndex和RightIndex的值需要做相应的调整，调整的规则如下（括号中为LeftIndex和RightIndex的值）：