AGILEJ的权限控制（角色树的算法）

<!---->

在权限控制的第一篇文中我们提到了在我们RBAC的模型中角色将是可继承性的，即如果角色A财务部经理是角色B财务员的父类，则角色A将会拥有角色B的所有权限，那么一个公司/组织的结构则是一个树型结构。在这里我们将会虚拟一个根节点，作为所有角色的祖先。如下图所示。

树的遍历通常有两种，第一种是按层次遍历，在图中的表示就是从根节点A开始，一层一层的向下走，每一个子节点按照它自己的parent节点来确定位置。通常使用这种遍历会保存节点的路径和该节点的父亲节点ID，对于图中K节点来说，它将会把路径ABCFK和F存储在自己的对象属性中。这种遍历的一个好处就是插入节点很方便，比如我要给K添加一个子节点，只需要查出K的路径，结合K对应的ID就可以了。但是如果是要求查询出一个节点（比如C）的所有子节点呢？很自然的想法是通过数据库的模糊查询找出路径属性包含C的所有记录，不过这样做就出现了一个性能问题，通过这种模糊查询方式速度会很慢。

第二种就是先根遍历，也是在AGILEJ的权限控制里面使用到的。具体的思想就是按照链状来构造树结构。如图所示，这颗树就是按照1－2－3... 20－21－22的顺序来遍历的。对于每个节点我们为其添加了两个属性－－左值和右值。现在如果我们要查询节点C的所有子节点，只需要找出数据表中所有左值大于C左值(3)并且右值小于C右值(10)的所有节点即可，这样就避免了使用模糊查询。如果我只是要查出C节点下面所有子节点的数目而非详细信息，那么可以用(C的右值-C的左值-1)/2，即(10-3-1)/2=3，是不是很方便？不过这种算法也有弱点，就是插比起层次遍历的方法要麻烦点。比如我要为H添加一个子节点，那我必须将所有左值大于12的节点的左值加上2，所有右值大于12的节点的右值加2，然后插入一条数据，其左值为14，右值为 15.

简单实现（假设节点C对应的object为roleC）：

• 查询节点c的所有子节点：
  collection = find all role where role.left_value>roleC.leftValue and role.right_value<roleC.rightValue; 
• 获得节点C的所有子节点个数：
  count = (roleC.rightValue-roleC.leftValue-1)/2
• 在节点M后插入节点
  update role set role.leftValue=role.leftValue+2 where role.rightValue>roleM.rightValue
  update role set role.rightValue=role.rightValue+2 where role.rightValue>=roleM.rightValue
  now save new Node with leftValue=roleM.leftValue+1 and rightValue=roleM.leftValue+2

对于权限控制的模型来说，需要进行节点添加删除的操作相对比较少，而查询使用的却会很多。因此先根遍历是一个不错的选择。